Método Húngaro en Investigaciones
Operativas
El Método Húngaro es un algoritmo desarrollado por Harold Kuhn en 1955, basado
en el trabajo previo de Dénes Kőnig y Jenő Egerváry. Se utiliza para resolver
problemas de asignación, que buscan minimizar costos o maximizar beneficios en la
distribución óptima de recursos.
Este método pertenece a la programación lineal y se basa en la teoría de matrices y
grafos bipartitos. Su ventaja principal es que garantiza encontrar una solución
óptima en tiempo polinómico.
Aplicaciones del Método Húngaro
El Método Húngaro se aplica en:
Asignación de tareas a trabajadores minimizando el costo total.
Distribución de trabajos en máquinas optimizando tiempos de procesamiento.
Asignación de rutas de transporte minimizando costos de viaje.
Distribución de proyectos entre equipos maximizando eficiencia.
Concepto del Problema de Asignación
El problema de asignación se presenta como una matriz de costos donde:
Las filas representan agentes (trabajadores, máquinas, etc.).
Las columnas representan tareas (trabajos, proyectos, etc.).
Cada celda contiene el costo de asignar un agente a una tarea.
El objetivo es encontrar una asignación óptima, es decir, una correspondencia uno a
uno entre filas y columnas, de modo que la suma de los costos sea mínima.
Ejemplo del Método Húngaro
Supongamos que tenemos 3 trabajadores y 3 tareas, con la siguiente matriz de costos
(en tiempo o dinero):
T1 T2 T3
W1 9 2 7
W2 6 4 3
W3 5 8 1
Nuestro objetivo es asignar cada trabajador a una sola tarea de manera que el costo
total sea mínimo.
Paso 1: Restar el mínimo valor de cada fila
Buscamos el menor valor en cada fila y lo restamos a todos los valores de esa fila.
Fila 1 (W1): mínimo = 2, restamos 2
o (9-2) 7, (2-2) 0, (7-2) 5 → (7, 0, 5)
Fila 2 (W2): mínimo = 3, restamos 3
o (6-3) 3, (4-3) 1, (3-3) 0 → (3, 1, 0)
Fila 3 (W3): mínimo = 1, restamos 1
o (5-1) 4, (8-1) 7, (1-1) 0 → (4, 7, 0)
Nueva matriz después del paso 1:
T1 T2 T3
W1 7 0 5
W2 3 1 0
W3 4 7 0
Paso 2: Restar el mínimo valor de cada columna
Buscamos el menor valor en cada columna y lo restamos de todos los valores de esa
columna.
Columna 1 (T1): mínimo = 3, restamos 3
o (7-3) 4, (3-3) 0, (4-3) 1 → (4, 0, 1)
Columna 2 (T2): mínimo = 0, no cambia.
Columna 3 (T3): mínimo = 0, no cambia.
Nueva matriz después del paso 2:
T1 T2 T3
W1 4 0 5
W2 0 1 0
W3 1 7 0
Paso 3: Trazar líneas para cubrir todos los ceros
1. Marcar todas las asignaciones posibles (un solo cero por fila o columna):
o W2 → T1 (0 en posición (2,1))
o W3 → T3 (0 en posición (3,3))
2. Trazar líneas para cubrir todos los ceros:
o Se cubre la columna T1 porque tiene un 0 asignado.
o Se cubre la columna T3 porque tiene otro 0 asignado.
o La columna T2 queda sin cubrir, por lo que seguimos al siguiente paso.
Paso 4: Ajuste de la matriz
Identificamos el menor valor no cubierto en la matriz → 1.
Restamos 1 de todos los valores no cubiertos.
Sumamos 1 en las intersecciones de las líneas.
Nueva matriz después del ajuste:
T1 T2 T3
W1 3 0 5
W2 0 0 0
W3 0 6 0
Paso 5: Asignación final
Ahora podemos hacer una asignación óptima sin conflictos:
W1 → T2
W2 → T1
W3 → T3
Asignación óptima obtenida con costo mínimo de 7 + 4 + 1 = 12.
