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

El algoritmo requiere lo siguiente:

  1. Tener una matriz de costos para la asignación de "m" personas para ser asignadas a "m" tareas
  2. Todos los costos son no-negativos
  3. El problema es un problema de minimización.

Inicio.

  1. En cada fila, restar el menor costo a todos los valores de la fila
  2. En la matriz resultante, restar el menor valor en cada columna a todos los valores de la columna

Pasos Iterativos

  1. 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.
  2. Encuentre el valor más pequeño no cubierto por las líneas: ese número es el valor de reducción
  3. 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
  4. Volver al paso 1.