Théorie du transport

En mathématiques et en économie, la théorie du transport est le nom donné à l'étude du transfert optimal de matière et à l'allocation optimale de ressources. Le problème a été formalisé par le mathématicien français Gaspard Monge en 1781. D'importants développements ont été réalisés dans ce domaine pendant la Seconde Guerre mondiale par le mathématicien et économiste russe Léonid Kantorovitch. Par conséquent, le problème dans sa forme actuelle est parfois baptisé problème (du transport) de Monge-Kantorovitch.

Motivation

Mines et usines

Transport de minerai

On se donne un ensemble de $n$ mines d'où est extrait un minerai de fer, et un ensemble de $n$ usines utilisant ce minerai comme matière première. Ces mines et ces usines ont une certaine aire. On suppose donc pour la clarté du propos que ces mines et ces usines constituent deux sous-ensembles disjoints et limités par une courbe fermée $M$ et $F$ du plan euclidien $\mathbb {R} ^{2}$. On suppose également qu'on dispose d'une fonction, que l'on appelle le coût, à savoir $c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,+\infty [$, telle que $c(x,y)$ soit le coût de transport d'un transfert de minerai du site $x$ au site $y$. Par souci de simplicité, on ignore le temps mis lors de ce transfert. On considère également que chaque mine ne peut fournir en minerai qu'une seule usine (pas de partage de minerai durant le transfert) et que la quantité transférée doit être intégralement distribuée à une usine donnée pour que celle-ci soit opérationnelle (les usines ne peuvent fonctionner ni en sur-capacité ni en sous-capacité).

Ayant fait ces hypothèses, un plan de transport est une bijection $T:M\to F$ — c.-à-d. un arrangement où chaque mine $m\in M$ alimente précisément une usine $T(m)\in F$. On désire trouver le plan de transport optimal, le plan $T$ dont le coût total

$c(T):=\sum _{m\in M}c(m,T(m))$

est minimal vis-à-vis de tous les plans de transport possibles de $M$ vers $F$.

Déplacement de livres : l'importance du type de la fonction de coût

L'exemple suivant illustre l'importance de la fonction coût dans la détermination du plan de transport optimal. On suppose qu'on a $n$ livres d'égale épaisseur sur une étagère (la droite réelle), arrangés sans espaces entre eux. On désire les réarranger toujours sans espace entre eux, mais selon un décalage égal à l'épaisseur d'un livre sur la droite. Deux candidats pour le plan de transport optimal se présentent ainsi :

1. déplacer l'ensemble des $n$ livres (en commençant par le plus à droite) d'une distance égale à l'épaisseur d'un livre vers la droite ; (« beaucoup de petits déplacements »)
2. déplacer le livre le plus à gauche d'une distance égale à l'épaisseur de $n$ livres vers la droite et laisser les autres livres en place. (« peu de grands déplacements »)

Si la fonction de coût est proportionnelle à la distance euclidienne ($c(x,y)=\alpha \|x-y\|$) alors ces deux candidats sont tous deux optimaux. Si, au contraire, on choisit une fonction de coût strictement convexe proportionnelle au carré de la distance euclidienne ($c(x,y)=\alpha \|x-y\|^{2}$), alors l'option « beaucoup de petits déplacements » devient l'unique minimiseur.

De manière intéressante, alors que les mathématiciens préfèrent travailler avec des fonctions de coût convexes, les économistes préfèrent les concaves. La justification intuitive de ce constat est que, une fois que des biens ont été chargés, disons, sur un train de marchandises, le transport de ces biens sur une distance de 200 kilomètres coûtera bien moins que le double du coût de transport sur une distance de 100 kilomètres. Les fonctions de coûts concaves représentent cette économie d'échelle.

Histoire

La formulation de Monge

Le problème du transport optimal est formalisé pour la première fois par le mathématicien français Gaspard Monge en 1781, dans un Mémoire sur la théorie des déblais et des remblais destiné à l'Académie des Sciences. Dans cet ouvrage, il considère la question du déplacement d'une quantité de terre, appelée les déblais, vers un espace qu'ils doivent occuper après leur transport, appelé les remblais. En considérant un coût de transport proportionnel à la masse déplacée ainsi qu'à la distance parcourue, il conjecture que tous les déplacements ne résulteront pas en un même coût total. Monge affirme de plus que parmi tous ces transports possibles, il en existe un, appelé transport optimal, pour lequel le coût total sera minimum. Contrairement à ce qu'il annonce, la preuve de l'existence et de l'unicité d'un tel transport n'est pas donnée dans son mémoire. Malgré quelques avancées réalisées par le mathématicien français Charles Dupin dans un mémoire de 1822, le problème ne connaît pas de développements importants pendant presque cent ans. En 1884, l'Académie des Sciences propose un prix à quiconque obtiendra des avancées majeures sur la question du transport optimal. C'est le mathématicien français Paul Appell qui remporte 2000 des 3000 francs proposés en 1886. Il publie en 1887 un mémoire sur ses travaux, dans lesquels la question de l'existence n'est toujours pas clairement formulée ni résolue.

La relaxation de Kantorovitch

Le mathématicien et économiste russe Leonid Kantorovitch est un des inventeurs du concept d'optimisation linéaire dans les années 1930. Cette théorie le conduit à s'intéresser au problème de transport optimal. Durant la Seconde Guerre Mondiale, il propose une formulation plus générale du problème de Monge, en n'imposant pas que le transport des masses soit nécessairement décrit par une fonction, mais plutôt par une mesure appelée plan de transport. Dans ce cadre, Kantorovich parvient à obtenir l'existence et l'unicité d'un plan de transport optimal, avec des hypothèses très faibles sur le coût de transport et la répartition des masses à transporter et des espaces les accueillant. Le mathématicien russe V. N. Sudavok utilise les outils développés par son prédécesseur pour revenir au problème original de Monge, auquel il propose une solution en 1976. Le mathématicien italien Luigi Ambrosio repère et corrige une erreur fondamentale dans l'argument de Sudakov en 2003, apportant une réponse jugée satisfaisante par la communauté mathématique à la question de l'existence et de l'unicité dans le problème de Monge.

Caractérisation et régularité

Dans les années 1990, le mathématicien français Yann Brenier réalise une avancée déterminante dans la caractérisation du problème pour le coût quadratique. Sous de faibles hypothèses de régularité, il montre que le transport se fait nécessairement via une fonction de transport qui est le gradient d'une fonction convexe. Le mathématicien italien Luigi Cafferelli poursuit les travaux sur le coût quadratique et obtient en 2002 des résultats importants sur la régularité de la fonction de transport. Poussant encore plus loin l'analyse du problème de transport, Ma, Trudinger et Wang établissent des propriétés de régularité de la fonction de transport en prenant des coûts ${\mathcal {C}}^{4}$ en 2005.

Formulation abstraite du problème

Les formulations de Monge et de Kantorovitch

La forme donnée à l'énoncé du problème du transport pourra varier quelque peu dans la littérature technique moderne en fonction des développements en géométrie riemannienne et en théorie de la mesure. L'exemple mines-usines, par sa simplicité, pourra être vu comme un bon point de départ pour aborder l'étude abstraite. Dans ce cadre, on s'autorise à considérer que les mines et les usines ne sont pas toutes nécessairement ouvertes pendant les transactions, que les mines peuvent alimenter plus d'une usine, et que chaque usine peut être ravitaillée en fer par plus d'une mine.

Soit $X$ et $Y$ deux espaces métriques séparables tels que toute mesure de probabilité sur $X$ (ou sur $Y$) soit une mesure de Radon (i.e. ce sont des espaces de Radon). Soit $c:X\times Y\to [0,+\infty ]$ une fonction mesurable au sens des boréliens. Étant donné des mesures $\mu$ sur $X$ et $\nu$ sur $Y$, la formulation de Monge du problème de transport optimal est issue de la recherche du plan de transport $T:X\to Y$ qui réalise l'infimum

$\inf \left\{\left.\int _{X}c(x,T(x))\,\mathrm {d} \mu (x)\right|T_{*}(\mu )=\nu \right\},$

où $T_{*}(\mu )$ représente la mesure image de $\mu$ par $T$. Un plan $T$ qui atteint cet infimum (i. e. l'infimum doit alors être appelé minimum) est appelé un « plan de transport optimal ».

Le problème de transport optimal selon la formulation de Monge peut être mal posé (car il n'y a parfois pas de $T$ satisfaisant $T_{*}(\mu )=\nu$ : ceci se produit, par exemple, quand $\mu$ est une mesure de Dirac et que $\nu$ n'en est pas une).

On peut alors améliorer cette formulation en adoptant la formulation de Kantorovich du problème de transport optimal, qui consiste à trouver la mesure $\gamma$ sur $X\times Y$ qui atteint l'infimum

$\inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)\right|\gamma \in \Gamma (\mu ,\nu )\right\},$

