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

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

Определения

Дана транспортная сеть $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⩽f(u,v)⩽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|⩾d$ впервые, останови алгоритм.
2. Пусть $p$ величина последнего дополнения потока.
3. Замени последний поток на поток со значением $p-(|f|-d)$.

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

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

Решения

• Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования.
• Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда. Для доказательства работы алгоритма покажем, что поток $f$ графа $G$ не является потоком минимальной стоимости пока остаточная сеть графа $G_f$ содержит отрицательный цикл $C$. Пусть $f^{*}$ - поток графа $G$ такой, что $l(f^{*})<l(f)$ и, следовательно, оба потока отличны друг от друга. Для всех рёбер $e\in E$ обозначим $f^{\prime }(e)=f^{*}(e)-f(e)$ и получим $f^{\prime }$ - циклический поток. Так как $f^{\prime }$ образован из максимум $m^{\prime }<m$ циклов $f{\text{'}}_i$ $(1⩽i⩽m^{\prime })$, справедливо следующее: $l(f^{\prime })=l(f^{*})-l(f)=\sum _{1⩽i⩽m^{\prime }}l(f{\text{'}}_i)$, а значит, существует такой $j$, что $l(f{\text{'}}_j)<0$. Для оптимизиации алгоритма можно выбирать каждую итерацию циклы с минимальной средней стоимостью $\bar{l}(C)=\frac{l(C)}{|C|}=\frac{\sum _{e\in C}l(e)}{|C|}$. Для доказательства времени работы алгоритма разобьем ход его выполнения на фазы, каждая из которых будет состоять из отдельных итераций. Пусть $f$ - поток к началу $i$-той фазы. Фаза $i$ считается завершенной, когда найден поток $g$ такой, что $\mu (g)⩽(1-1/n)\cdot \mu (f)$ или $\mu (g)⩽0$, где $\mu (f)=-\bar{l}(C)$. При $\mu (g)⩽0$ алгоритм прекращает работу. Далее пусть ${\mu }_0$ - значение $\mu$ к началу первой фазы и ${\mu }_i$ - значение $\mu$ к началу $i$-той фазы ($1⩽i⩽T$). Таким образом действительно: ${\mu }_i⩽(1-1/n)\cdot {\mu }_{i-1}⩽\frac{{\mu }_{i-1}}{e^{1/n}}$, а также ${\mu }_0⩽L=\sum _{e\in E}|l(e)|$. Вследствие свойства целочисленности ${\mu }_{T-1}⩾1/n$ следует $T-1⩽{\log }_{e^{1/n}}(nL)=\frac{\ln (nL)}{\ln (e^{1/n})}=n\ln (nL)$ и $T⩽n\ln (nL)+1$. Итерации условно можно разбить на несколько видов: Тип 1 - цикл $C$ содержит только рёбра с негативной стоимостью и Тип 2 - цикл $C$ содержит минимум одно ребро с положительной стоимостью. При каждой итерации первого типа будет "насыщено" и удалено хотя бы одно ребро. При этом все образованные рёбра будут иметь положительную стоимость (так как имеют обратное направление в остаточной сети). Таким образом алгоритм завершится после как минимум $m$ последовательных итераций первого типа. Если же в фазе содержатся более $m$ итераций, после $m-1$ итераций максимум будет выполнена итерация второго типа. Покажем однако, что такое невозможно: Пусть $g$ - поток первой итерации второго типа. Заметим, что действительно $\mathrm{\forall }e\in E(G_g):l(e)⩾-\mu (f)$, т.е. нет новых рёбер с отрицательной стоимостью. Пусть $C$ - цикл в $G_g$ с минимальным $\bar{l}(C)$ и $H$ - рёбра с отрицательной стоимостью в $C$: $\mu (g)=\sum _{e\in C}\frac{-l(e)}{|C|}⩽\sum _{e\in H}\frac{-l(e)}{|C|}⩽|H|\cdot \frac{\mu (f)}{|C|}$. Из $|H|⩽|C|-1$ следует $|H|/|C|⩽1-1/|C|⩽1-1/n$. Таким образом $\mu (g)⩽(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)=\underset{e=(w,v)\in E_f}{\min }(d_k(w)+l(e))$. Выходит, что все значения $d_k(v)$ можно подсчитать за $O(nm)$ используя динамическое программирование. Лемма: Значение $\bar{l}(C)$ цикла с минимальной средней стоимостью равно $\alpha =\underset{v\in V}{\min }{\max }_{j=0}^{n-1}(\frac{d_n(v)-d_j(v)}{n-j})$. Пусть $C$ - цикл с минимальной средней стоимостью. Если увеличить стоимость всех рёбер на $\delta$, то $C$ останется циклом с минимальной средней стоимостью, однако значение цикла увеличится на $\delta$. таким образом можно увеличить все стоимости рёбер так, что $\bar{l}(C)=0$. Покажем, что $\alpha ⩾0$: Выеберем любую вершину $v$ и путь $P$, заканчивающийся в $v$ и имеющий стоимость $d_n(v)$. $P$ должен содержать цикл $C$. Пусть $P^{\prime }$ - путь $P$ не содержащий цикла $C$ и имеющий длину $j$. Тогда в цикле имеется $n-j$ рёбер. Из-за $l(C)⩾0$ справедливо $d_n(v)=l(P)=l(C)+l(P^{\prime })⩾l(P^{\prime })⩾d_j(v)$ и для каждой вершины $v$ существует $j\in \{1,...,n-1\}$ такой, что $d_n(v)⩾d_j(v)$. Покажем, что $\alpha ⩽0$: Для этого докажем, что существует вершина $w$ для которой истино $d_n(w)⩽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)⩽l(P)+l(Q)=d_p(v)+l(Q)$, а также $d_p(v)⩽d_{j+r}(v)⩽d_j(w)+l(R)$ и из них следует, что $d_n(w)⩽d_j(w)+l(R)+l(Q)$. Путь $Q\odot R$ имеет стоимость 0, т.к. $l(C)=0$. Таким образом $d_n(w)⩽d_j(w)$ для всех $j\in \{1,...,n-1\}$. Учитывая лемму, получим $\alpha ⩽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))$.
• Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
• Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.

Ссылки

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

См. также

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

Литература

• Шаблон:Книга:CLRS