Алгоритм 4

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

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

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

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

Из множества 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} объем входящего потока равен объему выходящего потока, т.е. справедливо равенство

S{x(v) |i Î V⁺(i)}= S{x(v)| iÎ V ^-(i)},

т.е.

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

Для вершины t

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

для вершины s

S{x(v)| iÎ V⁺(i)} -S{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) = S{d(v)| vÎV(E1, E2, +)},

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

X(E1, E2)= S{x(v)| vÎV(E1, E2,+)} - S{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 – место последней помеченной вершины.