Problema de asignación en la investigación de operaciones

Investigación de operaciones
(IO).

Las raíces de la investigación de
operaciones se remontan a muchas décadas, cuando se
hicieron los primeros intentos para emplear el método
científico en la administración de una empresa. Sin
embargo, el inicio de la actividad llamada
investigación de operaciones, casi siempre se
atribuye a los servicios militares prestados a principios de la
segunda guerra mundial. Debido a los esfuerzos bélicos,
existía una necesidad urgente de asignar recursos escasos
a las distintas operaciones militares y a las actividades dentro
de cada operación, en la forma más efectiva. Por
esto, las administraciones militares americana e inglesa hicieron
un llamado a un gran número de científicos para que
aplicaran el método científico a éste y a
otros problemas estratégicos y tácticos. De hecho,
se les pidió que hicieran investigación sobre
operaciones (militares). Estos equipos de científicos
fueron los primeros equipos de IO. Con el desarrollo de
métodos efectivos para el uso del nuevo radar, estos
equipos contribuyeron al triunfo del combate aéreo
inglés. A través de sus investigaciones para
mejorar el manejo de las operaciones antisubmarinas y de
protección, jugaron también un papel importante en
la victoria de la batalla del Atlántico Norte. Esfuerzos
similares fueron de gran ayuda en a isla de campaña en el
pacífico.

Al terminar la guerra, el éxito de la
investigación de operaciones en las actividades
bélicas generó un gran interés en sus
aplicaciones fuera del campo militar. Como la explosión
industrial seguía su curso, los problemas causados por el
aumento en la complejidad y especialización dentro de las
organizaciones pasaron de nuevo a primer plano. Comenzó a
ser evidente para un gran número de personas, incluyendo a
los consultores industriales que habían trabajado con o
para los equipos de IO durante la guerra, que estos problemas
eran básicamente los mismos que los enfrentados por la
milicia, pero en un contexto diferente. Cuando comenzó la
década de 1950, estos individuos habían introducido
el uso de la investigación de operaciones en la industria,
los negocios y el gobierno. Desde entonces, esta disciplina se ha
desarrollado con rapidez.

Se pueden identificar por lo menos otros dos factores
que jugaron un papel importante en el desarrollo de la
investigación de operaciones durante este período.
Uno es el gran progreso que ya se había hecho en el
mejoramiento de las técnicas disponibles en esta
área. Después de la guerra, muchos
científicos que habían participado en los equipos
de IO o que tenían información sobre este trabajo,
se encontraban motivados a buscar resultados sustanciales en este
campo; de esto resultaron avances importantes. Un ejemplo
sobresaliente es el método simplex para resolver
problemas de programación lineal, desarrollado en 1947 por
George Dantzing. Muchas de las herramientas
características de la investigación de operaciones,
como programación lineal, programación
dinámica, líneas de espera y teoría de
inventarios, fueron desarrolladas casi por completo antes del
término de la década de 1950.

Un segundo factor que dio ímpetu al desarrollo de
este campo fue el advenimiento de las computadoras. Para
manejar de una manera efectiva los complejos problemas inherentes
a esta disciplina, por lo general se requiere un gran
número de cálculos. Llevarlos a cabo a mano puede
resultar casi imposible. Por lo tanto, el desarrollo de la
computadora electrónica digital, con su capacidad para
realizar cálculos aritméticos, miles o tal vez
millones de veces más rápido que los seres humanos,
fue una gran ayuda para la investigación de operaciones.
Un avance más tuvo lugar en la década de 1980 con
el desarrollo de las computadoras personales cada vez más
rápidas, acompañado de buenos paquetes de
software para resolver problemas de IO, esto puso las
técnicas al alcance de un gran número de personas.
Hoy en día, literalmente millones de individuos tiene
acceso a estos paquetes. En consecuencia, por rutina, se usa toda
una gama e computadoras, desde las grandes hasta las
portátiles, para resolver problemas de
investigación de operaciones. 

Naturaleza de la
investigación de operaciones

