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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

Решения

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

Ссылки

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

См. также

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

Литература

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