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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определения[править | править вики-текст]

Дана транспортная сеть \,G(V,E) с источником s \in V и стоком t \in V, где ребра (u,v) \in E имеют пропускную способность \,c(u,v), поток \,f(u,v) и цену \,a(u,v). Цена пересылки потока f(u,v) \cdot a(u,v). Необходимо переслать \,d единиц потока.

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

\sum_{u,v \in V} a(u,v) \cdot f(u,v)

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

Ограничение пропускной способности: \ f(u,v) \le c(u,v). Поток не может превысить пропускную способность.
Антисимметричность: \ f(u,v) = - f(v,u). Поток из \ u в \ v должен быть противоположным потоку из \ v в \ u.
Сохранение потока: \ \sum_{w \in V} f(u,w) = 0.
Необходимый поток: \,\sum_{w \in V} f(s,w) = d

Отношение к другим задачам[править | править вики-текст]

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

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

Решения[править | править вики-текст]

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

Ссылки[править | править вики-текст]

См. также[править | править вики-текст]

Литература[править | править вики-текст]