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

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

ОпределенияПравить

Дана транспортная сеть   с источником   и стоком  , где рёбра   имеют пропускную способность  , поток   и цену  . Цена пересылки потока  . Необходимо переслать   единиц потока.

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

 

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

Ограничение пропускной способности:  . Поток не может превысить пропускную способность.
Антисимметричность:  . Поток из   в   должен быть противоположным потоку из   в  .
Сохранение потока:  .
Необходимый поток:  

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

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

Более общая проблема — циркуляция потока минимальной стоимости, которая может быть использована для решения данной задачи. Ставим нижнюю границу для всех рёбер равную нулю и проводим дополнительное ребро из стока   в источник   с пропускной способностью   и нижней границей  .

РешенияПравить

  • Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования.
  • Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда.
  • Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
  • Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.

СсылкиПравить

См. такжеПравить

ЛитератураПравить