Como su nombre lo dice, la investigación de
operaciones significa "hacer investigación sobre las
operaciones". Entonces, la investigación de operaciones se
aplica a problemas que se refieren a la conducción y
coordinación de operaciones (o actividades)
dentro de una organización. La naturaleza de la
organización es esencialmente inmaterial y, de hecho, la
investigación de operaciones se ha aplicado de manera
extensa en áreas tan diversas como la manufactura, el
transporte, la constitución, las telecomunicaciones, la
planeación financiera, el cuidado de la salud, la milicia
y los servicios públicos, por nombrar sólo unas
cuantas. Así, la gama de aplicaciones es
extraordinariamente amplia.

La parte de investigación en el nombre
significa que la investigación de operaciones usa un
enfoque similar a la manera en que se lleva a cabo la
investigación en los campos científicos
establecidos. En gran medida, se usa el método
científico para investigar el problema en
cuestión. (De hecho, en ocasiones se usa el término
ciencias de la administración como
sinónimo de investigación de operaciones.) En
particular, el proceso comienza por la observación
cuidadosa y la formulación del problema incluyendo la
recolección de los datos pertinentes. El siguiente paso es
la construcción de un modelo científico (por lo
general matemático) que intenta abstraer la esencia del
problema real. En este punto se propone la hipótesis de
que el modelo es una representación lo suficientemente
precisa de las características esenciales de la
situación como para que las conclusiones (soluciones)
obtenidas sean válidas también para el problema
real. Después, se llevan a cabo los experimentos adecuados
para probar esta hipótesis, modificarla si es necesario y
eventualmente verificarla. (Con frecuencia este paso se conoce
como validación del modelo.) Entonces, en cierto
modo, la investigación e operaciones incluye la
investigación científica creativa de las
propiedades fundamentales de las operaciones. Sin embargo, existe
más que esto. En particular, la IO se ocupa también
de la administración práctica de la
organización. Así, para tener éxito,
deberá también proporcionar conclusiones claras que
pueda usar el tomador de decisiones cuando las
necesite.

Una característica más de la
investigación de operaciones es su amplio punto de vista.
Como quedó implícito en la sección anterior,
la IO adopta un punto de vista organizacional. de esta manera,
intenta resolver los conflictos de intereses entre las
componentes de la organización de forma que el resultado
sea el mejor para la organización completa. Esto no
significa que el estudio de cada problema deba considerar en
forma explícita todos los aspectos de la
organización sino que los objetivos que se buscan deben
ser consistentes con los de toda ella.

Una característica adicional es que la
investigación de operaciones intenta encontrar una
mejor solución, (llamada solución
óptima) para el problema bajo consideración.
(Decimos una mejor solución y no la mejor solución
porque pueden existir muchas soluciones que empaten como la
mejor.) En lugar de contentarse con mejorar el estado de las
cosas, la meta es identificar el mejor curso de acción
posible. Aun cuando debe interpretarse con todo cuidado en
términos de las necesidades reales de la
administración, esta "búsqueda de la optimidad" es
un aspecto importante dentro de la investigación de
operaciones.

Todas estas características llevan de una manera
casi natural a otra. Es evidente que no puede esperarse que un
solo individuo sea un experto en todos lo múltiples
aspectos del trabajo de investigación de operaciones o de
los problemas que se estudian; se requiere un grupo de individuos
con diversos antecedentes y habilidades. Entonces, cuando se va a
emprender un estudio de investigación de operaciones
completo de un nuevo problema, por lo general es necesario
emplear el empleo de equipo. Este debe incluir
individuos con antecedentes firmes en matemáticas,
estadística y teoría de probabilidades, al igual
que en economía, administración de empresas,
ciencias de la computación, ingeniería, ciencias
físicas, ciencias del comportamiento y, por supuesto, en
las técnicas especiales de investigación de
operaciones. El equipo también necesita tener la
experiencia y las habilidades necesarias para permitir la
consideración adecuada de todas las ramificaciones del
problema a través de la organización.

¿Qué es la investigación
de operaciones?

