Теория транспорта (математика)

Изучение оптимальной транспортировки и распределения ресурсов

В математике и экономике теория транспортировки или теория транспорта — это название, данное изучению оптимальной транспортировки и распределения ресурсов . Проблема была формализована французским математиком Гаспаром Монжем в 1781 году. ^[1]

В 1920-х годах А. Н. Толстой был одним из первых, кто исследовал транспортную задачу математически . В 1930 году в сборнике «Планирование перевозок» Том I для Народного комиссариата путей сообщения СССР он опубликовал статью «Способы нахождения минимального километража при перевозках грузов в пространстве». ^{[2] [3]}

Главные достижения в этой области были достигнуты во время Второй мировой войны советским математиком и экономистом Леонидом Канторовичем . ^[4] Следовательно, проблема в том виде, в котором она сформулирована, иногда известна как транспортная задача Монжа-Канторовича . ^[5] Формулировка транспортной задачи с помощью линейного программирования также известна как транспортная задача Хичкока - Купманса . ^[6]

Мотивация

Шахты и заводы

Предположим, что у нас есть набор шахт, добывающих железную руду, и набор заводов, которые используют железную руду, которую производят шахты. Предположим ради аргумента, что эти шахты и заводы образуют два непересекающихся подмножества и евклидовой плоскости . Предположим также, что у нас есть функция стоимости , так что это стоимость транспортировки одной партии железа из в . Для простоты мы игнорируем время, необходимое для выполнения транспортировки. Мы также предполагаем, что каждая шахта может снабжать только одну фабрику (без разделения поставок) и что каждой фабрике требуется ровно одна поставка для работы (фабрики не могут работать на половинной или двойной мощности). Сделав вышеуказанные предположения, транспортный план является биекцией . Другими словами, каждая шахта снабжает ровно одну целевую фабрику , и каждая фабрика снабжается ровно одной шахтой. Мы хотим найти оптимальный транспортный план , план , общая стоимость которого ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle c:\mathbb {R} ^{2}\times \mathbb {R} ^{2}\to [0,\infty )}$ ${\displaystyle c(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle T:M\to F}$ ${\displaystyle m\in M}$ ${\displaystyle T(m)\in F}$ ${\displaystyle T}$

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

является наименьшим из всех возможных планов транспортировки из в . Этот мотивирующий частный случай транспортной задачи является примером задачи назначения . Более конкретно, это эквивалентно поиску паросочетания с минимальным весом в двудольном графе . ${\displaystyle M}$ ${\displaystyle F}$

Перемещение книг: важность функции стоимости

Следующий простой пример иллюстрирует важность функции стоимости при определении оптимального плана транспортировки. Предположим, что у нас есть книги одинаковой ширины на полке ( реальная линия ), расположенные в один непрерывный блок. Мы хотим переставить их в другой непрерывный блок, но сдвинув одну ширину книги вправо. Представляются два очевидных кандидата на оптимальный план транспортировки: ${\displaystyle n}$

1. переместить все книги на ширину одной книги вправо («много маленьких ходов»); ${\displaystyle n}$
2. переместите ширину самой левой книги вправо, а все остальные книги оставьте фиксированными («один большой ход»). ${\displaystyle n}$

Если функция стоимости пропорциональна евклидову расстоянию ( для некоторых ), то эти два кандидата оба оптимальны. Если же, с другой стороны, мы выбираем строго выпуклую функцию стоимости, пропорциональную квадрату евклидова расстояния ( для некоторых ), то вариант «много маленьких ходов» становится единственным минимизатором. ${\displaystyle c(x,y)=\alpha \|x-y\|}$ ${\displaystyle \alpha >0}$ ${\displaystyle c(x,y)=\alpha \|x-y\|^{2}}$ ${\displaystyle \alpha >0}$

Обратите внимание, что приведенные выше функции стоимости учитывают только горизонтальное расстояние, пройденное книгами, а не горизонтальное расстояние, пройденное устройством, используемым для подъема каждой книги и перемещения книги в положение. Если вместо этого рассматривается последнее, то из двух планов транспортировки второй всегда оптимален для евклидова расстояния, в то время как при наличии не менее 3 книг первый план транспортировки оптимален для квадрата евклидова расстояния.

Проблема Хичкока

Следующая формулировка транспортной задачи принадлежит Ф. Л. Хичкоку : ^[7]

Предположим, что есть источники товара с единицами поставки в и приемники товара со спросом в . Если есть себестоимость единицы отгрузки из в , найдите поток, который удовлетворяет спрос со стороны поставок и минимизирует стоимость потока. Эта задача в логистике была рассмотрена DR Fulkerson ^[8] и в книге Flows in Networks (1962), написанной совместно с LR Ford Jr. ^[9] ${\displaystyle m}$ ${\displaystyle x_{1},\ldots ,x_{m}}$ ${\displaystyle a(x_{i})}$ ${\displaystyle x_{i}}$ ${\displaystyle n}$ ${\displaystyle y_{1},\ldots ,y_{n}}$ ${\displaystyle b(y_{j})}$ ${\displaystyle y_{j}}$ ${\displaystyle a(x_{i},\ y_{j})}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$

Тьяллингу Купмансу также приписывают разработку основ транспортной экономики и распределения ресурсов.

Абстрактная формулировка проблемы

Формулировки Монжа и Канторовича

Проблема транспортировки, как она сформулирована в современной или более технической литературе, выглядит несколько иначе из-за развития римановой геометрии и теории меры . Пример шахт-фабрик, каким бы простым он ни был, является полезной точкой отсчета при рассмотрении абстрактного случая. В этой обстановке мы допускаем возможность того, что мы можем не захотеть держать все шахты и фабрики открытыми для бизнеса и позволить шахтам снабжать более одной фабрики, а фабрикам принимать железо из более чем одной шахты.

Пусть и будут двумя сепарабельными метрическими пространствами такими, что любая вероятностная мера на (или ) является мерой Радона (т.е. они являются пространствами Радона ). Пусть будет измеримой по Борелю функцией . При заданных вероятностных мерах на и на , формулировка Монжа оптимальной транспортной задачи заключается в поиске транспортной карты , реализующей инфимум ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle c:X\times Y\to [0,\infty ]}$ ${\displaystyle \mu }$ ${\displaystyle X}$ ${\displaystyle \nu }$ ${\displaystyle Y}$ ${\displaystyle T:X\to Y}$

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

