Оптимизация на графах: потоки минимальной стоимости в транспортных сетях

Математически задача формулируется как модель линейного программирования со специфической матрицей инцидентности. Ограничения модели делятся на два типа: ограничения сохранения потока (баланс входящего и исходящего потока в каждом узле равен объему генерации или потребления ресурса) и ограничения на пропускную способность каждого направленного ребра. Целевая функция представляет собой сумму произведений величины потока на ребре и стоимости прохождения одной единицы потока по этому ребру. Унимодулярность матрицы инцидентности гарантирует, что при целочисленных пропускных способностях и объемах спроса оптимальное решение задачи автоматически будет целочисленным, что позволяет обойтись без использования NP-трудных методов дискретной оптимизации.

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

В промышленных масштабах чаще всего применяется сетевой симплекс-метод (Network Simplex Algorithm). Благодаря структуре графов, базисные решения в сетевом симплекс-методе представляют собой остовные деревья. Это позволяет выполнять шаги симплекс-метода (вычисление потенциалов узлов, поиск входящего ребра, пересчет потока по циклу) без явных матричных операций, используя лишь структуры данных на графах (указатели предков и глубины деревьев). Такой алгоритмический подход позволяет решать задачи с миллионами вершин и ребер в реальном времени.

Приложения задачи о потоке минимальной стоимости охватывают проектирование маршрутов доставки товаров в цепях поставок, телекоммуникационную маршрутизацию пакетов данных, управление финансовыми потоками в банковских структурах и оптимизацию перераспределения энергии в интеллектуальных энергосетях (Smart Grids). Понимание глубоких связей между сетевыми структурами и линейным программированием дает специалистам надежный инструмент для экономически эффективного управления ресурсными сетями любого масштаба.

Список литературы:
1. Ахуджа Р.К., Маньянти Т.Л., Орлин Дж.Б. Сетевые потоки: теория, алгоритмы и приложения. — М.: Мир, 1993.
2. Форд Л., Фалкерсон Д. Потоки в сетях. — М.: Мир, 1966.
3. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981.