Problema de Asignación
Algoritmo del Método Húngaro
Concepto Base
El modelo de asignación es un caso especial del modelo de transporte donde los orígenes (ej. trabajadores) se asignan a los destinos (ej. tareas) en una relación estricta de uno a uno (oferta = 1, demanda = 1). La herramienta matemática por excelencia para resolverlo a mano es el Método Húngaro.
Las 5 Fases del Método Húngaro
Reducción por Filas
Encuentra el elemento más pequeño en cada fila y réstalo a todos los elementos de esa misma fila.
Reducción por Columnas
Usando la nueva matriz, encuentra el costo mínimo de cada columna y réstalo a toda su columna.
Prueba de Optimalidad (Líneas)
Traza el número mínimo de líneas (H/V) para cubrir todos los ceros. Si Nº de líneas = Nº de filas, ¡Terminaste! Si es menor, ve al paso 5.
El Ajuste (Constante k)
Busca el menor número no cubierto. Réstalo a los no cubiertos, súmalo a las intersecciones de líneas. Repite desde el Paso 3.
Variantes Comunes
Problemas Desbalanceados
Si la matriz no es cuadrada (ej. 3 trabajadores, 4 tareas), el método fallará. Solución: Añade una fila o columna ficticia con costos de asignación iguales a cero.
Problemas de Maximización
Si los datos son ganancias en lugar de costos, debes convertirlo a un problema de minimización. Solución: Multiplica toda la matriz de ganancias por menos uno (-1) antes de empezar.
Simulador de Matrices Paso a Paso
Interactúa con las dos ramas de ejecución del algoritmo. Observa cómo cambian las celdas y cómo se tachan los ceros según el estado matemático del proceso.
Paso
Cargando descripción...