où $\Gamma (\mu ,\nu )$ représente l'ensemble des mesures définies sur $X\times Y$ de marginales données par $\mu$ sur $X$ et par $\nu$ sur $Y$. On peut montrer qu'un minimiseur de ce problème existe toujours quand la fonction coût $c$ est semi-continue inférieurement et que $\Gamma (\mu ,\nu )$ est un ensemble de mesures à espérances et variances bornées (ce qui est assuré par la nature des espaces de Radon $X$ et $Y$). (Comparer cette formulation avec la définition de la métrique de Wasserstein $W_{1}$ sur l'espace des mesures de probabilité.)

Formulation duale

Le minimum du problème de Kantorovitch est égal à

$\sup \left(\int _{Y}\phi (y)\,\mathrm {d} \nu (y)-\int _{X}\psi (x)\,\mathrm {d} \mu (x)\right),$

où la borne supérieure est à prendre parmi toutes les paires de fonctions continues bornées $\phi :Y\to \mathbb {R}$ et $\psi :X\to \mathbb {R}$ telles que

$\phi (y)-\psi (x)\leq c(x,y).$

Solution du problème

Transport optimal sur la droite réelle

Pour $1\leq p<+\infty$, soit ${\mathcal {P}}_{p}(\mathbb {R} )$ l'ensemble des mesures de probabilité sur $\mathbb {R}$ de $p^{\mathrm {i{\grave {e}}me} }$ moment fini. Soient $\mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )$ et soit $c(x,y)=h(x-y)$, où $h:\mathbb {R} \to [0,+\infty )$ est une fonction convexe.

1. Si $\mu$ n'a pas d'atome, i.e., si la fonction de répartition $F_{\mu }:\mathbb {R} \to [0,1]$ de $\mu$ est une fonction continue, alors $F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R}$ est un plan de transport optimal. Ce dernier est unique si $h$ est strictement convexe.
2. On a

