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

Размещено на http://www.allbest.ru/

Лекция

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

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

Предполагается, что сеть является симметрическим графом, т.е. если дуга (i,j) входит в сеть, то в неё входит и симметрическая дуга (j,i), хотя реально такой дуги может и не быть. Каждой дуге поставлено в соответствие число d_ij , называемое пропускной способностью дуги. Величина d_ij определяет максимальное количество продукции, которое может быть переведено по дуге (i,j) в единицу времени. Узел с номером Ш имеет неограниченный запас продукции и называется источником, а узел с номером n имеет неограниченную потребность в эой продукции и называется стоком. В остальных узлах, которые называются промежуточными, запас продукции или потребность в ней равны нулю.

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

Данная постановка справедлива для смешанных и неориентированных графов, т.е. множество D может содержать дуги и рёбра, только дуги или только рёбра.

Для математической постановки задачи введём переменные x_ij - количество продукции, перевозимое по дуге (i,j). Эта велчина называется потоком по дуге (i,j). Тогда математическая модель задачи будет иметь вид:

(1)

(2)

(3)

Целевая функция (1) отражает величину потока по сети, которая должна быть максимизирована. Очевидно, поток на сети равен количеству продукции, вывозимой из источника или ввозимой в сток. Равенство (2) для промежуточных узлов записано из условия баланса: количество продукции, привозимого в узел, должно равняться количеству продукции, вывозимого из узла. Ограничения (3) очевидны. Модель (1)-(3) относиться к классу ЗЛП. Однако существует более эффективеый алгоритм решения этой модели. Это алгоритм Форда.

Важную роль в обосновании алгоритма Форда решения задачи о максимальном потоке играет понятие разреза сети.

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

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

d (R,)=

Очевидно, что любой путь из источника в сток содержит хотя бы одну дугу разреза (R,). Поэтому если удалить все дуги какого-либо разреза, то все пути из источника в сток будут блокированы. Поскольку пропускная способность пути равна наименьшей из пропускных способностей дуг, входящих в этот путь, то величина потока V перемещаемого по всем возможным путям, соединяющим исток со стоком, не может превышать пропускной способности любого разреза сети, т.е. V? d(R,). Следовательно, если удастся постоить такой поток, что его величина V ^* окажется равной пропускной способности некоторого разреза (R^*,^*) , т.е. V ^*= d(R^*,^*), этот поток и будет максимальным, а (R^*,^*) - разрезом с минимальной пропускной способностью.

Теорема Форда - Фалкерсона.

Алгоритм решения задачи о максимальном потоке основан на теореме Форда - Фалкерсона о максимальном потоке и минимальном разрезе. Для рассмотрения этой теоремы вводятся понятияо прямой и обратной дуги цепи. Под цепью в данном случае понимается последовательность сцепленных дуг сети без учёта их ориетации. Дугу, принажлежащую некоторй цепи, называют прямой, если её направление совпадает с направлением обхода узлов этой цели, и обратной - в противном случае например, цепь µ=(3,5,4,7,6,8) на рис.1, связывающая узел 3 с вершиной 8, содержит три прямые дуги (3,5), (4,7), (6,8) и две обратные (4,5), (6,7).

форд фалкерсон сеть

Теорема. В любой сети максимальная величина потока из источника в сток равна пропускной способности минимального разреза сети.

Доказательство. Пусть имеем максимальный поток в сети. Если x_ij=d_ij, то говорят, что дуга (i,j) насыщена потоком. Предполагается, что V^* величина максимального потока в сети. Необходимо доказать, что найдется такой разрез (R^*,^*) на этой сети, пропускная способность которого равна V^* , т.е. V ^*= d(R^*,^*).

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

Узлы , составляющие подмножество R, определяются последовательно, начиная с источника Ш , по следующему правилу: Ш = R; если и x_ij < d_ij то ; если и x_ji >0, то . (4)

Применение правила (4) приводит к построению разреза. Очевидно, разрез будет построен в том случае , если сток .

Пусть сток . Тогда из правила (4) следует , что существует цепь из истока Ш в сток n с пропускной способностью больше нуля µ=(i₁,i₂,…,i_n), где i₁= Ш, i_n=n. Это следует из того , что все прямые дуги , входящие в цепь, ненасыщенные (xi_si_s+1< di_si_s+1 ), а для всех обратных дуг ( i_s+1,i_s ) величина потока xi_s+1i_s>0.

