Метод нахождения максимального потока. Методы применения алгоритма нахождения максимального потока в сети

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

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

0£ x(v) £ d(v) , vÎV . (6. 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. (6.2)

Для вершины t

{x(v)| iÎV + (i)} -{x(v)¦ iÎV - (i)}=-Q, (6.3)

для вершины s

{x(v)| iÎ V + (i)} -{x(v)¦ i Î V - (i)}= Q. (6.4)

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

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

Q ® max (6.5)

при ограничениях (6.1-6.4).

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

Задача (6.1-6.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) = {x(v)| vÎV(E1,E2,+)}-{x(v)| vÎV(E1,E2,-)}

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

Теорема 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)) , минимум берется по всем прямым дугам цепи, q1=min (x(v)) , минимум берется по всем обратным дугам цепи.

Теорема 2 .

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

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

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

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

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

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

Рассмотрим сеть распределения (рис. 4.21), в которой выделены пункты 0 (вход, например, склад готовой продукции производителя) и п (выход, распределительные центры, склады оптовых и розничных организаций, потребитель) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij > 0, называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество материального потока, которое может проходить по соответствующей дуге в единицу времени.

Рис. 4.21.

Количество продукции, проходящее по дуге от i до j , будем называть потоком по дуге (i ,j ) и обозначать через . Очевидно, что

Если учесть, что весь материальный поток, вошедший в промежуточный пункт сети, должен полностью выйти из него, получим

Из естественного требования равенства потоков на входе и на выходе имеем

Величину Z назовем величиной потока в сети и поставим задачу максимизации Z при соблюдении обозначенных выше условий.

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

Рассмотрим универсальный алгоритм поиска в матричной форме.

Начальный этап алгоритма состоит в построении матрицы D 0, в которую заносятся значения пропускных способностей (для неориентированной дуги берем симметричные значения элементов матрицы ).

Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.

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

и переносим метки столбцов на строки. Затем берем ί-ю отмеченную строку, ищем в ней непомеченный столбец с , которому сопоставляем метки-индексы

Метки столбцов переносим на строки, и этот процесс продолжаем до тех пор, пока не будет отмечен п-й столбец.

Затем "обратным ходом" по индексам выясняем путь, приведший к η-й вершине, уменьшаем пропускные способности дуг пути (элементы матрицы) на V n и увеличиваем симметричные элементы на эту же величину.

Такая процедура продолжается до тех пор, пока отмечание n -й вершины не станет невозможным.

Максимальный поток может быть найден вычитанием из исходной матрицы D 0, получаемой после приведенной выше корректуры матрицы пропускных способностей:

Пример 4.4

Производство размещено в Москве. Для распределения продукции предприятие привлекает посредников, которые работают с предприятием через распределительные центры различных уровней. В европейской части России работает оптовое предприятие 1, обслуживаемое центральным распределительным центром. Оптовое предприятие 2 работает в ближайшем зарубежье (Украина, Белоруссия) и обслуживается региональным распределительным центром. Есть у предприятия на местном рынке (Москва и Московская область) свои клиенты – ритейлеры, которые получают продукцию с городского распределительного центра. Запасы регионального и городского распределительных центров пополняются с центрального распределительного центра.

Выделим фрагмент распределительной сети:

• склад готовой продукции производственного предприятия;
• центральный распределительный центр;
• региональный распределительный центр;
• городской распределительный центр;
• два оптовых предприятия;
• розничная точка, принадлежащая компании;
• потребители.

Рис. 4.22.

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

Граф сети распределения продукции представлен на рис. 4.23. Построим матрицу D 0, в которую занесем значения пропускных способностей звеньев распределительной сети (рис. 4.24).

Рис. 4.23.

Рис. 4.24.

Из нулевой строки отметим вершины (строки-столбцы) 1, 2 и 3 индексами μ = 0 и V, равными 30,10 и 10.

Из помеченной строки 1 отметим вершины 4 и 5 индексами μ = 1 и V4 = min (30,15) = 15, V5 = min (30,10) = 10.

