Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.
Дана транспортная сеть с источником и стоком , где рёбра имеют пропускную способность , поток и цену . Цена пересылки потока . Необходимо переслать единиц потока.
Суть задачи — найти поток f(u, v), минимизирующий его общую стоимость:
Накладываются следующие условия:
Ограничение пропускной способности: | . Поток не может превысить пропускную способность. |
Антисимметричность: | . Поток из в должен быть противоположным потоку из в . |
Сохранение потока: | . |
Необходимый поток: |
Другой вариант этой задачи — найти максимальный поток имеющий минимальную цену среди максимальных.
Более общая проблема — циркуляция потока минимальной стоимости, которая может быть использована для решения данной задачи. Ставим нижнюю границу для всех рёбер равную нулю и проводим дополнительное ребро из стока в источник с пропускной способностью и нижней границей .
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .