Asignación y Transporte
1. Método de la esquina noroeste.
Parte de él “Algoritmo de Transporte en Programación Lineal”. El Método de la
esquina Noroeste (o esquina superior izquierda) es una heurística que se aplica a
una estructura especial de problemas de Programación Lineal llamada Modelo de
transporte, la cual permite asegurar que exista una solución básica factible inicial
(no artificial). Otros métodos para la obtención de una solución básica d inicio son
el Método de Costo Mínimo y Método de Aproximación de Vogel. En general, el
Método de Vogel produce la mejor solución básica de inicio y el de la esquina
noroeste la por, sin embargo, el método de la esquina noroeste implica el mínimo
de cálculos.
El método de la esquina es un método de programación lineal hecho a mano para
encontrar una solución inicial factible del modelo, muy conocido por ser el método
más fácil al determinar una solución básica factible inicial, pero al mismo tiempo por
ser el menos probable para dar una solución inicial acertada de bajo costo, debido
a que ignora la magnitud relativa de los costos es un proceso utilizado para resolver
problemas de transporte o asignación, si bien es un método no exacto tiene la
ventaja de poder resolver problemas manualmente y de una forma rápida, muy
cercano al valor óptimo. Cada problema debe representarse en forma de matriz en
donde las filas normalmente representan las fuentes y las columnas representan los
destinos.
Este método tiene como ventaja frente a sus similares, la rapidez de su ejecución,
y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y
destinos sea muy elevado.
El Método de la Esquina Noroeste comienza en la celda (ruta) correspondiente a la
esquina noroeste, o superior izquierda, de la tabla (variable ). Se parte por
esbozar en forma matricial el problema, es decir, filas que representen fuentes y
columnas que representen destinos. A continuación una descripción de los pasos:
Paso 1. Asignar todo lo posible a la celda seleccionada y ajustar las cantidades
asociadas de oferta y demanda restando la cantidad asignada.
Paso 2. Salir de la fila o la columna cuando se alcance oferta o demanda cero y
tacharlo, para indicar que no se pueden hacer más asignaciones a esa fila o
columna. Si una fila y una columna dan cero al mismo tiempo, tachar solo uno (la
fila o la columna) y dejar una oferta (demanda) cero en la fila (columna) que no se
tachó.
Paso 3. Si queda exactamente una fila o columna sin tachar, detenerse. En caso
contrario, avanzar a la celda de la derecha si se acaba de tachar una columna, o a
la de abajo si se tachó un renglón. Seguir con el paso 1.
Ejemplo 1
Una empresa energética colombiana dispone de cuatro plantas de generación para
satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y
Barranquilla. Las plantas 1, 2, 3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de
KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá,
Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día
respectivamente.
Y procedemos a restar la demanda y la oferta
luego, tapamos la planta 1 ya que la oferta
quedo en 0.
En este caso nos encontramos frente a la
eleccion de la fila o columna a eliminar (tachar),
sin embargo podemos utilizar un criterio
mediante el cual eliminemos la fila o columna
que presente los costos mas elevados. En este
caso la “Planta 2”.
Una vez finalizada esta asignación,
se elimina la “planta 3” que ya ha
sido satisfecha con la asignación
de 60 unidades, por ende nos
queda una sola fila a la cual le
asignamos las unidades
estrictamente.
CUADRO DE LAS ASIGNACIONES
El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda
así:
Los costos asociados a la distribución son:
Lo importante de estos ejercicios es que presenta un cumplimiento de todas las
restricciones y una rapidez de elaboración, lo cual es una ventaja en problemas
con innumerables fuentes y distintos en los cuales nonos importe más que
satisfacer las restricciones.
2. Método de Costo mínimo.
El método de costo mínimo es un algoritmo que tiene el objetivo de desarrollar la
resolución de problemas relacionados con el transporte o distribución proyectando
mejores resultados que otros métodos, como es el caso de la esquina noroeste.
Esto se debe, a que puede enfocarse en diversas rutas menores, que su vez
presentan costos menores.
El diagrama de flujo de este tipo de algoritmo, suele ser mucho más sencillo que
otros, ya que simplemente se relaciona con la asignación de todas las cantidades
posibles de unidades que se encuentran sujetas a todas las restricciones de
demandas y ofertas, es decir a todas las celdas de menor costo de toda la matriz
hasta llegar al final del método.
Todo esto significa, que este método de costo mínimo, simplemente busca la forma
de localizar la mejor solución inicial del modelo de transporte, por medio de la
utilización de las rutas más económicas.
El método del costo mínimo o método de los mínimos costos es un algoritmo
desarrollado con el objetivo de resolver problemas de transporte o distribución,
arrojando mejores resultados que métodos como el de la esquina noroeste, dado
que se enfoca en las rutas que representan menores costos.
Este algoritmo es mucho más sencillo que los anteriores, dado que se trata
simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a
las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz
hasta finalizar el método.
De esta forma el método del costo mínimo se inicia asignando lo máximo posible a
la celda que tenga el mínimo costo unitario (en caso de empates, estos se rompen
de forma arbitraria). A continuación, la fila o columna ya satisfechos se tacha, y las
cantidades de oferta y demanda se ajustan en consecuencia. Si se satisfacen de
forma simultanea una fila y una columna, solo se tacha uno de los dos (de forma
idéntica que el método de la esquina noroeste). Luego se busca la celda no tachada
con el costo unitario mínimo y se repite el proceso hasta que se queda sin tachar
exactamente una fila o una columna.
Entre las características más relevantes de este importante método se encuentran:
o Es un método que puede resultar exitoso al ser bien elaborado.
o Tiene claro los costos al realizar las asignaciones.
o Mayormente se mantiene al margen de la solución óptima.
o Es importante comenzar a resolverlo por las celdas que están vacías.
o La cantidad de casillas tiene que ser igual a m+n-1.
o Las líneas deben trazarse solo de forma horizontal y vertical.
o Las líneas pueden trazarse por las celdas que estén llenas o vacías sin ser
utilizadas.
o Su desarrollo debe comenzar en una celda que este vacía y al pasar por las
celdas que estén llenas, es importante que termine en la celda vacía en
donde se comenzó el proceso.
o En caso de que alguno de los índices de mejoramiento arroje un resultado
negativo, se debe tomar el menor número de la celda con signo negativo y a
su vez este valor se le debe sumar a todas las celdas que contengan signo
positivo y también se restara a las celdas que tengan signos negativos. De
esta forma, se van a generar las nuevas asignaciones.
o Si los índices de mejoramiento proporcionan cero como resultado o cualquier
número que sea positivo, se concluye el ejercicio, proporcionando un
resultado óptimo.
Sus ventajas son:
o Proporciona con rapidez a mejores soluciones.
o Asume en su análisis, diferencias entre los costos menores de transporte.
o Es un método completamente imparcial y preciso.
o Se escogen los sitios que producen los costos menores de transporte que se
relacionen con la materia prima y el producto terminado.
o Es muy sencillo y fácil de aplicar, ya que tiene en cuenta el análisis de los
costos de transporte.
Sus desventajas son:
o No tiene la capacidad de aportar ningún tipo de criterio que permita la
determinación si la solución obtenida mediante este método es la más optima
o no.
o El número de demandas y ofertas siempre son las mismas, debido a que no
varían con el tiempo.
o No considera otros tipos de efectos para localizar, sino solamente la de los
costos de transporte.
o Puede lograr tener diversos resultados, dependiendo del criterio con que
comience a trabajar, en caso de que se asigne una sola columna.
Importancia del método de costo mínimo:
Este método a diferencia de otros algoritmos que asignan envíos y costos de
transporte, en situaciones de demandas y ofertas, es mucho más eficiente y versátil
que diversos métodos de distribución de costos. También suele ser mucho más
sencillo, debido a que solamente busca designar mayor número de unidades.
Debido a la búsqueda de soluciones, este método se gana una gran importancia,
ya que tiene la capacidad de ofrecer las mejores soluciones a los problemas.
Algoritmo de la resolución del método de costo mínimo.
El método de costo mínimo se puede aplicar para establecer un confiable plan de
transporte de una determinada mercancía que provenga de diversas fuentes a
diferentes destinos a un mínimo costo. Para llevarlo a cabo se deben seguir los
siguientes pasos:
Paso 1. Se escoge la ruta o celda de menor costo de la matriz y se le debe designar
la mayor cantidad posible de unidades. Esta cantidad se puede llegar a limitar,
debido a las restricciones de demandas y ofertas.
En este primer paso, también se procede a la justificación de la oferta y demanda
que se encuentra en la fila y columna afectada. Esto se justifica restándole la
cantidad que esté asignada a la celda.
Paso 2. Durante el proceso de este segundo paso, se debe eliminar la fila o destino
donde la oferta o demanda sea 0 luego del paso 1, si se llega a presentar el caso
de que las dos están 0, se tiene que elegir de forma arbitraria, cual se tiene que
eliminar y la que quede restando, se debe dejar con la demanda y la oferta en 0
dependiendo del caso.
Paso 3. Cuando se llegue a este tercer paso, se pueden presentar dos posibilidades
que son:
o Que quede una sola columna o región, si esto llega a sucedes se debe
detener, ya que se ha culminado el método.
o En la segunda posibilidad, si llega a quedar más de una columna o renglón,
es necesario volver a iniciar en paso 1.
Ejemplo 1
Consideremos nuevamente el Problema de Transporte donde se desea satisfacer
la demanda de 4 molinos a través de los envíos de 3 silos, donde los valores en la
esquina superior derecha de cada cuadro Cij representan los costos unitarios de
transporte desde el silo i al molino j.
Fe de Erratas: En la imagen dice Molino 1, 2, 3 y 5 (columnas). Deberia decir: 1, 2,
3 y 4.
La aplicación del Método de Costo Mínimo al problema de transporte anterior da
origen a la siguiente solución factible de inicio:
Los pasos aplicados para llegar a dichos resultados se resumen a continuación:
o La celda X12 tiene el menor costo unitario, por tanto se asigna lo máximo
posible (15 unidades correspondientes a la oferta del silo 1). Con X12 = 15
se satisface tanto la demanda del molino 2 como la oferta del silo 1. Se tacha
de forma arbitraria la columna 2.
o Ahora la celda X31 tiene el mínimo costo unitario sin tachar. Se asigna
X31= 5 y se tacha la columna 1 porque quedo satisfecha (lo cual deja una
capacidad remanente del silo 3 de 5 unidades).
o Al continuar de este modo, se asigna en forma sucesiva 15 unidades a la
celda X23, 0 unidades a la celda X14 (la capacidad del silo 1 ya fue
asignada), 5 unidades a la celda X34 y 10 unidades a la celda X24.
La solución básica factible de inicio resultante con 6 variables básicas es: X12= 15,
X14= 0, X23=15, X24= 10, X31= 5, X34= 5 la cual reporta un valor en la función
objetivo (costo) de Z=15(2)+0(119+15(9)+10(20)+5(4)+5(18)= $475 que
efectivamente es una mejor solución inicial que la obtenida por el Método de la
Esquina Noroeste (que provee un valor de $520 al ser evaluado en la función
objetivo) pero por cierto no es la solución óptima según se aprecia en la siguiente
imagen que resume la implementación computacional del problema en Solver.
Ejemplo 2
Una empresa energética colombiana dispone de cuatro plantas de generación
para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá,
Medellín y Barranquilla. Las plantas 1, 2, 3 y 4 pueden satisfacer 80, 30, 60 y 45
millones de KW al día respectivamente. Las necesidades de las ciudades de Cali,
Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de KW al día
respectivamente. Los costos asociados al envío de suministro energético por cada
millón de KW entre cada planta y cada ciudad son los registrados en la siguiente
tabla.
Seleccionamos la celda con menor valor, es decir la menos costosa, para
asignarle la mayor cantidad posible.
Luego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la
«Planta 3», en un proceso muy lógico. Dado que Bogotá se queda sin demanda
esta columna desaparece, y se repite el primer proceso.
Nuevo proceso de asignación
Nuevo proceso de asignación
Una vez finalizado el cuadro anterior nos daremos cuenta que solo quedará una
fila, por ende asignamos las unidades y se ha terminado el método.
El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda
así:
Los costos asociados a la distribución son:
3. Método de aproximación de Vogel
El método de aproximación de Vogel es un método heurístico de resolución de
problemas de transporte capaz de alcanzar una solución básica no artificial de inicio,
este modelo requiere de la realización de un número generalmente mayor de
iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo
producen mejores resultados iniciales que los mismos.
El método de aproximación de Vogel es una versión mejorada del método del costo
mínimo y el método de la esquina noroeste que en general produce mejores
soluciones básicas factibles de inicio, entendiendo por ello a soluciones básicas
factibles que reportan un menor valor en la función objetivo (de minimización) de un
problema de transporte balanceado (suma de la oferta = suma de la demanda).
Su objetivo es reducir al mínimo posible los costos de transporte destinados a
satisfacer los requerimientos totales de demanda y materiales.
Sus características son:
- Se debe enviar las mayores cantidades al mayor costo posible.
- Tienen diferentes orígenes con diferentes destinos.
- Un origen puede abastecer a diferentes destinos.
- Al finalizar el ejercicio la oferta y la demanda deben ser satisfecha en su
totalidad y/o terminado sus valores en cero.
- La aproximación de Vogel finaliza en costo mínimo.
- Es más elaborado que los anteriores, más técnico y dispendioso.
- Tiene en cuenta los costos, las ofertas y las demandas para hacer las
asignaciones.
- Generalmente nos deja cerca al óptimo.
Sus ventajas son:
- Conduce rápidamente a una mejor solución.
- Tiene en cuenta en el análisis la diferencia entre los menores costos de
transporte.
- Es un método preciso y totalmente imparcial.
Sus desventajas son:
- No aporta ningún criterio que permita determinar si la solución obtenida por
este método es la mejor o no.
- Las cantidades de oferta y demanda no varían con el tiempo.
- No considera más efectos para la localización que los costos de transporte.
Algoritmo de Vogel
El método consiste en la realización de un algoritmo que consta de 3 pasos
fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
Paso 1. Determinar para cada fila y columna una medida de penalización restando
los costos menores en filas y columnas.
Paso 2. Escoger la fila o columna con la mayor penalización, es decir que de la resta
realizada en el “Paso 1” se debe escoger el número mayor. En caso de haber
empate, se debe escoger arbitrariamente (a juicio personal).
Paso 3. De la fila o columna de mayor penalización determinada en el paso anterior
debemos de escoger la celda con el menor costo, y en esta asignar la mayor
cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda
quedara satisfecha por ende se tachara la fila o columna, en caso de empate solo
se tachara 1, la restante quedara con oferta o demanda igual a cero (0).
Paso 4. De ciclo y excepciones:
✓ Si queda sin tachar exactamente una fila o columna con cero oferta o
demanda, detenerse.
✓ Si queda sin tachar una fila o columna con oferta o demanda positiva,
determine las variables básicas en la fila o columna con el método de costos
mínimos, detenerse.
✓ Si todas las filas y columnas que no se tacharon tienen cero oferta y
demanda, determine las variables básicas cero por el método del costo
mínimo, detenerse.
✓ Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que
las ofertas y las demandas se hayan agotado.
Ejemplo 1
Encuentre la solución inicial del problema de la compañía de renta de autos por el
método de aproximación de Vogel.
Una empresa está considerando satisfacer las necesidades de 4 clientes
empleando los artículos que tiene disponibles en 3 almacenes. La cantidad de
artículos que tiene en cada almacén son y es, 40 y 20 unidades respectivamente.
Los clientes necesitan 12, 15, 30 y 20 unidades respectivamente. El costo unitario
de embarque desde los almacenes hasta el cliente se encuentra en la siguiente
tabla:
Encuentre la solucion inicial del modelo de transporte ultilizando el metodo de
aproximación de vogel.
Ejemplo 2
Una empresa energética colombiana dispone de cuatro plantas de generación para
satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y
Barranquilla. Las plantes 1, 2, 3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de
KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá,
Medellín y Barranquilla son de 70, 40, 70 y 35 millones de KW al día
respectivamente. Los costos asociados al envió de suministro energético por cada
millón de KW entre cada planta y cada ciudad son los registrados en la siguiente
tabla.
Formule un modelo de programación lineal que permita satisfacer las necesidades
de todas las ciudades al tiempo que minimice los costos asociados al transporte.
El primer paso es determinar las medidas de penalización y consignarlas en el
tabulado de costos, tal como se muestra a continuación.
El paso siguiente es escoger la mayor penalización, de esta manera:
El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela
se le asigna la mayor cantidad posible de unidades, podemos observar como el
menor costo es “2” y que a esa celda se le pueden asignar como máximo 60
unidades “que es la capacidad de la planta 3”
Dado que la fila de la “Planta 3” ya ha asignado toda su capacidad (60 unidades)
esta debe desaparecer.
Se ha llegado al final del ciclo, por ende se repite el proceso
Iniciamos una nueva iteración
Continuamos con las iteraciones,
Iniciamos otra iteración
Al finalizar esta iteración podemos observar como el tabulado queda una fila sin
tachar y con valores positivos, por ende asignamos las variables básicas y hemos
concluido el método.
Los costos asociados a la distribución son:
De esta manera hemos llegado a la solución a la cual también llegamos mediante
programación lineal, definitivamente desarrollar la capacidad para modelar
mediante programación lineal y apoyarse de una buena herramienta como WinQSB,
STORM, LINGO, TORA, etc., termina siendo mucha más eficiente que la utilización
de los métodos heurísticos para problemas determinísticos; sin embargo cabe
recordar que uno de los errores más frecuentes en los que caen los ingenieros
industriales es en tratar de adaptar a sus organizaciones a los modelos
establecidos, cabe recordar que son los modelos los que deben adaptarse a las
organizaciones lo cual requiere de determinada habilidad para realizar de forma
inmediata cambios innovadores para sus fines, en pocas palabras un ingeniero
industrial requiere de un buen toque de HEURISTICA en su proceder.
4. Método de asignación
El método de asignación también es un caso especial del modelo de transporte.
Conocido como la Técnica de flood o el método Húngaro de asignación. El problema
de asignación debe su nombre a la aplicación particular de asignar hombres a
trabajos (o trabajos a maquinas), con la condición de que cada hombre puede ser
asignado a un trabajo y que cada trabajo tendrá asignada una persona.
El problema de asignación es una variación del problema original de transporte,
variación en la cual las variables de decisión X(i,j) solo pueden tomar valores
binarios, es decir ser cero (0) o uno (1), en la solución óptima, lo que supone que la
oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a
uno (1).
En el modelo de asignación, la idea fundamental de resolución es ¿Qué fuente
satisface mejor el destino?, y dado que hemos asociado el modelo a una gran
diversidad de circunstancias esta pregunta puede plantearse en múltiples contextos,
como ¿Qué candidato es el idóneo para la vacante?, o ¿Qué personal es el indicado
para la línea productiva?, o ¿Qué personal es el mejor para ejecutar determinada
tarea? Una característica particular del modelo de asignación es que para su
resolución no se hace necesario que el número de fuentes sea igual al número de
destinos, lo cual es muy común en la vida real, teniendo en cuenta su aplicación,
pues generalmente la cantidad de aspirantes es superior al número de vacantes
(lógicamente haciendo referencia a la aplicación del modelo al contexto de oferta y
demanda laboral).
“La mejor persona para el puesto” es una buena descripción del modelo de
asignación.
El problema de asignación tuvo su origen en la revolución industrial, ya que el
surgimiento de las maquinas hizo que fuera necesario asignar una tarea a un
trabajador.
Pero no es hasta 1955 cuando Harold W. Kuhn plantea el Método húngaro.
Su objetivo es el aplicar el método de asignación, la gerencia está buscando una
ruta de distribución o una asignación que optimizara algún objetivo; este puede ser
la minimización del costo total, la maximización de las utilidades o la minimización
del tiempo total involucrado.
Sus características son:
- El problema de asignación debe estar equilibrado, es decir que la demanda
y la oferta debe ser igual a 1.
- Si el número de agentes y tareas son iguales y el coste total para todas las
tarea es igual a la suma de los costes de cada agente (o a la suma de los
costes de cada tarea, que es lo mismo en este caso), entonces el problema
es llamado problema de asignación lineal.
Diferencias entre el Modelo de Transporte y el de Asignación:
Los problemas de asignación presentan una estructura similar a los de transporte,
pero con dos diferencias: asocian igual número de orígenes con igual número de
demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en
cada destino.
La restricción importante para cada agente es que será asignado a una y solo una
tarea.
Al hacer una asignación a menudo deben cumplirse estas condiciones:
- Cada elemento del primer grupo debe asignarse a exactamente un elemento
del segundo grupo.
- Cada elemento del segundo grupo debe asignarse a exactamente un
elemento del primer grupo.
- Su forma de programación es lineal.
- Se basa en tablas, se solucionan problemas de manera repetitiva (sumas y
restas) para minimizar o maximizar.
- Requiere que a cada trabajador se le asigne una tarea específica.
Elementos del problema de asignación:
Tabla de transporte: Otra forma de plantear el problema de transporte (recordemos
que el problema de asignación es un caso especial del de transporte) es mediante
una tabla llamada tabla de transporte, la cual tiene forma de matriz donde los
renglones representan las fuentes y las columnas los destinos o trabajos.
- Matriz de costos. Es una matriz cuadrada de n*n, donde cada elemento
representa el costo de asignar el enésimo trabajador al enésimo trabajo;
renglones = trabajadores.
- Matriz de costo reducida. Es la matriz que se obtiene después de haber
restado el elemento más pequeño a cada renglón (reducción de renglones)
y restarle a esa nueva matriz el elemento más pequeño a cada columna
(reducción de columnas).
- Distribución óptima. Sean un conjunto de fragmentos F = {F1, F2,…, Fn} y
una red formada por el conjunto de aplicaciones Q = {q1, q2,…, qq} se
ejecutan.
- Método simplex. Método de solución de los problemas de programación lineal
donde se obtiene una solución factible y optima (en donde se pueden obtener
resultados como solución múltiple, solución no acotada, o que el problema
no tenga solución).
Método húngaro
Apartándonos un poco de la idea expresada en módulos anteriores respecto a la
facilidad de resolver problemas atinentes a la investigación operativa en especial
aquellos de transporte mediante el uso de herramientas tecnológicas como lo son
WinQSB, LINGO, TORA, STORM, Excel, etc., vale la pena ya sea para fines
académicos o de cultura ingenieril realizar la resolución del problema de asignación
mediante el algoritmo que se creó para tal fin, como lo es el Método Húngaro.
El método Húngaro es un método de optimización de problemas de
asignación, conocido como tal gracias a que los primeros aportes al método
clásico definitivo fueron de Dénes König y Jenö Egerváry dos matemáticos
húngaros. El algoritmo tal como se detallara a continuación está diseñado
para la resolución de problemas de minimización únicamente, será entonces
cuestión de agregar un paso adicional para abordar ejercicios de
maximización.
Paso 1. Antes que nada cabe recordar que el método húngaro trabaja en una matriz
de costos n*m (en este caso conocida como matriz m*m, dado que el número de
filas es igual al número de columnas n = m), una vez construida esta se debe
encontrar el elemento más pequeño en cada fila de la matriz.
Paso 2. Una vez se cumple el procedimiento anterior se debe construir una nueva
matriz n*m, en la cual se consignaran los valores resultantes de la diferencia entre
cada costo y el valor mínimo de la fila a la cual cada costo corresponde (valor
mínimo hallado en el primer paso).
Paso 3. Este paso consiste en realizar el mismo procedimiento de los dos pasos
anteriores referidos ahora a las columnas, es decir, se halla el valor mínimo de cada
columna, con la diferencia que este se halla de la matriz resultante en el segundo
paso, luego se construirá una nueva matriz en la cual se consignaran los valores
resultantes de la diferencia entre cada costo y el valor mínimo de la columna a la
cual cada costo corresponde, matriz llamada “Matriz de Costos Reducidos”.
Paso 4. A continuación se deben de trazar líneas horizontales o verticales o ambas
(únicamente de esos tipos) con el objetivo de cubrir todos los ceros de la matriz de
costos reducidos con el menos número de líneas posibles, si el número de líneas
es igual al número de filas o columnas se ha logrado obtener la solución óptima (la
mejor asignación según el contexto de optimización), si el número de líneas es
inferior al número de filas o columnas se debe de proceder con el paso 5.
Paso 5. Este paso consiste en encontrar el menor elemento de aquellos valores que
no se encuentran cubiertos por las líneas del paso 4, ahora se restara del restante
de elementos que no se encuentran en las intersecciones de las líneas horizontales
y verticales, una vez finalizado este paso se debe volver al paso 4.
Ejemplo 1
Un equipo de 3 mecánicos debe ser asignado para la realización de 3 tareas, donde
cada mecánico debe hacer una tarea. Se requiere encontrar la asignación de costo
mínimo para lo cual se dispone de los costos asociados a que el mecánico “i” realice
la tarea “j”.
Solución:
En la matriz original de costo, identificar el mínimo de cada renglón y restarlo de
todos los elementos del renglón.
En la matriz que resulte del paso anterior, identificar el mínimo de cada columna, y
restarlo de todos los elementos de la columna.
Identificar la solución óptima como la asignación factible asociada con los elementos
cero de la matriz obtenida en el paso 2.
Las celdas con valor cero y color cafés son la solución óptima. En consecuencia el
mecánico 1 realiza la tarea 2, el mecánico 2 asuma la tarea 1 y el mecánico 3 la
tarea 3. Cada mecánico realiza exactamente una tarea y el costo total de dicha
asignación (valor optimo) es de Q9+Q10+Q8=Q27.
Ejemplo 2
JoShop debe asignar 4 tareas a 4 trabajadores. El costo de realizar un trabajo es
función de los conocimientos de los trabajadores. La siguiente tabla resume el costo
de las asignaciones. El trabajador 1 no puede hacer el trabajo 3 no puede hacer el
trabajo 4. Determine la asignación óptima con el método húngaro.
En la matriz original de costo, identificar el mínimo de cada renglón y restarlo de
todos los elementos del renglón.
En la matriz que resulte del paso anterior, identificar el mínimo de cada columna, y
restarlo de todos los elementos de la columna.
Si no se puede asegurar una asignación factible (con todos los elementos cero) con
los pasos 1 y 2.
a) Trazar la cantidad mínima de líneas horizontales y verticales en la última
matriz reducida que cubran todos los elementos cero.
b) Seleccionar el elemento mínimo no cubierto (color amarillo), restarlo de todo
elemento no cubierto y a continuación sumarlo a todo elemento en la
intersección de dos líneas.
c) Si no se puede encontrar una asignación factible entre los elementos cero
que resulten, repetir el paso. En caso contrario, seguir en el siguiente paso
para determinar la asignación óptima.
Identificar la solución óptima como la asignación factible asociada con los elementos
cero de la matriz obtenida en el paso anterior.
Las celdas con valor cero y color verde son la solución óptima. En consecuencia el
trabajador 1 realizara el trabajo 4, el trabajador 2 asuma el trabajo 3, el trabajador 3
realizara el trabajo 2 y el trabajador 4 el trabajo 1. Cada trabajador realizara
exactamente un trabajo y el costo total de dicha asignación (valor optimo) es de
Q20+Q20+Q30+70=Q140.
