Решение задачи о максимальном потоке. Алгоритм Фалкерсона

Пусть дана некоторая сеть. Разобьем множество вершин сети на два непересекающихся подмножества А и В так, чтобы исток I попал в подмножество А, а сток S – в подмножество В. В этом случае говорят, что на сети произведен разрез, отделяющий исток I от стока S. В результате произведенного разбиения вершин появятся ребра (i, j), конечные точки которых окажутся в разных подмножествах. Совокупность ребер (i, j), начальные точки которых принадлежат подмножеству А, а конечные – подмножеству В, называют разрезом сети и обозначают А/В.

На рисунке 8.1 изображена сеть, на которой около каждого ребра указана его пропускная способность в обоих направлениях (в скобках). Кроме этого, на рисунке 8.1 сети произведены два разреза: I и II. При разрезе I вершины сети оказались разбиты на два подмножества А={1} и В={2, 3, 4, 5}, а ребрами, образующими разрез стали (1, 2), (1, 3) и (1, 4). При разрезе II А={1, 2}; В={3,4,5}, а образуют разрез ребра (1, 3), (14)), (2, 3)  и (2, 5).

Введем важные определения.

Величина:

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

Пусть на сети задан поток X ={ x_ij } и произведен разрез А/В. Величина

Представляет собой сумму потоков x_ij по всем ребрам разреза, называется потоком через разрез.

Если на сети задан поток X ={ x_ij } и произведен разрез А/В, то хотя бы одно ребро любого полного пути, ведущего из истока I в сток S будет обязательно принадлежать разрезу А/В. При этом величина потока по любому полному пути не превышает пропускную способность каждого его ребра, а потому величина X суммарного потока, устремленного из истока I в сток S, не может превысить пропускную способность любого разреза сети:

Оказывается, если удается построить на сети поток X ={ x_ij }, величина которого равна пропускной способности некоторого разреза А/В, то этот поток будет максимальным, а разрез А/В обладает минимальной пропускной способностью.

Справедлива следующая теорема Форда – Фалкерсона, которая имеет важное прикладное значение. На любой сети максимальная величина потока из истока I в сток S равна минимальной пропускной способности разреза, отделяющего I от S. Доказательство приведено, например, в [2].

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

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

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

1) x_ij < r_ij и дуга согласованна;

2) r_ij >0 и дуга несогласованна.

По увеличивающей цепи можно пустить поток величины Q, где Q = min { q_i, 1 ≤ i ≤ l } и q_i = { x_ij – r_ij, если дуга согласованна, x_ij, если дуга не согласованна }. Для того, чтобы увеличить величину потока сети на Q, необходимо увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.

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

Для нахождения увеличивающей цепи ими был предложен «Метод расстановки пометок» [2]. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Как только сток оказался помеченным, мы можем говорить о существовании увеличивающей цепи из истока в сток. Метка, «наносимая» на вершины сети, содержит необходимый минимум информации, достаточный для того, чтобы восстановить эту цепь и определить величину, на которую можно изменить поток в ней. Вершина сети может находиться в одном из 3-х состояний: «непомеченная», «помеченная» и «просмотренная».

Этап 1. Расстановка меток

Все вершины получают статус непомеченных.

Процедура расстановки меток.

Возьмем произвольный помеченный, но не просмотренный узел z. Пусть он имеет пометку [ i, +, e (z)], где i – вершина из которой был помечен z; флаг, показывающий, что дуга (i, z) согласованна; e – величина потока, который можно пропустить по этой дуге. Рассмотрим все непомеченные смежные вершины y, такие что дуга (z, y) согласованна. Пометим вершину y меткой [ z, +, e (y)], где e (y) = min { e (z), r_zy – x_zy }. Затем рассмотрим все непомеченные смежные вершины y, соединенные с ней несогласованной дугой. Пометим их меткой [ z, -, e (y)], где e (y) = min { e (z), x_zy }. Теперь все рассмотренные узлы y имеют статус помеченных, а узел z - просмотренный.

