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

Модель максимального потока предназначена для решения задач, в которых необходимо определить, какой максимальный объём "потока" можно пропустить от одного узла (истока) к другому (стоку) через сеть с ограниченными пропускными способностями. Потоком может быть что угодно: количество товара, объем данных, людей, энергии — в зависимости от прикладной задачи.

Задача формулируется как сеть из узлов и дуг, где каждая дуга имеет ограниченную пропускную способность. Цель — определить, какой максимальный объем можно "перекачать" из начального узла в конечный, не превышая лимитов на каждой дуге и соблюдая баланс потоков во внутренних узлах.

Создание модели

Модель может быть создана через модуль менеджера моделей:

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

Или через менеджер библиотеки:

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

Добавление дуг

ДугаМоскваПетербург     = Модель.Дуга(0, 1, 50, "МоскваПетербург");     // <-- дуга с пропускной способностью 50
ДугаПетербургНовгород   = Модель.Дуга(1, 2, 20, "ПетербургНовгород");   // <-- дуга с пропускной способностью 20

Установка истока и стока

Для установки истока и стока необходимо указать индексы соответсвующих узлов:

// транспортируем ресурсы из узла 0 в узел 4
Модель.УстановитьИсток(0);
Модель.УстановитьСток(4);

Для получения текущих истока и стока:

Исток   = Модель.ПолучитьИсток();
Сток    = Модель.ПолучитьСток();

Решение модели

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

Обработка результата

СтатусРешения       = Решение.Статус();
ОптимальныйПоток    = Решение.ОптимальныйПоток();   // <-- найденый оптимальный поток
КоличествоДуг       = Решение.КоличествоДуг();      // <-- количество дуг

Если Решение.РешениеНайдено() Тогда
    ПотокДуги1 = Решение.ЗначениеПотока(Дуга1);             // <-- получаем поток по ссылке на дугу
    ПотокДуги2 = Решение.ЗначениеПотока("МоскваПетербург"); // <-- получаем поток по имени дуги

    // TODO
КонецЕсли;