Задача о потоке с минимальной стоимостью

Задача потока с минимальной стоимостью ( MCFP ) — это задача оптимизации и решения, позволяющая найти самый дешевый способ отправки определенного количества потока через потоковую сеть . Типичное применение этой проблемы включает в себя поиск наилучшего маршрута доставки от завода до склада, где дорожная сеть имеет определенную пропускную способность и затраты. Задача о потоке с минимальной стоимостью является одной из наиболее фундаментальных среди всех задач о потоках и циркуляции, поскольку большинство других подобных задач можно представить как задачу о потоке с минимальной стоимостью, а также то, что ее можно эффективно решить с использованием сетевого симплексного алгоритма .

Определение

Сеть потоков представляет собой ориентированный граф. $G=(V,E)$ с исходной вершиной $s\in V$ и вершина стока $t\in V$ , где каждое ребро $(u,v)\in E$ имеет емкость $c(u,v)>0$ , поток $f(u,v)$ и стоимость $a(u,v)$ , причем большинство алгоритмов потока с минимальной стоимостью поддерживают ребра с отрицательными затратами. Стоимость отправки этого потока по ребру $(u,v)$ является $f(u,v)\cdot a(u,v)$ . Проблема требует большого потока $d$ для отправки из источника $s$ тонуть $t$ .

Определение задачи состоит в том, чтобы минимизировать общую стоимость потока по всем ребрам:

\sum _{(u,v)\in E}a(u,v)\cdot f(u,v)

с ограничениями

Ограничения мощности :	$\,f(u,v)\leq c(u,v)$
Косая симметрия :	$\,f(u,v)=-f(v,u)$
Сохранение потока :	$\,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t$
Требуемый поток :	$\,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d$

Связь с другими проблемами

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

При использовании некоторых решений найти минимальную стоимость максимального расхода проще простого. Если нет, то максимальный поток можно найти, выполнив двоичный поиск по $d$ .

Связанной с этим проблемой является задача циркуляции минимальных затрат , которую можно использовать для решения потока минимальных затрат. Задача циркуляции минимальных издержек не имеет источника и стока; вместо этого он имеет стоимость, а также нижнюю и верхнюю границы на каждом ребре и ищет объемы потока в пределах заданных границ, которые уравновешивают поток в каждой вершине и минимизируют сумму по ребрам стоимости, умноженной на поток. Любой экземпляр потока с минимальной стоимостью можно преобразовать в экземпляр циркуляции с минимальной стоимостью, установив нижнюю границу всех ребер на ноль, а затем создав дополнительное ребро из стока. $t$ к источнику $s$ , с емкостью $c(t,s)=d$ и нижняя граница $l(t,s)=d$ , заставляя общий поток из $s$ к $t$ также быть $d$ .

Следующие проблемы являются частными случаями задачи о минимальном потоке затрат (мы по очереди приводим краткие описания каждого применимого сокращения): ^[1]

Задача о кратчайшем пути (один источник). Требовать, чтобы реальное решение проблемы потока с минимальной стоимостью отправляло одну единицу потока из назначенного источника. $s$ в назначенную раковину $t$ . Дайте всем ребрам бесконечную емкость.
Проблема максимального потока . Выберите большой спрос $d$ (достаточно большой, чтобы превысить максимальный поток; например, сумма мощностей исходной вершины). Установите стоимость всех ребер в экземпляре максимального потока равным нулю и введите новое ребро от источника до приемника со стоимостью единицы и мощностью. $d$ .
Проблема с назначением . Предположим, что каждая часть множества в двуразделе имеет $n$ вершины и обозначаем биделение через $(X,Y)$ . Дайте каждому $x\in X$ поставлять $1/n$ и дать каждому $y\in Y$ требовать $1/n$ . Каждое ребро должно иметь единичную емкость.

Решения

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

Кроме того, существует множество комбинаторных алгоритмов. ^[1] Некоторые из них являются обобщениями алгоритмов максимального потока , другие используют совершенно другие подходы.

Известные фундаментальные алгоритмы (имеют множество вариаций):

Отмена цикла : общий основной метод. ^[2]
Отмена резки : общий двойной метод. ^[3]^[4]
Отмена минимального среднего цикла : простой сильно полиномиальный алгоритм. ^[5]
Последовательный кратчайший путь и масштабирование мощности : двойственные методы, которые можно рассматривать как обобщение алгоритма Форда – Фулкерсона . ^[6]
Масштабирование стоимости : примитивно-двойственный подход, который можно рассматривать как обобщение алгоритма push-relabel . ^[7]
Сетевой симплексный алгоритм : специализированная версия линейного программирования симплексного метода . ^[8]
Нестандартный алгоритм Фулкерсона доктора

Приложение

Двустороннее сопоставление минимального веса

