Перейти к основному содержимому

Модель потока минимальной стоимости

Раздел знакомит с моделью потока минимальной стоимости в библиотеке О2: что она вычисляет, в каких прикладных задачах применима и какими приёмами моделируются типичные практические ситуации.

Полный перечень методов вынесен в раздел Программный интерфейс. Полные тексты решений — в раздел Примеры.

Назначение модели​

Модель потока минимальной стоимости (min-cost flow problem) определяет, по каким маршрутам и в каких объёмах передавать поток. Сеть задаётся ориентированным графом с лимитами на дугах и балансами «производство/потребление» в узлах. Цель — минимальная суммарная стоимость передачи.

Поток интерпретируется в терминах прикладной задачи: единицы товара, кубические метры сырья, мегабиты трафика, человеко-часы.

В отличие от модели максимального потока, здесь дуги дополнительно характеризуются стоимостью передачи единицы потока, а узлы могут одновременно производить и потреблять.

Это позволяет строго сформулировать классическую transportation problem (двудольное распределение «склады → потребители», известную также как задачу Хичкока), её обобщение transshipment problem (с промежуточными хабами), задачи распределения поставок, межскладских перемещений и оптимизации цепочек поставок.

На базе этой модели типично решаются задачи в подсистемах WMS, ERP, APS и S&OP-контурах: распределение остатков по магазинам, балансировка производственных площадок, маршрутизация однородного грузопотока через распределительные центры, перераспределение мощностей между узлами сети supply chain optimization.

Классическая задача о назначениях (assignment problem) также сводится к этой модели через двудольный граф «исполнители → задачи». Пример приведён здесь.

Когда выбирать эту модель​

  • Задача описывается ориентированным графом: объекты — узлы, связи — дуги.
  • В узлах различимы производители, потребители и транзитные точки, заданы целочисленные объёмы производства и потребления.
  • Дуги имеют стоимости передачи единицы потока. Иначе задача чрезмерно проста для этой модели и решается моделью максимального потока.
  • Поток однороден: моделируется один тип ресурса.
  • Цель формулируется как «передать заданный объём с минимальной суммарной стоимостью».
  • Стоимость линейна по объёму потока: нет фиксированных стоимостей открытия дуги, нет нелинейных эффектов (квадратичных, логарифмических).

Если хотя бы одно условие не выполняется — задача требует более выразительной модели:

Концепция модели​

Сеть описывается тремя сущностями: узлы, дуги, балансы узлов.

Узлы идентифицируются неотрицательными целыми индексами начиная с 0. Регистрировать узлы отдельно не требуется — множество узлов выводится из множества дуг и установленных балансов.

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

Баланс узла (вклад) — целое число, описывающее роль узла в сети:

  • положительное значение — узел является производителем и поставляет в сеть указанное число единиц;
  • отрицательное значение — узел является потребителем и принимает из сети указанное число единиц (по абсолютному значению);
  • ноль (значение по умолчанию) — узел транзитный: весь входящий поток выходит наружу.

Закон сохранения с балансами. Для каждого узла исходящий поток минус входящий равен установленному балансу. Это обобщение закона сохранения потока на случай источников и потребителей: транзитный узел не накапливает и не порождает поток, производитель эмитирует ровно свой баланс, потребитель поглощает ровно свой баланс.

Согласованность балансов. Сумма балансов всех узлов должна быть равна нулю: суммарное производство равно суммарному потреблению.

Если в прикладной задаче это условие не выполняется (например, предложение превышает спрос), его необходимо сбалансировать до запуска поиска. Балансировка выполняется фиктивным потребителем-«стоком», поглощающим излишек, или фиктивным производителем-«источником», покрывающим дефицит. Без согласованности балансов задача недопустима.

Целочисленность. Модель оперирует целыми числами. Дробные стоимости и пропускные способности приводятся к целым через единый масштабирующий коэффициент, кратный знаменателям всех входных значений. Результат интерпретируется в той же шкале с обратным масштабированием.

Целевая функция. Минимизируется суммарная стоимость передачи — сумма по всем дугам произведения «фактический поток через дугу × стоимость единицы».

Базовая схема использования​

