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)

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

Алгоритм 2.

begin

для произвольной (только одной) вершины iE u(i):= 0;

M1:

найти дугу vV' для которой известен

потенциал только одной из ее вершин

если такой дуги нет то конец работы

алгоритма иначе

begin

определяем неизвестный потенциал

вершины дуги v из уравнения

u(h2))=u(h1(v))+c(v);

goto M1

end;

end;

Для проверки критерия оптимальности найденного решения используется алгоритм :

Алгоритм 3.

1. Среди всех дуг vV\V' ищем дугу v₀ такую, что u(h2(v₀)) > u(h1(v₀)) +(v₀).

2. Если такой дуги нет, то исходная задача (6.1-6.3) решена, иначе следует выполнить алгоритм 4 перехода к новому базисному дереву.

Алгоритм 4.

V':=V'U{v₀} где, v₀ – дуга, найденная в Алгоритме 3. Теперь граф G'=<E, V', H> содержит ровно один цикл G''=<E'', V'', H>, причем v₀V'. На подграфе G'' задаем направление обхода, совпадающее с направлением дуги v₀ и пропускаем по подграфу G'' в направлении обхода дополнительный поток величиной . Каждой дуге vV'' приписываем символ '+'', если направление дуги v совпадает с направлением обхода, и символ '-'' в противном случае. Находим =min x(v) среди vV'', которым приписан символ '-'. Полагаем x(v₀):=;

Для всех v  V"\{v₀} :

x(v):= x(v)+  , если дуге v приписан знак +;

x(v):= x(v)- , если дуге v приписан знак -.

Из множества V'\{v₀} исключаем дугу, для которой x(v)=0. Если таких дуг несколько, то удаляем только одну так, чтобы не нарушилась связность графа G'=<E, V', H>.

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

6.3. Алгоритм поиска исходного базисного дерева

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

Строим граф G=<E, V, H>, в котором E=E  {i₀}, где i₀ - дополнительная вершина V=VV1V2,

где V1 – множество дополнительных дуг, направленных от вершин - пунктов производства к дополнительной вершине i₀ ;

V2 – множество дополнительных дуг, направляемых от i₀ к промежуточным вершинам и вершинам-пунктам потребления.

Для vV полагаем c(v)=0;

для vV1 полагаем c(v)=1;

для vV2 полагаем c(v)=1.

Полагаем b(i₀)=0.

В качестве исходного базисного дерева берется подграф G=<E,V1V2,H>. Если в результате решения этой задачи оказалось, что оптимальное значение функционала строго больше нуля, то исходная задача (6.1) – (6.3) решения не имеет, в противном случае будет получено базисное дерево исходной задачи.

7.1. Задача о максимальном потоке в сети

Пусть задан ориентированный граф G=<E, V, H>, в котором направление каждой дуги vV означает направление движения потока (например, поток автомобилей ), пропускная способность каждой дуги равна d(v). На множестве вершин E выделены две вершины t и s. Вершина t является источником потока, s – стоком. Требуется определить максимальный поток, который может быть пропущен из вершины t в s .

Обозначим через x(v) величину потока движущегося по дуге v. Очевидно, что

0 x(v)  d(v) vV . (7.1)

В каждой вершине iE\{t, s} объем входящего потока равен объему выходящего потока, т.е. справедливо равенство

{x(v)|i  V⁺(i)}= {x(v)| i V ^-(i)},

т.е.

{x(v)| iV⁺(i)} - {x(v)| iV ^-(i)}=0. (7.2)

Для вершины t

 {x(v)| iV⁺(i)} - {x(v)/ iV ^-(i)}=-Q. (7.3)

для вершины s

{x(v)| i V⁺(i)} -{x(v)/ i  V ^-(i)}= Q. (7.4)

величина Q является величиной потока, который выходит из вершины t и входит в вершину s.

Требуется определить

Q  max (7.5)

при ограничениях (7.1) – (7.4).

Величины Q, x(v), vV, удовлетворяющие ограничениям (7.1) – (7.4), будем называть потоком в сети и, если они максимизируют величину Q, то максимальным потоком. Нетрудно видеть, что значения Q=0, x(v)=0, vV являются потоком в сети.

Задача (7.1) – (7.5) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.

Разобьем множество вершины Е на две непересекающиеся части Е1 и Е2 таким образом, чтобы tE1, sE2. Разрезом V(E1, E2), разделяющим t и s, будем называть множество V(E1, E2)V такое, что для каждой дуги v  V(E1, E2) либо h1(v)E1 и h2(v)E2, либо h1(v)E2 и h2(v)E1.

Разобьем множество V(E1, E2) на две части V(E1, E2, +) V(E1, E2, -) следующим образом:

V(E1, E2, +)={vV(E1, E2)| h1(v)E1 и h2(v)E2},

V(E1, E2, -)= { vV(E1, E2)| h2(v)E1 и h1(v)E2}.

Пропускной способностью разреза будем называть

Q(E1, E2) = {d(v)| vV(E1, E2, +)},

Потоком через разрез величину

X(E1, E2)= {x(v)| vV(E1, E2,+)} - {x(v)| vV(E1, E2,-)}.

Справедлива следующая

Теорема 7.1. (о максимальном потоке и минимальном разрезе).

