Поток минимальной стоимости | это... Что такое Поток минимальной стоимости? (original) (raw)

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

Определения

Дана транспортная сеть \,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)

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

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

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

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

Решения

Ссылки

См. также

Литература