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

Материал из Алговики
Перейти к навигации Перейти к поиску

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

Транспортной сетью называется ориентированный граф [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{ \lvert f \rvert = \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,\\ \lvert f \rvert = 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]

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

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

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

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

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

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

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

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

Ссылки

  1. ↑ Fulkerson, D R. “An Out-of-Kilter Method for Minimal-Cost Flow Problems.” Journal of the Society for Industrial and Applied Mathematics 9, no. 1 (March 1961): 18–27. doi:10.1137/0109002.
  2. ↑ 2,0 2,1 Orlin, James B. “A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows.” Mathematical Programming 78, no. 2 (August 1997): 109–29. doi:10.1007/BF02614365.
  3. ↑ 3,0 3,1 Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.
  4. ↑ Goldberg, Andrew V, and Robert Endre Tarjan. “Finding Minimum-Cost Circulations by Canceling Negative Cycles.” Journal of the ACM 36, no. 4 (October 1989): 873–86. doi:10.1145/76359.76368.
  5. ↑ Goldberg, Andrew V, and Robert Endre Tarjan. “Finding Minimum-Cost Circulations by Successive Approximation.” Mathematics of Operations Research 15, no. 3 (August 1990): 430–66. doi:10.1287/moor.15.3.430.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Поиск_потока_минимальной_стоимости_в_транспортной_сети&oldid=2288