Нахождение потока наименьшей стоимости.

Нахождение потока наименьшей стоимости.

 

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

Все ребра допускают только одностороннее направление потока, т.е. являются (ориентированными) дугами.

Каждой дуге поставлена в соответствие (неотрицательная) стоимость прохождения единицы потока по данной дуге.

Дуги могут иметь положительную нижнюю границу пропускной способности.

Любой узел сети может выступать в качестве источника и стока.

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

Эта задача решается с помощью специального симплексного алгоритма.

Рассмотрим сеть G=(N,A) с ограниченной пропускной способностью, где N – множество узлов, A – множество дуг. Обозначим:

xi j – велиичина потока, протекающего от узла i к узлу j,

uij – верхняя пропускная способность дуги (i,j),

lij – нижняя пропускная способность дуги (i,j),

сij – стоимость прохождения потока по дуге (i,j),

fi – величина результирующего потока, протекающего через узел j.

 

 

Компания “Зернышко” снабжает зерном из трех зернохранилищ три птицеводческие фермы. Предложение зернохранилищ составляет 100, 200 и 50 тонн зерна в месяц. Компания может транспортировать зерно по железной дороге, за исключением трех маршрутов, где используется автомобильный транспорт.

 

 

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

Используя данные выше определения, можно записать задачу ЛП для сети с ограниченной пропускной способностью следующим образом:

 

Условие сбалансированности сети: ∑fi=0. Сбалансированность сети не гарантирует существования допустимого решения: этому может помешать ограниченность пропускных способностей дуг.

Алгоритм решения базируется на стандартном симплекс-методе и теории двойственности.

Модификация алгоритма симплекс-метода заключается в особых правилах ввода и исключения переменных (дуг), то есть в особых условиях оптимальности и допустимости, облегчающих процесс вычислений.

Базисному решению соответствует миинимальное остовное дерево, построенное на сети.