Из строки 3 отметим вершину 6 и, наконец, из строки 4 – вершину 7 (рис. 4.25).

Рис. 4.25.

Обратным ходом по μ обнаруживаем путь: к вершине 7 от 4, к вершине 4 от 1, к вершине 1 от 0; корректируем элементы D 0 на величину потока V7 = 15.

Очередной шаг дает путь с потоком 5 (рис. 4.26).

Рис. 4.26.

Последующий шаг дает результат, представленный на рис. 4.27.

Рис. 4.27.

Дальнейшее отмечание невозможно. Отсюда получаем матрицу максимального потока (рис. 4.28).

Рис. 4.28.

В результате применения алгоритма нахождения максимального потока в сети получены результаты, представленные на рис. 4.29. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.

Потоки в сетях

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

Пусть задана сеть, состоящая из множества вершин Е и множества дуг, соединяющих некоторые упорядоченные пары вершин, взятых из Е. Будем предполагать, что она является симметрическим графом, т. е. если дуга () входит в сеть, то в нее входит и симметричная дуга (), хотя реально такой дуги может и не быть. Для определенности присвоим вершинам сети следующие номера: . Каждая вершина характеризуется интенсивностью . Вершины, для которых , назовем источниками, вершины, для которых , - стоками, а остальные - промежуточными. По путям сети направляются некоторые потоки - однородное вещество (газ, жидкость) или транспорт - из источников в стоки. Каждой дуге () сети поставлено в соответствие число , называемое пропускной способностью дуги. Под пропускной способностью дуги понимается максимальный поток, который она может пропустить за единицу времени. Пусть , и для остальных вершин, тогда - единственный источник, - единственный сток, а - промежуточные вершины сети.

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

(3.9)

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

(3.11)

Условие (3.9) отражает величину максимального потока, который равен количеству вещества, вытекающего из источника, или притекающего в сток. Условия (3.10) означают, что поток по каждой дуге должен быть неотрицательным и не превышать ее пропускной способности; из условия (3.11) следует, что количество вещества, притекающего в любую промежуточную вершину, равно количеству вещества, вытекающего из нее.

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

Проиллюстрируем это на примере.

Рассмотрим сеть, состоящую из трех источников и двух стоков (Рис. 3.10). Пусть, для определенности, данная сеть описывает следующую задачу.

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

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

Рис. 3.10. Введение фиктивного источника и стока

Пример 3.

Приведем пример решения задачи о максимальном потоке в Excel. Рассмотрим некоторую транспортную сеть (Рис. 3.11.). Предположим также, что транспортные потоки могут идти в обоих направлениях некоторых дуг (очевидно, данный случай является более общим и сложным для решения, чем случай односторонних транспортных потоков). На рисунке обозначены максимальные пропускные способности в обоих направлениях: например из пункта 3 в пункт 6 может быть транспортирован поток интенсивностью 4 единицы, и такой же поток – из пункта 6 в пункт 3 (нули у окончаний некоторых дуг означают невозможность транспортировки в соответствующем направлении). Требуется определить максимальную пропускную способность сети в целом, т.е. максимальное значение потока .

Рис. 3.11. Сетевой график примера 3.

Решение.

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

Максимизировать при ограничениях:

Введем данные на рабочий лист в соответствии с Рис. 3.12.

Рис. 3.12. Данные для решения задачи о максимальном потоке

Диапазон ячеек A6:Q6 отведем под расчетные значения переменных. В ячейки A8:A14, а также в целевую ячейку F13 введем следующие формулы

После запуска Поиска решения введем следующие ограничения:

В окне диалога Поиска решения в для диапазона изменяемых ячеек укажем A6:Q6.

В результате решения получим ответ: ; потоки в дугах представлены ниже

Следует отметить, что данная задача имеет неединственное оптимальное решение, то есть при максимальном потоке в 17 единиц может иметь место различное распределение потоков по дугам.

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

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

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

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

