Dopravní teorie (matematika) - Transportation theory (mathematics)

V matematice a ekonomii je dopravní teorie nebo dopravní teorie pojmenována pro studium optimální dopravy a alokace zdrojů . Tento problém formalizoval francouzský matematik Gaspard Monge v roce 1781.

Ve 20. letech 20. století byl AN Tolstoi jedním z prvních, kdo matematicky studoval dopravní problém . V roce 1930 ve sbírce Transportation Planning Volume I pro Národní komisariát dopravy Sovětského svazu publikoval článek „Metody hledání minimální kilometrové vzdálenosti v nákladní přepravě ve vesmíru“.

Významného pokroku v oboru dosáhl během druhé světové války sovětský matematik a ekonom Leonid Kantorovich . V důsledku toho je problém, jak je uveden, někdy známý jako dopravní problém Monge -Kantorovich . Lineární programování formulace problému dopravy je také známý jako Hitchcock - Koopmans dopravního problému.

Motivace

Doly a továrny

Předpokládejme, že máme sbírku m dolů na těžbu železné rudy a sbírku n továren, které používají železnou rudu, kterou doly produkují. Předpokládejme, že pro účely tohoto argumentu, že tyto doly a továrny tvoří dvě disjunktní podmnožiny M a F z euklidovské roviny R ² . Předpokládejme také, že máme nákladovou funkci c  :  R ²  ×  R ²  → [0, ∞), takže c ( x ,  y ) jsou náklady na přepravu jedné zásilky železa z x do y . Pro jednoduchost ignorujeme čas potřebný k přepravě. Předpokládáme také, že každý důl může dodávat pouze jednu továrnu (žádné rozdělení zásilek) a že každá továrna vyžaduje, aby byla v provozu přesně jedna zásilka (továrny nemohou pracovat na poloviční nebo dvojnásobnou kapacitu). Po provedení výše uvedených předpokladů, je dopravní plán je bijection T  : M → F . Jinými slovy, každý důl m ∈ M dodává přesně jednu cílovou továrnu T ( m ) ∈ F a každou továrnu zásobuje přesně jeden důl. Chceme najít optimální dopravní plán , plán T, jehož celkové náklady

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

je nejméně ze všech možných dopravních plánů od M až F . Tento motivující speciální případ problému s přepravou je příkladem problému s přiřazením . Přesněji řečeno, je ekvivalentní nalezení minimální hmotnosti v bipartitním grafu.

Stěhování knih: důležitost nákladové funkce

Následující jednoduchý příklad ilustruje důležitost nákladové funkce při určování optimálního přepravního plánu. Předpokládejme, že máme n knih stejné šířky na polici ( skutečná čára ), uspořádaných do jednoho souvislého bloku. Chceme je přeskupit do dalšího souvislého bloku, ale posunuli jsme jednu šířku knihy doprava. Představují se dva zjevní kandidáti na optimální dopravní plán:

1. přesunout všech n knih o šířku jedné knihy doprava („mnoho malých tahů“);
2. přesuňte nejvíce vlevo n šířky knih doprava a všechny ostatní knihy nechte pevné („jeden velký tah“).

Pokud je nákladová funkce úměrná euklidovské vzdálenosti ( c ( x ,  y ) = α | x  -  y |), pak jsou oba tito kandidáti optimální. Pokud naopak zvolíme přísně konvexní nákladovou funkci úměrnou čtverci euklidovské vzdálenosti ( c ( x ,  y ) =  α | x  -  y | ² ), pak se možnost „mnoho malých tahů“ stane jedinečným minimalizátorem .

Všimněte si, že výše uvedené nákladové funkce berou v úvahu pouze horizontální vzdálenost, kterou knihy uběhly, nikoli horizontální vzdálenost, kterou urazí zařízení používané ke zvednutí každé knihy a přesunutí knihy na místo. Pokud je místo toho uvažován druhý, pak je ze dvou transportních plánů vždy druhý optimální pro euklidovskou vzdálenost, zatímco za předpokladu, že existují alespoň 3 knihy, je první transportní plán optimální pro druhou euklidovskou vzdálenost.

Hitchcockův problém

FL Hitchcock je připsána následující formulace problému s přepravou :

