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

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

исследовал транспортную проблему В 20-е годы А. Н. Толстой одним из первых математически . В 1930 году в I томе сборника «Планирование перевозок» для Народного комиссариата путей сообщения СССР он опубликовал статью «Методы нахождения минимального километража при грузовых перевозках в космосе».

Крупные успехи в этой области были достигнуты во время Второй мировой войны советским математиком и экономистом Леонидом Канторовичем . Следовательно, поставленную задачу иногда называют транспортной задачей Монжа–Канторовича . Формулировка с помощью линейного программирования транспортной задачи также известна как транспортная задача Хичкока – Купманса .

Мотивация

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

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

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

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

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

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

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

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

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

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

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

Предположим, есть $m$ источники $x_{1},\ldots ,x_{m}$ за товар, с $a(x_{i})$ единицы снабжения на $x_{i}$ и $n$ тонет $y_{1},\ldots ,y_{n}$ на товар, со спросом $b(y_{j})$ в $y_{j}$. Если $a(x_{i},\ y_{j})$ стоимость единицы отгрузки из $x_{i}$ к $y_{j}$, найти поток, который удовлетворяет спрос со стороны поставок и минимизирует стоимость потока. Эту задачу в логистике взял на себя Д. Р. Фулкерсон. и в книге «Потоки в сетях» (1962), написанной совместно с Л. Р. Фордом-младшим.

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

Абстрактная формулировка задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Экономическая интерпретация будет более ясной, если перевернуть знаки. Позволять ${\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)}$, задача Монжа–Канторовичапереписывает: $$\sup \left\{\int _{X\times Y}\Phi (x,y)d\gamma (x,y),\gamma \in \Gamma (\mu ,\nu )\right\}$$который имеет двойной : $$\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} }$. Если двойная задача имеет решение, то можно увидеть, что: $$v(y)=\sup _{x}\left\{\Phi (x,y)-u(x)\right\}$$так что ${\textstyle u(x)}$ интерпретируется как равновесная заработная плата работника типа ${\textstyle x}$, и ${\textstyle v(y)}$ интерпретируется как равновесная прибыль фирмы типа ${\textstyle y}$.

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

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

Оптимальная транспортная матрица

Непрерывная оптимальная транспортировка

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

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

$\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).

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

В случае, когда поля ${\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}$ назначение. Тогда целевая функция в основной задаче Канторовича будет равна

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

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

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

и

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

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

$\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$ и $\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)}$, формулировка задачи с помощью линейного программирования такова:

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

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

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

В случае, когда ${\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}$ является обратимым. Тогда у человека есть

$\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$

$\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$

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

Доказательство этого решения содержится в Galichon (2016).

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

Позволять $X$ — сепарабельное гильбертово пространство . Позволять ${\mathcal {P}}_{p}(X)$ обозначаем совокупность вероятностных мер на $X$ которые имеют конечный $p$-й момент; позволять ${\mathcal {P}}_{p}^{r}(X)$ обозначим эти элементы $\mu \in {\mathcal {P}}_{p}(X)$ которые являются регулярными по Гауссу : если $g$ — любая строго положительная гауссова мера на $X$ и $g(N)=0$, затем $\mu (N)=0$ также.

Позволять $\mu \in {\mathcal {P}}_{p}^{r}(X)$, $\nu \in {\mathcal {P}}_{p}(X)$, $c(x,y)=|x-y|^{p}/p$ для $p\in (1,\infty ),p^{-1}+q^{-1}=1$. Тогда задача Канторовича имеет единственное решение $\kappa$, и это решение индуцировано оптимальным транспортным отображением, т. е. существует борелевское отображение $r\in L^{p}(X,\mu ;X)$ такой, что

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

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

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

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

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

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

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

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

$\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: $\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: $\nu _{y}=\sum _{x\in \mathbf {X} }\exp \left({\frac {\varphi _{x}+\psi _{y}-c_{xy}}{\varepsilon }}\right)~\forall y\in \mathbf {Y}$

Обозначая ${\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}}$ решить уравнение 5.1 и ${\textstyle \psi _{y}}$ решить уравнение 5.2 . Таким образом, алгоритм Синкхорна – Кноппа представляет собой алгоритм спуска по координатам для двойной регуляризованной задачи.

Приложения

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

• изображения Регистрация и деформация
• Дизайн отражателя
• Получение информации из теневой и протонной радиографии.
• Сейсмическая томография и сейсмология отражений
• Широкий класс экономического моделирования, включающий валовые заменители собственности (среди прочего, модели соответствия и дискретного выбора ).

См. также

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

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

• Бруальди, Ричард А. (2006). Комбинаторные матричные классы . Энциклопедия математики и ее приложений. Том. 108. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-86565-4 . Установить   1106.05001 .