MaxFlow_TRA_LP1. Максимальный поток, Данциг. Максимум перевозок через транспортную сеть. Планирование поставок, логистика, ритейл. 1 интервал.

Постановка задачи

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

Дано:

•  1 источник – завод (склад), с которого начинается передача потока (перевозка товара).

•  1 сток – магазин (склад), которым заканчивается передача потока (перевозка товара).

•  Набор промежуточных вершин (складов), через которые проходит поток (перевозятся товары).

•  Набор дуг (дорог), соединяющих вершины графа. Каждой дуге сопоставляется пропускная способность.

•  Величина потока (объем товара) который требуется передать от источника к стоку.

Требуется:

Найти максимально возможную величину потока (объем товара) который можно передать от источника к стоку. Т.е. максимально возможный объем товара, который можно перевезти от завода до магазина.

кратко

Число установок соответствует числу вершин графа – завода, магазина, складов.

Установка отражает прохождение потока через вершину графа – прохождение товара через склад.

Операциями установки является прохождение потока по дуге графа, исходящей из вершины – прохождение товара по одной из дорог, выходящих из склада.

Потоками операции является величина потока, проходящего по дуге графа – объем товара, перевезенного по дороге.

Условия:

Для потоков операций установок задается ограничение баланса – товар не задерживается по дороге. Отсутствие буферизации в вершинах графа задается ограничениями на границы емкости в конце горизонта – товар не задерживается и не накапливается на складах.

Для задания требования по величине потока из источника в сток используются остатки емкостей и границы емкостей в конце горизонта – задается объем перевозки товара.

Ограничения на пропускную способность задается границами плана по потокам за горизонт.

Критерий – максимум потока, проходящего через транспортную сеть. Для максимизации потока используется критерий суммарных прибыли-затрат от продаж-покупок. Для этого цена емкости стока равна 1, и ее накопление аккумулирует поток через транспортную сеть.

кратко

Рисунок. Общий вид потоковой схемы объекта «краткая»

Рисунок. фрагмент потоковой схемы объекта «с именами»

кратко

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

Схематически это можно представить:

Рисунок. Пропускная способность и стоимость перевозки по участкам сети.

Примечание. Первая пометка является пропускной способностью, а вторая – стоимостью (в данной задаче не используется).

Пропускная способность участков сети задается ограничением на план по потоку

Рисунок. Фрагмент формы – установка, операция, поток

Критерий задачи – максимум суммарного потока перевозок через транспортную сеть, стоимость перевозок не учитывается.

Задается ценой последнего узла сети – Магазина и критерием максимума прибыли-затрат от продаж-покупок

Рисунок. Фрагмент формы – стадия, емкость

кратко

Выбор способа доставки объема товара по участкам пути

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Запасы товара в исходном заводе, промежуточных складах, объем доставки по отдельному участку.

Рисунок. Фрагменты формы – стадия, емкость

Примечание. Запасы завода не учитываются, ограничения на них нет. Запасы во всех промежуточных складах равны 0 – товар не накапливается на промежуточных складах.

Запасы товара промежуточных складах, магазине, объем доставки по отдельному участку.

Рисунок. Фрагменты формы – стадия, емкость

Примечание. Запасы во всех промежуточных складах равны 0 – товар не накапливается на промежуточных складах. Запас в магазине не ограничивается.

кратко

Доставленные товары по участкам транспортной сети:

Рисунок. Гистограммы изменения состояния емкостей

Перевезенные товары с завода в магазин:

Рисунок. Гистограммы изменения состояния емкостей

Объяснения решения

Рисунок. Фрагмент трассы объяснений Решателя LP

Размерность задачи и характеристики расчета

Размерность задачи:

Стадий 3, Установок 6, Операций 18, Емкостей 19, Интервалов 1, Переменных 128, Ограничений 238.

Характеристики расчета:

Минут до оптимального 00:00:00,231

Решатель LpSolve, сервер Intel Core i5-4570 3,2GHz.

кратко