Předpokládejme, že existují m zdroje pro zboží, s jednotkami zásobování v x _i a n propadů pro zboží, s požadavkem na y _j . Pokud jsou jednotkové náklady na přepravu od x _i do y _j , najděte tok, který uspokojí poptávku po dodávkách a minimalizuje náklady na tok. Této výzvy v logistice se chopil DR Fulkerson a v knize Toky v sítích (1962) napsané s LR Fordem ml .${\ displaystyle x_ {1}, \ ldots, x_ {m}}$${\ displaystyle a (x_ {i})}$${\ displaystyle y_ {1}, \ ldots, y_ {n}}$${\ displaystyle b (y_ {j})}$${\ Displaystyle a (x_ {i}, \ y_ {j})}$

Tjalling Koopmans je také připočítán s formulací ekonomiky dopravy a přidělování zdrojů.

Abstraktní formulace problému

Monge a Kantorovich formulace

Problém dopravy, jak je uvedeno v moderní nebo technické literatuře, vypadá poněkud odlišně kvůli vývoji Riemannovy geometrie a teorie míry . Jednoduchý příklad dolů-továren je užitečným referenčním bodem při přemýšlení o abstraktním případě. V tomto nastavení připouštíme možnost, že si možná nepřejeme ponechat všechny doly a továrny otevřené pro podnikání, a povolíme, aby doly zásobovaly více než jednu továrnu a továrny přijímaly železo z více než jednoho dolu.

Nechť X a Y jsou dva oddělitelné metrické prostory tak, že jakákoli míra pravděpodobnosti na X (nebo Y ) je radonová míra (tj. Jsou to radonové prostory ). Nechť c  : X × Y → [0, ∞] je Borelem měřitelná funkce . Vzhledem k pravděpodobnosti měření μ na X a ν na Y , Mongeova formulace optimálního transportního problému je najít transportní mapu T  : X → Y, která realizuje nekonečno

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

kde T _* ( μ ) označuje tlačit dopředu o u Stabilizátory podle T . Mapa T, která dosahuje tohoto infimum ( tj. Místo infimum jej činí minimem ), se nazývá „optimální dopravní mapa“.

Mongeova formulace optimálního transportního problému může být špatně postavena, protože někdy neexistuje T vyhovující T _∗ ( μ ) = ν : k tomu dochází například tehdy, když μ je Diracova míra, ale ν není.

Můžeme to zlepšit přijetím Kantorovichovy formulace optimálního transportního problému, kterým je najít míru pravděpodobnosti γ na X × Y, která dosáhne nekonečna

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

kde Γ ( μ , ν ) označuje soubor všech opatření pravděpodobnosti na X x Y s marginální μ na X a vmax na Y . Je možné ukázat, že minimalizátor pro tento problém vždy existuje, když je nákladová funkce c nižší polokontinuální a Γ ( μ ,  ν ) je těsný soubor opatření (což je zaručeno pro radonové prostory X a Y ). (Porovnejte tuto formulaci s definicí Wassersteinovy ​​metriky W ₁ o prostoru pravděpodobnostních měr.) Formulaci gradientního sestupu pro řešení Monge -Kantorovichova problému poskytli Sigurd Angenent , Steven Haker a Allen Tannenbaum .

Vzorec duality

Minimum Kantorovichova problému se rovná

${\ Displaystyle \ sup \ left (\ int _ {X} \ varphi (x) \, \ mathrm {d} \ mu (x)+\ int _ {Y} \ psi (y) \, \ mathrm {d} \ nu (y) \ vpravo),}$

kde supremum běží přes všechny páry ohraničených a spojitých funkcí a tak ${\ Displaystyle \ varphi: X \ rightarrow \ mathbf {R}}$${\ Displaystyle \ psi: Y \ rightarrow \ mathbf {R}}$

${\ Displaystyle \ varphi (x)+\ psi (y) \ leq c (x, y).}$

Ekonomická interpretace

Ekonomická interpretace je jasnější, pokud jsou značky převráceny. Nechme stát vektor charakteristik pracovníka, vektor charakteristik firmy a ekonomický výstup generovaný pracovníkem, který odpovídá firmě . Nastavení a problém Monge-Kantorovich přepíše: ${\ displaystyle \ textstyle x \ in X}$${\ displaystyle \ textstyle y \ in Y}$${\ Displaystyle \ textstyle \ Phi \ left (x, y \ right) =-c \ left (x, y \ right)}$${\ displaystyle \ textstyle x}$${\ displaystyle \ textstyle y}$${\ Displaystyle \ textstyle u \ left (x \ right) =-\ varphi \ left (x \ right)}$${\ Displaystyle \ textstyle v \ left (y \ right) =-\ psi \ left (y \ right)}$

