metodo hungaro

Modelado[editar]
El algoritmo modela un problema de asignación como una matriz de costes n×m, donde cada elemento representa el coste de asignar el enésimo trabajador al emésimo trabajo. Pordefecto, el algoritmo realiza la minimización de los elementos de la matriz; de ahí que en caso de ser un problema de minimización de costes, es suficiente con comenzar la eliminación de Gauss-Jordan parahacer ceros (al menos un cero por línea y por columna). Sin embargo, en caso de un problema de maximización del beneficio, el coste de la matriz necesita ser modificado para que la minimización de suselementos lleve a una maximización de los valores de coste originales. En un problema de costes infinito, el coste inicial de la matriz puede ser remodelado restando a cada elemento de cada línea elvalor máximo del elemento de esa línea (o análogamente columna ). En un problema de coste infinito, todos los elementos son restados por el valor máximo de la matriz entera. En la matriz se tiene querealizar un conjunto de operaciones que nos permitirán conocer con mejor eficacia el resultado final de la problemática planteada.

Algoritmo[editar]
(1) \, Dada la matriz de costes C \,, seconstruye C^\prime\, encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C}_{i,j}-\min \mathit{C}_{i,j}
( 2 ) \, Se encuentrael valor mínimo de cada columna y se resta a cada elemento de la columna.
\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C'}_{i,j}-\min \mathit{C}_{i,j}
(3) \, A partir de \mathit{C'}\, se considera"grafo de las igualdades" a G=(N1,N2,A) \, tal que A \, está constituido por todas las copias ({i,j})\, tales que \mathit{C'}_{i,j}=0 \,. En otras palabras, verificamos si para todas las filas existe unacolumna con costo 0 que no ha sido asignada a otra fila.
Determinar sobre G\, un matching M\, de cardinalidad máxima.


si |\mathit{M}| = |N_1| = |N_2| \Rightarrow \; STOP
Si todas las filas...