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

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

Определения

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

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

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

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

Ограничение пропускной способности:	$0\leqslant f(u,v)\leqslant 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$.

Примечательно, что для $d=1$, задача нахождения потока минимальной стоимости соответствует задаче о поиске кратчайшего пути. В случае же, когда стоимость $a(e)=0$ для всех рёбер графа, задача может быть решена адаптированными алгоритмами поиска максимального потока:

1. Как только $|f|\geqslant d$ впервые, останови алгоритм.
2. Пусть $p$ величина последнего дополнения потока.
3. Замени последний поток на поток со значением $p-(|f|-d)$.

Существует также и альтернативный вариант решения задачи с нулевой стоимостью рёбер:

1. Создай новую вершину-источник $s'$.
2. Добавь ребро $e'=(s',s)$ с пропускной способностью $c(e')=d$.
3. Таким образом максимальный поток будет ограничен $d$.

Решения

• Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования.
• Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда. Для доказательства работы алгоритма покажем, что поток $f$ графа $G$ не является потоком минимальной стоимости пока остаточная сеть графа $G_{f}$ содержит отрицательный цикл $C$. Пусть $f^{*}$ - поток графа $G$ такой, что $l(f^{*})<l(f)$ и, следовательно, оба потока отличны друг от друга. Для всех рёбер $e\in E$ обозначим $f'(e)=f^{*}(e)-f(e)$ и получим $f'$ - циклический поток. Так как $f'$ образован из максимум $m'<m$ циклов $f'_{i}$ $(1\leqslant i\leqslant m')$, справедливо следующее: $l(f')=l(f^{*})-l(f)=\sum _{1\leqslant i\leqslant m'}l(f'_{i})$, а значит, существует такой $j$, что $l(f'_{j})<0$. Для оптимизиации алгоритма можно выбирать каждую итерацию циклы с минимальной средней стоимостью ${\overline {l}}(C)={\frac {l(C)}{|C|}}={\frac {\sum _{e\in C}l(e)}{|C|}}$. Для доказательства времени работы алгоритма разобьем ход его выполнения на фазы, каждая из которых будет состоять из отдельных итераций. Пусть $f$ - поток к началу $i$-той фазы. Фаза $i$ считается завершенной, когда найден поток $g$ такой, что $\mu (g)\leqslant (1-1/n)\cdot \mu (f)$ или $\mu (g)\leqslant 0$, где $\mu (f)=-{\overline {l}}(C)$. При $\mu (g)\leqslant 0$ алгоритм прекращает работу. Далее пусть $\mu _{0}$ - значение $\mu$ к началу первой фазы и $\mu _{i}$ - значение $\mu$ к началу $i$-той фазы ($1\leqslant i\leqslant T$). Таким образом действительно: $\mu _{i}\leqslant (1-1/n)\cdot \mu _{i-1}\leqslant {\frac {\mu _{i-1}}{e^{1/n}}}$, а также $\mu _{0}\leqslant L=\sum _{e\in E}|l(e)|$. Вследствие свойства целочисленности $\mu _{T-1}\geqslant 1/n$ следует $T-1\leqslant \log _{e^{1/n}}(nL)={\frac {\ln(nL)}{\ln(e^{1/n})}}=n\ln(nL)$ и $T\leqslant n\ln(nL)+1$. Итерации условно можно разбить на несколько видов: Тип 1 - цикл $C$ содержит только рёбра с негативной стоимостью и Тип 2 - цикл $C$ содержит минимум одно ребро с положительной стоимостью. При каждой итерации первого типа будет "насыщено" и удалено хотя бы одно ребро. При этом все образованные рёбра будут иметь положительную стоимость (так как имеют обратное направление в остаточной сети). Таким образом алгоритм завершится после как минимум $m$ последовательных итераций первого типа. Если же в фазе содержатся более $m$ итераций, после $m-1$ итераций максимум будет выполнена итерация второго типа. Покажем однако, что такое невозможно: Пусть $g$ - поток первой итерации второго типа. Заметим, что действительно $\forall e\in E(G_{g}):l(e)\geqslant -\mu (f)$, т.е. нет новых рёбер с отрицательной стоимостью. Пусть $C$ - цикл в $G_{g}$ с минимальным ${\overline {l}}(C)$ и $H$ - рёбра с отрицательной стоимостью в $C$: $\mu (g)=\sum _{e\in C}{\frac {-l(e)}{|C|}}\leqslant \sum _{e\in H}{\frac {-l(e)}{|C|}}\leqslant |H|\cdot {\frac {\mu (f)}{|C|}}$. Из $|H|\leqslant |C|-1$ следует $|H|/|C|\leqslant 1-1/|C|\leqslant 1-1/n$. Таким образом $\mu (g)\leqslant (1-1/n)\cdot \mu (f)$. Противоречие - мы уже достигли конца фазы, а значит итераций второго типа не существует и каждая фаза заканчивается через $m-1$ итераций первого типа. Цикл с минимальным средним весом может быть найден за $O(|V||E|)$. Доказательство: Пусть $d_{k}(v)$ - стоимость самого выгодного пути к $v\in V$ через ровно $k$ рёбер, тогда действительно $d_{0}(v)=0$ и $d_{k+1}(v)=\min _{e=(w,v)\in E_{f}}(d_{k}(w)+l(e))$. Выходит, что все значения $d_{k}(v)$ можно подсчитать за $O(nm)$ используя динамическое программирование. Лемма: Значение ${\overline {l}}(C)$ цикла с минимальной средней стоимостью равно $\alpha =\min _{v\in V}\max _{j=0}^{n-1}({\frac {d_{n}(v)-d_{j}(v)}{n-j}})$. Пусть $C$ - цикл с минимальной средней стоимостью. Если увеличить стоимость всех рёбер на $\delta$, то $C$ останется циклом с минимальной средней стоимостью, однако значение цикла увеличится на $\delta$. таким образом можно увеличить все стоимости рёбер так, что ${\overline {l}}(C)=0$. Покажем, что $\alpha \geqslant 0$: Выеберем любую вершину $v$ и путь $P$, заканчивающийся в $v$ и имеющий стоимость $d_{n}(v)$. $P$ должен содержать цикл $C$. Пусть $P'$ - путь $P$ не содержащий цикла $C$ и имеющий длину $j$. Тогда в цикле имеется $n-j$ рёбер. Из-за $l(C)\geqslant 0$ справедливо $d_{n}(v)=l(P)=l(C)+l(P')\geqslant l(P')\geqslant d_{j}(v)$ и для каждой вершины $v$ существует $j\in \{1,...,n-1\}$ такой, что $d_{n}(v)\geqslant d_{j}(v)$. Покажем, что $\alpha \leqslant 0$: Для этого докажем, что существует вершина $w$ для которой истино $d_{n}(w)\leqslant d_{j}(w)$ для всех $j\in \{1,...,n-1\}$. Пусть $v$ - вершина цикла с минимальной средней стоимостью $C$, $P$ - кратчайший путь, заканчивающийся на $v$ и не содержащий в себе цикла. пусть $p<n$ количество вершин в $P$. Также ввёдем вершину $w$, которая лежит на $C$ на расстоянии $n-p$ вершин от $v$. Путь от $v$ к $w$ назовём $Q$. Пусть $R$ - путь из $w$ к $v$, а $S$ - путь минимальной длины $j$ из источника графа к $w$. Тогда истино следующее: $d_{n}(w)\leqslant l(P)+l(Q)=d_{p}(v)+l(Q)$, а также $d_{p}(v)\leqslant d_{j+r}(v)\leqslant d_{j}(w)+l(R)$ и из них следует, что $d_{n}(w)\leqslant d_{j}(w)+l(R)+l(Q)$. Путь $Q\odot R$ имеет стоимость 0, т.к. $l(C)=0$. Таким образом $d_{n}(w)\leqslant d_{j}(w)$ для всех $j\in \{1,...,n-1\}$. Учитывая лемму, получим $\alpha \leqslant 0$. Время выполнения такого алгоритам составит $O(m^{2}\cdot n^{2}\cdot \log(nL))$, так как в процессе выполнения алгоритма пройдут $n\log(nL)+1$ фаз, в каждой из которых $m$ итераций, требующих $O(nm)$ времени. Основываясь не предидущей оценке времени можно составить и следующую: $O(m^{3}\cdot n^{2}\cdot \log(n))$.
• Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
• Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.

Ссылки

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

См. также

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

Литература

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