Учитывая двудольный граф $G = (A \cup B, E)$ , цель состоит в том, чтобы найти паросочетание максимальной мощности в G , которое имеет минимальную стоимость. Пусть w : E → R — весовая функция на ребрах E . Задача двудольного сопоставления минимального веса или задача назначения состоит в том, чтобы найти идеальное паросочетание $M \subseteq E$ , общий вес которого минимизирован. Идея состоит в том, чтобы свести эту проблему к проблеме сетевого потока.

Пусть $G' = (V' знак равно А \cup B, E' знак равно E)$ . Присвойте пропускную способность всем ребрам в E ' равную 1. Добавьте исходную вершину s , соедините ее со всеми вершинами в A ' и добавьте сток. вершину t и соедините все вершины внутри группы B′ с этой вершиной. Емкость всех новых ребер равна 1, а их стоимость равна 0. Доказано, что в G существует поток с минимальной стоимостью существует идеальное двудольное паросочетание минимального веса тогда и только тогда, когда в G' . ^[1]

См. также

Ссылки

^ Jump up to: ^а ^б ^с Равиндра К. Ахуджа ; Томас Л. Маньянти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис-Холл, Inc. ISBN 978-0-13-617549-0 .
^ Мортон Кляйн (1967). «Основной метод минимальных потоков затрат с применением к задачам назначения и транспортировки». Наука управления . 14 (3): 205–220. CiteSeerX 10.1.1.228.7696 . дои : 10.1287/mnsc.14.3.205 .
^ Рафаэль Хассин (1983). «Проблема потока минимальной стоимости: объединяющий подход к существующим алгоритмам и новый алгоритм поиска по дереву». Математическое программирование . 25 : 228–239. дои : 10.1007/bf02591772 .
^ Томас Р. Эрволина и С. Томас МакКормик (1993). «Два сильно полиномиальных алгоритма отмены сокращения для сетевого потока с минимальной стоимостью» . Дискретная прикладная математика . 4 : 133–165. дои : 10.1016/0166-218x(93)90025-j .
^ Эндрю В. Голдберг и Роберт Э. Тарьян (1989). «Нахождение минимальных тиражей путем отмены отрицательных циклов». Журнал АКМ . 36 (4): 873–886. дои : 10.1145/76359.76368 .
^ Джек Эдмондс и Ричард М. Карп (1972). «Теоретические улучшения алгоритмической эффективности решения задач сетевых потоков» . Журнал АКМ . 19 (2): 248–264. дои : 10.1145/321694.321699 .
^ Голдберг, Эндрю В. и Тарьян, Роберт Э. (1990). «Нахождение минимальных стоимостных тиражей методом последовательного приближения». Математика исследования операций . 15 (3): 430–466. дои : 10.1287/moor.15.3.430 .
^ Джеймс Б. Орлин (1997). «Симплекс-алгоритм простой сети с полиномиальным временем для потоков с минимальной стоимостью». Математическое программирование . 78 (2): 109–129. дои : 10.1007/bf02614365 . hdl : 1721.1/2584 .

Внешние ссылки

[AMO93-1] Jump up to: ^а ^б ^с Равиндра К. Ахуджа ; Томас Л. Маньянти и Джеймс Б. Орлин (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис-Холл, Inc. ISBN 978-0-13-617549-0 .

[K67-2] Мортон Кляйн (1967). «Основной метод минимальных потоков затрат с применением к задачам назначения и транспортировки». Наука управления . 14 (3): 205–220. CiteSeerX 10.1.1.228.7696 . дои : 10.1287/mnsc.14.3.205 .

[H83-3] Рафаэль Хассин (1983). «Проблема потока минимальной стоимости: объединяющий подход к существующим алгоритмам и новый алгоритм поиска по дереву». Математическое программирование . 25 : 228–239. дои : 10.1007/bf02591772 .

[EM93-4] Томас Р. Эрволина и С. Томас МакКормик (1993). «Два сильно полиномиальных алгоритма отмены сокращения для сетевого потока с минимальной стоимостью» . Дискретная прикладная математика . 4 : 133–165. дои : 10.1016/0166-218x(93)90025-j .

[GT89-5] Эндрю В. Голдберг и Роберт Э. Тарьян (1989). «Нахождение минимальных тиражей путем отмены отрицательных циклов». Журнал АКМ . 36 (4): 873–886. дои : 10.1145/76359.76368 .

[EK72-6] Джек Эдмондс и Ричард М. Карп (1972). «Теоретические улучшения алгоритмической эффективности решения задач сетевых потоков» . Журнал АКМ . 19 (2): 248–264. дои : 10.1145/321694.321699 .

[GT90-7] Голдберг, Эндрю В. и Тарьян, Роберт Э. (1990). «Нахождение минимальных стоимостных тиражей методом последовательного приближения». Математика исследования операций . 15 (3): 430–466. дои : 10.1287/moor.15.3.430 .

[O97-8] Джеймс Б. Орлин (1997). «Симплекс-алгоритм простой сети с полиномиальным временем для потоков с минимальной стоимостью». Математическое программирование . 78 (2): 109–129. дои : 10.1007/bf02614365 . hdl : 1721.1/2584 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]