Como toda disciplina en desarrollo, la
investigación de operaciones ha ido evolucionando no
sólo en sus técnicas y aplicaciones sino en la
forma como la conceptualizan los diferentes autores, en la
actualidad no existe solamente una definición sino muchas,
algunas demasiado generales, otras demasiado engañosas,
aquí seleccionamos dos de las mas aceptadas y
representativas.

LA DEFINICIÓN DE CHURCHMAN, ACKOFF Y
ARNOFF: LA INVESTIGACIÓN DE OPERACIONES ES LA
APLICACIÓN, POR GRUPOS INTERDISCIPLINARIOS, DEL
MÉTODO CIENTÍFICO A PROBLEMAS RELACIONADOS CON EL
CONTROL DE LAS ORGANIZACIONES O SISTEMAS (HOMBRE-MÁQUINA),
A FIN DE QUE SE PRODUZCAN SOLUCIONES QUE MEJOR SIRVAN A LOS
OBJETIVOS DE LA ORGANIZACIÓN.

De ésta definición se pueden destacar los
siguientes conceptos:

1.   Una organización es un sistema
formado por componentes que se interaccionan, unas de estas
interacciones pueden ser controladas y otras no.

2.   En un sistema la información es
una parte fundamental, ya que entre las componentes fluye
información que ocasiona la interacción entre
ellas. También dentro de la estructura de los sistemas se
encuentran recursos que generan interacciones. Los objetivos de
la organización se refieren a la eficacia y eficiencia con
que las componentes pueden controlarse, el control es un
mecanismo de autocorrección del sistema que permite
evaluar los resultados en términos de los objetivos
establecidos.

3.   La complejidad de los problemas que se
presentan en las organizaciones ya no encajan en una sola
disciplina del conocimiento, se han convertido en
multidisciplinario por lo cual para su análisis y
solución se requieren grupos compuestos por especialistas
de diferentes áreas del conocimiento que logran
comunicarse con un lenguaje común.

4.   La investigación de operaciones es
la aplicación de la metodología científica a
través modelos matemáticos, primero para
representar al problema y luego para resolverlo. La
definición de la sociedad de investigación de
operaciones de la Gran Bretaña es la siguiente:

La investigación de operaciones es el ataque de
la ciencia moderna a los complejos problemas que surgen en la
dirección y en la administración de grandes
sistemas de hombres, máquinas, materiales y dinero, en la
industria, en los negocios, en el gobierno y en la defensa. Su
actitud diferencial consiste en desarrollar un modelo
científico del sistema tal, que incorpore valoraciones de
factores como el azar y el riesgo y mediante el cual se predigan
y comparen los resultados de decisiones, estrategias o controles
alternativos. Su propósito es el de ayudar a la gerencia a
determinar científicamente sus políticas y
acciones. 

En relación a ésta definición
deben destacarse los siguientes aspectos:

1.   Generalmente se asocian los conceptos de
dirección y administración a las empresas de tipo
lucrativo, sin embargo, una empresa es un concepto más
amplio, es algo que utiliza hombres, máquinas, materiales
y dinero con un propósito específico; desde
éste punto de vista, se considera como empresa desde una
universidad hasta una armadora de automóviles.

2.   Para tratar de explicar el comportamiento
de un sistema complejo, el científico debe representarlo
en términos de los conceptos que maneja, lo hace
expresando todos los rasgos principales del sistema por medio de
relaciones matemáticas. A esta representación
formal se le llama modelo.

3.   La esencia de un modelo es que debe ser
predictivo, lo cual no significa predecir el futuro, pero si ser
capaz de indicar muchas cosas acerca de la forma en que se puede
esperar que un sistema opere en una variedad de circunstancias,
lo que permite valorar su vulnerabilidad. Si se conocen las
debilidades del sistema se pueden tomar cursos de acción
agrupados en tres categorías: A) Efectuar cambios que
lleven a la empresa o parte de ella a una nueva ruta;  
B)  Realizar  un  plan  de  toma 
de  decisiones; C) Instalar estrategias que generen
decisiones. Cuando se aplica alguno de estos remedios, la
investigación de operaciones nos ayuda a determinar la
acción menos vulnerable ante un futuro
incierto.

