Оптимизация на графах: задача о максимальном потоке минимальной стоимости (Min-Cost Max-Flow)

Математическая модель задачи Min-Cost Max-Flow формулируется на ориентированном графе, где каждое ребро характеризуется двумя параметрами: максимальной пропускной способностью (Capacity) и стоимостью прохождения одной единицы потока (Cost). Целевая функция заключается в строгой минимизации суммы произведений величины потока на каждом ребре на его удельную стоимость. При этом система ограничений требует строгого выполнения закона сохранения потока во всех транзитных узлах (сколько вошло, столько и вышло) и соблюдения лимитов пропускной способности труб. В отличие от простой транспортной задачи, граф здесь может иметь сложнейшую многоуровневую структуру с петлями и обходными магистралями, что делает матрицу ограничений гигантской.

Одним из самых интуитивно понятных алгоритмов решения является метод последовательных кратчайших путей (Successive Shortest Path Algorithm). Алгоритм начинает работу с нулевого потока и на каждом шаге ищет в остаточной сети самый дешевый (с точки зрения стоимости) путь от истока к стоку. Для поиска этого пути используется модифицированный алгоритм Беллмана-Форда или алгоритм Дейкстры с потенциалами Джонсона (чтобы избежать проблем с отрицательными стоимостями обратных дуг). Найдя такой путь, алгоритм проталкивает по нему максимально возможный поток, пока не упрется в лимит самого узкого ребра на маршруте. Процесс жадно повторяется до тех пор, пока весь требуемый объем ресурса не будет перекачан. Этот метод гарантирует минимизацию затрат, так как каждая новая порция груза всегда отправляется по самому дешевому из доступных на данный момент обходных путей.

Диаметрально противоположным подходом является алгоритм отмены циклов (Cycle Canceling Algorithm). Он начинает с любого произвольного потока, который удовлетворяет требованию по объему (например, найденного обычным алгоритмом Форда-Фалкерсона), совершенно игнорируя стоимость. Затем алгоритм строит остаточную сеть и ищет в ней ориентированные циклы с отрицательной суммарной стоимостью. Наличие такого цикла означает, что можно пустить поток по кругу, перераспределив груз между магистралями так, что общий объем переданного ресурса не изменится, но суммарные финансовые затраты уменьшатся. Метод итеративно отменяет эти отрицательные циклы (проталкивая поток вдоль них), пока в сети не останется ни одного отрицательного контура, что математически знаменует достижение абсолютного глобального оптимума.

Подлинным триумфом в решении задачи Min-Cost Max-Flow стал алгоритм Out-of-Kilter, разработанный Д.Р. Фалкерсоном. Этот алгоритм позволяет стартовать с абсолютно любого состояния сети (которое может нарушать и закон сохранения, и лимиты труб). Для каждого ребра вводится так называемое состояние килтера (соответствие условиям оптимальности двойственной задачи). Если ребро нарушает условия (находится out-of-kilter), алгоритм итеративно корректирует потоки и узловые потенциалы, стремясь загнать все дуги в оптимальное русло (in-kilter). Сегодня этот изящный алгебраический аппарат применяется повсеместно: от оптимизации распределения порожних вагонов в железнодорожных сетях до балансировки маршрутизации трафика в облачных дата-центрах.