где обозначает перемещение вперед на . Карта , которая достигает этой нижней грани ( т.е. делает ее минимумом вместо нижней грани), называется «оптимальной транспортной картой». ${\displaystyle T_{*}(\mu )}$ ${\displaystyle \mu }$ ${\displaystyle T}$ ${\displaystyle T}$

Формулировка Монжа оптимальной транспортной задачи может быть некорректной, поскольку иногда не существует удовлетворяющего решения : например, это происходит, когда является мерой Дирака , но не является. ${\displaystyle T}$ ${\displaystyle T_{*}(\mu )=\nu }$ ${\displaystyle \mu }$ ${\displaystyle \nu }$

Мы можем улучшить это, приняв формулировку Канторовича для оптимальной транспортной задачи, которая заключается в нахождении вероятностной меры , достигающей инфимума ${\displaystyle \gamma }$ ${\displaystyle X\times Y}$

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

где обозначает набор всех вероятностных мер на с маргиналами на и на . Можно показать ^[10] , что минимизатор для этой задачи всегда существует, когда функция стоимости полунепрерывна снизу и является плотным набором мер (что гарантировано для пространств Радона и ). (Сравните эту формулировку с определением метрики Вассерштейна на пространстве вероятностных мер.) Формулировка градиентного спуска для решения задачи Монжа–Канторовича была дана Сигурдом Ангенентом , Стивеном Хакером и Алленом Танненбаумом . ^[11] ${\displaystyle \Gamma (\mu ,\nu )}$ ${\displaystyle X\times Y}$ ${\displaystyle \mu }$ ${\displaystyle X}$ ${\displaystyle \nu }$ ${\displaystyle Y}$ ${\displaystyle c}$ ${\displaystyle \Gamma (\mu ,\nu )}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle W_{p}}$

Формула двойственности

Минимум задачи Канторовича равен

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

где супремум пробегает все пары ограниченных и непрерывных функций и таких, что ${\displaystyle \varphi :X\rightarrow \mathbb {R} }$ ${\displaystyle \psi :Y\rightarrow \mathbb {R} }$

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

Экономическая интерпретация

Экономическая интерпретация становится яснее, если знаки поменять местами. Пусть обозначает вектор характеристик работника, вектор характеристик фирмы и экономический выпуск, произведенный работником, сопоставленным с фирмой . Принимая во внимание и , задача Монжа–Канторовича переписывается следующим образом: которая имеет двойственную  : где инфимум пробегает ограниченную и непрерывную функцию и . Если двойственная задача имеет решение, можно увидеть, что: так что интерпретируется как равновесная заработная плата работника типа , а интерпретируется как равновесная прибыль фирмы типа . ^[12] ${\textstyle x\in X}$ ${\textstyle y\in Y}$ ${\textstyle \Phi (x,y)=-c(x,y)}$ ${\textstyle x}$ ${\textstyle y}$ ${\textstyle u(x)=-\varphi (x)}$ ${\textstyle v(y)=-\psi (y)}$ $${\displaystyle \sup \left\{\int _{X\times Y}\Phi (x,y)d\gamma (x,y),\gamma \in \Gamma (\mu ,\nu )\right\}}$$ $${\displaystyle \inf \left\{\int _{X}u(x)\,d\mu (x)+\int _{Y}v(y)\,d\nu (y):u(x)+v(y)\geq \Phi (x,y)\right\}}$$ ${\textstyle u:X\rightarrow \mathbb {R} }$ ${\textstyle v:Y\rightarrow \mathbb {R} }$ $${\displaystyle v(y)=\sup _{x}\left\{\Phi (x,y)-u(x)\right\}}$$ ${\textstyle u(x)}$ ${\textstyle x}$ ${\textstyle v(y)}$ ${\textstyle y}$

Решение проблемы

Оптимальная транспортировка по реальной линии

Для пусть обозначает совокупность вероятностных мер на , имеющих конечный -й момент . Пусть и пусть , где - выпуклая функция . ${\displaystyle 1\leq p<\infty }$ ${\displaystyle {\mathcal {P}}_{p}(\mathbb {R} )}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle p}$ ${\displaystyle \mu ,\nu \in {\mathcal {P}}_{p}(\mathbb {R} )}$ ${\displaystyle c(x,y)=h(x-y)}$ ${\displaystyle h:\mathbb {R} \rightarrow [0,\infty )}$

1. Если не имеет атома , т. е. если кумулятивная функция распределения является непрерывной функцией , то является оптимальным транспортным отображением. Это единственное оптимальное транспортное отображение, если является строго выпуклым. ${\displaystyle \mu }$ ${\displaystyle F_{\mu }:\mathbb {R} \rightarrow [0,1]}$ ${\displaystyle \mu }$ ${\displaystyle F_{\nu }^{-1}\circ F_{\mu }:\mathbb {R} \to \mathbb {R} }$ ${\displaystyle h}$
2. У нас есть

${\displaystyle \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.}$

Доказательство этого решения представлено в работе Рачева и Рюшендорфа (1998). ^[13]

Дискретная версия и формулировка линейного программирования

В случае, когда поля и дискретны, пусть и будут вероятностными массами, соответственно назначенными и , и пусть будет вероятностью назначения . Целевая функция в основной задаче Канторовича тогда будет ${\textstyle \mu }$ ${\textstyle \nu }$ ${\textstyle \mu _{x}}$ ${\textstyle \nu _{y}}$ ${\textstyle x\in \mathbf {X} }$ ${\textstyle y\in \mathbf {Y} }$ ${\textstyle \gamma _{xy}}$ ${\textstyle xy}$

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

и ограничение выражается как ${\textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$

${\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} .}$

Чтобы ввести это в задачу линейного программирования , нам нужно векторизовать матрицу , либо сложив ее столбцы, либо строки , мы называем эту операцию. В порядке по столбцам ограничения выше переписываются как ${\textstyle \gamma _{xy}}$ ${\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 }$и ${\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 }$

где — произведение Кронекера , — матрица размера со всеми элементами из единиц, а — единичная матрица размера . В результате, устанавливая , формулировка задачи линейного программирования имеет вид ${\textstyle \otimes }$ ${\textstyle 1_{n\times m}}$ ${\textstyle n\times m}$ ${\textstyle I_{n}}$ ${\textstyle n}$ ${\textstyle z=\operatorname {vec} \left(\gamma \right)}$