4.   El objetivo global de la
investigación de operaciones es el de apoyar al tomador de
decisiones, en cuanto ayudarlo a cumplir con su función
basado en estudios científicamente
fundamentados.

Concepto de optimización.

Una característica adicional, que se
mencionó como de pasada, es que la Investigación de
Operaciones intenta encontrar la mejor solución, o la
solución óptima, al problema bajo
consideración. En lugar de contentarse con sólo
mejorar el estado de las cosas, la meta es identificar el mejor
curso de acción posible. Aún cuando debe
interpretarse con todo cuidado, esta "búsqueda de la
optimalidad" es un aspecto muy importante dentro de la
Investigación de Operaciones.

Enfoque de la investigación de
operaciones:

la parte innovadora de la IO es sin duda alguna su
enfoque modelístico, producto de sus creadores aunado a la
presión de supervivencia de la guerra o la sinergía
generada al combinarse diferentes disciplinas, una
descripción del enfoque es la siguiente. (Ver la figura
11).

1.   Se define el sistema real en donde
se presenta el problema. Dentro del sistema interactúan
normalmente un gran número de variables.

2.   Se seleccionan las variables que
norman la conducta o el estado actual del sistema, llamadas
variables relevantes, con las cuales se define un sistema asumido
del sistema real.

3.   Se construye un modelo
cuantitativo del sistema asumido, identificando y simplificando
las relaciones entre las variables relevantes mediante las
utilización de funciones matemáticas.

4.   Se obtiene la solución al
modelo cuantitativo mediante la aplicación de una o
más de las técnicas desarrolladas por la
IO.

5.  Se adapta e imprime la
máxima realidad posible a la solución
teórica del problema real obtenida en el punto 4, mediante
la consideración de factores cualitativos o no
cuantificables, los cuales no pudieron incluirse en el modelo.
Además se ajusta los detalles finales vía el juicio
y la experiencia del tomador de decisiones.

6.   Se implanta la solución en
el sistema real.

La investigación de operaciones obtiene la
solución del problema real indirectamente, y no como
normalmente se intentaría pasando directamente del
problema real a la solución real.

Modelos:
clasificación

Como acabamos de ver con anterioridad una de las fases
de la aplicación del método científico se
basa en la construcción de modelos o formulación de
hipótesis. En nuestro caso nos centraremos en la
construcción de modelos.

Aunque hay numerosas acepciones y definiciones de un
modelo, hemos elegido la de Aracil (1):

" Un modelo constituye una representación
abstracta de un cierto aspecto de la realidad, y tiene una
estructura que esta formada por los elementos que caracterizan el
aspecto de la realidad modelada y por las relaciones entre estos
elementos".

A partir de este concepto de modelo se pueden obtener
distintas clasificaciones (icónico, analógicos,
simbólicos, etc.), sin embargo, solo estamos interesados
en los modelos matemáticos, es decir, los modelos formales
basados en la lógica matemática, y se basan en un
conjunto de relaciones matemáticas (tales como ecuaciones,
inecuaciones, relaciones lógicas, etc.) que se
corresponden con las relaciones del mundo real (tales como
relaciones tecnológicas, leyes físicas,
restricciones del mercado, etc.).

No vamos a entrar en esta polémica, sino que lo
único que queremos es poner de manifiesto que los modelos
deben usarse como una herramienta más para la toma de
decisiones y que deben valorarse en su justa medida, ya que
difícilmente es comprensible un problema complejo sin una
mínima modelización, aunque también hay que
reconocer que no es posible modelar la totalidad de las
situaciones reales.

Con anterioridad nos hemos referido a tipos de modelos
basados en sus formas de representación (icónico,
analógicos, simbólicos), no obstante podemos
establecer otros tipos de clasificaciones de los modelos
matemáticos:

Clasificados según su
función:

Modelos predictivos: Este tipo de modelos nos
informan del comportamiento de la  variable en un futuro, es
decir, lo que debería ser. A este tipo de modelos
corresponden aquellos basados en técnicas
estadísticas y/o econométricas, es decir, modelos
de previsión.