který má duální  : kde infimum přechází přes ohraničenou a spojitou funkci a . Pokud má duální problém řešení, je vidět, že: ${\ Displaystyle \ textstyle u: X \ rightarrow \ mathbf {R}}$${\ Displaystyle \ textstyle v: Y \ rightarrow \ mathbf {R}}$ to se interpretuje jako rovnovážná mzda pracovníka typu a interpretuje jako rovnovážný zisk firmy typu . ${\ displaystyle \ textstyle u \ left (x \ right)}$${\ displaystyle \ textstyle x}$${\ displaystyle \ textstyle v \ left (y \ right)}$${\ displaystyle \ textstyle y}$

Řešení problému

Optimální doprava na skutečné lince

Pro , ať značí kolekci pravděpodobnosti opatření, na která mají konečnou tý moment . Nech a nech , kde je konvexní funkce . ${\ Displaystyle 1 \ leq p <\ infty}$${\ displaystyle {\ mathcal {P}} _ {p} (\ mathbf {R})}$${\ displaystyle \ mathbf {R}}$${\ displaystyle p}$${\ Displaystyle \ mu, \ nu \ in {\ mathcal {P}} _ {p} (\ mathbf {R})}$${\ Displaystyle c (x, y) = h (xy)}$${\ Displaystyle h: \ mathbf {R} \ rightarrow [0, \ infty)}$

1. Pokud nemá atom , tedy v případě, že kumulativní distribuční funkce z je spojitá funkce , pak je optimální dopravní mapa. Je to jedinečná optimální dopravní mapa, pokud je přísně konvexní.${\ Displaystyle \ mu}$ ${\ Displaystyle F _ {\ mu} = \ mathbf {R} \ rightarrow [0,1]}$${\ Displaystyle \ mu}$${\ Displaystyle F _ {\ nu}^{-1} \ circ F _ {\ mu}: \ mathbf {R} \ to \ mathbf {R}}$${\ displaystyle h}$
2. My máme

