Введение в линейное программирование. Палий И.А. - 68 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

Составители: 

Рубрика: 

4. Вершина
i
− не помечена, вершина
−
j
не помечена. Тогда
0,0,0 ===
ijji
wpp ; 0
=
+
+
−
ijji
wpp .
Пусть
0
1
>
i
x
. Источник помечен, возможны два случая
1. Вершина
i
− помечена, тогда
0,1
1
=
=
ii
wp
;
1
1
=+
ii
wp
.
2. Вершина
i
− не помечена, тогда
1,0
1
=
=
ii
wp
;
1
1
=+
ii
wp
.
Пусть
0>
in
x
. Сток не помечен, возможны два случая
1. Вершина
i
− помечена, тогда
1,1
1
=
=
ii
wp
;
0
1
=+
−
ii
wp
.
2. Вершина
i
− не помечена, тогда
0,0
1
=
=
ii
wp
;
0
1
=+−
ii
wp
.
Итак,
∑
=
n
j
j
x
2
1
=
∑∑
−
==
1
12
n
i
n
j
ijij
wr
;
**
),( RRv =
. Теорема доказана.
9.5. Алгоритм Форда-Фалкерсона решения задачи о
максимальном потоке (метод расстановки пометок)
Алгоритм Форда–Фалкерсона решения задачи о максимальном потоке
следует непосредственно из доказательства теоремы Форда–Фалкерсона. В
нем осуществляется систематический поиск увеличивающих цепей из
источника в сток по правилу (9.9). Как только не удается найти
увеличивающую цепь, алгоритм прекращает работу: в сети построен
максимальный поток.
Формальное описание алгоритма.
Шаг 1. Пометить вершину s
меткой (0, ∞).
Шаг 2. Выбрать любую помеченную вершину V
i
(первоначально это
единственная вершина s). Рассмотреть все непомеченные вершины V
j
,
связанные дугами с вершиной V
i
. Тем вершинам V
j
, для которых x(V
i
, V
j
) <
< r(V
i
, V
j
) приписать метку (
+
i
V
, E
Vj
), где E
Vj
= min[E
Vi
, r(V
i
, V
j
) − x(V
i
, V
j
)].
Тем вершинам V
j
, для которых x(V
j
, V
i
) > 0, приписать метку (
−
i
V
, E
Vj
), где
E
Vj
= min[E
Vi
, x(V
j
, V
i
)].
Шаг 3. Повторять шаг 2 до тех пор, пока:
а) или окажется помеченной вершина t;
б) или все возможные метки проставлены, а вершина t осталась
непомеченной.
В случае а) перейти к шагу 4, а в случае б) – к шагу 6.

Страницы