Объем информации, энергии или вещества, передаваемый в сети от узла x i к узлу x j , называют потоком и обозначают j ij .

Наибольший поток, который может пропустить дуга (x i , x j), называют пропускной способностью дуги и обозначают с ij .

Очевидно, что 0£j ij £ с ij .

В вершине-истоке х 0 величина потока есть сумма потоков по всем дугам, исходящим из вершины х 0 , т.е. j=å i j 0i + .

В вершине-стоке х k величина потока есть сумма потоков по всем дугам, заходящим в вершину х k , т.е. j=å i j ik - .

Для любой промежуточной вершины х i сумма исходящих потоков равна сумме заходящих потоков, т.е. å j j ij + =å k j ik - .

На рис. 3.29 показана условная сеть, содержащая вершину-исток х 0 , вершину-сток х k и две промежуточные вершины х i и х j . На каждой дуге в круглых скобках приведены обозначения потока и пропускной способности соответствующей дуги. При этом поток, подводимый к сети равен j=(j 0i +j 0j), поток отводимый от сети равен j=(j ik +j jk), поток из вершины х i в вершину х j равен j ij . Для вершины х i имеем j 0i =(j ij +j ik), для вершину х j - j jk =(j 0j +j ij).

Если множество вершин графа разбить на два непересекающихся подмножества, одно из которых содержит вершину-исток, а другое - вершину-сток, то множество дуг, соединяющих эти два множества, формируют разрез А i , пропускная способность которого равна сумме пропускных способностей дуг. Таких разрезов может быть несколько.

В таблице приведены четыре разреза для сети на рис. 3.29

Например, для разреза А 1 имеем Х’={x 0 } и X\Х’={х i , х j , х k }, для А 2 - Х’={х 0 , х i } и X\Х’={х j , х k }, для А 3 - Х’={х 0 , х i , x j } и X\Х’={х k }, для А 4 - Х’={х 0 , х j } и X\Х’={x i , х k }.

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

j max =min{С(A i)}

Итак, максимальный поток в сети с заданными пропускными способностями дуг можно находить, вычисляя пропускные способности разрезов и выбирая среди них - минимальную. Однако при таком решении остается неизвестным распределение потока по дугам.

Для поиска распределения потока по дугам разработано несколько алгоритмов. Особое место среди них занимает алгоритм Форда-Фалкерсона, суть которого состоит в разметке вершин графа.

Метка вершины графа указывает на возможность изменения потока через данную вершину и указывает источник этого изменения. На рис. 3.30 дан фрагмент сети, объясняющий суть алгоритма.

Если по дуге (х s , х i) возможно увеличение потока (j si < c si), то вершину х i следует пометить +s , что указывает на источник увеличения потока.

Если по дуге (х i , х j) возможно увеличение потока j ij < c ij , то вершину х j пометить +i . Это означает, что приращение потока Dj si пойдет по направлению дуги (х i , х j) от вершины х s .

Если насыщена дуга (х s , х i), т.е. j si =c si , то метку +s нельзя ставить у вершины х i . Следовательно, если вершина x i не помечена, то у вершины x j нельзя ставить метку +i.

Если по дуге (х t , х j) возможно увеличение потока, т.е. j tj < c tj , то вершину х j следует пометить +t , что указывает на источник увеличения потока.

Если вершина х j не имеет пометки +i , то для увеличения потока в фрагменте сети, следует уменьшить поток в дуге (х i , х j) и направить его далее по другим дугам фрагмента на сток. Для указания этого у вершины x i ставят метку – j. Это означает что при общем приращении потока на участке (х i , х j) он должен быть уменьшен на величину Dj tj .

Если насыщена дуга (х t , х j), т.е. j tj =c tj , то метку +t нельзя ставить у вершины х j . Следовательно, если вершина x j не помечена, то у вершины x i нельзя ставить метку -j.

Если насыщены обе дуги (х s , х i) и (х t , х j), что означает невозможность приращения потока Dj si и Dj tj , то нельзя ставить метки у вершин x i и x j и продолжения разметки следующих вершин сети до вершины-стока.

