Поток минимальной стоимости: когда важно не только «сколько»

Коротко

К пропускным способностям добавляется цена за единицу потока на каждом ребре. Теперь мало пропустить нужную величину - надо пропустить её ПОДЕШЕВЛЕ. В остаточной сети цена обратного ребра равна цене прямого СО ЗНАКОМ МИНУС: отменяя единицу потока, ты возвращаешь заплаченное. Критерий оптимальности красив и проверяем: поток данной величины самый дешёвый тогда и только тогда, когда в остаточной сети нет цикла отрицательной стоимости - иначе по нему можно прогнать положительный поток в пределах остаточных ёмкостей и сэкономить, не меняя величины.

Если ты умеешь записать сеть со стоимостями, помнишь, что цена обратного ребра равна минус исходной, и знаешь критерий «нет отрицательного цикла», листай до «Теперь сам».

Как думаешь, чем плох просто максимальный поток

Три курьера и три заказа, каждый курьер берёт один заказ. Доставка стоит по-разному: у первого курьера цены 4, 2 и 8; у второго 4, 3 и 7; у третьего 3, 1 и 6.

Максимальный поток тут найдётся мгновенно - три назначения, и любая полная расстановка подойдёт. Но их шесть штук, и стоят они по-разному: от 12 до 14. Алгоритму максимального потока всё равно, какую выдать, - он про величину. Значит нужна другая постановка задачи и другой критерий остановки.

На что это похоже

Билеты на поезд. Мест хватает - вопрос, в каком вагоне ехать. Задача «уехать» и задача «уехать дешевле» решаются по-разному, хотя ограничение на число мест одно и то же. И главное: чтобы подешеветь, иногда надо кого-то ПЕРЕСАДИТЬ - выкупленный билет вернуть, деньги получить обратно и купить другой. Для оплаченного билета с положительной ценой возврат соответствует обратному ребру с отрицательной ценой. В общем случае обратная цена равна минус исходной: у ребра с ценой −2 обратная цена будет +2.

Механизм: цена на ребре и остаточная сеть

сеть:      c(u, v) - пропускная способность,  a(u, v) - цена ЕДИНИЦЫ потока
стоимость: сумма a(u, v) · f(u, v) по всем рёбрам

постановки:
   поток заданной величины K минимальной стоимости
   максимальный поток минимальной стоимости (частый случай: K = |f_max|)

остаточная сеть:
   прямое ребро:   остаток c − f,  цена  a(u, v)
   обратное ребро: остаток f,      цена −a(u, v)     ← вернуть заплаченное

В этой схеме нижние границы потоков равны 0. Если на ребре обязателен минимум ℓ, его обратная остаточная ёмкость равна f−ℓ: отменять можно только часть сверх минимума. Прямой остаток остаётся c−f, цены рёбер - a и −a.

Критерий оптимальности:

поток величины K минимален по стоимости
    ⇔ в остаточной сети НЕТ цикла отрицательной стоимости

Проверять критерий умеем: отрицательный цикл ищет Беллман-Форд из раздела про кратчайшие пути. Для проверки всей остаточной сети добавь временный общий источник с нулевыми рёбрами ко всем вершинам, либо задай все начальные расстояния равными нулю. Запуск только из исходного s пропустит отрицательный цикл в недостижимой компоненте. Обрати внимание на устройство утверждения - оно двустороннее. Есть отрицательный цикл - поток точно не оптимален: прогони по циклу δ>0, не превышающее минимальной остаточной ёмкости. Величина не изменится, потому что цикл замкнут, а стоимость упадёт. Для обратного направления представь разность более дешёвого и текущего потока как циркуляцию в остаточной сети. Её можно разложить на циклы с положительными коэффициентами. Если суммарная стоимость отрицательна, хотя бы один из циклов имеет отрицательную стоимость. Поэтому без такого цикла улучшение невозможно.

Правило

У каждого ребра появляется цена за единицу потока; стоимость потока - сумма a(u, v)·f(u, v). В остаточной сети цена обратного ребра равна цене прямого со знаком минус - отмена возвращает заплаченное. Поток заданной величины минимален по стоимости ТОГДА И ТОЛЬКО ТОГДА, когда в остаточной сети нет цикла отрицательной стоимости; допустимый положительный прогон по такому циклу не меняет величину потока и уменьшает стоимость. Задача «максимальный поток» и задача «самый дешёвый поток данной величины» - разные: одна максимизация величины минимальной цены не гарантирует.

Разбор: шесть расстановок и одна дешёвая

Курьеры из вступления. Цены:

          заказ 1   заказ 2   заказ 3
курьер A      4         2         8
курьер Б      4         3         7
курьер В      3         1         6

Переберём все шесть назначений (для трёх курьеров это честно, для десяти - уже 10! вариантов):

A1 Б2 В3 = 4 + 3 + 6 = 13
A1 Б3 В2 = 4 + 7 + 1 = 12     ← дешевле
A2 Б1 В3 = 2 + 4 + 6 = 12     ← дешевле
A2 Б3 В1 = 2 + 7 + 3 = 12     ← дешевле
A3 Б1 В2 = 8 + 4 + 1 = 13
A3 Б2 В1 = 8 + 3 + 3 = 14

Минимум 12, и достигается он тремя разными способами. А жадность - «каждый берёт самое дешёвое из свободного» - даст вот что: курьер A возьмёт заказ 2 (цена 2), курьер Б - заказ 1 (цена 4), курьеру В останется заказ 3 (цена 6), итого 12. Повезло. Поменяй порядок курьеров - и жадность сломается: если первым выбирает В, он берёт заказ 2 (цена 1), A берёт заказ 1 (4), Б - заказ 3 (7), итого 12... снова 12. На пятёрке курьеров из задачи этой главы жадность по строкам даёт 18 против оптимальных 13. Дополнение без учёта цены может дать и 43: пары «курьер i → заказ i» стоят 13 + 11 + 2 + 9 + 8 = 43. Совпадения на трёх элементах ничего не доказывают: один удачный пример не доказывает правильность жадности.

