Поток минимальной стоимости

Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.

Определения

Дана транспортная сеть $\,G(V,E)$ с источником $s \in V$ и стоком $t \in V$, где ребра $(u,v) \in E$ имеют пропускную способность $\,c(u,v)$, поток $\,f(u,v)$ и цену $\,a(u,v)$. Цена пересылки потока $f(u,v) \cdot a(u,v)$. Необходимо переслать $\,d$ единиц потока.

Суть задачи — найти поток f(u, v), минимизирующий его общую стоимость:

$\sum_{u,v \in V} a(u,v) \cdot f(u,v)$

Накладываются следующие условия:

Ограничение пропускной способности:	$\ f(u,v) \le c(u,v)$. Поток не может превысить пропускную способность.
Антисимметричность:	$\ f(u,v) = - f(v,u)$. Поток из $\ u$ в $\ v$ должен быть противоположным потоку из $\ v$ в $\ u$.
Сохранение потока:	$\ \sum_{w \in V} f(u,w) = 0$.
Необходимый поток:	$\,\sum_{w \in V} f(s,w) = d$

Отношение к другим задачам

Другой вариант этой задачи — найти максимальный поток имеющий минимальную цену среди максимальных.

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

Решения

• Задача о потоке минимальной стоимости может быть решена, используя линейное программирование.
• Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда.
• Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
• Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.

Ссылки

• Визуализатор алгоритма нахождения максимального потока минимальной стоимости
• Реализация поиска максимального потока минимальной стоимости на Java

См. также

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

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4