${\displaystyle {\begin{aligned}&{\text{Minimize }}&&\operatorname {vec} (c)^{\top }z\\[4pt]&{\text{subject to:}}&&z\geq 0,\\[4pt]&&&{\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}}z={\binom {\mu }{\nu }}\end{aligned}}}$

которые можно легко ввести в крупномасштабный решатель линейного программирования (см. главу 3.4 Galichon (2016) ^[12] ).

Полудискретный случай

В полудискретном случае и представляет собой непрерывное распределение по , в то время как представляет собой дискретное распределение, которое назначает массу вероятности месту . В этом случае мы можем видеть ^[14] , что прямая и двойственная задачи Канторовича соответственно сводятся к: для прямой, где означает, что и , и: для двойственной, что можно переписать как: которая является конечномерной выпуклой задачей оптимизации, которая может быть решена стандартными методами, такими как градиентный спуск . ${\textstyle X=Y=\mathbb {R} ^{d}}$ ${\textstyle \mu }$ ${\textstyle \mathbb {R} ^{d}}$ ${\textstyle \nu =\sum _{j=1}^{J}\nu _{j}\delta _{y_{i}}}$ ${\textstyle \nu _{j}}$ ${\textstyle y_{j}\in \mathbb {R} ^{d}}$ $${\displaystyle \inf \left\{\int _{X}\sum _{j=1}^{J}c(x,y_{j})\,d\gamma _{j}(x),\gamma \in \Gamma (\mu ,\nu )\right\}}$$ ${\textstyle \gamma \in \Gamma \left(\mu ,\nu \right)}$ ${\textstyle \int _{X}d\gamma _{j}\left(x\right)=\nu _{j}}$ ${\textstyle \sum _{j}d\gamma _{j}\left(x\right)=d\mu \left(x\right)}$ $${\displaystyle \sup \left\{\int _{X}\varphi (x)d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}:\psi _{j}+\varphi (x)\leq c\left(x,y_{j}\right)\right\}}$$ $${\displaystyle \sup _{\psi \in \mathbb {R} ^{J}}\left\{\int _{X}\inf _{j}\left\{c\left(x,y_{j}\right)-\psi _{j}\right\}d\mu (x)+\sum _{j=1}^{J}\psi _{j}\nu _{j}\right\}}$$

В случае, когда , можно показать, что множество назначенных определенному сайту является выпуклым многогранником. Полученная конфигурация называется диаграммой мощности . ^[15] ${\textstyle c\left(x,y\right)=\left\vert x-y\right\vert ^{2}/2}$ ${\textstyle x\in \mathbf {X} }$ ${\textstyle j}$

Квадратичный нормальный случай

Предположим частный случай , , и где обратим. Тогда имеем ${\textstyle \mu ={\mathcal {N}}\left(0,\Sigma _{X}\right)}$ ${\textstyle \nu ={\mathcal {N}}\left(0,\Sigma _{Y}\right)}$ ${\textstyle c(x,y)=\left\vert y-Ax\right\vert ^{2}/2}$ ${\textstyle A}$

${\displaystyle \varphi (x)=-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 (y)=-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(x)=(A^{\top })^{-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}x}$

Доказательство этого решения представлено в работе Галихона (2016). ^[12]

Сепарабельные гильбертовы пространства

Пусть — сепарабельное гильбертово пространство . Пусть обозначает совокупность вероятностных мер на , имеющих конечный -й момент; пусть обозначает те элементы, которые являются гауссовски регулярными : если — любая строго положительная гауссовская мера на и , то также. ${\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}$

Пусть , , для . Тогда задача Канторовича имеет единственное решение , и это решение индуцируется оптимальным транспортным отображением: т.е. существует борелевское отображение такое, что ${\displaystyle \mu \in {\mathcal {P}}_{p}^{r}(X)}$ ${\displaystyle \nu \in {\mathcal {P}}_{p}(X)}$ ${\displaystyle c(x,y)=|x-y|^{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 ).}$

Более того, если имеет ограниченную поддержку , то ${\displaystyle \nu }$

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

