Théorie des transports (mathématiques)

mathématiques et en économie, la théorie des transports désigne l'étude du transport optimal et de l'allocation des ressources . Ce problème a été formalisé par le mathématicien français Gaspard Monge en 1781.

Dans les années 1920, A.N. Tolstoï fut l'un des premiers à étudier mathématiquement le problème du transport . En 1930, dans le recueil « Planification des transports, volume I » du Commissariat national aux transports de l'Union soviétique, il publia un article intitulé « Méthodes de recherche du kilométrage minimal dans le transport de marchandises dans l'espace ».

Des avancées majeures ont été réalisées dans ce domaine pendant la Seconde Guerre mondiale par le mathématicien et économiste soviétique Leonid Kantorovich . Par conséquent, le problème, tel qu'il est formulé, est parfois appelé problème de transport de Monge-Kantorovich . La formulation de ce problème en programmation linéaire est également connue sous le nom de problème de transport de Hitchcock - Koopmans .

Deux distributions unidimensionnelles

et, tracé sur le et On peut se représenter les deux distributions comme deux tas de terre, l'un avant le déplacement, l'autre après. La carte thermique au centre représente un plan de transport et indique la destination de chaque atome de terre.

Supposons que nous ayons une collection de $des mines d'extraction de minerai de fer et une collection dedes usines qui utilisent le minerai de fer produit par les mines. Supposons, pour les besoins de la démonstration, que ces mines et ces usines forment deux sous-ensembles disjoints.etdu plan euclidienSupposons également que nous ayons une fonction de coût, de sorte queest le coût du transport d'un chargement de fer depuisàPar souci de simplification, nous négligeons le temps de transport. Nous supposons également que chaque mine ne peut approvisionner qu'une seule usine (pas de fractionnement des livraisons) et que chaque usine nécessite une livraison complète pour fonctionner (les usines ne peuvent pas fonctionner à mi-capacité ni à double capacité). Ces hypothèses étant posées, un plan de transport est une bijection.Autrement dit, chaque minefournit précisément une usine cibleChaque usine est approvisionnée par une seule mine. Nous souhaitons trouver le plan de transport optimal .dont le coût total$

est le moins coûteux de tous les plans de transport possibles depuis $à Ce cas particulier motivant du problème de transport est une instance du problème d'affectation . Plus précisément, il équivaut à trouver un couplage de poids minimal dans un graphe biparti .$

Ce résultat peut être généralisé au cas continu, où il existe une infinité de mines et d'usines réparties sur la droite réelle, ou plus généralement dans tout espace métrique. Ce cas est généralement représenté comme « modifier la forme d'un tas de terre », et est ainsi appelé le problème du terrassier .

Déplacer des livres : l'importance de la fonction de coût

L'exemple simple suivant illustre l'importance de la fonction de coût dans la détermination du plan de transport optimal. Supposons que nous ayons $Des livres de largeur égale sont disposés en bloc sur une étagère (la ligne réelle). On souhaite les réorganiser en un autre bloc contigu, décalé d'une largeur de livre vers la droite. Deux solutions de transport optimales se présentent :$

déplacer tout $livres d'une largeur de livre vers la droite (« de nombreux petits mouvements ») ;$
déplacer le livre le plus à gauche $Déplacez les livres de largeur à droite et laissez tous les autres livres fixes (« un grand mouvement »).$

