Задача о максимальном потоке и минимальной стоимости. Метод Форда - Фалкерсона

 

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

Теорема 1.

Если имеется оптимальное решение для задачи с матрицей c_ij, то это решение будет оптимальным и для задачи с преобразованной матрицей c_ij^’=c_ij+d,t(i,j).

Теорема 2.

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

1) c_ij>0, x_ij=0;

2) c_ij<0, x_ij=d_ij;

3) c_ij=0, 0£x_ij£d_i.j.

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

1⁰. Добавим начальные и конечные узлы S и t, причем полагаем и .

2⁰. Начальный поток x_ij считаем равным 0 по всем дугам.

3⁰. Пометим вершину S =[-, ].

4⁰. Проведем процесс расстановки пометок для смежных с S вершин, пытаясь достичь вершины t.

Правила расстановки таковы:

Узел j может быть помечен из узла i, если:

а) c_ij^’£0, x_ij<d_ij

б) c_ij^’³0, x_ij>0

Если узел i имеет пометку i=[k^±,e_i], то узел j получает пометку:

j=[i⁺, e_j=min(e_i, d_ij-x_ij)] в случае (а),

j=[i^-, e_j=min(e_i, x_ij)] в случае (б).

Знаки ± ставят в зависимости от того, по прямой или обратной дуге происходит пометка, т.е. в случае (а) ставится «+», в случае (б) – «-». Шаг 4⁰ продолжается до тех пор, пока не пометим конечную вершину.

Если происходит прорыв, то переходим к шагу 5⁰, если непрорыв – к шагу 6⁰.

5⁰. Если произошел прорыв, т.е. если узел t получил пометку, т.е. из s в t найден путь, то изменяем потоки следующим образом:

x_ij+e_t, (i,j)Î прямой дуге;

x_ij^’ = x_ij-e_t, (i,j)Î обратной дуге;

x_ij, в остальных случаях.

Также изменяем значение a_s^’=a_s-e_t. Переходим к шагу 3⁰.

6⁰. Если происходит непрорыв, то производим изменение стоимости дуг, для этого выделяем множества:

A₁={(i,j)/iÎ , jÎ , c_ij³0}

A₂={(j,i)/iÎ , jÎ , c_ij<0}

Где – множество помеченных вершин, – множество непомеченных.

Тогда d₁=min_A1c_ij, d₂=min_A2|c_ij|, d=min(d₁, d₂).

c_ij-d, iÎ , jÎ ;

c_ij^’ = c_ij+d, iÎ , jÎ ;

c_ij, в остальных случаях.

Таким образом вводят в рассмотрение по крайней мере еще одну допустимую дугу из A1 или A2. Переход к шагу 3⁰.

7⁰. Вычисления заканчиваются, когда либо a_s=0, либо A₁ и A₂ равны 0, т.е. получен минимальный разрез.

 

Пример 2

 

Рис.2

1) Вводим вершины s и t.

a_s=åa_j=30+50+70=150

2) Полагаем xij=0 "(i,j).

3) Помечаем вершину s=[-, e_s=a_s=150]

Из S можно пометить 1, 2, 3, т.к. c_sj=0:

1=[S⁺,e₁=min(es, d_s1-x_s1)=min(150,30-0)=30]

2=[S⁺,e₂=min(es, d_s2-x_s2)=min(150,50-0)=50]

3=[S⁺,e₃=min(es, d_s3-x_s3)=min(150,70-0)=70]

Другие вершины не можем пометить, т.к. не выполняются условия cij³0, xij>0 (последний равен 0)

6) Произошел непрорыв, поэтому вводим два множества:

A₁={"cij>0: (1,5), (1,4), (2,4), (2,7), (3,5), (3,7)}

A₂=0, т.к. нет (i,j) с c_ij<0.

Стоимости дуг, входящих в A₁, A₂:

d₁=min(7,4,5,8,6,7)=4, d₂=¥, d=min(d₁, d₂)=4.

Изменяем стоимости дуг по множеству A₁ (на рисунке). Теперь можно пометить вершину 4.

4=[1⁺,e₄=min(e₁, d₁₄-x₁₄)=min(80,15-0)=15]

6) Произошел непрорыв, т.к. из вершины 4 нельзя пометить вершину t:

A₁={(1,5), (4,5), (4,6), (2,7), (3,5), (3,7)}. Здесь дуга (2,4) не рассматривается (Ответьте, почему?).

A₂=0.

d₁=min(3,3,5,4,2,3)=2, d=4.

Во всех дугах множества A1 стоимости меняются на c_ij-2 (на рисунке).

Можно пометить следующие вершины:

5=[3⁺,e₅=min(e₃, d₃₅-x₃₅)=min(70,30-0)=30]

t=[5⁺,e_t=min(e₅, d_5t-x_5t)=min(30,40-0)=30]

4) Произошел прорыв, т.е. найден следующий путь S®3®5®t, по которому провозится 30 единиц товара. Потоки по этим дугам меняем на 30 ед., дуга (3,5) насыщена, в дальнейшем она не рассматривается.

5) a_s=150-30=120. Заново помечаем вершины, начиная с вершины s

……...

При применении вычислительного алгоритма метода Форда – Фалкерсона будет проведено 11 итераций. (Проверить самостоятельно).