Алгоритм 1.

6.1. Транспортная задача в сетевой постановке

Пусть G=<E, V, H> cвязный ориентированный граф, где Е – множество вершин, V – множество ориентированных дуг, H– отображение H:V®E´E, H(v)=(h1(v), h2(v)). Вершину h1(v) будем называть началом дуги v, h2(v) – ее концом. V⁺(i) – множество дуг, входящих в вершину i, V^-(i) – множество дуг, выходящих из вершины i. Все вершины графа делятся на пункты производства (источники), пункты потребления (стоки)потока и промежуточные вершины. Для каждой вершины iÎЕ известна величина, задающая объем производства или потребления i-й вершины, причем если b(i)<0,то вершина i – пункт производства (источник),если b(i)>0, то i-ая вершина – пункт потребления (сток) потока, если b(i)=0, то вершина i-промежуточная вершина.

Для каждой дуги vÎV задана величина c(v), характеризующая стоимость перевоза единицы груза по данной дуге.

Задача состоит в том, чтобы определить количество перевозимого груза x(v) по каждой дуге vÎV при условии, что весь поток из пунктов производства будет вывезен, потребности всех пунктов потребления будут удовлетворены и суммарная стоимость транспортного потока будет наименьшей.

Приведем формализованную постановку данной задачи:

L(x)=å { c(v) ´ x(v) | vÎ V } ® min, (6.1)

при ограничениях

å{x(v) | vÎV⁺(i)}-å{x (v):vÎV ^-(i)} =b(i), iÎ E, (6.2)

x(v) ³ 0, v ÎV. (6.3)

Здесь формула (6.1) – минимизируемый функционал (суммарная стоимость перевоза потока), (6.2)– уравнение материального баланса, т.е. суммарный поток, входящий в вершину, минус суммарный поток ,выходящий из вершины, должен быть равен объему потока, производимому (потребляемому) вi-м пункте. Соотношение (6.3)означает, что транспортируемый поток движется только в направлении дуг графа G.

Эта задача разрешима, если å { b(i)| iÎE }=0. Легко видеть, что она является задачей линейного программирования и может быть решена алгоритмом симплекс-метода.

Однако сетевая структура задачи позволяет разработать более эффективные методы ее решения. Таковым является метод потенциалов для решения транспортных задач.

Метод потенциалов решения данной задачи предполагает, что на исходном графе некоторым способом определено начальное исходное базисное дерево G'=<E, V', H> (его дуги будем называть базисными), по которому осуществляется перевозка груза таким образом, что для vÎV' x(v) ³ 0 и для всех внебазисных дуг v, т.е. для vÎV\V', x(v)=0.

Для определения величин x(v)ÎV' можно воспользоваться следующим алгоритмом:

Алгоритм 1.

begin

while ( |E| >1 ) do

begin

for (iÎE) do

if ( |V ' ⁺(i)| + |V ' ^-(i)| = 1 ) then {т.е.вершина i – концевая на

дереве G}

begin

if ( |V' ⁺(i)| = 1 ) then

for (vÎV' ⁺(i)) do

begin

x(v):=b(i);

b(h1(v)):=b(h1(v))+x(v);

end;

if ( |V' ^-(i)| = 1 ) then

for vÎV' ^-(i) do

begin

x(v) := -b(i);

b(h2(v)):=b(h2(v))-x(v);

end;

удаляем из графа G'=<E, V', H> вершину i и инцидентную ей дугу.

end;

end.

Замечание 6.1.

В результате работы алгоритма может получиться недопустимое решение, т.е. для некоторых vÎV x(v)<0. В этом случае следует сменить исходное базисное дерево. Однако это не гарантирует, что на нем будет получено допустимое решение.

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

Будем считать, что исходное базисное дерево G’найдено, и для vÎV' определены x(v)>0.

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

6.2. Критерий оптимальности

Пусть x(v), vÎV - такое решение задачи (6.1 – 6.3),что для vÎV\V' x(v)=0 и для vÎV' x(v)³ 0. Это решение оптимально тогда и только тогда, когда существуют числа u(i), iÎE называемые потенциалами такие что

u(h2(v))=u(h1(v))+c(v) vÎV' (6.4)

u(h2(v))£ u(h1(v))+c(v) v Î V\V' (6.5)

Для определения потенциалов применяется следующий алгоритм:

12 3 4 5 Следующая ⇒