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

Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда-Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
- исток сети; - сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.

r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток - это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.


4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.


5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.


6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.

2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки (красные круги)


Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы - в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети
Вычисление величины максимального потока

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

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

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

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

Объем информации, энергии или вещества, передаваемый в сети от узла 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 .

Алгоритм расчета максимального потока в сетях

I итерация. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. В качестве М 1 возьмем маршрут(v и =V 1 , V 2 , V 5 , v с =V 7), рассмотренный в примере 1. Для него А (М 1) = 10.

Также несложно выделить независимый от М 1 маршрут М 2 = (v и =V 1 , V 3 , V 6 , v с =V 7). Выполним для него расчет максимальной пропускной способности и скорректируем пропускную способность дуг: А (М 2)= min {d 13 , d 36 , d 67 }= min {45, 40, 30}= 30. d 13 ¢= d 13 - 30 = 15, d 36 ¢= d 36 - 30 = 10, d 67 ¢= d 67 - 30 = 0.

II итерация. ШАГ 2. В качестве единственного независимого маршрута примем М 3 = (v и =V 1 , V 4 , V 2 , V 5 , v с =V 7). Для него:

А (М 3)= min {d 14 , d 42 , d 25 , d 57 }= min {15, 10, 10, 15}= 10.

d 14 ¢= d 14 - 10 = 5, d 42 ¢= d 42 - 10 = 0, d 25 ¢= d 25 - 10 = 0, d 57 ¢= d 57 - 10 = 5.

ШАГ 4. Коррекция сети. Максимальный поток А (М 3)вычитаем из дуг маршрута М 13 . Результат дан на рис.1.16 б.

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

Сетевое планирование

Любую задачу по проектированию либо построению достаточно сложного объекта (проект ) можно разбить на ряд более мелких составляющих шагов. От правильного выбора последовательности выполнения данных шагов зависят сроки выполнения всего проекта.

Весь комплекс действий по выполнению проекта представляют в виде совокупности событий и работ . Событиями называют отдельные этапы проекта. Работами называют процесс их выполнения. Весь комплекс событий и работ, необходимых для выполнения проекта, может быть представлен в виде двухполюсной сети Г = ({v и, v з }, V, X ), в которой:

а) все события обозначены множеством вершин V, среди них выделено исходное событие v и (начало работ) и завершающее событие v з (завершение выполнения всего проекта), внутренние вершины сети задают промежуточные события - этапы, которые необходимо выполнить в процессе реализации проекта,

б) все работы обозначены дугами, соединяющими между собой пары событий - вершин.

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

В качестве примера рассмотрим организацию некоторого производства. Проект требует выполнения следующих работ:

I) маркетинговые исследования, II) предпроектные исследования по оборудованию, III) организация сети сбыта, IV) проведение рекламной кампании, V) разработка технического задания на производственное оборудование, VI) разработка технической документации на производственные помещения и коммуникации, VII) закупка стандартного оборудования, VIII) проектирование и изготовление нестандартного оборудования, IX)строительство производственных помещений и монтаж коммуникаций, X) монтаж стандартного оборудования, XI) монтаж нестандартного оборудования, XII) пусконаладочные работы.

Данные работы обозначим в сетевом графике дугами с соответствующими номерами.

Событиями в данном проекте будут следующие:

1) начало работ (исходное событие), 2) завершение маркетинговых исследований, 3) завершение предпроектных исследований, 4) организация сети сбыта, 5) организация рекламной кампании, 6) подготовка технического задания на производственное оборудование, 7) завершение разработки технической документации на производственные помещения и коммуникации, 8) завершение закупки стандартного оборудования, 9) завершение проектирования и изготовления нестандартного оборудования, 10) завершение строительства производственных помещений и монтажа коммуникаций, 11) завершение установки оборудования и пуско-наладочных работ,

12) завершение проекта (завершающее событие).

Событиям сопоставляем вершины с соответствующими номерами. Сетевой график выполнения проекта дан на рис. 1.17:

Рис.1.17. Сетевой график выполнения проекта

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

Рассмотрим ребро (i, j) с (начальной) пропускной способностью. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись - остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

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

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

Множество узлов j, в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью >0 для всех j. Если, выполняем 3 этап, в противном случае переходим к 4.

В находим узел k, такой, что. Положим и пометим узел k меткой. Если k=n, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i=k и возвращаемся к 2 этапу.

Откат назад. Если i=1, сквозной путь не возможен, и переходим к 6. Если, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем его из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко 2 этапу.

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

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

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

1) , если поток идет от узла i к j,

2) , если поток идет от узла j к i.

а) при m найденных сквозных путях максимальный поток выражается

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

Пример 1. Найти максимальный поток в сети рис. 1

Итерация 1. =

3) k=3, так как. Назначаем и помечаем узел 3 меткой. i=3 и возвращаемся к 2)

5) k=5 и. Помечаем узел 5 меткой. Получаем сквозной путь.

6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: . и. Вычисляем остаточные пропускные способности вдоль пути:

Итерация 2.

1) и помечаем узел 1 меткой. i=1

2») (, поэтому узел 5 не включается в

3») k=4, и помечаем узел 4 меткой. i=4 и возвращаемся к 2)

2""") (так как узлы 1 и 3 помечены, они не включаются в)

3""") k=5 и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)

Итерация 3.

1) и помечаем узел 1 меткой. i=1

3) k=2, и помечаем узел 2 меткой. i=2 и возвращаемся к 2)

3") k=3 и. Помечаем узел 3 меткой. i=3 и возвращаемся к 2)

2») (так как) переходим к 4)

4) метка узла 3 показывает номер предшествующего узла. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. и возвращаемся к 2)

2""") (так как узел 3 удален из возможного сквозного пути)

3""") и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)

5) и. Вычисляем остаточные пропускные способности вдоль пути:

Итерация 4. на этой итерации получен путь с

Итерация 5. на этой итерации получен путь с

Итерация 6. новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к 6) для определения решения

6) максимальный объем потока в сети равен единиц.

Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей из первоначальных значений пропускных способностей.

Результаты вычислений: табл. 1

Графическое последовательное выполнение алгоритма нахождения максимального потока (пример 1)

д) е) Сквозных путей нет

Рис.

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).

Табл.2. Исходные данные к задаче о максимальном потоке

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)

Табл.3. Решение задачи о максимальном потоке

Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М. Согласно рис. 2 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM, а именно, Х 01, Х 02, Х 03, Х 12, Х 13, Х 14, Х 23, Х 24, Х 34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

Х 01 + Х 02 + Х 03 = F (0)

Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)

Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)

Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)

Х 14 - Х 24 - Х 34 = - F (4)

Х КМ? 0, К, М = 0, 1, 2, 3, 4

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) - это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).

Транспортная задача
Может возникать в физике, экономике и т.д.
На отдельные компоненты транспортной сети
(сеть железнодорожных, автомобильных и т.д.
путей; сеть трубопроводов и т.д.) наложены
ограничения – их максимально допустимая
нагрузка.
Необходимо определить максимально
возможное количество пассажиров, товара,
продукта и т.д., которое можно провезти по этой
сети и каким образом.
Мы построим графовую дискретную модель
этой транспортной задачи и решим ее в этой
модели.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.