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

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

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

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

Мотивация [ править ]

Шахты и фабрики [ править ]

Предположим, что у нас есть набор из n шахт, добывающих железную руду, и набор из n заводов, которые используют железную руду, добываемую на рудниках. Предположим , ради аргумента , что эти шахты и фабрики образуют два непересекающихся подмножества M и F в евклидовой плоскости R ² . Предположим также, что у нас есть функция стоимости c  :  R ²  ×  R ²  → [0, ∞), так что c ( x ,  y ) - это стоимость перевозки одной партии железа из x в y.. Для простоты мы игнорируем время, затраченное на транспортировку. Мы также предполагаем, что каждая шахта может поставлять продукцию только на одну фабрику (без разделения партий) и что для каждой фабрики требуется ровно одна партия для работы (фабрики не могут работать с половинной или двойной мощностью). Сделав вышеуказанные предположения, А транспортный план является взаимно однозначным соответствием Т  : М → Ж . Другими словами, каждая шахта m ∈ M снабжает ровно одну фабрику T ( m ) ∈ F, и каждая фабрика снабжается ровно одной шахтой. Мы хотим найти оптимальный транспортный план , план T которогоОбщая стоимость

${\ Displaystyle с (Т): = \ сумма _ {м \ в М} с (м, Т (м))}$

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

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

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

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

Если функция затрат пропорциональна евклидова расстояния ( с ( х ,  у ) = α | х  -  у |) , то эти два кандидата являются одновременно оптимальными. Если, с другой стороны, мы выберем строго выпуклую функцию стоимости, пропорциональную квадрату евклидова расстояния ( c ( x ,  y ) =  α | x  -  y | ² ), то опция «много маленьких ходов» станет уникальным минимизатором. .

Проблема Хичкока [ править ]

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

Предположим, что есть m источников для товара, с единицами предложения в x _i и n потребителями для товара, со спросом в y _j . Если - удельная стоимость перевозки от x _i до y _j , найдите поток, который удовлетворяет спрос на поставки и минимизирует затраты потока. Эта проблема логистики была рассмотрена Д. Р. Фулкерсоном ^[8] и в книге « Потоки в сетях» (1962), написанной вместе с Л. Р. Фордом-младшим . ^[9]${\ displaystyle x_ {1}, \ ldots, x_ {m}}$${\ Displaystyle а (х_ {я})}$${\ displaystyle y_ {1}, \ ldots, y_ {n}}$${\ displaystyle b (y_ {j})}$${\ Displaystyle а (х_ {я}, \ у_ {j})}$

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

Абстрактная постановка задачи [ править ]

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

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

Пусть X и Y - два сепарабельных метрических пространства такие, что любая вероятностная мера на X (или Y ) является мерой Радона (т. Е. Они являются пространствами Радона ). Пусть c  : X × Y → [0, ∞] - измеримая по Борелю функция . Учитывая вероятностные меры μ на X и ν на Y , формулировка Монжем оптимальной транспортной задачи состоит в том, чтобы найти транспортное отображение T  : X → Yчто реализует инфимум

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

где Т _* ( μ ) обозначает толчок вперед по ц от Т . Отображение T, которое достигает этого нижнего предела ( то есть делает его минимальным, а не нижним пределом), называется «оптимальным транспортным отображением».

Формулировка Монжем оптимальной транспортной задачи может быть некорректной, потому что иногда не существует T, удовлетворяющего T _∗ ( μ ) = ν : это происходит, например, когда μ является мерой Дирака, а ν - нет.

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

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

где Γ ( μ , ν ) обозначает совокупность всех вероятностных мер на X × Y с маргинальными μ на X и v , на Y . Можно показать ^[10], что минимизатор для этой проблемы всегда существует, когда функция стоимости c полунепрерывна снизу и Γ ( μ ,  ν ) является плотным набором мер (что гарантируется для пространств Радона X и Y ). (Сравните эту формулировку с определением метрики Вассерштейна W ₁на пространстве вероятностных мер.) Построение градиентного спуска для решения проблемы Монжа – Канторовича было дано Сигурдом Ангенентом , Стивеном Хакером и Алленом Танненбаумом . ^[11]

Формула двойственности [ править ]

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

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

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

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

Экономическая интерпретация [ править ]

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

который имеет двойной  :где нижняя грань пробегает ограниченную и непрерывную функцию и . Если у двойной проблемы есть решение, можно увидеть следующее:${\displaystyle \textstyle u:X\rightarrow \mathbf {R} }$${\displaystyle \textstyle v:Y\rightarrow \mathbf {R} }$таким образом, это интерпретируется как равновесная заработная плата работника определенного типа и интерпретируется как равновесная прибыль фирмы определенного типа . ^[12]${\displaystyle \textstyle u\left(x\right)}$${\displaystyle \textstyle x}$${\displaystyle \textstyle v\left(y\right)}$${\displaystyle \textstyle y}$

Решение проблемы [ править ]

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

Для , пусть обозначает набор вероятностных мер на, которые имеют конечный -й момент . Позвольте и пусть , где - выпуклая функция .${\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(x-y)}$${\displaystyle h:\mathbf {R} \rightarrow [0,\infty )}$

1. Если не атом , то есть, если функция распределения из является непрерывной функцией , то оптимальная транспортная карта. Это единственная оптимальная транспортная карта, если она строго выпуклая.${\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. У нас есть

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

Доказательство этого решения содержится в Rachev & Rüschendorf (1998). ^[13]

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

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

и ограничение выражается как${\displaystyle \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.} }$

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

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

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

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

Полудискретный случай [ править ]

В полудискретном случае и является непрерывным распределением по , а - дискретным распределением, которое присваивает вероятностную массу сайту . В этом случае мы видим ^[15], что прямая и двойственная задачи Канторовича сводятся соответственно к:${\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}}$

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

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

Разделимые гильбертовы пространства [ править ]

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

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

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

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

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

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

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

${\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 }}\right)+\epsilon }$

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

Уравнение 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} }$

Уравнение 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} }$

Обозначая как матрицу члена , решение двойственного, следовательно, эквивалентно поиску двух диагональных положительных матриц и соответствующих размеров и , таких что и . Существование таких матриц обобщает теорему Sinkhorn в и матрицы могут быть вычислены с использованием алгоритма Sinkhorn-Knopp , ^[17] , который просто состоит из итеративно ищет , чтобы решить уравнение 5.1 , и решить уравнение 5.2 . Таким образом, алгоритм Синкхорна-Кноппа представляет собой алгоритм координатного спуска для двойной регуляризованной задачи.${\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}}$

Приложения [ править ]

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

• Регистрация и деформация изображения ^[18]
• Конструкция отражателя ^[19]
• Получение информации из теневой и протонной радиографии ^[20]
• Сейсмическая томография и сейсмология отражений ^[21]

См. Также [ править ]

Викискладе есть медиафайлы, связанные с теорией транспорта .

• Метрика Вассерштейна
• Транспортная функция
• Венгерский алгоритм
• Планирование транспортировки
• Дистанция земного движителя

Ссылки [ править ]

Дальнейшее чтение [ править ]

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