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

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

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

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

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

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

Это базовая задача класса network flow optimization. На практике она применяется:

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

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

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

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

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

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

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

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

Закон сохранения потока. Во всех узлах, кроме истока и стока, входящий объём равен исходящему. Транзитный узел не накапливает поток и не порождает его. Поток возникает только в истоке и поглощается только в стоке.

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

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

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

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

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

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

Модель.Граф().УстановитьИсток(0);
Модель.Граф().УстановитьСток(3);

Модель.Дуги().Добавить(0, 1, 20, "0_1");
Модель.Дуги().Добавить(0, 2, 30, "0_2");
Модель.Дуги().Добавить(1, 3, 10, "1_3");
Модель.Дуги().Добавить(2, 3, 25, "2_3");

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

Если Решение.РешениеНайдено() Тогда
    МаксимальныйПоток = Решение.ОптимальныйПоток();
КонецЕсли;

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

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

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

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

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

Несколько истоков или стоков​

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

От супер-истока к каждому реальному источнику ведёт дуга с пропускной способностью, равной мощности этого источника. От каждого реального потребителя к супер-стоку — дуга, равная его потребности.

СуперИсток = 0;
СуперСток  = 99;

Модель.Граф().УстановитьИсток(СуперИсток);
Модель.Граф().УстановитьСток(СуперСток);

// Источники: реальные узлы 1, 2 с мощностями 40 и 60
Модель.Дуги().Добавить(СуперИсток, 1, 40);
Модель.Дуги().Добавить(СуперИсток, 2, 60);

// Потребители: реальные узлы 10, 11 с потребностями 30 и 50
Модель.Дуги().Добавить(10, СуперСток, 30);
Модель.Дуги().Добавить(11, СуперСток, 50);

Двусторонняя связь​

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

Модель.Дуги().Добавить(1, 2, 50, "1_2");
Модель.Дуги().Добавить(2, 1, 50, "2_1");

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

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

Все исходно входящие связи перевешиваются на «вход», все исходящие — на «выход».

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

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

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

Параллельные дуги​

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

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

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

Анализ узких мест​

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

Для Каждого Дуга Из Дуги Цикл
    Если Решение.ЗначениеПотока(Дуга) = Дуга.МаксимальныйПоток Тогда
        // Дуга насыщена — кандидат в "бутылочное горлышко".
    КонецЕсли;
КонецЦикла;

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

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

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

См. также​