Эта общая для всех узлов сети процедура. Пометим исток меткой [~, ~, ∞] и будем последовательно вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только процедура будет вызвана для стока, будет получена увеличивающая цепь и следует перейти ко второму этапу. В противном случае процедура будет вызываться, пока все помеченные вершины не станут просмотренными, и если сток сети не был достигнут – увеличивающая цепь не может быть построена и по теореме Форда-Фалкерсона имеющийся поток сети является максимальным.

Этап 2. Изменение потока

Процедура изменения потока дуги.

Возьмем узел z. Если он имеет метку [ y, +, e ], то увеличим поток по дуге (y, z) на e. Если он имеет метку [ y, -, e ], то уменьшим поток по дуге (y, z) на e. Если y не является источником, то вызовем процедуру для узла y.

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

Алгоритм Форда-Фалкерсона гарантирует нахождение максимального потока только в сетях с целочисленными пропускными способностями. На практике «чистый» алгоритм Форда-Фалкерсона не применяется, т.к. оценка его производительности зависит от величины пропускных способностей дуг сети. Все дело в том, что в нем не дается каких либо правил выбора увеличивающей цепи.

Рассмотрим сеть на рисунке 8.2. Предположим, что реализован алгоритм, отдающий предпочтение увеличивающим цепям максимальной длины. В этом случае на первом шаге мы пустим дополнительный поток по цепи (1,2),(2,3),(3,4) (рисунок 8.3).

Рисунок 8.2 – Рассматриваемая сеть

 

Рисунок 8.3 – Рассматриваемая сеть после первой итерации

 

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

 

Рисунок 8.4 – Рассматриваемая сеть после второй итерации

 

Очевидно, что для нахождения максимального потока понадобиться 1000 итераций. В то время как, если бы мы на первом шаге выбрали цепь (1,2),(2,4), то результат был бы получен за одну итерацию. На практике, величина пропускных способностей часто зависит от единиц измерения, и может принимать огромные значения. Если же допустить иррациональные пропускные способности дуг, то можно привести пример невычислимой сети. Величина потока в такой сети не превысит даже четверти истинного значения. Подобная неопределенность длилась не долго, уже вначале 70-х г. были предложены сразу 2 правила выбора увеличивающих цепей, которые существенно улучшают алгоритм Форда-Фалкерсона.

Наиболее известны алгоритмы Эдмондса-Карпа:

1) Алгоритм кратчайших увеличивающих цепей. Суть этого алгоритма сводится к тому, что все дуги имеют единичную длину. В качестве увеличивающей цепи выбирается цепь наименьшей длины, при этом не учитывается пропускная способность дуг этой цепи.

2) Алгоритм локально-максимального увеличения. Согласно этому методу, поток изменяется вдоль цепи с наибольшей пропускной способностью.

Мы остановимся на последнем, который изложен в [6].

Алгоритм Эдмондса-Карпа

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

Для произвольного узла j, получающего поток от узла i, определим метку [a_j,i], где a_i – величина потока, протекающего от узла j к узлу i. Алгоритм предполагает выполнение следующих действий.

Шаг 1 Для всех ребер (i,j) положим остаточную пропускную способность, равной первоначальной пропускной способности, т.е. приравняем (с _ij, с _ji) = (r _ij, r_ji). Назначим а₁=∞ и пометим узел 1 меткой [∞,-]. Полагаем i =1 и переходим к шагу 2.

Шаг 2 Определяем множество S _i, как множество узлов j, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. c_ij >0 для всех j Î S_i) и каждый из узлов еще не помечен никакой меткой. Если S_i ¹ Æ, выполняем третий шаг, в противном случае переходим к шагу 4.

Шаг 3 В множестве S_i находим узел k, такой что . Положим a _k = c_ik и пометим узел k меткой [ a_k, i ]. Если последней меткой помечен узел стока (т.е., если k=n), сквозной путь найден, и мы переходим к пятому шагу. В противном случае полагаем i=k и возвращаемся ко второму шагу.

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

Шаг 5 (Определение остаточной сети). Обозначим через N _p ={1, k ₁, k ₂,…, n } множество узлов, через которые проходит p -й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n). Тогда максимальный поток, проходящий по этому пути, вычисляется как f _p =min{ a ₁, a_{k 1}, a_{k 2},…, a_n }. Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину f_p в направлении движения потока и увеличиваются на ту же величину в противоположном направлении. Таким образом для ребра (i,j), входящего в сквозной путь, текущие остаточные стоимости (с _ij, с _ji) изменятся следующим образом:

