Cinq techniciens, cinq chantiers, et une seule bonne façon de les apparier.
Une entreprise doit envoyer cinq techniciens sur cinq chantiers, un par chantier. Chaque couple (technicien, chantier) a un coût — heures de trajet, matériel à déplacer, compétence plus ou moins adaptée. Il faut apparier de façon à minimiser le total. C'est le problème d'affectation, et c'est le même quand il s'agit de machines et de travaux, de camions et de tournées, ou d'internes et d'hôpitaux.
minimiser Σij cij xij sous Σj xij = 1 Σi xij = 1 xij ∈ {0, 1}
C'est un cas particulier du problème de transport où toutes les offres et toutes les demandes valent 1 — mais il possède un algorithme propre, la méthode hongroise de Kuhn et Munkres (1955), qui travaille uniquement par soustractions dans le tableau et donne l'optimum en temps cubique là où l'énumération demanderait n! essais. Les planches qui suivent la démontent entièrement, puis s'achèvent sur un fait remarquable : quand les coûts sont tirés au hasard, le coût optimal converge vers une constante universelle, et l'on connaît sa valeur exacte à chaque taille.
Une affectation est une permutation : chaque ligne choisit une colonne, et deux lignes ne choisissent jamais la même. Il y en a n! — 120 pour cinq techniciens, mais déjà 3,6 millions pour dix et 2,4·1018 pour vingt. La méthode qui vient à l'esprit — prendre la case la moins chère, barrer sa ligne et sa colonne, recommencer — est rapide et régulièrement mauvaise.
L'idée fondatrice est d'une simplicité désarmante : retrancher une constante à toute une ligne ne change pas la solution optimale, puisque chaque affectation prend exactement une case par ligne. On peut donc soustraire à chaque ligne son minimum, puis à chaque colonne le sien, sans rien perdre — et le tableau se remplit de zéros. Si l'on parvient à choisir n zéros sans deux dans la même ligne ni la même colonne, ils forment l'affectation optimale : elle coûte zéro dans le tableau réduit, donc le minimum possible.
Quand on n'y parvient pas, c'est qu'un petit nombre de lignes et de colonnes suffit à couvrir tous les zéros. On retranche alors le plus petit terme non couvert à toutes les cases non couvertes et on l'ajoute aux cases doublement couvertes : de nouveaux zéros apparaissent, et l'on recommence.
La lecture décisive est celle de la dernière ligne des relevés : le total de tout ce qu'on a retranché au fil de l'algorithme est exactement égal au coût optimal. Ce n'est pas une coïncidence — ces réductions sont les variables du problème dual, et leur somme est la valeur duale, qui par dualité forte égale la valeur primale.
Au cœur de la méthode se cache un résultat de théorie des graphes bien antérieur. Représentons les zéros du tableau par un graphe biparti : une arête entre le technicien i et le chantier j si la case (i,j) est nulle. Chercher n zéros indépendants, c'est chercher un couplage ; chercher le plus petit nombre de lignes et de colonnes qui couvrent tous les zéros, c'est chercher une couverture par sommets. Le théorème de König (1931) affirme que dans un graphe biparti, ces deux nombres sont toujours égaux.
Toutes les situations réelles s'y ramènent par une simple manipulation du tableau. Plus de techniciens que de chantiers : on ajoute des chantiers fictifs à coût nul, et ceux qui y sont affectés restent disponibles. Une affectation impossible : on lui met un coût prohibitif. Un problème de maximisation — des profits plutôt que des coûts : on remplace chaque case par son écart au maximum. Enfin, si l'on veut non pas minimiser la somme mais le pire des coûts individuels, c'est l'affectation goulot, qui se résout par dichotomie sur un seuil — et qui donne, elle, une tout autre solution.
La dernière ligne mérite qu'on s'y arrête. Minimiser la somme et minimiser le pire ne sont pas deux façons de dire la même chose : sur cette matrice, imposer qu'aucun technicien ne dépasse un certain seuil oblige à sacrifier lourdement le total. C'est le même arbitrage qu'entre efficacité et équité — celui qu'on optimise décide de la solution, et il n'y a pas de choix neutre.
Remplissons le tableau au hasard, avec des coûts indépendants tirés d'une loi exponentielle de moyenne 1, et calculons l'optimum. On pourrait croire ce coût imprévisible ; il ne l'est pas. Giorgio Parisi a conjecturé en 1998, et l'on a démontré en 2005, que sa valeur moyenne vaut exactement, pour toute taille n :
E[Cn] = 1 + 1/4 + 1/9 + ⋯ + 1/n² → π²/6 = 1,644934…
Pas d'approximation, pas de terme correctif : une somme finie, exacte à chaque n. Que le coût d'un problème d'optimisation combinatoire admette une formule aussi limpide est extrêmement rare, et le mécanisme en est encore mal compris. Les points bleus sont des moyennes de simulations, la courbe rouge est la formule.
Les coûts uniformes donnent une courbe plus basse à taille finie, mais elle rejoint la même limite : seule compte la densité de la loi au voisinage de zéro, et une uniforme y ressemble à une exponentielle. C'est le signe que 1,644934 ne dépend ni de la loi choisie, ni de rien d'autre que la structure du problème — d'où le mot d'universalité.