$\min _{\gamma \in \Gamma (\mu ,\nu )}\int _{\mathbb {R} ^{2}}c(x,y)\,\mathrm {d} \gamma (x,y)=\int _{0}^{1}c\left(F_{\mu }^{-1}(s),F_{\nu }^{-1}(s)\right)\,\mathrm {d} s.$

Dans le cas de distributions de probabilités uniformes discrètes, et pour $c(x,y)=(x-y)^{2},\$ une version très élémentaire du problème de transport optimal est l'inégalité de réarrangement.

Espaces de Hilbert séparables

Soit $X$ un espace de Hilbert séparable. Soit ${\mathcal {P}}_{p}(X)$ l'ensemble des mesures de probabilité sur $X$ de $p^{\mathrm {i{\grave {e}}me} }$ moment fini ; soit ${\mathcal {P}}_{p}^{r}(X)$ les $\mu \in {\mathcal {P}}_{p}(X)$ qui sont réguliers au sens gaussien : pour toute mesure gaussienne $g$ strictement positive sur $X$ avec $g(N)=0$, alors $\mu (N)=0$ aussi.

Soit $\mu \in {\mathcal {P}}_{p}^{r}(x)$, $\nu \in {\mathcal {P}}_{p}(X)$, $c(x,y)=|x-y|^{p}/p$ pour $p\in (1,+\infty )$, $p^{-1}+q^{-1}=1$. Alors le problème de Kantorovitch a une solution unique $\kappa$, et cette solution est induite par le plan de transport optimal : i.e., il existe une carte $r\in L^{p}(X,\mu ;X)$ au sens de Borel telle que

$\kappa =(\mathrm {id} _{X}\times r)_{*}(\mu )\in \Gamma (\mu ,\nu ).$

De surcroît, si $\nu$ est à support borné, alors

$r(x)=x-x|\nabla \phi (x)|^{q-2}\nabla \phi (x)$ pour $\mu$-presque tout $x\in X$

pour un certain potentiel maximal de Kantorovitch $\phi$ localement lipschitzien et $c$-concave. (Ici $\nabla \phi$ représente la dérivée de Gateaux de $\phi$.)

Régularisation entropique

En pratique, on considère souvent une variante du problème du transport optimal, faisant intervenir un terme de régularisation entropique, celle-ci étant plus simple à résoudre numériquement. Le nouveau problème s'écrit alors, pour un certain $\varepsilon >0$ donné :

$\inf \left\{\left.\int _{X\times Y}c(x,y)\,\mathrm {d} \gamma (x,y)+\varepsilon \mathrm {KL} (\gamma |\mu \otimes \nu )\ \right|\ \gamma \in \Gamma (\mu ,\nu )\right\},$

où $\mathrm {KL} (\gamma |\mu \otimes \nu )=\int _{X\times Y}\log \left({\frac {d\gamma }{d\ \mu \!\otimes \!\nu }}\right)d\gamma$ est la divergence de Kullback-Leibler, aussi appelée entropie relative, du fait de son lien avec l'entropie de Shannon. Ce problème peut alors être résolu par l'algorithme de Sinkhorn.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Transportation theory » (voir la liste des auteurs).

Liens internes

• Problème du flot de coût minimum

Liens externes

• (fr) [PDF] Cédric Villani, « Transport optimal de mesure : coup de neuf pour un très vieux problème », Images des mathématiques, 2004, pp. 114-119.
• (fr) [html] Yann Brenier, « La brouette de Monge ou le transport optimal », Interstices, 2007.
• (en) [PDF] Gabriel Peyré, Marco Cuturi, « Computational Optimal Transport», , 2019.
• (fr) Étienne Ghys, « Gaspard Monge : Le mémoire sur les déblais et les remblais », Images des mathématiques,‎ 20 janvier 2012 (lire en ligne)