Théorie du transport

Théorie du transport

En mathématique 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[1]. D'importants développements ont été réalisés dans ce domaine pendant la Seconde Guerre mondiale par le mathématicien et économiste russe Leonid Kantorovich[2]. Par conséquent, le problème dans sa forme actuelle est parfois baptisé problème (du transport) de Monge-Kantorovich.

Sommaire

Motivation

Mines et usines

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. On suppose pour la clarté du propos que ces mines et ces usines constituent deux sous-ensembles disjoints M et F du plan euclidien \mathbb{R}^{2}. On suppose également qu'on dispose d'une fonction coût 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 — i.e. 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 fonction coût

L'exemple suivant illustre simplement 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 selon un unique bloc contigu. On désire les réarranger selon un autre bloc contigu, 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 de manière évidente :

  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 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 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 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.

Formulation abstraite du problème

Les formulations de Monge et de Kantorovich

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 (en) (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 μ sur X et ν 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 * (μ) représente la mesure image (en) de μ 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 * (μ) = ν : ceci se produit, par exemple, quand μ est une mesure de Dirac et que ν 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 γ 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ù Γ(μ,ν) représente l'ensemble des mesures définies sur X \times Y de lois conditionnelles données par μ sur X et par ν sur Y. On peut montrer[3] qu'un minimiseur de ce problème existe toujours quand la fonction coût c est semi-continue inférieurement et que Γ(μ,ν) est un ensemble de mesures à espérances et variances bornéees (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 W1 sur l'espace des mesures de probabilité.)

Formulation duale

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

\sup \left( \int_{X} \phi (x) \, \mathrm{d} \mu (x) + \int_{Y} \psi (y) \, \mathrm{d} \nu (y) \right),

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

\phi (x) + \psi (y) \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 μ n'a pas d'atome, i.e., si la fonction de répartition F_{\mu} : \mathbb{R} \to [0, 1] de μ 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 μ(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 Kantorovich a une solution unique κ, 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 ν est à support borné, alors

r(x) = x - x | \nabla \phi (x) |^{q - 2} \nabla \phi (x) pour presque-au-sens-de-μ tout x \in X

pour un certain potentiel maximal de Kantorovich ϕ localement lipschitzien et c-concave. (Ici \nabla \phi représente la dérivée de Gâteaux de ϕ.)

Références

  1. ↑ G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666–704, 1781.
  2. ↑ L. Kantorovich. On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.
  3. ↑ L. Ambrosio, N. Gigli & G. Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel. (2005)

Lien externe


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie du transport de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • théorie du transport — pernašos teorija statusas T sritis fizika atitikmenys: angl. transport theory vok. Transporttheorie, f rus. теория переноса, f; теория транспорта, f pranc. théorie du transport, f …   Fizikos terminų žodynas

  • théorie de transport des neutrons — neutronų pernašos teorija statusas T sritis fizika atitikmenys: angl. neutron transport theory vok. Neutronentransporttheorie, f rus. теория переноса нейтронов, f pranc. théorie de transport des neutrons, f …   Fizikos terminų žodynas

  • transport theory — pernašos teorija statusas T sritis fizika atitikmenys: angl. transport theory vok. Transporttheorie, f rus. теория переноса, f; теория транспорта, f pranc. théorie du transport, f …   Fizikos terminų žodynas

  • Theorie de la cinetique d'oxydation de Wagner — Théorie de la cinétique d oxydation de Wagner La Théorie de la cinétique d oxydation de Wagner est une théorie physique destinée à modéliser la vitesse de croissance d une couche d oxyde sur un métal lorsque celle ci est compacte et adhérente,… …   Wikipédia en Français

  • Théorie de Wagner — Théorie de la cinétique d oxydation de Wagner La Théorie de la cinétique d oxydation de Wagner est une théorie physique destinée à modéliser la vitesse de croissance d une couche d oxyde sur un métal lorsque celle ci est compacte et adhérente,… …   Wikipédia en Français

  • Théorie de la cinétique d'oxydation de wagner — La Théorie de la cinétique d oxydation de Wagner est une théorie physique destinée à modéliser la vitesse de croissance d une couche d oxyde sur un métal lorsque celle ci est compacte et adhérente, dans le cadre de la corrosion sèche. Elle fut… …   Wikipédia en Français

  • Theorie de la reponse lineaire — Théorie de la réponse linéaire En physique statistique hors d équilibre, la théorie de la réponse linéaire permet de définir les susceptibilités et les coefficients de transport d un système au voisinage de l équilibre thermique indépendamment… …   Wikipédia en Français

  • Transport d’Ekman — Transport d Ekman Le transport d Ekman est le déplacement horizontal des couches d’eaux superficielles de l océan par la seule action de la friction du vent à la surface. On distingue le transport en volume, exprimé par les océanographes en… …   Wikipédia en Français

  • TRANSPORT (COEFFICIENTS DE) — TRANSPORT COEFFICIENTS DE Coefficients Lik des relations linéaires (équations de transport) qui existent, en première approximation, entre les courants 淋 size=1晴 («flux») des grandeurs extensives transportées Gi et les agents Xi («forces… …   Encyclopédie Universelle

  • Theorie de l'information — Théorie de l information La théorie de l information, sans précision, est le nom usuel désignant la théorie de l information de Shannon, qui est une théorie probabiliste permettant de quantifier le contenu moyen en information d un ensemble de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”