а) (с_ij- f_p, c_ji + f_p), если поток идет от узла i к узлу j,

б) (с_ij+ f_p, c_ji - f_p), если поток идет от узла j к узлу i.

Далее восстанавливаем все узлы, удаленные на шаге 4 и стираем все метки на всех узлах. Полагаем i=1 и возвращаемся ко второму шагу для поиска нового сквозного пути.

Шаг 6 (Решение).

а) При m найденных сквозных путях максимальный поток вычисляется по формуле F=f₁+ f ₂ +…+ f_m.

б) Имея значения начальных (r _ij, r_ji) и конечных (с _ij, с _ji) пропускных способностей ребра (i,j), можно вычислить оптимальный проток через это ребро следующим образом. Положим (a, b)= (r _ij -с _ij, r_ji - c_ji). Если a>0, поток, проходящий через ребро (i,j), равен a. Если b>0, тогда поток равен b. Случай, когда одновременно a>0, b>0, невозможен.

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

Пример 8.1

Решим задачу для сети, изображенной на рисунке 8.1 с помощью  алгоритма Эдмондса-Карпа. На рисунке 8.5 предлагается графическая иллюстрация выполнения алгоритма.

Итерация 1

Положим остаточные пропускные способности (с _ij, с _ji) всех ребер равными первоначальным пропускным способностям (r _ij, r_ji).

Шаг 1. Начинаем а₁=∞ и помечаем узел 1 меткой [∞, - ]. Полагаем i=1.

Шаг 2. S ₁ =[2,3,4] ¹ Æ.

Шаг 3. k =3, поскольку c ₁₃ =max {c ₁₂,c ₁₃,c ₁₄ }=max {20,30,10}=30. Назначаем a ₃ =c ₁₃ =30 и помечаем узел 3 меткой [30,1]. Полагаем i=3 и возвращаемся к шагу 2.

Шаг 2. S₁=[4,5] ¹ Æ.

Шаг 3. k=5 и a₅=c₃₅=max{10,20}=20. Помечаем узел 5 меткой [20,3]. Получен сквозной путь. Переходим к шагу 5.

Шаг 5. Сквозной путь определяем по меткам, начиная с 5 узла. И заканчиваем узлом 1: (5) ® [20,3] ® (3) ® [30,1] ® (1). Таким образом, N ₁ ={1,3,5} и f ₁ =min {a ₁, a ₃,a ₅ }={∞,30,20}=20. Вычисляем остаточные пропускные способности вдоль пути N ₁:

(с₁₃, с₃₁)=(30-20, 0+20)=(10,20),

(с₃₅, с₅₃)=(20-20, 0+20)=(0, 20).

Итерация 2

Шаг 1. Начинаем а₁=∞ и помечаем узел 1 меткой [∞, - ]. Полагаем i=1.

Шаг 2. S ₁ =[2,3,4] ¹ Æ.

Шаг 3. k =2, поскольку c ₁₂ =max {c ₁₂,c ₁₃,c ₁₄ }=max {20,10,10}=20. Назначаем a ₂ =c ₁₂ =20 и помечаем узел 2 меткой [20,1]. Полагаем i=2 и возвращаемся к шагу 2.

Шаг 2. S ₂=[ 3,5] ¹ Æ.

Шаг 3. k =3, a ₃ =c ₂₃ =40. Помечаем узел 3 меткой [40,2]. Полагаем i=3 и возвращаемся к шагу 2.

 

Шаг 2. S₃=[4]¹Æ.

Шаг 3. k =4, a ₄ =c ₃₄ =10. Помечаем узел 4 меткой [10,3]. Полагаем i=4 и возвращаемся к шагу 2.

 

Шаг 2. S ₄ =[5] ¹ Æ. Поскольку узлы 1 и 3 уже помечены, они не включаются в S₄.

