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.

3
Tarea 1Tarea 2Tarea 3
Trabajador 1
Trabajador 2
Trabajador 3
Optimización Combinatoria y Grafos Bipartitos

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)

Paso 1: Reducción por Filas

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.

Paso 2: Reducción por Columnas

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.

Paso 3: Cobertura Mínima con Líneas

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.

Paso 4: Modificación de la Matriz

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.

Paso 5: Asignación de Ceros Óptimos

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 / MachineTask 1 (T₁)Task 2 (T₂)Task 3 (T₃)Task 4 (T₄)
Trabajador 1 (W₁)9278
Trabajador 2 (W₂)6437
Trabajador 3 (W₃)5818
Trabajador 4 (W₄)7694

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 WorkerMatched TaskOriginal 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.