Trois usines, quatre clients, et la question de savoir qui livre qui.
Trois usines produisent le même bien et doivent approvisionner quatre clients. Chaque usine a une capacité, chaque client une demande, et acheminer une tonne de l'usine i au client j coûte cij. Il faut décider des quantités xij qui vident les usines, servent tous les clients, et minimisent la facture totale.
minimiser Σij cij xij sous Σj xij = ai Σi xij = bj xij ≥ 0
C'est un programme linéaire, mais d'une espèce si particulière qu'on ne lui applique jamais le simplexe général : sa structure permet de tout faire à la main, dans un tableau, avec des additions et des soustractions. Cette page suit cette voie — construire une première solution, la corriger jusqu'à l'optimum, lire les prix cachés qu'elle révèle — puis se termine sur un fait que le bon sens refuse : il arrive très souvent qu'expédier davantage de marchandise coûte moins cher.
Tout tient dans un tableau à trois lignes et quatre colonnes : dans chaque case, le coût unitaire en petit, la quantité expédiée en grand. Les marges portent les capacités et les demandes. Une solution est admissible si chaque ligne totalise sa capacité et chaque colonne sa demande. Trois méthodes classiques en fabriquent une, de la plus bête à la plus fine.
Le coin nord-ouest ne regarde même pas les coûts : il remplit mécaniquement de haut en gauche. La méthode du coût minimum sert d'abord les cases les moins chères. Celle de Vogel, la plus subtile, calcule pour chaque ligne et chaque colonne la pénalité — l'écart entre les deux coûts les plus bas — et sert en priorité celle qui aurait le plus à perdre si on la servait mal. Elle tombe souvent directement sur l'optimum.
Une solution admissible étant donnée, comment savoir si elle est la meilleure ? On attribue à chaque usine un potentiel ui et à chaque client un potentiel vj, choisis pour que ui + vj = cij sur toutes les cases utilisées. Le coût réduit d'une case vide vaut alors
dij = cij − ui − vj
et donne exactement ce que coûterait — ou rapporterait — le fait d'y faire passer une unité, une fois répercutés tous les rééquilibrages nécessaires. S'il est négatif quelque part, on y envoie de la marchandise en suivant l'unique circuit qui referme le tableau, alternant additions et soustractions. Quand tous les coûts réduits sont positifs, c'est fini.
Les ui et vj ne sont pas un artifice de calcul : ce sont les variables du problème dual, et elles ont un sens économique précis. ui est ce que vaut une tonne de capacité supplémentaire à l'usine i, vj ce que coûte une tonne de demande supplémentaire chez le client j. La somme des deux donne exactement la variation du coût total lorsqu'on augmente d'une unité à la fois l'usine i et le client j.
Le tableau ci-dessus affiche en petit, dans chaque case vide, son coût réduit. Les cases utilisées sont celles où il vaut zéro : c'est la définition même des potentiels. Une case dont le coût réduit est élevé est une liaison qu'il ne faudrait ouvrir sous aucun prétexte, même si son coût brut paraît modeste — ce qui compte n'est jamais le coût seul, mais le coût relativement aux prix implicites du réseau.
Trois complications surgissent dans la pratique, et toutes trois se règlent sans changer de méthode. Si l'offre dépasse la demande, on invente un client fictif à coût nul qui absorbe le surplus : la quantité qu'il reçoit indique quelle usine restera en sous-charge. Si une liaison est impossible, on lui donne un coût prohibitif. Et si une solution occupe moins de m + n − 1 cases, elle est dégénérée : les potentiels ne se calculent plus, et il faut occuper une case supplémentaire avec une quantité nulle pour rétablir l'arbre.
Le dernier contrôle n'est pas anodin. On n'impose nulle part que les xij soient entiers, et pourtant ils le sont toujours dès que les capacités et les demandes le sont. C'est une conséquence de la totale unimodularité de la matrice des contraintes : ici, la relaxation continue d'un problème en nombres entiers ne coûte rien du tout, ce qui est l'exception et non la règle.
Voici le fait que le tableau révèle et que l'intuition rejette. Si pour un couple (usine, client) la somme ui + vj est négative, alors augmenter simultanément la capacité de cette usine et la demande de ce client fait baisser la facture totale : on transporte davantage de marchandise et l'on paie moins cher. Ce n'est pas une erreur de calcul — c'est la lecture directe de la formule de la planche 3, valable tant que la structure de la solution optimale ne change pas. Le graphique ci-dessous confronte cette prédiction, en pointillés, au coût réellement recalculé : les deux coïncident jusqu'à la rupture, au-delà de laquelle le raisonnement ne s'applique plus et le coût finit par remonter.
On présente souvent ce paradoxe comme une bizarrerie de manuel. Il n'en est rien. Le bouton ci-dessous tire des instances au hasard et compte celles où il se produit — c'est-à-dire celles où l'on peut acheminer plus de marchandise pour une facture inférieure.
L'explication tient en une phrase : le problème équilibré force à écouler exactement l'offre, même vers des clients coûteux à servir. Ouvrir un débouché bon marché supplémentaire permet de réorganiser toute la desserte, et l'économie sur les réacheminements l'emporte sur le coût du transport ajouté. La morale est de méthode : dans un réseau, une contrainte d'égalité n'est jamais innocente, et il faut toujours se demander si l'on a intérêt à la desserrer.