${\ Displaystyle \ min _ {\ gamma \ in \ Gamma (\ mu, \ nu)} \ int _ {\ mathbf {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.}$

Důkaz tohoto řešení se objevuje v Rachev & Rüschendorf (1998).

Diskrétní verze a lineární formulace programování

V případě, že okraje a jsou diskrétní, nechť a být pravděpodobnostní hmotnosti přiřazené k a , a nechť je pravděpodobnost přiřazení. Objektivní funkce v prvotním Kantorovichově problému je pak ${\ displaystyle \ textstyle \ mu}$${\ displaystyle \ textstyle \ nu}$${\ displaystyle \ textstyle \ mu _ {x}}$${\ displaystyle \ textstyle \ nu _ {y}}$${\ Displaystyle \ textstyle x \ in \ mathbf {X}}$${\ Displaystyle \ textstyle y \ in \ mathbf {Y}}$${\ displaystyle \ textstyle \ gamma _ {xy}}$${\ displaystyle \ textstyle xy}$

${\ Displaystyle \ sum _ {x \ in \ mathbf {X}, y \ in \ mathbf {Y}} \ gamma _ {xy} c_ {xy}}$

a omezení vyjadřuje jako ${\ Displaystyle \ textstyle \ gamma \ in \ Gamma \ left (\ mu, \ nu \ right)}$

${\ Displaystyle \ sum _ {y \ in \ mathbf {Y}} \ gamma _ {xy} = \ mu _ {x}, \ forall x \ in \ mathbf {X}}$ a ${\ Displaystyle \ sum _ {x \ in \ mathbf {X}} \ gamma _ {xy} = \ nu _ {y}, \ forall y \ in \ mathbf {Y.}}$

Abychom to mohli zadat do problému s lineárním programováním , musíme matici vektorizovat buď stohováním jejích sloupců, nebo jejích řádků , nazýváme tuto operaci. V pořadí hlavních sloupců se výše uvedená omezení přepisují jako ${\ displaystyle \ textstyle \ gamma _ {xy}}$${\ displaystyle \ textstyle \ operatorname {vec}}$

${\ Displaystyle \ left (1_ {1 \ times \ left \ vert \ mathbf {Y} \ right \ vert} \ otimes I _ {\ left \ vert \ mathbf {X} \ right \ vert} \ right) \ operatorname {vec } \ left (\ gamma \ right) = \ mu}$ a ${\ Displaystyle \ left (I _ {\ left \ vert \ mathbf {Y} \ right \ vert} \ otimes 1_ {1 \ times \ left \ vert \ mathbf {X} \ right \ vert} \ right) \ operatorname {vec } \ left (\ gamma \ right) = \ nu}$

kde je produkt Kronecker , je matice velikosti se všemi položkami jedniček a je maticí velikosti velikosti . V důsledku toho je nastavení lineární programovací formulace problému ${\ displaystyle \ textstyle \ otimes}$${\ displaystyle \ textstyle 1_ {n \ times m}}$${\ displaystyle \ textstyle n \ times m}$${\ displaystyle \ textstyle I_ {n}}$${\ displaystyle \ textstyle n}$${\ displaystyle \ textstyle z = \ operatorname {vec} \ left (\ gamma \ right)}$

${\ displaystyle \ min _ {z \ geq 0} \ operatorname {vec} \ left (c \ right)^{\ top} z}$

Svatý ${\ Displaystyle {\ begin {pmatrix} 1_ {1 \ times \ left \ vert \ mathbf {Y} \ right \ vert} \ otimes I _ {\ left \ vert \ mathbf {X} \ right \ vert} \\ I_ { \ left \ vert \ mathbf {Y} \ right \ vert} \ otimes 1_ {1 \ times \ left \ vert \ mathbf {X} \ right \ vert} \ end {pmatrix}}}$ ${\ displaystyle z = {\ binom {\ mu} {\ nu}}}$

které lze snadno zadat ve velkém měřítku lineárního programovacího řešiče, jako je Gurobi (viz kapitola 3.4 programu Galichon (2016)).

Polodiskrétní pouzdro

V semi-diskrétním případě, a je spojité rozdělení , zatímco je diskrétní rozdělení, které přiřazuje pravděpodobnostní hmotnost místu . V tomto případě vidíme, že primární a duální Kantorovichovy problémy se snižují na: ${\ Displaystyle \ textstyle X = Y = \ mathbf {R} ^{d}}$${\ displaystyle \ textstyle \ mu}$${\ Displaystyle \ textstyle \ mathbf {R} ^{d}}$${\ Displaystyle \ textstyle \ nu = \ sum _ {j = 1}^{J} \ nu _ {j} \ delta _ {y_ {i}}}$${\ displaystyle \ textstyle \ nu _ {j}}$${\ Displaystyle \ textstyle y_ {j} \ in \ mathbf {R} ^{d}}$

Pro prvotní, kde znamená, že i a: ${\ Displaystyle \ textstyle \ gamma \ in \ Gamma \ left (\ mu, \ nu \ right)}$${\ Displaystyle \ textstyle \ int _ {X} d \ gamma _ {j} \ left (x \ right) = \ nu _ {j}}$${\ Displaystyle \ textstyle \ sum _ {j} d \ gamma _ {j} \ left (x \ right) = d \ mu \ left (x \ right)}$ pro duál, který lze přepsat jako: což je problém konvexní optimalizace konečných rozměrů, který lze vyřešit standardními technikami, jako je například gradientový sestup .

V případě, kdy lze ukázat, že množina přiřazená konkrétnímu místu je konvexní mnohostěn. Výsledná konfigurace se nazývá diagram napájení . ${\ Displaystyle \ textstyle c \ left (x, y \ right) = \ left \ vert xy \ right \ vert ^{2}/2}$${\ Displaystyle \ textstyle x \ in \ mathbf {X}}$${\ displaystyle \ textstyle j}$

Kvadratický normální případ

Předpokládejme, že konkrétní případ , a kde je nezvratné. Jeden pak má ${\ Displaystyle \ textstyle \ mu = {\ mathcal {N}} \ left (0, \ Sigma _ {X} \ right)}$${\ Displaystyle \ textstyle \ nu = {\ mathcal {N}} \ left (0, \ Sigma _ {Y} \ right)}$${\ Displaystyle \ textstyle c \ left (x, y \ right) = \ left \ vert y-Ax \ right \ vert ^{2}/2}$${\ displaystyle \ textstyle A}$

${\ Displaystyle \ varphi \ left (x \ right) =-x^{\ top} \ Sigma _ {X}^{-1/2} \ left (\ Sigma _ {X}^{1/2} A^ {\ top} \ Sigma _ {Y} A \ Sigma _ {X}^{1/2} \ right)^{1/2} \ Sigma _ {X}^{-1/2} x/2}$

${\ Displaystyle \ psi \ left (y \ right) =-y^{\ top} A \ Sigma _ {X}^{1/2} \ left (\ Sigma _ {X}^{1/2} A^ {\ top} \ Sigma _ {Y} A \ Sigma _ {X}^{1/2} \ right)^{-1/2} \ Sigma _ {X}^{1/2} Ay/2}$

${\ Displaystyle T \ left (x \ right) = \ left (A^{\ top} \ right)^{-1} \ Sigma _ {X}^{-1/2} \ left (\ Sigma _ {X }^{1/2} A^{\ top} \ Sigma _ {Y} A \ Sigma _ {X}^{1/2} \ right)^{1/2} \ Sigma _ {X}^{- 1/2}}$

Důkaz tohoto řešení se objevuje v Galichonu (2016).

Oddělitelné Hilbertovy prostory

Nechť je oddělitelný Hilbertův prostor . Nechť značí kolekci pravděpodobnosti opatření, na která mají omezenou tý moment; ať znamenají ty prvky , které jsou Gaussian pravidelný : pokud je nějaký striktně pozitivní Gaussian opatření na a pak také. ${\ displaystyle X}$ ${\ displaystyle {\ mathcal {P}} _ {p} (X)}$${\ displaystyle X}$${\ displaystyle p}$${\ displaystyle {\ mathcal {P}} _ {p}^{r} (X)}$${\ Displaystyle \ mu \ in {\ mathcal {P}} _ {p} (X)}$${\ displaystyle g}$ ${\ displaystyle X}$${\ displaystyle g (N) = 0}$${\ displaystyle \ mu (N) = 0}$

Nechť , , pro . Pak má Kantorovichův problém jedinečné řešení a toto řešení je vyvoláno optimální transportní mapou: tj. Existuje Borelova mapa , která ${\ Displaystyle \ mu \ in {\ mathcal {P}} _ {p}^{r} (X)}$${\ displaystyle \ nu \ in {\ mathcal {P}} _ {p} (X)}$${\ Displaystyle c (x, y) = | xy |^{p}/p}$${\ Displaystyle p \ in (1, \ infty), p^{-1}+q^{-1} = 1}$${\ displaystyle \ kappa}$${\ Displaystyle r \ in L^{p} (X, \ mu; X)}$

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

Navíc, pokud má omezenou podporu , pak ${\ displaystyle \ nu}$

${\ Displaystyle r (x) = x- | \ nabla \ varphi (x) |^{q-2} \, \ nabla \ varphi (x)}$

pro -téměř vše pro nějaký lokálně Lipschitz , c -konkávní a maximální Kantorovichův potenciál . (Zde označuje dortů derivát z ). ${\ Displaystyle \ mu}$${\ displaystyle x \ v X}$${\ Displaystyle \ varphi}$${\ Displaystyle \ nabla \ varphi}$${\ Displaystyle \ varphi}$

Entropická regularizace

Uvažujme variantu diskrétního problému výše, kde jsme k objektivní funkci primárního problému přidali entropický regularizační člen

${\ Displaystyle \ min _ {\ gamma \ geq 0} \ sum _ {x \ in \ mathbf {X}, y \ in \ mathbf {Y}} \ gamma _ {xy} c_ {xy}+\ epsilon \ gamma _ {xy} \ ln \ gamma _ {xy}}$

st a${\ Displaystyle \ sum _ {y \ in \ mathbf {Y}} \ gamma _ {xy} = \ mu _ {x}, \ forall x \ in \ mathbf {X}}$${\ Displaystyle \ sum _ {x \ in \ mathbf {X}} \ gamma _ {xy} = \ nu _ {y}, \ forall y \ in \ mathbf {Y}}$

Lze ukázat, že problém s dvojí regulací je

${\ Displaystyle \ max _ {\ varphi, \ psi} \ sum _ {x \ in \ mathbf {X}} \ varphi _ {x} \ mu _ {x}+\ sum _ {y \ in \ mathbf {Y }} \ psi _ {y} v_ {y}-\ epsilon \ sum _ {x \ in \ mathbf {X}, y \ in \ mathbf {Y}} \ exp \ left ({\ frac {\ varphi _ { x}+\ psi _ {y} -c_ {xy}} {\ epsilon}} \ vpravo)+\ epsilon}$

kde ve srovnání s neregulovanou verzí bylo „tvrdé“ omezení v dřívější dvojí ( ) nahrazeno „měkkou“ penalizací tohoto omezení (součet výrazů). Podmínky optimality v duálním problému lze vyjádřit jako ${\ Displaystyle \ textstyle \ varphi _ {x}+\ psi _ {y} -c_ {xy} \ geq 0}$${\ Displaystyle \ textstyle \ epsilon \ exp \ left ((\ \ varphi _ {x}+\ psi _ {y} -c_ {xy})/\ epsilon \ right)}$

Rov. 5.1: ${\ Displaystyle \ mu _ {x} = \ sum _ {y \ in \ mathbf {Y}} \ exp \ left ({\ frac {\ varphi _ {x}+\ psi _ {y} -c_ {xy} } {\ epsilon}} \ right) ~ \ forall x \ in \ mathbf {X}}$

Rov. 5.2: ${\ Displaystyle \ nu _ {y} = \ sum _ {x \ in \ mathbf {X}} \ exp \ left ({\ frac {\ varphi _ {x}+\ psi _ {y} -c_ {xy} } {\ epsilon}} \ right) ~ \ forall y \ in \ mathbf {Y}}$

Označení jako matice pojmu , řešení duálu je tedy ekvivalentní hledání dvou diagonálních kladných matic a příslušných velikostí a takových, které a . Existence takových matic zobecňuje Sinkhornovu větu a matice lze vypočítat pomocí algoritmu Sinkhorn-Knopp , který jednoduše spočívá v iterativním hledání řešení rovnice 5.1 a řešení rovnice 5.2 . Algoritmus Sinkhorn-Knopp je tedy algoritmus sestupu souřadnic na dvojitě regulovaném problému. ${\ displaystyle \ textstyle A}$${\ Displaystyle \ textstyle \ left \ vert \ mathbf {X} \ right \ vert \ times \ left \ vert \ mathbf {Y} \ right \ vert}$${\ Displaystyle \ textstyle A_ {xy} = \ exp \ left (-c_ {xy}/\ epsilon \ right)}$${\ displaystyle \ textstyle D_ {1}}$${\ displaystyle \ textstyle D_ {2}}$${\ Displaystyle \ textstyle \ left \ vert \ mathbf {X} \ right \ vert}$${\ Displaystyle \ textstyle \ left \ vert \ mathbf {Y} \ right \ vert}$${\ Displaystyle \ textstyle D_ {1} AD_ {2} 1 _ {\ left \ vert \ mathbf {Y} \ right \ vert} = \ mu}$${\ Displaystyle \ textstyle \ left (D_ {1} AD_ {2} \ right)^{\ top} 1 _ {\ left \ vert \ mathbf {X} \ right \ vert} = \ nu}$${\ displaystyle \ textstyle \ varphi _ {x}}$${\ displaystyle \ textstyle \ psi _ {y}}$

Aplikace

Optimální transport Monge – Kantorovich našel uplatnění v širokém rozsahu v různých oblastech. Mezi ně patří:

• Registrace obrazu a deformace
• Design reflektoru
• Načítání informací ze stínové a protonové radiografie
• Seismická tomografie a reflexní seismologie

Viz také

• Wassersteinova metrika
• Transportní funkce
• Maďarský algoritmus
• Plánování dopravy
• Vzdálenost stěhováku Země
• Monge – Ampérova rovnice

Reference

Další čtení

• Brualdi, Richard A. (2006). Třídy kombinatorické matice . Encyklopedie matematiky a její aplikace. 108 . Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl  1106.05001 .