для -почти всех для некоторого локально липшицевого , -вогнутого и максимального потенциала Канторовича . (Здесь обозначает производную Гато от .) ${\displaystyle \mu }$ ${\displaystyle x\in X}$ ${\displaystyle c}$ ${\displaystyle \varphi }$ ${\displaystyle \nabla \varphi }$ ${\displaystyle \varphi }$

Энтропийная регуляризация

Рассмотрим вариант дискретной задачи выше, где мы добавили член энтропийной регуляризации к целевой функции основной задачи

${\displaystyle {\begin{aligned}&{\text{Minimize }}\sum _{x\in \mathbf {X} ,y\in \mathbf {Y} }\gamma _{xy}c_{xy}+\varepsilon \gamma _{xy}\ln \gamma _{xy}\\[4pt]&{\text{subject to: }}\\[4pt]&\gamma \geq 0\\[4pt]&\sum _{y\in \mathbf {Y} }\gamma _{xy}=\mu _{x},\forall x\in \mathbf {X} \\[4pt]&\sum _{x\in \mathbf {X} }\gamma _{xy}=\nu _{y},\forall y\in \mathbf {Y} \end{aligned}}}$

Можно показать, что двойственная регуляризованная задача имеет вид

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

где, по сравнению с нерегуляризованной версией, «жесткое» ограничение в бывшей двойственной задаче ( ) было заменено «мягким» штрафом этого ограничения (суммой членов ). Условия оптимальности в двойственной задаче можно выразить как ${\textstyle \varphi _{x}+\psi _{y}-c_{xy}\geq 0}$ ${\textstyle \varepsilon \exp \left((\varphi _{x}+\psi _{y}-c_{xy})/\varepsilon \right)}$

