Проблема максимального потока

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

Определения

Дана транспортная сеть $\,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$ единиц потока.

Суть задачи — минимизировать общую стоимость потока:

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

Решения

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

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

Ссылки

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

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1