Metodo Hungaro

metodo de hungaro
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que elempleado para resolver el problema del transporte por el alto grado de degeneración quepuedenpresentar los problemas de asignación. Las fases para la aplicación del método Húngaro son:
Paso 1:
Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; sedebeconstruir una nueva matriz al restar de cada costo el costo mínimo de cada fila; encontrarpara esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir unanueva matriz(denominada matriz de costos reducidos) al restar de cada costo el costo mínimo desu columna.
Paso 2:
(En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el númeromínimo de líneas(horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, setiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. E lnúmero de líneas para cubrir los ceroses igual a la cantidad de asignaciones que hasta esemomento se pueden realizar.
Paso 3:
Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no estácubierto por las líneas dibujadas en el paso 2; a continuación se deber estar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elementode la matriz de costos reducidoscubierto por dos líneas (intersecciones). Por último se debe regresar al paso 2
Paso 4: En caso de no encontrar una solución factible con los pasos anteriores aplicar entonces este:
1) Trace el númeromínimo de lineas horizontales y verticales en la última matriz reducida que cubrirá TODAS las entradas cero.
2) Selecciones el elemento no cubierto más pequeño y réstelo de todos los elementos no...