Разбор: почему отрицательный цикл - это деньги на дороге

Пусть в остаточной сети нашёлся цикл u → v → w → u со стоимостью −3. Прогоним по нему одну единицу потока; в этом примере остаток на каждом ребре не меньше 1. При минимальном остатке 0,5 можно прогнать только 0,5 и сэкономить 1,5.

величина потока:  не изменилась - цикл замкнут, из истока не вышло ничего нового
стоимость:        уменьшилась на 3

физический смысл: часть потока переложили с одного маршрута на другой,
                  и новый маршрут дешевле старого на 3

Отсюда сразу два вывода. Первый: пока такой цикл есть, поток не оптимален - и это даёт целый алгоритм («отмена циклов»): начни с любого потока нужной величины и отменяй отрицательные циклы, пока они есть. При целых нижних и верхних границах потока, целочисленном старте и целых ценах каждый максимальный прогон уменьшает целую стоимость хотя бы на 1; при конечных ёмкостях она ограничена снизу, поэтому процесс завершится. Для произвольных вещественных данных из одного критерия конечное число шагов ещё не следует. Второй: критерий проверяем за O(V·E) Беллманом-Фордом, то есть ответ можно не просто получить, а ПРОВЕРИТЬ - ровно как пару «поток и разрез» из первой главы.

Важная оговорка: цикл ищется в ОСТАТОЧНОЙ сети, а не в исходной. В исходной сети отрицательных цен может не быть вовсе - они появляются у обратных рёбер, то есть только там, где уже идёт поток.

Что ломается без этого

Первое: искать отрицательный цикл в исходной сети - там его обычно нет, и алгоритм решит, что всё оптимально. Второе: забыть про минус у обратного ребра: тогда отмена назначения будет «стоить» столько же, сколько само назначение, и поток застрянет в первом попавшемся решении. Третье: считать, что произвольный максимальный поток уже минимален по стоимости. Исправление может потребовать переложить весь поток. Для SSP такой старт без проверки оптимальности недопустим; отмена циклов допускает его и устраняет отрицательные циклы до выполнения критерия. Четвёртое: применять Дейкстру для поиска дешёвого пути напрямую - отрицательные цены обратных рёбер ломают её так же, как в разделе про кратчайшие пути. Пятое: путать «цену ребра» и «пропускную способность»: первая умножается на поток, вторая его ограничивает.

Зачем это в работе

Это та постановка, в которую укладывается большинство реальных задач распределения: назначить заказы курьерам с учётом расстояний, распределить смены с учётом пожеланий, развезти товар со складов по магазинам с минимальными затратами (транспортная задача), поставить задачи в очередь с учётом цены простоя. Везде есть и ограничение («не больше одной задачи на человека», «не больше тонны в кузов»), и цена («сколько километров», «сколько рублей»). Отдельно стоит вспомнить, что поток минимальной стоимости - это линейная задача из прошлой главы, у которой матрица вполне унимодулярна: если задача имеет конечный оптимум, при целых нижних и верхних границах потока и балансах существует целый оптимальный поток. Целые дополняющие шаги сохраняют целость потока; произвольный LP-решатель может вернуть дробную смесь нескольких целых оптимумов.

Теперь сам

Сеть: s→a = 2 по цене 1, s→b = 2 по цене 3, a→t = 1 по цене 1, b→t = 2 по цене 1, a→b = 2 по цене 1. Нужно пропустить 2 единицы. Найди самый дешёвый способ и посчитай стоимость.

Ответ. Посмотрим на варианты. Путь s→a→t стоит 1 + 1 = 2 за единицу, но пропускает только одну (мешает a→t = 1). Путь s→a→b→t стоит 1 + 1 + 1 = 3 за единицу. Путь s→b→t стоит 3 + 1 = 4 за единицу.

Берём самое дешёвое в порядке возрастания цены:

единица 1: по пути s→a→t,   цена 2     (теперь a→t насыщено)
единица 2: по пути s→a→b→t, цена 3     (s→a ещё пропускает 1)
итого: 2 единицы, стоимость 5

Проверим критерием: есть ли в остаточной сети отрицательный цикл? Обратные рёбра: a→s (−1), t→a (−1), b→a (−1), t→b (−1). Любой замкнутый маршрут по ним и прямым рёбрам даёт неотрицательную сумму - например, a→b→t→a стоит 1 + 1 − 1 = 1. Отрицательного цикла нет, значит 5 - минимум.

Сравни с «просто максимальным потоком». Обход в ширину берёт пути по числу рёбер, а не по цене: сначала s→a→t (два ребра, цена 2), потом - тоже двухрёберный - s→b→t за 4, и трёхрёберный s→a→b→t за 3 он даже не рассмотрит. Итог: та же величина 2, но стоимость 6 вместо 5. Переплата в двадцать процентов - и ровно из-за того, что путь выбирался не по цене.

Главное

В задаче о потоке минимальной стоимости у каждого ребра есть цена за единицу, а стоимость потока - сумма a(u, v)·f(u, v). В остаточной сети цена обратного ребра противоположна цене прямого: отмена возвращает заплаченное. Поток заданной величины минимален по стоимости тогда и только тогда, когда в ОСТАТОЧНОЙ сети нет цикла отрицательной стоимости; допустимый положительный прогон по такому циклу сохраняет величину и уменьшает цену. Критерий проверяется Беллманом-Фордом за O(V·E), а «максимальный поток» и «самый дешёвый поток данной величины» - разные задачи.