Теория транспорта (математика) - Transportation theory (mathematics)

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

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

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

Мотивация

Шахты и фабрики

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

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

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

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

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

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

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

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

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

Предположим, есть м источники ${displaystyle x_{1},...x_{m}}$ для товара, с ${displaystyle a(x_{i})}$ единиц поставки в Икс_я и п раковины ${displaystyle y_{1},...y_{n}}$ на товар, со спросом ${displaystyle b(y_{j})}$ в у_j. Если ${displaystyle a(x_{i}, y_{j})}$ это удельная стоимость отгрузки из Икс_я к у_j, найдите поток, который удовлетворяет спрос со стороны поставщиков и минимизирует стоимость потока.

Эту задачу в логистике взяли на себя Д. Р. Фулкерсон^[8] и в книге Потоки в сетях (1962) написано с Л. Р. Форд-младший.^[9]

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

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

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

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

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

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

куда Т_∗(μ) обозначает продвигать μ по Т. Карта Т который достигает этого нижнего предела (т.е. делает это минимум вместо инфимума) называется «оптимальной транспортной картой».

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

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

${displaystyle inf left{left.int _{X imes Y}c(x,y),mathrm {d} gamma (x,y)ight|gamma in Gamma (mu ,u )ight},}$

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

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

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

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

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

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

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

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

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

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

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

1. Если ${displaystyle mu }$ не имеет атом, т.е. если кумулятивная функция распределения ${displaystyle F_{mu }=mathbf {R} ightarrow [0,1]}$ из ${displaystyle mu }$ это непрерывная функция, тогда ${displaystyle F_{u }^{-1}circ F_{mu }:mathbf {R} o mathbf {R} }$ оптимальная транспортная карта. Это единственная оптимальная транспортная карта, если ${displaystyle h}$ строго выпуклый.
2. У нас есть

${displaystyle min _{gamma in Gamma (mu ,u )}int _{mathbf {R} ^{2}}c(x,y),mathrm {d} gamma (x,y)=int _{0}^{1}cleft(F_{mu }^{-1}(s),F_{u }^{-1}(s)ight),mathrm {d} s.}$

Доказательство этого решения приведено в.^[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 u in {mathcal {P}}_{p}(X)}$, ${displaystyle c(x,y)=|x-y|^{p}/p}$ за ${displaystyle pin (1,infty ),p^{-1}+q^{-1}=1}$. Тогда проблема Канторовича имеет единственное решение ${displaystyle kappa }$, и это решение индуцировано оптимальным транспортным отображением: т.е. существует борелевское отображение ${displaystyle rin L^{p}(X,mu ;X)}$ такой, что

${displaystyle kappa =(mathrm {id} _{X} imes r)_{*}(mu )in Gamma (mu ,u ).}$

Более того, если ${displaystyle u }$ имеет ограниченный поддерживать, тогда

${displaystyle r(x)=x-|abla varphi (x)|^{q-2}abla varphi (x)}$

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

Приложения

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

• Регистрация изображения и деформация ^[13]
• Дизайн отражателя ^[14]
• Получение информации из тенография и протонная радиография ^[15]
• Сейсмическая томография и сейсмология отражений ^[16]

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

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

Рекомендации

1. Г. Монж. Mémoire sur la theorie des 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. Шрайвер, Александр, Комбинаторная оптимизация, Берлин; Нью-Йорк: Спрингер, 2003. ISBN  3540443894. Ср. стр.362
3. Айвор Граттан-Гиннесс, Айвор, Сопутствующая энциклопедия истории и философии математических наук, Том 1, JHU Press, 2003. Ср. стр.831
4. Л. Канторович. О перемещении масс. К.Р. (Доклады) Акад. Sci. УРСС (Н.С.), 37: 199–201, 1942.
5. Седрик Виллани (2003). Темы оптимального транспорта. American Mathematical Soc. п. 66. ISBN  978-0-8218-3312-4.
6. Сингиресу С. Рао (2009). Инженерная оптимизация: теория и практика (4-е изд.). Джон Вили и сыновья. п. 221. ISBN  978-0-470-18352-6.
7. Фрэнк Л. Хичкок (1941) «Распространение продукта из нескольких источников по многочисленным местам», Журнал математики и физики Массачусетского технологического института 20:224–230 МИСТЕР0004469.
8. Д. Р. Фулкерсон (1956) Транспортная проблема Хичкока, Корпорация РЭНД.
9. Л. Р. Форд-младший & Д. Р. Фулкерсон (1962) § 3.1 в Потоки в сетях, стр.95, Princeton University Press
10. Л. Амбросио, Н. Джильи и Г. Саваре. Градиентные потоки в метрических пространствах и в пространстве вероятностных мер. Лекции по математике ETH Zürich, Birkhäuser Verlag, Базель. (2005)
11. Angenent, S .; Haker, S .; Танненбаум, А. (2003). «Минимизирующие потоки для задачи Монжа – Канторовича». SIAM J. Math. Анальный. 35 (1): 61–97. CiteSeerX  10.1.1.424.1064. Дои:10.1137 / S0036141002410927.
12. Рачев, Светлозар Т. и Людгер Рюшендорф. Проблемы общественного транспорта: Том I: Теория. Vol. 1. Springer, 1998.
13. Хейкер, Стивен; Чжу, Лэй; Танненбаум, Аллен; Ангенент, Сигурд (1 декабря 2004 г.). «Оптимальный массовый транспорт для регистрации и деформации». Международный журнал компьютерного зрения. 60 (3): 225–240. CiteSeerX  10.1.1.59.4082. Дои:10.1023 / B: VISI.0000036836.66311.97. ISSN  0920-5691. S2CID  13261370.
14. Glimm, T .; Оликер, В. (1 сентября 2003 г.). «Оптический дизайн одноотражательных систем и проблема массопереноса Монжа – Канторовича». Журнал математических наук. 117 (3): 4096–4108. Дои:10.1023 / А: 1024856201493. ISSN  1072-3374. S2CID  8301248.
15. Касим, Мухаммад Фирмансьях; Керворст, Люк; Ратан, Нарен; Сэдлер, Джеймс; Чен, Николай; Сэверт, Александр; Тринес, Рауль; Бингхэм, Роберт; Берроуз, Филип Н. (16 февраля 2017 г.). «Количественная теневая и протонная радиография для модуляции большой интенсивности». Физический обзор E. 95 (2): 023306. arXiv:1607.04179. Bibcode:2017PhRvE..95b3306K. Дои:10.1103 / PhysRevE.95.023306. PMID  28297858. S2CID  13326345.
16. Метивье, Людовик (24 февраля 2016 г.). «Измерение несоответствия между сейсмограммами с использованием оптимального расстояния транспортировки: приложение для полной инверсии формы волны». Международный геофизический журнал. 205 (1): 345–377. Bibcode:2016GeoJI.205..345M. Дои:10.1093 / gji / ggw014.

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

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