Уравнение 5.1: ${\displaystyle \mu _{x}=\sum _{y\in \mathbf {Y} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall x\in \mathbf {X} }$

Уравнение 5.2: ${\displaystyle \nu _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall y\in \mathbf {Y} }$

Обозначая как матрицу члена , решение двойственной задачи эквивалентно поиску двух диагональных положительных матриц и соответствующих размеров и , таких, что и . Существование таких матриц обобщает теорему Синкхорна , и матрицы можно вычислить с помощью алгоритма Синкхорна–Кноппа [ ^16] , который просто состоит из итеративного поиска для решения уравнения 5.1 и решения уравнения 5.2 . Таким образом, алгоритм Синкхорна–Кноппа является алгоритмом спуска по координатам для двойственной регуляризованной задачи. ${\textstyle A}$ ${\textstyle \left\vert \mathbf {X} \right\vert \times \left\vert \mathbf {Y} \right\vert }$ ${\textstyle A_{xy}=\exp \left(-c_{xy}/\varepsilon \right)}$ ${\textstyle D_{1}}$ ${\textstyle D_{2}}$ ${\textstyle \left\vert \mathbf {X} \right\vert }$ ${\textstyle \left\vert \mathbf {Y} \right\vert }$ ${\textstyle D_{1}AD_{2}1_{\left\vert \mathbf {Y} \right\vert }=\mu }$ ${\textstyle \left(D_{1}AD_{2}\right)^{\top }1_{\left\vert \mathbf {X} \right\vert }=\nu }$ ${\textstyle \varphi _{x}}$ ${\textstyle \psi _{y}}$

Приложения

Оптимальный транспорт Монжа-Канторовича нашел широкое применение в различных областях. Среди них:

• Регистрация и деформация изображения ^[17]
• Конструкция рефлектора ^[18]
• Получение информации с помощью теневой съемки и протонной радиографии ^[19]
• Сейсмическая томография и сейсмология отраженных волн ^[20]
• Широкий класс экономического моделирования, который включает в себя валовые заменители собственности (среди прочих, модели соответствия и дискретного выбора ).

Смотрите также

• метрика Вассерштейна
• Транспортная функция
• венгерский алгоритм
• Планирование перевозок
• Расстояние землеройной машины
• Уравнение Монжа-Ампера

Ссылки

1. Г. Монж. Мемуар о теории déblais et des 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 , страницы 666–704, 1781.
2. Шрийвер, Александр , Комбинаторная оптимизация, Берлин; Нью-Йорк: Springer, 2003. ISBN  3540443894 . См. п. 362
3. Айвор Граттан-Гиннесс, Айвор, Справочная энциклопедия истории и философии математических наук, том 1, JHU Press, 2003. См. стр. 831
4. Л. Канторович, О перемещении масс, Доклады АН СССР, 37:199–201, 1942.
5. Седрик Виллани (2003). Темы в оптимальной транспортировке . Американское математическое общество. стр. 66. ISBN 978-0-8218-3312-4.
6. Singiresu S. Rao (2009). Engineering Optimization: Theory and Practice (4-е изд.). John Wiley & Sons. стр. 221. ISBN 978-0-470-18352-6.
7. Фрэнк Л. Хичкок (1941) «Распределение продукта из нескольких источников в многочисленные местоположения», MIT Journal of Mathematics and Physics 20:224–230 MR 0004469.
8. DR Fulkerson (1956) Транспортная проблема Хичкока, корпорация RAND.
9. LR Ford Jr. & DR Fulkerson (1962) § 3.1 в Flows in Networks , стр. 95, Princeton University Press
10. L. Ambrosio, N. Gigli & G. Savaré. Градиентные потоки в метрических пространствах и в пространстве вероятностных мер. Лекции по математике ETH Zürich, Birkhäuser Verlag, Базель. (2005)
11. Angenent, S.; Haker, S.; Tannenbaum, A. (2003). «Минимизация потоков для задачи Монжа–Канторовича». SIAM J. Math. Anal . 35 (1): 61–97. CiteSeerX 10.1.1.424.1064 . doi :10.1137/S0036141002410927. 
12. Галихон, Альфред . Оптимальные методы транспортировки в экономике . Princeton University Press, 2016.
13. Рачев, Светлозар Т. и Людгер Рюшендорф. Проблемы массового транспорта: Том I: Теория . Том 1. Springer, 1998.
14. Сантамброджио, Филиппо. Оптимальный транспорт для прикладных математиков . Birkhäuser Basel, 2016. В частности, глава 6, раздел 4.2.
15. Ауренхаммер, Франц (1987), «Диаграммы мощности: свойства, алгоритмы и приложения», SIAM Journal on Computing , 16 (1): 78–96, doi :10.1137/0216006, MR  0873251.
16. Пейре, Габриэль и Марко Кутури (2019), «Вычислительный оптимальный транспорт: с приложениями к науке о данных», Основы и тенденции в машинном обучении: Том 11: № 5-6, стр. 355–607. DOI: 10.1561/2200000073.
17. Хакер, Стивен; Чжу, Лей; Танненбаум, Аллен; Ангенент, Сигурд (1 декабря 2004 г.). «Оптимальный массовый транспорт для регистрации и деформации». International Journal of Computer Vision . 60 (3): 225–240. CiteSeerX 10.1.1.59.4082 . doi :10.1023/B:VISI.0000036836.66311.97. ISSN  0920-5691. S2CID  13261370. 
18. Glimm, T.; Oliker, V. (1 сентября 2003 г.). «Оптическое проектирование систем с одним отражателем и проблема переноса массы Монжа–Канторовича». Журнал математических наук . 117 (3): 4096–4108. doi :10.1023/A:1024856201493. ISSN  1072-3374. S2CID  8301248.
19. Касим, Мухаммад Фирмансья; Кёрворст, Люк; Ратан, Нарен; Садлер, Джеймс; Чен, Николас; Саверт, Александр; Тринес, Рауль; Бингем, Роберт; Берроуз, Филип Н. (16 февраля 2017 г.). «Количественная теневая съемка и протонная радиография для больших модуляций интенсивности». Physical Review E. 95 ( 2): 023306. arXiv : 1607.04179 . Bibcode : 2017PhRvE..95b3306K. doi : 10.1103/PhysRevE.95.023306. PMID  28297858. S2CID  13326345.
20. Метивье, Людовик (24 февраля 2016 г.). «Измерение несоответствия между сейсмограммами с использованием оптимального расстояния переноса: применение к полной инверсии формы волны». Geophysical Journal International . 205 (1): 345–377. Bibcode : 2016GeoJI.205..345M. doi : 10.1093/gji/ggw014 .

Дальнейшее чтение

• Brualdi, Richard A. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том 108. Кембридж: Cambridge University Press . ISBN 978-0-521-86565-4. Збл  1106.05001.