Поиск потока минимальной стоимости в транспортной сети: различия между версиями
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | {{level-p}} | ||
+ | |||
== Постановка задачи == | == Постановка задачи == | ||
Строка 14: | Строка 16: | ||
:<math> | :<math> | ||
− | \ | + | \left \vert f \right \vert = \sum_{e = (s, v)} f(e). |
</math> | </math> | ||
Строка 26: | Строка 28: | ||
\begin{cases} | \begin{cases} | ||
C(f) \to \min,\\ | C(f) \to \min,\\ | ||
− | \ | + | \left \vert f \right \vert = F |
\end{cases} | \end{cases} | ||
</math> | </math> | ||
Строка 62: | Строка 64: | ||
<references /> | <references /> | ||
+ | |||
+ | [[Категория:Статьи в работе]] | ||
+ | |||
+ | [[en:Finding minimal-cost flow in a transportation network]] |
Текущая версия на 17:06, 14 марта 2018
Содержание
1 Постановка задачи
Транспортной сетью называется ориентированный граф [math]G = (V, E)[/math], каждому ребру [math]e \in E[/math] которого приписана положительная пропускная способность [math]c(e)[/math] и цена [math]p(e)[/math].
Пусть в графе [math]G[/math] выделены две вершины: источник [math]s[/math] и сток [math]t[/math]. Без ограничения общности можно считать, что все остальные вершины лежат на каком-либо пути из [math]s[/math] в [math]t[/math]. Потоком называется функция [math]E \to \mathbb{R}[/math], удовлетворяющая следующим требованиям:
- ограничение по пропускной способности: [math]f(e) \le c(e)[/math];
- закон сохранения потока:
- [math] \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). [/math]
Величиной потока называется суммарный поток из источника:
- [math] \left \vert f \right \vert = \sum_{e = (s, v)} f(e). [/math]
Стоимостью потока называется
- [math] C(f) = \sum_{e \in E} f(e) p(e). [/math]
Задача о потоке минимальной стоимости в транспортной сети. Требуется найти поток заданной величины, имеющий наименьшую возможную стоимость:
- [math] \begin{cases} C(f) \to \min,\\ \left \vert f \right \vert = F \end{cases} [/math]
2 Свойства задачи
Суммарный поток из источника равен суммарному потоку в сток:
- [math] \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). [/math]
(Для доказательства достаточно просуммировать закон сохранения потока для всех вершин, кроме источника и стока.)
3 Варианты задачи
В зависимости от ограничений на значения пропускной способности:
- произвольная положительная пропускная способность;
- целая пропускная способность;
- единичная пропускная способность.
4 Алгоритмы решения задачи
- сведение к задаче линейного программирования специального вида[1][2];
- последовательное вычисление кратчайших путей для всех пар вершин[3];
- удаление циклов отрицательной стоимости[4];
- масштабирование пропускной способности[3];
- масштабирование цен[5].
5 Существующие реализации
- Python: NetworkX
- функция
network_simplex
: алгоритм Network Simplex[2] для целых цен; - функция
capacity_scaling
: алгоритм масштабирования пропускной способности.
- функция
6 Ссылки
- ↑ 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,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,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.
- ↑ 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.
- ↑ 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.