Algorithme hongrois

Contenus

Aussi appelé algorithme de Kühn, l’algorithme hongrois, ou méthode hongroise résout des problèmes d’affectation de type table de coûts. Considérons un certain nombre de machines et autant de tâches. Chaque machine exécute une tâche à un certain coût. L’objectif est de déterminer la machine sur laquelle s’exécutera chaque tâche, en parallèle.

Ce problème étant similaire à un problème de couplage dans un graphe, il répond au critère de König pour la couverture nodale de poids minimum. L’objectif est donc de trouver un élément par ligne et colonne dans la table telle que la somme des coûts soit minimale. Si l’on part d’un problème de maximisation, il faudra inverser les coûts afin de retomber sur un problème de minimisation.

Prenons un exemple simple afin de montrer le processus de l’algorithme. Soient 5 machines (ligne) et 5 tâches (colonne) donnant la table de coûts suivants :

17	15	9	5	12
16	16	10	5	10
12	15	14	11	5
4	8	14	17	13
13	9	8	12	17

Étape 1 algorithme hongrois : réduction du tableau initial

On soustrait à chaque ligne le plus petit élément de la ligne. Plus on soustrait à chaque colonne le plus petit élément de la colonne.

12	9	4	0	7
11	10	5	0	5
7	9	9	6	0
0	3	10	13	9
5	0	0	4	9

Cette normalisation des coûts machines et des tâches permet d’avoir au moins un zéro par ligne et par colonne.

Étape 2 algorithme hongrois : rechercher une solution réalisable

On cherche la ligne comportant le moins de zéros non barrés. En cas d’égalité on prendra la ligne la plus haute.

On encadre un des zéros de cette ligne (arbitrairement celui le plus à gauche).
On barre tous les zéros se trouvant sur la même ligne et colonne que celui sélectionné.
On recommence jusqu’à ce que tous les zéros sont encadrés ou barrés.

Si on a encadré un zéro par ligne et par colonne, nous avons une solution optimale. Sinon on passe à l’étape 3.

12	9	4	0	7
11	10	5	-0-	5
7	9	9	6	0
0	3	10	13	9
5	0	-0-	4	9

Étape 3 algorithme hongrois : création des pivots

Le sous-tableau permet par retranchement de posséder une configuration permettant de trouver une solution optimale. La construction des pivots se fait ainsi :

On marque toute ligne ne contenant aucun zéro encadré.
On marque toute colonne ayant un zéro barré sur une ligne marquée.
On marque toute ligne ayant un zéro encadré dans une colonne marquée.
Répéter 2 et 3 jusqu’à ne plus avoir de modification.

On trace alors un trait sur toute ligne non marquée et sur toute colonne marquée. Dans notre exemple, la ligne 1 et 2 sont marqués, ainsi que la colonne 4. Les éléments deux fois marqués sont accompagnés d’une étoile.

12	9	4	-0-	7
11	10	5	-0-	5
-7-	-9-	-9-	-6-	-0-
-0-	-3-	-10-	-13-	-9-
-5-	-0-	-0-	-4-	-9-

Étape 4 algorithme hongrois : modification du tableau

Les cases non traversées par un trait constituent un tableau partiel.

On retranche à toutes les cases de ce tableau le plus petit élément de celui-ci.
On ajoute cet élément à toutes les cases du tableau barrées dans les deux sens (accompagnées d’une étoile).

On recommence les étapes 2 à 4 jusqu’à obtenir un résultat optimal. Dans notre exemple, nous obtenons un résultat optimal après la première itération.

8	5	0	0	3
7	6	1	0	1
7	9	9	10	0
0	3	10	17	9
5	0	0	8	9

L’affectation minimale se calcule à partir du tableau initial : 9+5+5+4+9 = 32.

La figure suivante montre les changements dans le graphe bipartie avec l’algorithme hongrois.