Calculadora del Método Húngaro (Problema de Asignación)
Resuelve problemas de asignación paso a paso mediante el algoritmo Húngaro, desde reducciones por fila/columna hasta el cubrimiento óptimo de ceros.
| Tarea 1 | Tarea 2 | Tarea 3 | |
|---|---|---|---|
| Trabajador 1 | |||
| Trabajador 2 | |||
| Trabajador 3 |
El Problema de Asignación y el Algoritmo Húngaro: Guía Académica
Desarrollo matemático formal del algoritmo de Kuhn-Munkres (Método Húngaro) para el emparejamiento ponderado y asignación óptima de recursos.
1. ¿Qué problema resuelve el Modelo de Asignación?
El Problema de Asignación es un modelo clásico de optimización combinatoria donde n agentes (operarios, máquinas) deben asignarse a n tareas de forma biyectiva (uno a uno). Dada una matriz de costos C donde cᵢⱼ representa el costo de asignar el agente i a la tarea j, el objetivo es minimizar el costo total ∑ cᵢⱼ xᵢⱼ sujeto a que cada agente y cada tarea tengan una única asignación, con xᵢⱼ ∈ {0, 1}. El Método Húngaro de Harold Kuhn resuelve este problema en tiempo polinomial O(n³).
2. Los 5 Pasos del Algoritmo Húngaro (Kuhn-Munkres)
Identifica el menor valor de cada fila y réstalo de todos los elementos de esa misma fila. Esto genera al menos un cero por fila sin alterar la jerarquía de soluciones óptimas.
Sobre la matriz reducida, identifica el menor valor de cada columna y réstalo de todos los elementos de dicha columna, garantizando al menos un cero por columna.
Traza el número mínimo de líneas horizontales y verticales para cubrir todos los ceros. Si el número de líneas es igual a n, existe una asignación óptima con costo cero (ir al Paso 5). Si es menor que n, pasar al Paso 4.
Halla el menor elemento no cubierto k. Réstalo de todos los elementos no cubiertos y súmalo a los elementos situados en la intersección de dos líneas. Los elementos cubiertos por una sola línea no varían. Regresa al Paso 3.
Selecciona ceros independientes en filas y columnas de modo que ningún agente ni tarea compartan asignación. Asocia las posiciones a los costos de la matriz original para obtener el costo mínimo.
3. Ejemplo Académico Resuelto: 4 Trabajadores × 4 Tareas
Sigue las reducciones sucesivas de una matriz 4×4 y comprueba el resultado exacto del motor.
| Worker / Machine | Task 1 (T₁) | Task 2 (T₂) | Task 3 (T₃) | Task 4 (T₄) |
|---|---|---|---|---|
| Trabajador 1 (W₁) | 9 | 2 | 7 | 8 |
| Trabajador 2 (W₂) | 6 | 4 | 3 | 7 |
| Trabajador 3 (W₃) | 5 | 8 | 1 | 8 |
| Trabajador 4 (W₄) | 7 | 6 | 9 | 4 |
A. Reducción por Filas (Restar Mínimos de Fila)
Fila 1 mín = 2 → [7, 0, 5, 6] | Fila 2 mín = 3 → [3, 1, 0, 4] | Fila 3 mín = 1 → [4, 7, 0, 7] | Fila 4 mín = 4 → [3, 2, 5, 0]. Cada fila cuenta ya con al menos un cero.
B. Reducción por Columnas (Restar Mínimos de Columna)
Columna 1 tiene mínimo 3 → [4, 0, 1, 0]. Las columnas 2, 3 y 4 ya tienen mínimo 0 y quedan intactas: Col 2 = [0, 1, 7, 2], Col 3 = [5, 0, 0, 5], Col 4 = [6, 4, 7, 0].
C. Cobertura de Líneas e Independencia
Los ceros resultantes están en (W₁, T₂), (W₂, T₁), (W₂, T₃), (W₃, T₃), (W₄, T₁) y (W₄, T₄). El número mínimo de líneas para cubrirlos a todos es exactamente 4 (= n). Por tanto, la asignación óptima es inmediata sin requerir el desplazamiento del Paso 4.
| Assigned Worker | Matched Task | Original Cost |
|---|---|---|
| Trabajador 1 (W₁) | Tarea 2 (T₂) | 2 € |
| Trabajador 2 (W₂) | Tarea 1 (T₁) | 6 € |
| Trabajador 3 (W₃) | Tarea 3 (T₃) | 1 € |
| Trabajador 4 (W₄) | Tarea 4 (T₄) | 4 € |
Resultado del Costo Mínimo Óptimo
Costo Total Z* = 2 + 6 + 1 + 4 = 13 €. (Cada trabajador queda asignado a una tarea distinta con costo mínimo global, coincidiendo con el motor de cálculo).
4. Errores Típicos en Ejercicios de Asignación
Problemas de Maximización sin Invertir la Matriz
Si se busca maximizar beneficios o rendimiento, se debe transformar la matriz restando cada valor del elemento máximo de la matriz original, o multiplicar todos los coeficientes por -1.
Matrices Rectangulares No Cuadradas (m ≠ n)
El Método Húngaro exige una matriz cuadrada. Si hay más tareas que trabajadores (o viceversa), deben añadirse filas o columnas ficticias con costos 0 antes de reducir.
Modificación Errónea en el Paso 4
En el Paso 4, el valor k se resta a las celdas sin cubrir y se suma únicamente a las intersecciones de dos líneas. Las celdas cubiertas por una sola línea no se modifican.