Так достигают максимального значения потока от вершин-истоков х s и х t по дугам к вершинам - стокам х i и х j .

Алгоритм Форда-Фалкерсона:

шаг 1 : присвоить всем вершинам графа индексы 0,1,2,...k; где 0-индекс вершины-истока графа, k -индекс вершины-стока графа;

шаг 2 : присвоить начальной вершине метку “0”;

шаг 3 : все непомеченные вершины х i , в которые идут ненасыщенные дуги из помеченной вершины х s , пометить индексом “+s”, что свидетельствует о возможности увеличения потока из вершины х s по дуге (х s , х i);

шаг 4 : все непомеченные вершины х i , из которых идут дуги (насыщенные или ненасыщенные) в помеченную вершину х j , пометить индексом “-j”, что свидетельствует о возможности уменьшения потока в вершину х j по дуге (х i , х j);

шаг 5 : если в результате этих операций окажется помеченной вершина-сток x k , то между начальной и конечной вершинами сети найдется маршрут, все вершины которого различны и с точностью до знака помечены индексами предыдущих вершин, формирующих переход, по которому можно увеличить поток, и перейти к шагу 6, иначе конец.

шаг 6 : увеличить поток в маршруте, сформированном на шаге 5, на единицу и перейти к шагу 3.

Признаком окончания работы алгоритма является невозможность пометки вершины-стока.

Пример : На рис. 3.31 дан граф. Найти величину максимального потока и его распределение в сети.

На каждой дуге (х i , х j) указаны величина потока и пропускная способность - (j ij , c ij).

Все расчеты сведены в две таблицы таблица а)

таблица b)

В таблице а) на каждом шаге итерации для каждой вершины графа указаны возможные метки, а в таблице b) даны приращения потока по дугам (х i , х j). Полужирным шрифтом выделены насыщенные дуги графа

В результате выполнения первого шага итерации возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0); (х k , х 2 , х 3 , х 0); (х k , х 2 , х 3 , х 1 , х 0);

(х k , х 3 , х 0); (х k , х 3 , х 1 , х 0)}. Пусть выбран n 0k =(х k , х 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((х 0 , х 3), (х 3 , х k)).

На втором шаге возможны те же переходы. Пусть выбран переход n 0k =(х k , х 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m={(х 0 , х 3), (х 3 , х k)}. При этом дуга (х 3 , х k) оказывается насыщенной, т. е. j 3k =c 3k =2.

На третьем шага возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0); (х k , х 2 , х 3 , х 0); (х k , х 2 , х 3 , х 1 , х 0)}. Пусть выбран n 0k =(х k , х 2 , х 3 , х 1 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 1), (x 1 , x 3), (x 3 , x 2), (x 2 , x k)). При этом оказывается насыщенной дуга (х 3 , х 2), т. е. j 32 =c 32 =1.

На четвертом шаге возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0)}. Пусть выбран n ok =(х k , х 1 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 1), (x 1 , x k)),. При этом оказывается насыщенной дуга (х 0 , х 1), т. е. j 01 =c 01 =2.

На пятом шаге возможны переходы: n 0k ={(х k , х 1 , -x 3 , х 0); (х k , х 2 , х 0)}. Пусть выбран n ok =(х k , х 1 , -x 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 3), (x 3 , x 1), (x 1 , x k))),. При этом оказывается насыщенной дуга (х 0 , х 3), т. е. j 03 =c 03 =3.

На шестом шаге возможен только один переход n 0k =(х k , х 2 , х 0), так как дуги (x 0 , x 1) и (x 0 , x 3) насыщены. Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 2), (x 2 , x k)),. При этом оказывается насыщенной дуга (х 0 , х 2), т. е. j 02 =c 02 =1.

На седьмом шаге невозможны ни один переход от x o к x k , так как дуги (x 0 , x 1), (x 0 , x 3) и (х 0 , х 2) насыщены и невозможно поставить метки у вершин x 1 , x 2 , и x 3 .