MinCostFlow_TRA_LP1. Поток минимальной стоимости, Форд-Фалкерсон. Минимум затрат на транспортировку потока через сеть. Планирование поставок, логистика, ритейл. 1 интервал.

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

Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.

Дано:

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

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

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

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

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

Требуется:

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

кратко

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

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

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

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

Условия:

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

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

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

Критерий – минимум суммарной стоимости потока. Для минимизации стоимости используется критерий прибыли/издержек от выполнения операций. Для этого стоимость выполнения операции равна стоимости прохождения потока по дуге, деленной на 2 (объем потока в операции учитывается дважды — один входящий, другой выходящий).

кратко

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

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

кратко

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

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

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

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

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

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

Требуемый объем доставки – 20 шт. Задается наличием на заводе и отсутствием в магазине на начало (выделено желтым) и наличием в магазине и отсутствием на заводе на конец (выделено синим)

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

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

кратко

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

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

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

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

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

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

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

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

кратко

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

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

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

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

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

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

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

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

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

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

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

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

кратко