Шаг 3. k =5, a ₅ =c ₄₅ =20. Помечаем узел 5 меткой [10,3]. Полагаем i=4 и возвращаемся к шагу 2.

Шаг 5. N ₂ ={1,2,3,4,5} и f ₂ =min{∞,20,40,10,20}=10. Вычисляем остаточные пропускные способности вдоль пути N ₂:

(с₁₂, с₂₁)=(20-10, 0+10)=(10,10),

(с₂₃, с₃₂)=(40-10, 0+10)=(30,10),

(с₃₄, с₄₃)=(10-10, 5+10)=(0,15),

(с₄₅, с₅₄)=(20-10, 0+10)=(10, 10).

Итерация 3

Шаг 1. Начинаем а₁=∞ и помечаем узел 1 меткой [∞, - ]. Полагаем i=1.

Шаг 2. S₁=[2,3,4] ¹ Æ.

Шаг 3. k =2, a ₂ =c ₁₂ =max {10,10,10}=10 и помечаем узел 2 меткой [10,1]. Полагаем i=2 и возвращаемся к шагу 2.

 

Шаг 2. S ₂ =[3,5] ¹ Æ.

Шаг 3. k =3, a ₃ =c ₂₃ =30 и помечаем узел 3 меткой [30,2]. Полагаем i=3 и возвращаемся к шагу 2.

 

Шаг 2. S₃={ Æ } (поскольку c ₃₄ =c ₃₅ =0). Переходим к шагу 4.

Шаг 4. Метка [30,2] узла 3 показывает номер предшествующего узла r =2. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. Полагаем i=r=2 и возвращаемся к шагу 2.

Шаг 2. S ₄ =[5] ¹ Æ. Поскольку узел 3 удален из возможного сквозного пути.

Шаг 3. k =5, a ₅ =c ₂₅ =30. Помечаем узел 5 меткой [30,2]. Получен сквозной путь. Идем к шагу 5.

Шаг 5. N ₃ ={1,2,5} и f ₃ =min{∞,10,30}=10. Вычисляем остаточные пропускные способности вдоль пути N ₃:

(с₁₂, с₂₁)=(10-10, 10+10)=(0,20),

(с₂₅, с₅₂)=(30-10, 0+10)=(20,10).

 

Итерация 4

На этой итерации получается путь N ₄ ={1,3,2,5} с f ₄ =10.

Итерация 5

На этой итерации получен путь N ₅ ={1,4,5} с f ₅ =10.

 

Рисунок 8.4 Графическая иллюстрация метода Эдмондса-Карпа

 

Итерация 6

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

Шаг 6. Максимальный поток в сети равен F=f₁+ f ₂ +…+f ₅ =20+10+10+10+10=60. Значения потока по различным ребрам вычисляются путем вычитания последних остаточных пропускных способностей из первоначальных значений пропускных способностей. Значения приведены в таблице 8.2

 

Таблица 8.2 Результаты вычисления примера 8.1

Ребро	(rij-rji)-(cij-cji)	Величина потока	Направление
(1,2)	(20,0)-(0,20)=(20,-20)	20	1®2
(1,3)	(30,0)-(0,30)=(30,-30)	30	1®3
(1,4)	(10,0)-(0,10)=(10,-10)	10	1®4
(2,3)	(40,0)-(40,0)=(0,0)	0	-
(2,5)	(30,0)-(10,20)=(20,-20)	20	2®5
(3,4)	(10,5)-(0,15)=(10,-10)	10	3®4
(3,5)	(20,0)-(0,20)=(20,-20)	20	3®5
(4,5)	(20,0)-(0,20)=(20,-20)	20	4®5

 

 

Контрольные вопросы

1 Что называется сетью?

2 Почему задача о максимальном потоке может решаться симплекс-методом.

3 Что такое разрез сети?

4 В чем суть теоремы Форда-Фалкерсона?

5 Какие недостатки имеются в алгоритме Форда-Фалкерсона?

6 Объясните алгоритм Эдмондса-Карпа.

 

Приложение А

(справочное)

Перечень ключевых слов

 

 

