Metodo hungaro

METODO HUNGARO
¿Qué es?
El Método Húngaro es un problema de transporte balanceado, en el cual todas las ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente un problemade asignación m x m mediante el método Húngaro.
 
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte porel alto grado de degeneración que pueden presentar los problemas de asignación.
EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo. La primeraversión conocida del método Húngaro, fue inventado y publicado por Harold W. Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, elalgoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.
El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos Húngaros: DénesKőnig y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fuertemente polinómico (ver Complejidad computacional para más detalles).
El algoritmo húngaro construye una solución del problema primalpartiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible

¿Cómo se usa?
Paso 1: Encontrar primero el elemento más pequeño encada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. Acontinuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.
Paso 2:(En algunos pocos textos este paso se atribuye aFlood). Consiste en trazar el númeromínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que serequieren para cubrir todos los ceros en la matriz de costos reducidos; si se...