Пусть д₁ наименьшая разность между пропускной способностью и величиной потока, взята по всем прямым дугам цепи µ , а д₂ - наименьшая величина потока, взятая по всем обратным дугам этой цепи. Далее определяется величина д= min(д₁, д₂) > 0 и увеличивается поток по всем прямым дугам цепи на д ,а на ту же величину уменьшается поток по всем обратным дугам цепи. Таким образом, величина нового потока равна V+ д , что противоречит предположению о максимальности V . Следовательно предположение неверно, и , а множество дуг (R,) есть разрез, отделяющий исток от стока.

Пропускная способность построенного разреза равна максимальному потоку на сети. Действительно, из правила (4) нахождения подмножества R следует , что если , , то x_ij = d_ij ; в противном случае узел j входил бы в R.

Таким образом,

Теорема доказана.

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

Исходные данные заносятся в таблицу размерности (n+1) Ч (n+1) . Если дуга , то в соответствующей клетке таблицы записывается значение d_ij.

Если обратная дуга , то в соответствующей клетке записывается значение d_ji, если дуга , то в клетке (j,i) записывается Ш.

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

Каждый шаг алгоритма Форда состоит из трёх действий.

1.Находится путь по таблице из узла- истока Ш в узел-сток n с пропускной способностью больше 0. Для этого столбец, соответствующий узлу-истоку, отмечается знаком *. Далее отыскиваются в строке с номером 0 элементы d_ij > 0 и столбцы, в которых они находятся, отмечаются сверху номером просматриваемой строки (цифрой 0). В результате окажутся выделенными все дуги (0, j) c положительными пропускными способностями. Эти дуги могут служить первыми дугами пути из истока в сток.

Далее просматриваются те строки, номера которых совпадают с номерами отмеченных столбцов. В каждой такой строке i отыскиваются элементы d_ij > 0, находящиеся в непомеченных столбцах, и эти столбцы отмечаются номером просматриваемой строки. Таким образом, окажутся выделенными дуги, которые могут служить вторыми дугами путей из истока в сток.

Аналогичный просмотр строк продолжается до тех пор, пока: а) либо не будет помечен столбец с номером n (сток) что означает выделение пути с пропускной способностью больше нуля из истока в сток; б) либо нельзя помечать новые столбцы (в просматриваемых строках не окажется положительных элементов ) , при этом столбец с номером n также останется не отмеченным.

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

В случае ”а” искомый путь µ из источника в сток находится используя пометки столбцов. Пусть последний столбец n помечен номером k , тогда дуга (k,n) последнее звено искомого пути. Далее просматривается столбец с номером k, пусть отметка этого столбца l. Тогда дуга (l,k) предпоследнее звено искомого пути и т.д.Этот процесс продолжается до тех пор, пока не найдётся отметка *, т.е. отметка истока Ш. Пусть эта отметка будет цифра m. Таким образом путь от истока к стоку будет состоять из дуг µ=(( Ш,m),…, (l,k), (k,n)). (5)

2.Клетки , соответствующие дугам этого пути, отмечаются знаком (-), а симметричные им клетки, т.е. соответствующие обратным дугам - знаком (+). По найденному пути (5) можно пропустить максимально возможный поток, величина которого равна И =min { d_ij^- }.Эта величина И отнимается от всех пропускных способностей клеток, отмеченных знаком (-) и прибавляется к пропускным способностям клеток, отмеченных знаком (+). В результате получается новая таблица, в которой записаны неиспользованные пропускные способности дуг после пропускания максимального потока по пути (5).

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

Это процесс продолжается до тех пор, пока не будет иметь место случай б).

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

Для определения максимального потока на сети V^* в последней таблице выделяются отмеченные столбцы, номера которых образуют множество R^*, причём исток ^*. В результате получается минимальный разрез (R^*,^*) и по теореме Форда- Фалкерсона

Для нахождения значений потоков по дугам x_ij^*, образующих поток V^* из элементов первой таблицы вычитаются соответствующие элементы последней таблицы.

Если в клетке получается неотрицательная величина , то она оставляется; если - отрицательная, то в клетке записывается . Значения заполненных клеток будут соответствовать потокам по дугам x_ij^*. Причём

Пример. На данной сети определить максимальный поток из узла в узел 4.

1. * 0 0 1 2

И₁= min (19,9)=9.

2. * 0 0 1 3

И₂= min (17,12,24)=12.

3. * 0 0 2 3

И₃= min (10,8,12)=8.

4. * 0 0 1 2

Пути из 0 в 4 нет! Определяются множества: R*={0,1,2}, ={3,4}.

(R^*,^*)=((1,3),(2,3),(2,4))

d(R^*,^*)=V^*=12+8+9=29

5. В заключительной таблице положительные элементы определяют потоки по дугам x_ij^*.

Размещено на Allbest.ru