Sciences

La redécouverte : Leonid Kantorovich

Dossier - Maths : transport au moindre coût
DossierClassé sous :Mathématiques , transport optimal , économie

-

Originellement concu au dix-huitième siècle comme un problème d'ingénierie, le transport optimal se retrouve maintenant au coeur de diverses questions de mathématiques fondamentales et de physique théorique. En suivant quelques-unes de ses péregrinations, nous verrons comment la magie des mathématiques peut s'approprier, mélanger et métamorphoser des sujets venus d'horizons divers.

  
DossiersMaths : transport au moindre coût
 

Leonid Kantorovich (1912-1986) est un mathématicien russe de renom. Sa vie présente plusieurs points communs avec celle de Monge : tous deux sont devenus professeurs à un âge remarquablement précoce.

Tous deux ont eu à s'opposer aux autorités politiques de leur temps et ont vu certains de leurs travaux frappés par le secret défense ; tous deux étaient de brillants théoriciens très intéressés par les applications pratiques et l'organisation de la société, à tel point que Kantorovich recevra en 1975 le Prix Nobel d'économie pour ses travaux sur le partage des ressources !

 Portrait de Kantorovich. © Domaine public

Des travaux qui sont directement en rapport avec le problème de transport optimal... Une entreprise l'ayant consulté pour améliorer son organisation interne, Kantorovich redécouvre à cette occasion (sans le savoir) le problème de coût minimum posé par Monge. Il introduit alors deux avancées fondamentales :

- il reformule le transport optimal comme un problème linéaire,

- il introduit un problème dual, qui aura des répercussions fondamentales aussi bien en mathématiques qu'en économie.

Qu'entend-on par problème linéaire ? Pour caricaturer, dans l'approche de Kantorovich on minimise la quantité

où x est le point de départ, et y le point d'arrivée ; à comparer à
comme faisait Monge. Supposons que les unités de production sont encodées par des nombres a1,... aN(pour reprendre notre analogie précédente, aiest la quantité de croissants que produit la boulangerie Bi) et les unités de consommation par des nombres b1,... bm (bj est la quantité de croissants consommés dans le café Cj). Alors l'inconnue dans le problème de Kantorovich est une matrice (pij)où chaque pij représente la quantité de croissants produite en i et acheminée en j.  Bien sûr on doit avoir d'une part :

et le problème consiste à minimiser le coût total

où cij est le coût de transport d'un panier de croissants Bide la boulangerie au café Cj.

L'observation cruciale de Kantorovich est que les équations (1) et (2), ainsi que la quantité à minimiser (3), sont des fonctions "linéaires'' des inconnues pij! Plus précisément, si (pij) et (p'ij)sont deux solutions (deux façons différentes de réaliser le transport au moindre coût), alors la demi-somme (pij +p'ij)/2 sera également solution.

Kantorovich comprend que de nombreux problèmes importants présentent cette même structure, et développe des méthodes efficaces pour les résoudre : c'est la naissance de la programmation linéaire, qui joue aujourd'hui un rôle vital en algorithmique.

La dualité de Kantorovich est également la manifestation de cette structure linéaire. Pour l'expliquer, je vais continuer l'analogie dans la même veine que précédemment: vous faites tourner votre affaire de croissants, boulangeries et cafés, quand un jour se présente un entrepreneur qui vous propose de lui sous-traiter le problème du transport. Ne vous inquiétez pas, vous dit-il, vous me donnerez simplement tous les chiffres de production et de consommation, et je me chargerai de votre transport. Je viendrai acheter la marchandise aux boulangeries, je la revendrai aux cafés. Et pas d'embrouille : le prix que je demanderai à l'arrivée ne sera jamais plus élevé que la somme du prix d'achat et du prix de transport ! vous avez donc intérêt à me laisser carte blanche.>>

Bien entendu, vous acceptez le marché: vous êtes forcément gagnant. Le problème de l'entrepreneur, maintenant, est de fixer des prix appropriés. Il doit respecter sa promesse (la différence entre prix de vente et prix d'achat ne doit jamais excéder le coût du transport), mais en même temps son intérêt est de fixer les prix les plus élevés possibles ; ou plus précisément, de fixer les prix de façon à obtenir un profit maximal.

Nous avons donc un nouveau problème d'optimisation : les inconnues sont des prix u1, u2, ... (ui est le prix d'achat à la boulangerie Bi) ; et des prix v1,v2,...  (vjest le prix de vente au café Cj). La contrainte est :

(le prix d'arrivée n'excède jamais la somme du prix d'achat et du prix de transport), et le problème est de maximiser le "profit'':

Le théorème de Kantorovich énonce que le résultat est le même que celui du transport optimal ! Avec les notations ci-dessus,


Autrement dit, l'intermédiaire peut se débrouiller pour empocher exactement la somme que vous auriez dépensée en faisant le transport vous-même!

Pour les lecteurs avertis : Le théorème de dualité de Kantorovich, énonce de manière plus précise, stipule que sous des hypothèses ad hoc (très générales),

où c (x,y) est le coût de transport entre x et y, 

(x) et 
 (y) les prix d'achat et de vente en x et y respectivement ; µ est v sont deux mesures de probabilité  représentant  les distributions initiale et finale ; π (dx dy) est une mesure de probabilité jointe dont les marginales sont égales à µ(dx) et v(dy) respectivement ; et
,
 sont liées par la contrainte
 (en tout x et en tout y).

Les contributions de Kantorovich sonnent le début d'une ère prospère pour le transport optimal. Pendant des décennies, il sera utilisé avec succès par des économistes, statisticiens, probabilistes, ... avec le  théorème de dualité de Kantorovich en chef d'orchestre.