Modelos evaluativos: Una técnica
evaluativa corresponde a medir las diferentes alternativas, y
así poder comparar los resultados de ellas. Este tipo de
modelos se corresponden con los denominados árboles de
decisión.

Modelos de optimización: Se trata de
modelos que tratan de identificar un optimo (por lo general, el
optimo global) del problema, es decir, buscan la mejor de las
alternativas posibles. Estos métodos son los que
están basados en las técnicas de
programación matemática.

Otra clasificación de los modelos se basa en la
realidad que pretender modelar, así podemos hablar
de:

Modelos deterministas versus modelos
estocásticos. En los modelos deterministas todos los
datos del problema se conocen con absoluta certeza, mientras que
cuando esto no es así tenemos los modelos
estocásticos. Por lo general los modelos más
realistas son los modelos estocásticos, pero tienen la
dificultad de poderlos resolver adecuadamente, y muchas de las
técnicas aplicables a los modelos estocásticos
tratan de reducir el problema a su versión determinista
para poderlo resolver.

Modelos estáticos versus modelos
dinámicos. En un modelo estático la variable
tiempo no desempeña un papel relevante, mientras que en
los modelos dinámicos la variable fundamental, y de la que
dependen las restante variables relevantes. Además, la
variable tiempo se considera como una variable
continua.

Una vez establecida una serie de clasificaciones
de  los modelos, es conveniente plantear una medida de su
solución, ya que el objetivo de plantear el modelo es el
poderlo resolver y extraer de la solución los resultados
necesarios para la toma de decisiones. El nivel de resolubilidad
de los problemas es función de tres características
fundamentales:

a)  El tamaño del problema: El numero de
variables y ecuaciones que contiene. Cuanto mayor sea este
número, más difícil de resolver
es.

b)  La clase del problema: Lineal, Entero y No
lineal, y además por ese orden, es decir, los problemas
lineales son "fácilmente" resolubles, mientras que los no
lineales son "intrínsecamente" difíciles de
resolver.

c)  El tipo de instancias utilizadas: Ciertas o
deterministas, con riesgo (conocemos las probabilidades de
ocurrencia), con incertidumbre (conocemos los resultamos posibles
pero no las probabilidades de ocurrencia) y turbulencia ( no
conocemos nada). 2

Problema de
asignación

El Problema de la Asignación es un problema
clásico de la Investigación de Operaciones y es un
caso particular del Problema del Transporte.

Este problema se trata de asignar una serie de Recursos
a una serie de tareas. 

Tiene una limitante y es que a cada tarea se le puede
asignar sólo un recurso, pueden sobrar recursos o
podrían sobrar tareas pero no se le puede asignar dos
recursos a una misma tarea, o tres… por ejemplo si se tienen
tres operarios con diferentes tiempos de operación en
cuatro máquinas el modelo nos diría como asignar
los tres operarios a tres máquinas (nos sobraría
una) de manera que se minimice el tiempo total, pero no nos
diría como asignar dos operarios a dos máquinas y
el otro operario a las otras dos máquinas.

Ejemplos de Asignaciones: Operarios a Tareas,
Máquinas a Operarios, Nadadores a Estilos, Novias a
días de la semana, etc, etc, etc.

El Problema de la Asignación se basa en una
información comparativa para tomar la decisión de
que asignar a que, por ejemplo una matriz de costos, una matriz
de tiempos, de ingresos, etc.

Cuando la matriz no está balanceada, es decir,
cuando no es cuadrada, cuando sobran filas o columnas, se debe
balancear para que tenga solución mediante la
inclusión de filas o columnas ficticias, con valores de
cero en dicha matriz.

Supongamos el siguiente ejemplo:

Existen cuatro operarios que se pueden asignar al
trabajo con tres máquinas.  Un estudio de tiempos y
movimientos ha arrojado los siguientes tiempos por operario para
las tres máquinas. Indicar que operario debe trabajar en
que máquina y cuál de ellos no será asignado
a ninguna.

