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

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

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

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

• ограничение по пропускной способности: [math]\displaystyle{ f(e) \le c(e) }[/math];
• закон сохранения потока:

[math]\displaystyle{ \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). }[/math]

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

[math]\displaystyle{ \left \vert f \right \vert = \sum_{e = (s, v)} f(e). }[/math]

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

[math]\displaystyle{ C(f) = \sum_{e \in E} f(e) p(e). }[/math]

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

[math]\displaystyle{ \begin{cases} C(f) \to \min,\\ \left \vert f \right \vert = F \end{cases} }[/math]

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

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

[math]\displaystyle{ \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). }[/math]

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

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

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

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

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

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

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

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