Método Húngaro - Problema de
Asignación
El algoritmo requiere lo siguiente:
-
Tener una matriz de costos para la asignación de "m" personas para
ser asignadas a "m" tareas
-
Todos los costos son no-negativos
-
El problema es un problema de minimización.
Inicio.
-
En cada fila, restar el menor costo a todos los valores de la fila
-
En la matriz resultante, restar el menor valor en cada columna a todos
los valores de la columna
Pasos Iterativos
-
Realizar tantas asignaciones con valor 0 como sea posible. Si todos los
trabajadores han sido asignados, entonces FIN; esta es la asignación
al menor costo. Sino, dibuje el menor número de lineas horizontales
y verticales para cubrir todos los ceros en la matriz.
-
Encuentre el valor más pequeño no cubierto por las líneas:
ese número es el valor de reducción
-
Restar el valor de reducción a todos los números no
cubiertos por las líneas. Sumar el valor de reducción
a aquellos números que están cubiertos tanto por líneas
horizontales como verticales
-
Volver al paso 1.