GUÍA ASIGNACIÓN – 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 por qué termina cuando se necesitan m líneas.
EJERCICIOS PROPUESTOS:
1.- El jefe de un departamento, tiene 5 obreros y 5 trabajos
para hacer, los obreros difieren en su eficiencia y los
trabajos difieren en su dificultad intrínseca. El estimado de
los tiempos que cada hombre tomará para hacer cada
trabajo, está dado en la siguiente tabla.
¿Cómo deberán asignarse los trabajos, uno a cada obrero, para minimizar el total de horas
hombre?
Cada trabajo debe ser ejecutado por uno y solo un obrero y a cada obrero solo le debe ser
asignado uno y solo un trabajo.
2.- El gerente de una empresa, tiene 4 trabajadores y 4 trabajos para ejecutar, por su experiencia
y el nivel de dificultad de cada uno de los trabajos, los tiempos de ejecución de cada trabajador,
se muestran en la siguiente tabla.
El gerente desea que cada trabajo sea ejecutado por un
solo trabajador y a cada trabajador, solo se le asigne un
trabajo.
Que trabajador se debe asignar a cada trabajo, de tal
manera que la duración total de todos ellos sea la mínima?
3.- Considere el problema de asignación, cuya matriz de costos es la siguiente:
4.- El entrenador de un equipo de natación debe asignar competidores para la prueba de 200
metros combinados por equipos, para enviarlos a las olimpiadas juveniles.
Como muchos de sus
nadadores son rápidos en
más de un estilo, no le es
fácil decidir a que estilo
asignar a cada uno.
Los cuatro mejores
nadadores y sus mejores
tiempos (En segundos), en cada estilo son:
El entrenador quiere determinar como asignar los cuatro nadadores a los cuatro tipos de nado,
para minimizar la suma de los mejores tiempos correspondientes.
5.- Un corredor de bienes raíces, planea la venta de 5 lotes de terreno y ha recibido ofertas
individuales de cuatro clientes. Debido a la cantidad de capital que se requiere, estas ofertas se
han hecho en el entendimiento de que ninguno de los cuatro clientes comprará más de un lote.
Las ofertas se muestran en la siguiente tabla:
El corredor de bienes raíces quiere maximizar su ingreso total
a partir de esas ofertas. Resuelva éste problema mediante el
método Húngaro.
6.- Una empresa va a decidir cuál de cuatro vendedores debe asignar a cada uno de sus cuatro
distritos de ventas. Cada vendedor está en condiciones de lograr ventas diferentes en cada
distrito. En la tabla siguiente se muestran las estimaciones de ventas para diferentes
combinaciones de vendedor y distrito.
A la empresa le gustaría maximizar el volumen de ventas total.
Sin embargo, es imposible asignar al vendedor B para el distrito 1 y
al vendedor A para el distrito 2, ya que esas decisiones violarían las
políticas de rotación de personal. Use el método Húngaro para
resolver éste problema. Establezca el valor óptimo de la función
objetivo.
7.- Una compañía de contadores, tiene tres nuevos clientes. Se asignarán a los tres clientes, tres
jefes de proyecto. Con base en los distintos antecedentes y experiencia de los citados, las
diversas asignaciones entre jefes de proyecto y clientes, varía en función de los tiempos
esperados de terminación. Se muestra a continuación las posibles asignaciones y los tiempos
esperados de terminación.
Resuelva el problema y determine que jefe de proyecto se le asigna a cada cliente.
1
8.- Se tienen 4 trabajadores que deben ser asignados a 4 trabajos, con base en los tiempos
empleados por cada uno de ellos en cada trabajo, cuál es la asignación óptima que permite, en
conjunto, obtener el tiempo mínimo?
9.- Cuatro personas acaban de terminar el curso de ventas de la compañía y se les va a asignar a
cuatro distritos diferentes. Basándose en su experiencia, actuación en el curso, conocimiento del
proyecto y los clientes potenciales, la administración a hecho estimaciones del éxito esperado de
cada uno en cada distrito. Las estimaciones en la escala de 1 (Bajo) al 10 (Alto), son:
10.- El gerente de una agencia de publicidad, debe decidir, cuál de cuatro ejecutivos de
contabilidad debe asignar a cada uno de sus cuatro clientes principales. En la tabla se presentan
los costos estimados de la asignación de cada ejecutivo. Use el método Húngaro para encontrar
la solución óptima del problema y establezca el valor de la función objetivo.
11.- Coruniversitaria recibe ofertas para las 4 rutas de buses escolares de la ciudad. Cuatro
compañías presentaron las ofertas que se muestran en la tabla siguiente:
Suponga que se puede asignar solamente una ruta a
cada licitador.
Utilice el método de asignación para minimizar el
costo de Coruniversitaria para operar las 4 rutas de
buses.
12.- Container, Inc., fabrica contenedores de muchos tamaños y formas. Recientemente ha
recibido pedidos para producir diversas cantidades de contenedores de cocina de 6 diferentes
tamaños. Cada tamaño de contenedor puede producirse en cualquiera de cuatro máquinas.
Debido a las distintas tecnologías y tiempos de disposición, el número total de horas, incluyendo
el tiempo de disposición, necesarias para procesar cada tamaño de contenedor en cada máquina
varía, como se muestra en la siguiente tabla:
Tamaño del contenedor Máquina Adecuar una máquina para que cambie
el 1 2 3 4 tamaño de un contenedor toma largo
3x4 25 20 28 30 tiempo, así que la gerencia ha decidido
que 4x6 24 22 25 23 cada máquina producirá contenedores
de 6 x 8 30 30 28 25 un solo tamaño. Por tanto, solo se
8 x 12 38 32 30 30 producirán 4 de los 6 tamaños en las 4
12 x 18 40 40 28 30 máquinas disponibles dentro de la fecha
16 x 20 36 41 44 35 límite asignada. Como los ingresos por
cada tamaño de contenedor son
aproximadamente iguales, la gerencia de Container, Inc., es indiferente en cuanto a cual de los 6
pedidos no satisfacer. Como gerente del departamento de producción, se le ha pedido determinar
cuáles 4 de los 6 pedidos aceptar y desarrollar un plan de producción que minimice el tiempo de
procesamiento total para satisfacer esos pedidos.