Como la matriz no esta balanceada, es necesario
incluir una máquina ficticia:(esto es fundamental
para asegurar que haya una res

puesta. Si la matriz no está balanceada, el
problema no será factible de resolver)

Xij = Se debe asignar el operario i a la máquina
j? Sí o no?

En matemáticas existen dos números cuyas
propiedades hacen que puedan representar estas respuestas son el
1 y el 0, debido a que todo número multiplicado por 1 da
el mismo número entonces el 1 se puede reemplazar por la
respuesta Sí y como todo número multiplicado por
cero da cero entonces se puede reemplazar por la respuesta
No.

Así por ejemplo:

10X11 + 7X12 + 9X13 + 0X14

representa el tiempo sumado  que emplearía
el operario1 en operar las máquinas, pero solo una
variable de las tres anteriores puede tomar el valor de
Sí, o sea de 1 las demás tendrán que tomar
el valor de 0, y eso es debido a que el operario 1 sólo
puede ser asignado a una máquina, lo que
significaría que el tiempo que utilice el operario 1 puede
ser ya sea de "10" de "7" o de "9". Con base en esto podemos
formular la función objetivo:

Restricciones:

Como cada operario sólo puede estar asignado a
una máquina….

X11 + X12 + X13 + X14 = 1X21 + X22 + X23 + X24 = 1X31 +
X32 + X33 + X34 = 1X41 + X42 + X43 + X44 = 1

Y como cada máquina solo puede tener un operario
asignado…

X11 + X21  + X31 + X41 = 1X12 + X22  + X32 +
X42 = 1X13 + X23  + X33 + X43 = 1X14 + X24  + X34 + X44
= 1

Xij = 1 o 0 para toda i,j.

Al resolver utilizando Software, por ejemplo el Solver
del Excel, la respuesta que se obtiene es la
siguiente:

Esto significa que el Operario 1 queda asignado a la
Máquina Ficticia (es decir, es el que sobra), el operario
2 se asigna a la máquina 2, el operario 3 se asigna a la
máquina 1 y el operario 4 se asigna a la máquina
3.

Teorema fundamental de la
asignación:

Si a todos los elementos de una fila o de una columna de
una matriz de rendimientos se le suma o se le resta una cantidad
constante la asignación optima no varía.

Algoritmo húngaro:

El algoritmo Húngaro está destinado para
minimizar si tenemos que maximizar tendremos previamente que
darle la vuelta a la matriz restándole el mayor elemento
de toda la matriz a cada uno de los elementos de la misma de
manera que el elemento que era más pequeño pasara a
ser el más grande y a la inversa.

El Algoritmo Húngaro se debe a D. König y E.
E Egervóry.

Cuando hay que pasar de maximizar a minimizar en lugar
de operar con el mayor de toda la matriz podemos ir tomando el
mayor de cada fila o columna e ir restándole todos los
elementos de esa fila o columna con lo cual conseguiremos de
camino obtener por lo menos un cero como mínimo en cada
fila o columna. Si en alguna columna no hubiera ceros le quitamos
el mayor a la columna.

El método Húngaro:

Este algoritmo se usa para resolver problemas de
minimización, ya que es más eficaz que el empleado
para resolver el problema del transporte por el alto grado de
degeneración que pueden presentar los problemas de
asignación. Las fases para la aplicación del
método Húngaro son:

Paso 1: Encontrar primero el elemento más
pequeño en cada fila de la matriz de costos m*m; se debe
construir una nueva matriz al restar de cada costo el costo
mínimo de cada fila; encontrar para esta nueva matriz, el
costo mínimo en cada columna. A continuación se
debe construir una nueva matriz (denominada matriz de costos
reducidos) al restar de cada costo el costo mínimo de su
columna.

Paso 2: (En algunos pocos textos este paso se
atribuye a Flood). Consiste en trazar el número
mínimo de líneas (horizontales o verticales o ambas
únicamente de esas maneras) que se requieren para cubrir
todos los ceros en la matriz de costos reducidos; si se necesitan
m líneas para cubrir todos los ceros, se tiene una
solución óptima entre los ceros cubiertos de la
matriz. Si se requieren menos de m líneas para cubrir
todos los ceros, se debe continuar con el paso 3. El
número de líneas para cubrir los ceros es igual a
la cantidad de asignaciones que hasta ese momento se pueden
realizar.