В любой сети величина максимального потока из источника t в сток s равна минимальной пропускной способности Q(E1, E2) среди всех разрезов V(E1, E2), разделяющих вершины t и s.

Заметим, что в максимальном потоке

x(v)=d(v), vV(E1, E2, +),

x(v)=0, vV(E1, E2, -).

Пусть Q, x(v), vV - некоторый поток в сети, последовательность t=i(0), v(1), i(1), v(2), i(2),...,v(k), i(k)=s,

является цепью, соединяющей вершины t и s. Зададим на этой цепи направление движения от вершины t к s. Дуга v(j) из этой цепи называется прямой, если ее направление совпадает с направлением движения от t к s и обратной в противном случае. Эту цепь будем называть путем увеличения потока, если для прямых дуг v цепи x(v) < d(v) и для обратных x(v) > 0. По этой цепи можно пропустить дополнительный поток q из t к s величиной q = min (q1, q2), где q1=min (d(v) -x(v)), минимум берется по всем прямым дугам цепи, q2=min (x(v)), минимум берется по всем обратным дугам цепи.

Теорема 7.2.

Поток Q, x(v), vV максимальный тогда и только тогда, когда не существует пути увеличения потока.

Предлагаемый алгоритм решения задачи о максимальном потоке в сети основан на поиске пути увеличения потока из t в s, который, в свою очередь, основан на процессе расстановки пометок вершин. Будем говорить, что:

вершина i помечена пометкой [g(i), +v(i)], если до нее дошел некоторый дополнительный поток величиной q(i)>0, а также известна дуга, прямая дуга v(i), через которую поступил этот поток, либо помечена пометкой [g(i), -v(i)], если до нее дошел некоторый дополнительный поток величиной q(i)>0, а также известна обратная дуга v(i), через которую поступил этот поток;

вершина i просмотрена, если помечены все соседние с ней вершины.

Если помечена вершина s, то найден путь увеличения потока величиной q, который пропускается по этому пути. Для описания алгоритма нам понадобится также массив SPW, в который помещаются номера помеченных вершин в порядке их пометки. С1 – номер в массиве SPW просматриваемой вершины, С2 – номер последней помеченной вершины в этом массиве.

Замечание 7.1.

Массив SPW можно организовать как список ссылок на помеченные вершины, как очередь или стек, то С1– ссылка на место, просматриваемой вершины, C2 – место последней помеченной вершины.

Алгоритм 1.

begin

for vV do x(v):=0; {обнуление начального потока}

М1:

g(t):= {достаточно большое число};

SPW(1):=t; C1:=1;C2:=1;{вершина t помечена и внесена в массив SPW}.

for i  E \{t} do g(i):=0;{все вершины из Е\{t} не помечены}

M2:

i:=SPW(С1); {i-номер просматриваемой вершины}

for v  V^-(i) do {пометка по прямым дугам}

begin j:=h2(v);

if g(j)=0 then {т.е. вершина j не помечена}

if (d(v) -x(v)) >0 then {по дуге можно пропустить дополнительный поток в прямом направлении}.

begin

g(j):=min (g(i) d(v) -x(v));

v(j):=v;

C2:= C2+1; SPW(C2):=j;

if j=s then {дополнительный поток дошел до вершины s}

goto М3;

end;

end;

for v  V⁺(i) do {пометка по обратным дугам}

begin j:=h1(v);

if g(j)=0 then {т.е. вершина j не помечена}

if x(v) >0 then {по дуге можно пропустить дополнительный поток в обратном направлении}.

begin

g(j):=min (g(i) x(v));

v(j):=-v;

C2:= C2+1; SPW(C2):=j;

if j=s then {дополнительный поток дошел до вершины s}

goto М3;

end;

end;

if С1=C2 then stop; {все помеченные вершины просмотрены, но до вершины s дополнительный поток не дошел, т.е. задача решена, найден максимальный поток}

if C1C2 then

begin

С1:=C1+1;

goto М2; {переход на просмотр следующей помеченной вершины}

end;

М3:

begin {по найденному пути из t в s пропускается дополнительный поток}

i=s;

while i  t do

begin

v:=abs (v(i));

if v(i)>0 then

begin

x(v):=x(v)+g(s); {поток прошел по прямой дуге}

i:=h1(v);

end

else

begin

x(v):=x(v)-g(s);{поток прошел по обратной дуге}

i:= h2(s)

end;

end;

goto М1;{переход на поиск нового пути увеличения потока }

end;

end.

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

Алгоритм 2.

begin

Е1:=; E2:=;

for iE do

если g(i)>0 then {до вершины i дошел дополнительный поток}

Е1:=E1{i}

else Е2:=E2{i};

{E(1) - множество вершин, к которым существует цепь увеличения потока из вершины t, E(2) - множество вершин, к которым такой цепи нет}

V(E1 E2 +):= ; V(E1 E2 -):=  ;

for vV do

begin

if ((h1(v)  E1 ) and (h2(v)  E2 )) then

V(E1 E2 +):=V(E1 E2 +)  {v};

if ((h1(v)  E2) and (h2(v)  E1 )) then

V(E1 E2 -):=V(E1 E2 -)  {v};

end;

V(E1 E2):=V(E1 E2 +) V(E1 E2 -);

end.

Множество дуг V(E1, E2) составляет разрез с минимальной пропускной способностью.