Анализ чувствительности	Неограниченное решение
Базисное решение	Опорное решение
Венгерский метод	Оптимальное допустимое решение
Графическое решение задачи ЛП	Отсутствие допустимых решений
Двойственная задача	Переменные избыточные
Двойственные цены	Переменные остаточные
Двойственный симплекс-метод	Переменные свободные
Достаточное правило допустимости	Приведенная стоимость
Достаточное правило оптимальности	Сетевой график
Задача о назначениях	Симплекс-таблица
Задача коммивояжера	Симплекс-метод
Задача о максимальном потоке	Соотношения двойственности
Задача распределения ресурсов	Стоимость единицы ресурсов
Метод ветвей и границ	Теорема о дополнительной нежесткости
Метод Гаусса-Жордана	Крайняя точка
Метод минимального элемента	Условие допустимости
Метод отсекающих плоскостей	Условие оптимальности
Метод северо-западного угла	Условие неотрицательности переменных
Метод потенциалов	Транспортная задача
Метод критического пути	Теорема Форда-Фалкерсона
Метод Фогеля	Целевая функция
Модель линейного программирования	Целочисленное программирование
Начальное решение	Цикл в транспортной таблице
Недопустимое решение	Экстремум

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1 Белобородова, Т. В. Математическое моделирование в среде Excel: учебное пособие / Т. В. Белобородова.- Красноярский филиал ИрГУПС, Красноярск, 2006. - 337 с.

2 Вагнер, Г. Основы исследования операций. Т.1 / Г.Вагнер; пер. с анг. - М.: Мир, 1972. - 335 с.

3 Кремер, Н.Ш. Исследование операций в экономике: учебное пособие для вузов / Н.Ш Кремер, И.М.Тришин, М.Н.Фридман; под ред. НШ.Кремера. - М.: ЮНИТИ, 2001. - 407 с.

4 Михайлов, А.С. Решение задач линейного программирования: методические указания / А.С. Михайлов. – Красноярск, 2007. - 16 с.

5 Михайлов, А.С. Методы оптимизации: лабораторный практикум по одномерным и многомерным методам минимизации для студентов специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем очной, очной сокращенной и заочной форм обучения/ А.С.Михайлов. - Красноярск: СибГТУ, 2007.-36с.

6  Михайлов А.С. Линейное программирование: учебное пособие для студентов всех форм обучения направления 230100 Информатика и вычислительная техника, специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем, а также направления 230400 информационные системы и технологии, специальности 230401 Информационные системы и технологии в промышленности/ А.С.Михайлов. – Красноярск: СибГТУ, 2011. – 58с.

7 Рубан, А.И. Методы оптимизации: учебное пособие. - Изд. 2-е, исправленное и дополненное / А.И. Рубан. - Красноярск: НИИ ИПУ, 2001.- 528 с.

8 Таха, Х. А. Введение в исследование операций.- Изд. 6-е / Х.Таха,  А.Хэмбди; пер. с анг. – М: Издательский дом «Вильямс», 2001- 912 с.: ил.

9 Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху. – М.: Изд-во «Мир», 1983. – 592 c.

Заключение

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

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

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

Кроме того, рассматриваются методы целочисленного программирования: метод ветвей и границ и метод отсечения, а также метод потенциалов для решения транспортных задач и венгерский метод для решения задачи о назначениях.

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

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

Материал, изложенный в курсе лекций, изучается на 3 курсе в V семестре дисциплины «Методы оптимизации» в объеме 18 часов лекционных и 36 часов лабораторных занятий, приведенных в методических указаниях «Решение задач линейного и сетевого программирования» [4] и лабораторном практикуме «Методы оптимизации» [5].

 

 

Александр Сергеевич Михайлов

 

МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Курс лекций

 

 

Отв. Редактор                 доц. Г.В.Ващенко

Редактор РИЦ                Л.М.Буторина

 

 

Подписано в печать 10.10.2011

Формат 60×84 1/16.  Изд. №2/9(2011).

Тираж 100экз. Уч.-изд.л.3,75.

Заказ №

 

 

Редакционно-издательский центр СибГТУ

660049, г.Красноярск, пр. Мира, 82

Телефон (391) 227-69-90

Факс (391) 211-97-25