Il s'agit de l'algorithme Hongrois proposé par Kuhn.
Il s'agit d'une matrice carré, là où les valeurs infinies restent inchangées.
L'algorithme procède en trois étapes successives.
1- éliminer le plus petit élément de chacune des colonnes puis celui de chacune des lignes de la matrice des coûts.
2- Si, cette solution n'est pas optimale, on considère la ligne ayant un nombre minimal de zéros. On encadre l'un des zéros de cette ligne, puis on barre les zéros qui se trouvent sur la même ligne ou la même colonne que le zéro encadré. On procède de même pour toutes les lignes.
3- On marque toutes les lignes qui ne contiennent aucun zéro encadré
On marque les lignes qui ont un zéro encadré dans une colonne marqué
On marque les colonnes qui ont un ou plusieurs zéros barrés dans une ligne marquée.
On répète ces trois marquages successifs jusqu'à ce que l'on ne puisse plus affecter de nouveaux marquages.
On barre ensuite, les lignes non marquées ainsi que les colonnes marquées.
Dans le tableau réduit obtenu, on retranche la valeur de l'élément le plus petit aux colonnes non barrées et on l'ajoute aux lignes barrées.
On poursuit la procédure de traitement sur la matrice résultante en reprenant à la seconde phase jusqu'à l'obtention d'une solution optimale.