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

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

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

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

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

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

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

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

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

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

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

Установка производства и потребления

По умолчанию все узлы сети являются транзитными. То есть входящий поток в такие узелы равен исходящиму.

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

// узел №0 производит 15 ед. потока
Модель.УстановитьВкладУзла(0, 15);

// узел №2 потребляет 20 ед. потока
Модель.УстановитьВкладУзла(2, -20);

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

ВлкадУзла1   = Модель.ПолучитьВкладУзла(1);
ВлкадУзла3   = Модель.ПолучитьВкладУзла(3);

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

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

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

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

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

    СтоимостьПотокаДуги1 = ПотокДуги1 * Дуга1.Стоимость;    // <-- вычисляем стоимость потока через дугу

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