Поиск потока минимальной стоимости в транспортной сети

1 Постановка задачи

Транспортной сетью называется ориентированный граф $G = (V, E)$, каждому ребру $e \in E$ которого приписана положительная пропускная способность $c(e)$ и цена $p(e)$.

Пусть в графе $G$ выделены две вершины: источник $s$ и сток $t$. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из $s$ в $t$. Потоком называется функция $E \to \mathbb{R}$, удовлетворяющая следующим требованиям:

• ограничение по пропускной способности: $f(e) \le c(e)$;
• закон сохранения потока:

$\forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e).$

Величиной потока называется суммарный поток из источника:

$\left \vert f \right \vert = \sum_{e = (s, v)} f(e).$

Стоимостью потока называется

$C(f) = \sum_{e \in E} f(e) p(e).$

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

$\begin{cases} C(f) \to \min,\\ \left \vert f \right \vert = F \end{cases}$

2 Свойства задачи

Суммарный поток из источника равен суммарному потоку в сток:

$\forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e).$

(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)

3 Варианты задачи

В зависимости от ограничений на значения пропускной способности:

• произвольная положительная пропускная способность;
• целая пропускная способность;
• единичная пропускная способность.

4 Алгоритмы решения задачи

• сведение к задаче линейного программирования специального вида;
• последовательное вычисление кратчайших путей для всех пар вершин;
• удаление циклов отрицательной стоимости;
• масштабирование пропускной способности;
• масштабирование цен.

5 Существующие реализации

• Python: NetworkX
  • функция network_simplex: алгоритм Network Simplex для целых цен;
  • функция capacity_scaling: алгоритм масштабирования пропускной способности.