Problema de Asignación - Método Húngaro

El método húngaro en lenguaje claro

El problema clásico

Tienes n trabajadores y n tareas. Cada trabajador puede hacer cualquier tarea, pero con costo (o beneficio) distinto. Necesitas asignar UN trabajador a UNA tarea (y cada trabajador a una sola tarea) minimizando el costo total. Es un caso especial de problema de transporte donde oferta y demanda son siempre 1.

El método húngaro (Kuhn, 1955)

Resuelve el problema en tiempo O(n³). Se basa en la propiedad: si restas una constante de toda una fila o toda una columna, la solución óptima no cambia. Aprovechando eso, transforma la matriz hasta encontrar n ceros tales que cada fila y cada columna tenga exactamente uno. Esos ceros son la asignación óptima.

Los pasos del algoritmo

1. Reducción de filas: resta el mínimo de cada fila.
2. Reducción de columnas: resta el mínimo de cada columna.
3. Buscar n ceros independientes (uno por fila y columna).
4. Si no se logra: cubrir todos los ceros con la menor cantidad de líneas posibles, encontrar el mínimo no cubierto, restarlo a no cubiertos y sumarlo a doblemente cubiertos. Volver al paso 3.
5. Asignación óptima: cuando se encuentran n ceros independientes.

Maximización en lugar de minimización

Para maximizar (asignar para mayor beneficio), se transforma a un problema de minimización restando cada elemento del máximo de la matriz. Esto invierte el problema: maximizar el original = minimizar el transformado.

Matrices no cuadradas

Si hay más trabajadores que tareas (o viceversa), se agregan filas/columnas ficticias con costo 0 (o algún costo de penalización si no asignar tiene costo).

Aplicaciones reales

• Asignación de proyectos: qué empleado hace qué proyecto.
• Asignación de turnos: qué persona en qué horario.
• Asignación de máquinas: qué pieza se procesa en qué máquina.
• Matching: bipartite matching en redes (incluso aplicaciones modernas como rideshare matching).
• Subastas: asignar bienes a postores maximizando el valor total.

Comparación con simplex y transporte

El simplex resuelve el problema de asignación general pero es ineficiente para esta estructura. El transporte funciona pero el húngaro es más rápido en matrices grandes y siempre da solución entera directa (sin necesidad de programación entera).

Limitaciones

• Asume asignación uno-a-uno. Si un trabajador puede tomar varias tareas o una tarea requiere varios trabajadores, usa modelos más generales (transporte, scheduling).
• Asume costos conocidos y determinísticos. Si hay incertidumbre, modelos estocásticos.
• No considera preferencias: solo el costo objetivo importa. Para matching con preferencias (Stable Marriage), algoritmo de Gale-Shapley.

Tip de examen: verifica siempre que el costo total sea menor o igual al de cualquier asignación "obvia" (la diagonal, asignación aleatoria). Si tu solución del húngaro es peor, hay un error de cálculo. La heurística greedy raramente da el óptimo en problemas medianos o grandes.