Si la fonction de coût est proportionnelle à la distance euclidienne ( $0 α > 0$

Il est important de noter que les fonctions de coût mentionnées ci-dessus ne prennent en compte que la distance horizontale parcourue par les livres, et non celle parcourue par le dispositif servant à les déplacer. Si l'on considère cette dernière, alors, parmi les deux options de transport, la seconde est toujours optimale pour la distance euclidienne, tandis que, s'il y a au moins trois livres, la première option est optimale pour le carré de la distance euclidienne.

Problème d'Hitchcock

La formulation suivante du problème de transport est attribuée à FL Hitchcock :

Supposons qu'il y ait

sources pour une matière première, avec unités d'approvisionnement à et éviers pour cette matière première, avec la demande à . Si est le coût unitaire de l'expédition depuis à Il s'agit de trouver un flux qui satisfait la demande à partir des approvisionnements tout en minimisant les coûts de ce flux. Ce défi logistique a été abordé par D.R. Fulkerson et présenté dans l'ouvrage *Flows in Networks * (1962), écrit en collaboration avec L.R. Ford Jr.

On attribue également à Tjalling Koopmans des formulations en matière d'économie des transports et d'allocation des ressources.

Formulation abstraite du problème

formulations de Monge et Kantorovich

Le problème du transport, tel qu'il est formulé dans la littérature moderne ou plus technique, présente des aspects quelque peu différents du fait du développement de la géométrie riemannienne et de la théorie de la mesure . L'exemple des mines et des usines, aussi simple soit-il, constitue un point de repère utile pour aborder le cas abstrait. Dans ce cadre, on admet la possibilité de ne pas maintenir toutes les mines et usines en activité, et l'on autorise les mines à approvisionner plusieurs usines, et les usines à recevoir du fer provenant de plusieurs mines.

Laisser $et soient deux espaces métriques séparables tels que toute mesure de probabilité sur (ou) est une mesure de Radon (c'est-à-dire qu'il s'agit d'espaces de Radon). Soit une fonction mesurable au sens de Borel . Étant donné des mesures de probabilité sur et sur La formulation de Monge du problème de transport optimal consiste à trouver une carte de transport qui réalise l' infimum$

où $désigne la poussée vers l'avant de par Une carte celle qui atteint cet infimum (c'est- à-dire qui en fait un minimum au lieu d'un infimum) est appelée « carte de transport optimale ».$

La formulation du problème de transport optimal par Monge peut être mal posée, car il arrive parfois qu'il n'y ait pas de solution. $satisfaisant Cela se produit, par exemple, lorsque est une mesure de Dirac mais Non.$

Nous pouvons améliorer cela en adoptant la formulation de Kantorovich du problème de transport optimal, qui consiste à trouver une mesure de probabilité $sur qui atteint l'infimum$

où $désigne l'ensemble de toutes les mesures de probabilité sur avec des marginaux sur et sur .$

dualité des coûts

Étant donné une fonction de coût $, elle produit une transformation de dualité défini par Cela généralise la transformation de Legendre, ce qui est le cas où avec un panneau retourné.$

$.$

On dit qu'une fonction $est c -convexe si pour certains Notez que parce que, nous pouvons toujours supposer que est c -convexe. La c -convexification d'une fonction est . De manière équivalente, il s'agit de la plus petite fonction c -convexe tel que point par point. Comme dans le cas de la transformation convexe, est c -convexe si et seulement si .$

Si $est c -convexe, alors l'ensemble des c -sous-différentiels de à est l'ensemble de tel que De même pour .$

Quand $, le graphique peut être construit comme suit : Prenez le graphe de et retournez-le. À chaque étape, construire un graphe de a culminé à . C'est-à-dire, il s'agit du graphique de On obtient ainsi un ensemble complet de tels graphes. Leur enveloppe inférieure est le graphe de .$

Sur la même image, nous pouvons voir ce que cela signifie pour une fonction $Une graphe est c - convexe si et seulement si son graphe entier peut être « touché » par un « outil incliné » en mouvement et à géométrie variable. Lorsque l'outil incliné est à, elle a la forme de et est élevé à une hauteur de Le graphique de la c -convexification est construit en exécutant l'outil incliné de manière à ce qu'il soit abaissé autant que possible, tout en restant en contact avec le graphique de du côté supérieur. L'enveloppe inférieure balayée par l'outil pointu est le graphique de .$

Par exemple, si $est un espace métrique et, alors Une fonction est c -convexe si et seulement si elle est 1- lipschitzienne . Cette propriété est utilisée dans la définition de la distance 1-Wasserstein ., alors est c -convexe si et seulement si son graphe pourrait être touché par le haut par un outil pointu ayant la forme d'un paraboloïde .$

Existence et unicité

Sous des hypothèses relativement permissives, un plan de transport optimal existe.

Si
$sont des espaces de probabilité polonais,$
$est semi-continue inférieurement,$
et il existe certaines fonctions semi-continues supérieures $de type tel que,$
alors il existe un plan de transport optimal . C'est-à-dire, il existe $de sorte qu'elle atteigne l'infimum.$

Notez que l'infimum pourrait être infini si tous les plans de transport s'avéraient être infinis. Par exemple, si $est la distribution de Cauchy, et .$

Si
$sont des espaces de probabilité polonais,$
$est semi-continue inférieurement,$
il existe certaines fonctions semi-continues supérieures $de type tel que,$
il existe un plan de transport à coût fini,
et pour toute fonction c -convexe $, pour -presque tous, possède un sous-différentiel c unique en$
alors il existe une carte de transport optimale .

Une restriction d'un plan de transport optimal reste optimale. Autrement dit, supposons $est optimal, et et définir le plan de transport normalisé, alors est un plan de transport optimal entre ses propres marginales. Si Si une solution n'est pas optimale, il existe une amélioration possible, qui se traduit alors par une amélioration de la solution originale. .$

Dualité de Kantorovich

La dualité de Kantorovich énonce que :

Si $sont des espaces de probabilité polonais, est semi-continue inférieurement, et il existe certaines fonctions semi-continues supérieurement de type tel que, alors Si en outre, ne prend que des valeurs réelles, il existe un plan de transport à coût fini et il existe certaines fonctions tel que, alors$

Considérons le deuxième cas, où nous pouvons parvenir à un plan parfaitement optimal, au lieu de simplement nous en rapprocher progressivement. Dans ce cas, un plan de transport optimal $, contraint la forme d'une paire de prix optimale et vice versa.$

Étant donné une telle paire de prix optimale $,$

étant donné un plan de transport arbitraire $, si tout satisfait l'égalité exacte, alors est un plan optimal ;$
compte tenu d'un plan de transport optimal $, n'importe lequel doit satisfaire à l'égalité exacte .$

Plus succinctement, un plan de transport est optimal si et seulement s'il est supporté par l'ensemble des paires de sous-différentiels c de $.$

Stabilité

Le transport optimal est stable au sens suivant :

Supposons que $sont des espaces de probabilité polonais, est continu, et est finie. Étant donné une suite de fonctions continues convergeant uniformément vers sur, une séquence faiblement, une séquence faiblement, et une séquence de plans de transport optimaux Si les coûts de transport satisfaire et, alors converge faiblement vers un certain, et est un plan de transport optimal depuis à .$

De même, la carte de transport optimale est également stable.

Supposons que $sont des espaces de probabilité polonais, est localement compact, est semi-continue inférieure, et est finie. Étant donné une suite de fonctions semi-continues inférieurement convergeant uniformément vers sur, une séquence faiblement,$

Interprétation économique

Le problème de transport optimal a une interprétation économique. Cédric Villani rapporte l'interprétation suivante de Luis Caffarelli :

Supposons que vous souhaitiez expédier du charbon provenant de mines, distribué comme $, aux usines, distribués comme La fonction de coût du transport est Un transporteur se présente alors et vous propose d'effectuer le transport. Vous le rémunéreriez. par charbon pour le chargement du charbon à et le payer par charbon pour le déchargement du charbon à Pour que vous acceptiez l'offre, le barème des prix doit satisfaire aux conditions suivantes : La dualité de Kantorovich stipule que l'expéditeur peut établir une grille tarifaire qui vous fait payer presque autant que si vous expédiiez vous-même.$

Dans cette interprétation, la transformation de dualité transforme une fonction de coût de chargement $dans la fonction de coût de déchargement optimale (pour l'expéditeur) Si la fonction de coût de déchargement si la valeur était plus élevée à un moment donné, il y aurait alors un itinéraire. sur lequel Cela signifie qu'il existe un itinéraire sur lequel vous préféreriez expédier vous-même vos marchandises. Cependant, si le coût de déchargement était inférieur à un endroit donné, l'expéditeur aurait pu augmenter ses revenus en augmentant le prix à cet endroit. Par conséquent, l'expéditeur devrait toujours choisir cet itinéraire. Le même argument, appliqué à nouveau, stipule que l'expéditeur devrait toujours choisir., et nous obtenons donc la moitié inférieure de la formule de dualité : La dualité de Kantorovich stipule qu'il s'agit en fait d'une égalité, c'est-à-dire que l'expéditeur peut vous faire payer autant que vous paieriez vous-même, même si l'expéditeur n'atteindra peut-être jamais exactement la limite (d'où l'utilisation de l'infimum et du supremum, au lieu du minimum et du maximum).$

Supposons que l'expéditeur doive en réalité payer la même fonction de coût que nous, et puisse atteindre exactement le revenu maximal en utilisant $Selon leur grille tarifaire, l'expéditeur doit alors utiliser un plan optimal, auquel cas il atteint tout juste le seuil de rentabilité, sans réaliser de profit. Réciproquement, tout plan d'expédition permettant à l'expéditeur d'atteindre exactement le seuil de rentabilité est nécessairement optimal.$

Solution du problème

Transport optimal sur la ligne réelle

Matrice de transport optimale

transport optimal continu

Pour $, laisser désigne l'ensemble des mesures de probabilité sur qui ont une valeur finie -ième moment . Soit et laissez, où est une fonction convexe .$

Si $n'a pas d'atome, c'est-à-dire si la fonction de répartition cumulative de est une fonction continue, alors est une carte de transport optimale. C'est la carte de transport optimale unique si est strictement convexe.$
Nous avons

La démonstration de cette solution apparaît dans Rachev & Rüschendorf (1998).

Version discrète et formulation de programmation linéaire

Dans le cas où les marges $et sont discrètes, soit et soient les masses de probabilité respectivement attribuées à et et laissez soit la probabilité d'un L'affectation. La fonction objectif du problème primal de Kantorovich est alors$

et la contrainte $s'exprime comme$

Pour intégrer cela dans un problème de programmation linéaire , nous devons vectoriser la matrice. $en empilant soit ses colonnes, soit ses lignes, nous appelons cette opération. Dans l' ordre colonne-major, les contraintes ci-dessus se réécrivent comme suit :$

et

où $est le produit Kronecker, est une matrice de taille avec toutes les entrées de un, et est la matrice identité de taille . Par conséquent, la mise en place, la formulation de programmation linéaire du problème est$

qui peut être facilement saisi dans un solveur de programmation linéaire à grande échelle (voir chapitre 3.4 de Galichon (2016) ).

Cas semi-discret

Dans le cas semi-discret, $et est une distribution continue sur, alors que est une distribution discrète qui attribue une masse de probabilité vers le site Dans ce cas, nous pouvons voir que les problèmes primal et dual de Kantorovich se réduisent respectivement à :$

pour le primordial, où $signifie que et, et:$

pour le dual, qui peut se réécrire comme suit :

qui est un problème d'optimisation convexe de dimension finie qui peut être résolu par des techniques standard, telles que la descente de gradient .

Dans le cas où $, on peut montrer que l'ensemble de affecté à un site particulier est un polyèdre convexe. La configuration résultante est appelée diagramme de puissance .$

Cas normal quadratique

Supposons le cas particulier $,, et où est inversible. On a alors$

La preuve de cette solution apparaît dans Galichon (2016).

Espaces de Hilbert séparables

Laisser $Soit un espace de Hilbert séparable . désigne l'ensemble des mesures de probabilité sur qui ont une valeur finie -ième moment; laissez désigner ces éléments qui sont gaussiennes régulières : si est une mesure gaussienne strictement positive quelconque sur et, alors aussi.$

Laisser $,, pour Alors le problème de Kantorovich admet une solution unique. et cette solution est induite par une application de transport optimale : c'est-à-dire qu'il existe une application de Borel tel que$

De plus, si $a un support borné, alors$

pour $-presque tous pour certains localement Lipschitz, -concave et potentiel de Kantorovich maximal . (Ici désigne le dérivé Gateaux de .)$

En minimisant les flux

Une formulation de descente de gradient pour la solution du problème de Monge–Kantorovich a été donnée par Sigurd Angenent , Steven Haker et Allen Tannenbaum .

régularisation entropique

Considérons une variante du problème discret ci-dessus, dans laquelle nous avons ajouté un terme de régularisation entropique à la fonction objectif du problème primal.

On peut montrer que le problème dual régularisé est

où, par rapport à la version non régularisée, la contrainte « dure » dans l'ancien dual ( $) a été remplacée par une pénalisation « douce » de cette contrainte (la somme des (termes). Les conditions d'optimalité du problème dual peuvent être exprimées comme$

{\displaystyle \mu _{x}=\sum _{y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }} ight)~\forall x\in \mathbf {X} </span referrerpolicy=

{\displaystyle u _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }} ight)~\forall y\in \mathbf {Y} </span referrerpolicy=

Dénotant $comme le matrice de termes, résoudre le problème dual revient donc à chercher deux matrices diagonales positives. et de tailles respectives et, de sorte que et L'existence de telles matrices généralise le théorème de Sinkhorn et ces matrices peuvent être calculées à l'aide de l' algorithme de Sinkhorn-Knopp, qui consiste simplement à rechercher itérativement pour résoudre l'équation 5.1 et pour résoudre l'équation 5.2 . L'algorithme de Sinkhorn-Knopp est donc un algorithme de descente de coordonnées sur le problème régularisé dual.$

Applications

Le transport optimal de Monge-Kantorovich a trouvé de nombreuses applications dans différents domaines. Parmi celles-ci :

Enregistrement et déformation d'images
Conception du réflecteur
Récupération d’informations à partir de la shadowgraphie et de la radiographie protonique
Tomographie sismique et sismologie de réflexion
La vaste catégorie de modélisation économique qui implique la propriété des substituts bruts (entre autres, les modèles d' appariement et de choix discret ).