METODO HUNGARO

 

MÉTODO HÚNGARO

El método Húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros. El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente.

Es importante resaltar que el método húngaro trabaja en una matriz de costos n*m (en este caso conocida como matriz m*m, dado que el número de filas es igual al número de columnas n = m).

Para resolver problemas de asignación, aplicando el método Húngaro, se requiere seguir los siguientes algoritmos o pasos:

Paso 1

En la matriz original de costo, identificar el mínimo de cada renglón y restarlo de todos los elementos del renglón.

Paso 2

En la matriz que resulte del paso 1, identificar el mínimo de cada columna, y restarlo de todos los elementos de la columna.

 

• Paso 2.1

  Si no se puede asegurar una asignación factible (con todos los elementos cero) con los pasos 1 y 2,

  a). Trazar la cantidad mínima de líneas horizontales y verticales en la última matriz reducida que cubran todos los elementos cero.
  b). Seleccionar el elemento mínimo no cubierto, restarlo de todo elemento no cubierto y a continuación sumarlo a todo elemento en la intersección de dos líneas.
  c). Si no se puede encontrar una asignación factible entre los elementos cero que resulten, repetir el paso 2.1. En caso contrario, seguir en el paso 3 para determinar la asignación óptima.

 

Paso 3

Identificar la solución óptima como la asignación factible asociada con los elementos cero de la matriz obtenida en el paso 2.