documentos

Método Húngaro[editar]
Pasos para el método húngaro
Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cadacosto el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) alrestar de cada costo el costo mínimo de su columna.
Paso 2: Consiste en trazar el número mínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todoslos ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de mlíneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar (En algunostextos este paso se atribuye a Flood).
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; acontinuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos líneas (intersecciones). Porúltimo se debe regresar al paso 2. (scrib2)
Paso 4: En caso de no encontrar una solución factible con los pasos anteriores aplicar entonces este:
1) Trace el número mínimo de lineas horizontales yverticales 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 cubiertos; después, súmelos a todos loselementos en la intersección de dos líneas.
3) Si no es posible encontrar una asignación factible entre las entradas cero resultantes, repita es paso. De lo contrario regrese al paso 3 para...