Paso 3: Encontrar el menor elemento diferente de
cero (llamado k) en la matriz de costos reducidos, que no
está cubierto por las líneas dibujadas en el paso
2; a continuación se debe restar k de cada elemento no
cubierto de la matriz de costos reducidos y sumar k a cada
elemento de la matriz de costos reducidos cubierto por dos
líneas (intersecciones). Por último se debe
regresar al paso 2.

Notas:

1. Para resolver un problema de asignación
en el cual la meta es maximizar la función objetivo, se
debe multiplicar la matriz de ganancias por menos uno (-1) y
resolver el problema como uno de minimización.

2. Si el número de filas y de columnas en
la matriz de costos son diferentes, el problema de
asignación está desbalanceado. El método
Húngaro puede proporcionar una solución incorrecta
si el problema no está balanceado; debido a lo anterior,
se debe balancear primero cualquier problema de asignación
(añadiendo filas o columnas ficticias) antes de resolverlo
mediante el método Húngaro.

3. En un problema grande, puede resultar
difícil obtener el mínimo número de filas
necesarias para cubrir todos los ceros en la matriz de costos
actual. Se puede demostrar que si se necesitan j líneas
para cubrir todos los ceros, entonces se pueden asignar solamente
j trabajos a un costo cero en la matriz actual; esto explica
porqué termina cuando se necesitan m
líneas.

Mediante el siguiente ejemplo vamos a ilustrar la manera
de aplicar el método Húngaro a la solución
de un problema de asignación de
minimización:

Una factoría tiene cuatro operarios, los cuales
deben ser asignados al manejo de cuatro máquinas; las
horas requeridas para cada trabajador en cada máquina se
dan en la tabla adjunta; el tiempo a laborar por cada operario en
cada una de las máquinas se pretende que sea
mínimo, para lo cual se busca la asignación
óptima posible.

Planteamiento del
Modelo Primal

MIN W = 10 X11+ 14 X12+ 16 X13+ 13 X14+ 12 X21+ 13 X22+
15 X23+ 12 X24+ + 9 X31+ 12 X32+ 12 X33+ 11 X34+ 14 X41+ 16 X42+
18 X43+ 16 X44

sujeto a las siguientes restricciones:

Aplicando el método Húngaro
tenemos:

Solución Optima Unica:A-1, B-4, C-3 y D-2.Lo
anterior quiere decir que Antonio va a laborar en la
máquina 1 (10 horas), Bernardo en la máquina 4 (12
horas), Carlos va a trabajar en la máquina 3 (12 horas) y
Diego en la máquina 2 (16 horas).

La combinación óptima de los recursos para
este problema de minimización de asignación es de
50 horas, resultantes de adicionar las asignadas a cada uno de
los operarios en cada una de las máquinas. Dicho valor
corresponde al valor óptimo de la función
objetivo.

Bibliografía

• Nassir Sepag Chain, Reinaldo Sepas Chain
  "PREPARACIÓN Y EVALUACIÓN DE PROYECTO" 3ra.
  Edición, Mac Graw-Hill, MÉXICO,2001.

• Gitman, Laurence J, " PRINCIPIO DE
  ADMINISTRACIÓN FINANCIERA" 8va. Edición,
  Abenada, West Liengrad. MÉXICO, 2000.

• Polimeni, Ralphas y otros " CONTABILIDAD DE COSTOS"
  3ra Edición, MacGraw-Hill. COLOMBIA, 2000.

• INVESTIGACIÓN DE OPERACIONES EN LA CIENCIA
  ADMINISTRATIVA

• Eppen, G. D / Gould F. J. / Schmidt, C.P. / Moore,
  Jeffrey H, / Weathrford, Larry R.

• Prentice – Hall 5ª Edición México
  1999 – 1987

Partes: 1, 2