Comment ça marche, précisément
Chaque personne classe les options. Un vœu de rang 1 coûte 1, de rang 2 coûte 2, et ainsi de suite : la matrice des coûts est construite.
On cherche l'affectation qui minimise le coût TOTAL, en explorant toutes les combinaisons possibles de manière intelligente — jamais une à une, ce qui serait hors de portée.
Conséquence importante : le calcul peut sacrifier une personne pour en soulager plusieurs. L'optimum est collectif, et c'est exactement ce qu'on lui demande.
Un exemple chiffré
Trois personnes, trois missions. Les cases donnent le rang du vœu.
| Audit | Refonte | Support | |
|---|---|---|---|
| Chloé | 1 | 2 | 3 |
| Ali | 1 | 3 | 2 |
| Bruno | 2 | 1 | 3 |
- Servir tout le monde en premier vœu est impossible : Chloé et Ali visent Audit.
- Chloé→Audit, Bruno→Refonte, Ali→Support : coût total 1 + 1 + 2 = 4.
- Ali→Audit, Bruno→Refonte, Chloé→Support : coût total 1 + 1 + 3 = 5.
La première combinaison est retenue : à qualité de vœux comparable, elle coûte moins cher au groupe. Aucun autre arrangement ne fait mieux que 4.
D'où ça vient
C'est le « problème d'affectation », l'un des classiques de la recherche opérationnelle. Harold Kuhn en publie en 1955 une solution efficace qu'il baptise « algorithme hongrois », en hommage aux travaux des mathématiciens hongrois Dénes Kőnig et Jenő Egerváry dont il s'inspire.
On découvrira plus tard que Carl Gustav Jacobi avait résolu le problème au XIXᵉ siècle, dans des travaux publiés à titre posthume en 1890 — soit soixante-cinq ans avant sa redécouverte.
L'algorithme est aujourd'hui un outil industriel banal : affectation d'équipages à des vols, de tâches à des machines, de véhicules à des courses. Toute application qui apparie deux ensembles en optimisant un coût total en est l'héritière.
Où on s'en sert
- Répartir des missions ou des dossiers dans une équipe en maximisant la satisfaction globale.
- Affecter des élèves à des ateliers, des options ou des projets.
- Attribuer des créneaux de garde ou des astreintes.
- Planifier des équipages, des tournées ou des machines — l'usage industriel historique.
Limites et pièges
- La meilleure satisfaction totale possible
- Aucun tirage au sort
- Résultat exact, pas approché
- Peut sacrifier une personne pour le bien commun
- Classements tactiques possibles
- Moins intuitif à raconter
Questions fréquentes
En quoi est-ce mieux que le tour de choix ?
En moyenne, le groupe est plus satisfait : l'algorithme voit toutes les combinaisons d'un coup, là où le tour de choix subit l'ordre de passage. Le prix à payer est la lisibilité — et la possibilité de mentir.
Que se passe-t-il en cas d'égalité entre deux affectations ?
Plusieurs solutions peuvent atteindre le même coût minimal ; l'une est retenue. Si l'enjeu est fort, annoncez à l'avance la règle de départage, ou passez au tour de choix, dont la mécanique est reproductible.
Faut-il autant de places que de personnes ?
Non, mais l'écart se paie : s'il manque des places, quelqu'un ne sera pas affecté ; s'il y en a trop, certaines resteront vides. Le calcul reste valide dans les deux cas.
Sources
Les références primaires sur lesquelles s'appuie cette fiche.
- Kuhn, Harold W., The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly, 2(1-2), 83-97, 1955. DOI ↗
- Munkres, James, Algorithms for the Assignment and Transportation Problems, Journal of the Society for Industrial and Applied Mathematics, 5(1), 32-38, 1957. DOI ↗
- Jacobi, Carl Gustav Jacob, De investigando ordine systematis aequationum differentialium vulgarium cujuscunque, Journal für die reine und angewandte Mathematik (Crelle), 64, 297-320 — publication posthume ; repris dans les Gesammelte Werke, vol. V, Berlin, 1890, 1865. DOI ↗
- Burkard, Rainer, Dell'Amico, Mauro et Martello, Silvano, Assignment Problems, SIAM, Philadelphie, 2009.