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

редактировать

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

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

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

Содержание

1 Мотивация
- 1.1 Шахты и фабрики
- 1.2 Подвижные книги: важность функции стоимости
2 Проблема Хичкока
3 Абстрактная формулировка проблемы
- 3.1 Формулировки Монжа и Канторовича
- 3.2 Формула двойственности
4 Решение задачи
- 4.1 Оптимальная транспортировка по реальной прямой
- 4.2 Разделимые гильбертовы пространства
5 Приложения
6 См. также
7 Ссылки
8 Дополнительная литература

Мотивация

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

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

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

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

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

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

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

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

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

Задача Хичкока

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

Предположим, имеется m источников

x 1,... xm {\ displaystyle x_ {1},... x_ {m}}

{\ displaystyle x_ {1},... x_ {m}}

для товара, с

a (xi) {\ displaystyle a (x_ {i})}

{\ displaystyle a (x_ {i})}

единиц питания в x i и n приемниках

y 1,... yn {\ displaystyle y_ {1},... y_ {n}}

{\ displaystyle y_ {1},... y_ {n}}

для товара со спросом

b (yj) {\ displaystyle b (y_ {j})}

{\ displaystyle b (y_ {j})}

при y j. Если

a (xi, yj) {\ displaystyle a (x_ {i}, \ y_ {j})}

{\ displaystyle a (x_ {i}, \ y_ {j})}

- это удельная стоимость доставки из x i в y j, найти поток, который удовлетворяет спрос на поставки и минимизирует затраты потока.

Эту задачу в логистике взял на себя D. Р. Фулкерсон и в книге «Потоки в сетях» (1962), написанной с Л. Р. Форду младшему.

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

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

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

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

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

inf {∫ X c (x, T (x)) d μ (x) | T * (μ) знак равно ν}, {\ Displaystyle \ Inf \ left \ {\ left. \ Int _ {X} с (х, Т (х)) \, \ mathrm {d} \ mu (x) \; \ right | \; T _ {*} (\ mu) = \ nu \ right \},}

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

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

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

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

inf {∫ X × Y c (x, y) d γ (x, y) | γ ∈ Γ (μ, ν)}, {\ displaystyle \ inf \ left \ {\ left. \ int _ {X \ times Y} с (x, y) \, \ mathrm {d} \ gamma (x, y) \ right | \ gamma \ in \ Gamma (\ mu, \ nu) \ right \},}

\ 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 и ν на Y. Можно показать, что минимизатор для этой задачи всегда существует, когда функция стоимости c полунепрерывна снизу и Γ (μ, ν) является плотным набором меры (что гарантировано для радоновских пространств X и Y). (Сравните эту формулировку с определением метрики Вассерштейна W1на пространстве вероятностных мер.) Формулировка градиентного спуска для решения проблемы Монжа – Канторовича была дана Сигурдом Ангенентом, Стивен Хейкер и Аллен Танненбаум.

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

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

sup (∫ X φ (x) d μ (x) + ∫ Y ψ ( y) d ν (y)), {\ displaystyle \ sup \ left (\ int _ {X} \ varphi (x) \, \ mathrm {d} \ mu (x) + \ int _ {Y} \ psi ( y) \, \ mathrm {d} \ nu (y) \ right),}

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

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

φ (x) + ψ (y) ≤ c (x, y). {\ displaystyle \ varphi (x) + \ psi (y) \ leq c (x, y).}

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

Решение задачи

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

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

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

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

Если $μ {\ displaystyle \ mu}$ $\ mu$ не имеет атома, т.е. если кумулятивная функция распределения $F μ = R → [0, 1] {\ displaystyle F _ {\ mu} = \ mathbf {R} \ rightarrow [0,1]}$ ${\ displaystyle F _ {\ mu} = \ mathbf {R} \ rightarrow [0,1]}$ из $μ {\ displaystyle \ mu}$ $\ mu$ - это непрерывная функция, тогда $F ν - 1 ∘ F μ: R → R {\ displaystyle F _ {\ nu} ^ {- 1} \ circ F _ {\ mu}: \ mathbf {R} \ to \ mathbf {R}}$ $F _ {{\ nu }} ^ {{- 1}} \ circ F _ {{\ mu}}: {\ mathbf {R}} \ to {\ mathbf {R}}$ оптимальная транспортная карта. Это единственная оптимальная транспортная карта, если $h {\ displaystyle h}$ $h$ строго выпукло.
Мы имеем

min γ ∈ Γ (μ, ν) ∫ R 2 c (x, y) d γ (x, y) = ∫ 0 1 c (F μ - 1 (s), F ν - 1 (s)) ds. {\ 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.}

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

Доказательство этого решения приведено в.

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

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

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

κ = (id X × r) ∗ (μ) ∈ Γ (μ, ν). {\ displaystyle \ kappa = (\ mathrm {id} _ {X} \ times r) _ {*} (\ mu) \ in \ Gamma (\ mu, \ nu).}

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

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

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

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

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

Приложения

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

Регистрация изображения и деформация
Дизайн отражателя
Получение информации из теневой съемки и протонной радиографии
Сейсмической томографии и сейсмология отражений

См. Также

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

Ссылки

Дополнительная литература

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