Рекомендуемый способ создания модели — через фасад О2.Модели:

Модель = О2
    .Модели()
    .МодельПотокаМинимальнойСтоимости()
    .СоздатьМодель();

// Балансы узлов: производство 10 ед. в узле 0, потребление 10 ед. в узле 3.
Модель.Узлы().УстановитьВклад(0, 10);
Модель.Узлы().УстановитьВклад(3, -10);

// Дуги: хвост, голова, пропускная способность, стоимость единицы потока, имя.
Модель.Дуги().Добавить(0, 1, 8,  4, "0_1");
Модель.Дуги().Добавить(0, 2, 8,  3, "0_2");
Модель.Дуги().Добавить(1, 3, 10, 2, "1_3");
Модель.Дуги().Добавить(2, 3, 10, 5, "2_3");

Решение = Модель.Решить();

Если Решение.РешениеНайдено() Тогда
    СтоимостьОптимума = Решение.ОптимальнаяСтоимость();
    ПотокЧерезУзел1   = Решение.ЗначениеПотока("0_1");
КонецЕсли;

Когда тип модели определяется динамически, доступна универсальная точка входа:

Модель = О2.СоздатьМодель(
    О2.ТипыМоделей().МодельПотокаМинимальнойСтоимости()
);

Полный пошаговый разбор — в примере решения задачи потока минимальной стоимости. Полный перечень методов модели, дуг, узлов и параметров поиска — в разделе Программный интерфейс — Поток минимальной стоимости.

Приёмы моделирования​

Несколько типичных практических ситуаций не имеют прямого выражения в базовом API модели, но сводятся к нему стандартными приёмами.

Несколько источников и потребителей​

В отличие от модели максимального потока, дополнительные узлы-«супер-источник» и «супер-сток» не нужны: модель естественно поддерживает любое число производителей и потребителей.

Достаточно установить положительные балансы во всех узлах-производителях и отрицательные — во всех потребителях. Алгоритм сам распределяет поток между ними с минимальной суммарной стоимостью.

// Два склада с остатками 40 и 60 ед.
Модель.Узлы().УстановитьВклад(0, 40);
Модель.Узлы().УстановитьВклад(1, 60);

// Три магазина с потребностями 30, 40 и 30 ед.
Модель.Узлы().УстановитьВклад(2, -30);
Модель.Узлы().УстановитьВклад(3, -40);
Модель.Узлы().УстановитьВклад(4, -30);

Транспортная задача как частный случай​

Классическая transportation problem — двудольный граф «склады → потребители», без транзитных узлов.

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

// Склады: 0, 1 — балансы +50, +30.
Модель.Узлы().УстановитьВклад(0, 50);
Модель.Узлы().УстановитьВклад(1, 30);

// Потребители: 2, 3 — балансы −40, −40.
Модель.Узлы().УстановитьВклад(2, -40);
Модель.Узлы().УстановитьВклад(3, -40);

// Маршруты: пропускная способность ограничена мощностью склада, стоимость — тариф.
Модель.Дуги().Добавить(0, 2, 50, 7);
Модель.Дуги().Добавить(0, 3, 50, 9);
Модель.Дуги().Добавить(1, 2, 30, 8);
Модель.Дуги().Добавить(1, 3, 30, 6);

Транзитные узлы и многоступенчатые цепочки​

Узлы с балансом 0 (значение по умолчанию) служат промежуточными точками: они не производят и не потребляют поток, но позволяют разнести длинный маршрут на несколько дуг с независимыми пропускными способностями и стоимостями.

Так моделируются распределительные центры, кросс-докинговые площадки, узловые станции — то есть задача transshipment problem.

Ограничение пропускной способности на узле​

Если ограничение установлено не на дугу, а на сам узел (например, суточная мощность сортировочного центра), узел расщепляется на два — «вход» и «выход», соединённых одной дугой с нужной пропускной способностью.

Стоимость этой дуги — либо ноль, если обработка в узле бесплатна, либо тариф обработки единицы. Все исходно входящие связи перевешиваются на «вход», все исходящие — на «выход».

УзелВход  = 5;
УзелВыход = 6;

