Задача потока минимальной стоимости
Задача потока минимальной стоимости (Minimum Cost Flow Problem) — классическая задача теории графов и оптимизации, тесно связанная с задачей максимального потока. В этой задаче каждая дуга направленного графа имеет не только пропускную способность (максимальный поток), но и стоимость транспортировки единицы потока. Цель — найти поток в сети, который минимизирует общую стоимость при соблюдении ограничений на пропускную способность и баланс потока в узлах.
В отличие от задачи максимального потока, где есть один источник и один сток, в задаче потока минимальной стоимости могут быть множественные узлы производства и потребления:
- Узлы производства (supply nodes) — узлы, где генерируется поток. Положительное значение supply означает, что узел производит определённое количество единиц потока (например, склад с товарами, завод с продукцией).
- Узлы потребления (demand nodes) — узлы, где поток потребляется. Отрицательное значение supply (т.е. demand) означает, что узел требует определённое количество единиц потока (например, магазин, нуждающийся в товарах).
- Транзитные узлы — узлы с нулевым значением supply/demand, через которые поток только проходит.
Постановка задачи
Имеется сеть из 5 узлов (0, 1, 2, 3, 4) и 9 дуг. Узел 0 является узлом производства с supply = 20, узлы 3 и 4 являются узлами потребления с demand -5 и -15 соответственно. Узлы 1 и 2 — транзитные.
Вклады узлов (supply/demand):
- Узел 0: supply = +20 (производство);
- Узел 1: supply = 0 (транзит);
- Узел 2: supply = 0 (транзит);
- Узел 3: demand = -5 (потребление);
- Узел 4: demand = -15 (потребление).
Решение задачи
1. Выбор модели
Для решения задачи потока минимальной стоимости используется специализированная модель потока минимальной стоимости. Эта модель разработана специально для задач на графах с потоками и использует эффективные алгоритмы, основанные на теории сетевых потоков.
2. Создание модели
Инициализируется объект модели потока минимальной стоимости.
// Создание модели потока минимальной стоимости
Модель = О2
.Модели()
.МодельПотокаМинимальнойСтоимости()
.СоздатьМодель();
3. Ввод данных
Определение дуг сети. Для каждой дуги указываются: начальный узел (хвост), конечный узел (голова), максимальный поток и стоимость единицы потока.
// Входные данные дуг (хвост, голова, максимальный поток и стоимости)
ДанныеДуг = Новый Массив;
ДанныеДуг.Добавить("0, 1, 15, 4");
ДанныеДуг.Добавить("0, 2, 8, 4");
ДанныеДуг.Добавить("1, 2, 20, 2");
ДанныеДуг.Добавить("1, 3, 4, 2");
ДанныеДуг.Добавить("1, 4, 10, 6");
ДанныеДуг.Добавить("2, 3, 15, 1");
ДанныеДуг.Добавить("2, 4, 4, 3");
ДанныеДуг.Добавить("3, 4, 20, 2");
ДанныеДуг.Добавить("4, 2, 5, 3");
// Преобразуем входные данные в числовой формат
Для К = 0 По ДанныеДуг.ВГраница() Цикл
ДанныеДуг[К] = О2.Утилиты().МассивЧиселИзСтроки(ДанныеДуг[К]);
КонецЦикла;
Вклады узлов (supply/demand). Массив вкладов определяет, сколько единиц потока производится (+) или потребляется (-) в каждом узле.
ВкладыУзлов = О2.Утилиты().МассивЧиселИзСтроки("20, 0, 0, -5, -15");
- Узел 0: +20 — производит 20 единиц
- Узлы 1, 2: 0 — транзитные узлы
- Узел 3: -5 — потребляет 5 единиц
- Узел 4: -15 — потребляет 15 единиц
Сумма всех вкладов должна равняться нулю (20 + 0 + 0 - 5 - 15 = 0), что означает, что всё произведённое будет потреблено.
4. Добавление дуг в модель
Каждая дуга добавляется в модель с указанием всех её параметров.
// Добавляем дуги в модель
Дуги = Новый Массив();
Для К = 0 По ДанныеДуг.ВГраница() Цикл
Дуга = Модель.Дуга(ДанныеДуг[К][0], ДанныеДуг[К][1], ДанныеДуг[К][2], ДанныеДуг[К][3]);
Дуги.Добавить(Дуга);
КонецЦикла;
Метод Дуга создаёт дугу и принимает четыре параметра:
- Хвост (tail) — начальный узел дуги;
- Голова (head) — конечный узел дуги;
- Максимальный поток (capacity) — пропускная способность дуги;
- Стоимость (unit cost) — стоимость транспортировки одной единицы потока.
5. Вклады узлов
Для каждого узла устанавливается его вклад (производство/потребление).
// Вклады узлов (производство и потребление)
Для К = 0 По ВкладыУзлов.ВГраница() Цикл
Модель.УстановитьВкладУзла(К, ВкладыУзлов[К]);
КонецЦикла;
Метод УстановитьВкладУзла связывает каждый узел с его вкладом в сеть.
6. Решение модели
Запускается процесс поиска оптимального решения.
// Выполняем поиск решения
Решение = Модель.Решить();
Решатель использует специализированные алгоритмы теории графов (например, алгоритм последовательных кратчайших путей или алгоритм масштабирования стоимости) для нахождения потока минимальной стоимости.
7. Вывод результатов
Результаты извлекаются и выводятся в удобном формате.
// Вывод результатов
СтатусРешения = Решение.Статус();
ОптимальнаяСтоимость = Решение.ОптимальнаяСтоимость();
Если НЕ Решение.РешениеНайдено() Тогда
Сообщение = "Обнаружена проблема с входными данными" + Символы.ПС;
Сообщение = Сообщение + "Статус: " + СтатусРешения;
Сообщить(Сообщение);
Возврат;
КонецЕсли;
Сообщение = "Минимальная стоимость потока: " + Строка(Решение.ОптимальнаяСтоимость()) + Символы.ПС;
Сообщение = Сообщение + Символы.ПС + "Потоки по дугам:" + Символы.ПС;
// Получаем потоки решения для всех дуг
Для Каждого Дуга Из Дуги Цикл
ПотокДуги = Решение.ЗначениеПотока(Дуга);
СтоимостьПотокаДуги = ПотокДуги * Дуга.Стоимость;
Сообщение = Сообщение + СтрШаблон(
"%1 → %2 %3 / %4, Стоимость: %5%6",
Дуга.Хвост,
Дуга.Голова,
ПотокДуги,
Дуга.МаксимальныйПоток,
СтоимостьПотокаДуги,
Символы.ПС
);
КонецЦикла;
Сообщить(Сообщение);
Полный код решения задачи
Ниже представлен полный код решения с текстовым выводом результатов. Вы также можете скачать пример в виде готовой обработки, в которую добавлен графический вывод потока в виде графа.
// Создание модели потока минимальной стоимости
Модель = О2
.Модели()
.МодельПотокаМинимальнойСтоимости()
.СоздатьМодель();
// Входные данные дуг (хвост, голова, максимальный поток и стоимости)
ДанныеДуг = Новый Массив;
ДанныеДуг.Добавить("0, 1, 15, 4");
ДанныеДуг.Добавить("0, 2, 8, 4");
ДанныеДуг.Добавить("1, 2, 20, 2");
ДанныеДуг.Добавить("1, 3, 4, 2");
ДанныеДуг.Добавить("1, 4, 10, 6");
ДанныеДуг.Добавить("2, 3, 15, 1");
ДанныеДуг.Добавить("2, 4, 4, 3");
ДанныеДуг.Добавить("3, 4, 20, 2");
ДанныеДуг.Добавить("4, 2, 5, 3");
// Преобразуем входные данные в числовой формат
Для К = 0 По ДанныеДуг.ВГраница() Цикл
ДанныеДуг[К] = О2.Утилиты().МассивЧиселИзСтроки(ДанныеДуг[К]);
КонецЦикла;
ВкладыУзлов = О2.Утилиты().МассивЧиселИзСтроки("20, 0, 0, -5, -15");
// Добавляем дуги в модель
Дуги = Новый Массив();
Для К = 0 По ДанныеДуг.ВГраница() Цикл
Дуга = Модель.Дуга(ДанныеДуг[К][0], ДанныеДуг[К][1], ДанныеДуг[К][2], ДанныеДуг[К][3]);
Дуги.Добавить(Дуга);
КонецЦикла;
// Вклады узлов (производство и потребление)
Для К = 0 По ВкладыУзлов.ВГраница() Цикл
Модель.УстановитьВкладУзла(К, ВкладыУзлов[К]);
КонецЦикла;
// Выполняем поиск решения
Решение = Модель.Решить();
// Вывод результатов
СтатусРешения = Решение.Статус();
ОптимальнаяСтоимость = Решение.ОптимальнаяСтоимость();
Если НЕ Решение.РешениеНайдено() Тогда
Сообщение = "Обнаружена проблема с входными данными" + Символы.ПС;
Сообщение = Сообщение + "Статус: " + СтатусРешения;
Сообщить(Сообщение);
Возврат;
КонецЕсли;
Сообщение = "Минимальная стоимость потока: " + Строка(Решение.ОптимальнаяСтоимость()) + Символы.ПС;
Сообщение = Сообщение + Символы.ПС + "Потоки по дугам:" + Символы.ПС;
// Получаем потоки решения для всех дуг
Для Каждого Дуга Из Дуги Цикл
ПотокДуги = Решение.ЗначениеПотока(Дуга);
СтоимостьПотокаДуги = ПотокДуги * Дуга.Стоимость;
Сообщение = Сообщение + СтрШаблон(
"%1 → %2 %3 / %4, Стоимость: %5%6",
Дуга.Хвост,
Дуга.Голова,
ПотокДуги,
Дуга.МаксимальныйПоток,
СтоимостьПотокаДуги,
Символы.ПС
);
КонецЦикла;
Сообщить(Сообщение);