// Пропускная способность узла — 100 ед/сут, стоимость обработки — 2 ед.
Модель.Дуги().Добавить(УзелВход, УзелВыход, 100, 2);

// Дуги, входящие в исходный узел, ведут в УзелВход.
// Дуги, исходящие из исходного узла, выходят из УзелВыход.

Двусторонние связи​

Дуги направленные. Канал, по которому поток может идти в обе стороны, моделируется двумя встречными дугами — с собственными пропускными способностями и стоимостями.

Стоимости в направлениях могут различаться. Например, при возвратной логистике обратный тариф обычно отличается от прямого.

// Прямой рейс: стоимость 6 за единицу.
Модель.Дуги().Добавить(1, 2, 50, 6);
// Обратный рейс: стоимость 9 за единицу (порожняк дороже).
Модель.Дуги().Добавить(2, 1, 50, 9);

Параллельные дуги для ступенчатого тарифа​

Между одной и той же парой узлов допускается произвольное число параллельных дуг. Это удобно, когда тариф нелинеен, но кусочно-линейный — как в оптовых скидках, прогрессивных тарифах перевозки, ступенчатых тарифах на электроэнергию.

Каждая «ступень» представляется своей дугой со своей пропускной способностью и стоимостью. Решатель сначала насыщает дешёвую дугу, а в более дорогие переходит только при необходимости.

// Первые 30 ед. — по 4, следующие 50 — по 7, остальные — по 12.
Модель.Дуги().Добавить(1, 2, 30, 4);
Модель.Дуги().Добавить(1, 2, 50, 7);
Модель.Дуги().Добавить(1, 2, 9999, 12);

Для корректной работы приёма стоимости параллельных дуг должны быть упорядочены по возрастанию. Иначе модель остаётся математически валидной, но не воспроизводит ступенчатый тариф: поток сначала пойдёт по самой дешёвой ступени независимо от её положения в порядке заведения.

Дробные стоимости и пропускные способности​

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

Мягкий спрос через фиктивную дугу штрафа​

Если допустимо неудовлетворённое потребление (например, дефицит в магазине нежелателен, но не запрещён), вводится дуга-«штраф» с большой стоимостью.

По этой дуге поток может миновать дорогие участки сети или, наоборот, заместить отсутствующее предложение. Стоимость такой дуги выбирается заведомо большей, чем любой реальный тариф. Тогда модель использует её только при невозможности удовлетворить спрос обычными маршрутами.

Сведение задачи о назначениях​

Задача о назначениях (assignment problem) — частный случай задачи потока минимальной стоимости на двудольном графе «исполнители → задачи».

Каждому исполнителю назначается баланс +1, каждой задаче — баланс −1. Дуги соединяют допустимые пары «исполнитель — задача» со стоимостью назначения и единичной пропускной способностью. Поскольку поток целочисленный и пропускные способности равны единице, в оптимуме каждая дуга либо «выбрана» (поток 1), либо нет.

Полный разбор подхода и сценария с группировкой исполнителей в бригады — в примере Задача о назначениях через поток минимальной стоимости.

Что модель не выражает​

Базовая модель не учитывает:

  • фиксированные стоимости открытия дуги или узла (fixed-charge network flow) — требуются бинарные переменные и решаются математическим программированием;
  • несколько типов потока одновременно (multi-commodity flow) — также реализуются через математическое программирование;
  • дробные значения потока, стоимости или пропускной способности — требуется предварительное масштабирование к целым;
  • нелинейные стоимости (квадратичные, логарифмические) — кусочно-линейные приближаются параллельными дугами, остальное вне модели;
  • дискретные решения на структуре сети (выбрать один маршрут из набора, включить/выключить узел) — сопряжение с такими решениями выполняется через модель ограничений (CP-SAT);
  • временную динамику — модель статична. Для задач с горизонтом планирования сеть разворачивается во времени (узел в каждом такте — отдельный узел сети) либо применяются специализированные подходы;
  • мягкие ограничения на баланс узла — баланс жёсткий. Неудовлетворённый спрос или избыточное предложение вводятся явно через фиктивные дуги штрафа (см. приём выше).

См. также​