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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Из неравенства (9.5) следует, что если мы построим поток такой
величины v* и разрез такой пропускной способности
∗
),( RRr
,
что v*=
∗
= ),( RRr
, этот поток будет максимальным, а разрез
∗
),( RRr
−
минимальным.
Если пропускные способности дуг − целые числа, то задача о
максимальном потоке, очевидно, имеет решение. Величина максимального
потока не превышает
.)),(,),((min
←∈
→∈
∑
∑
tj
Si
EV
j
EV
i
tVrVsr
Но тогда и задача отыскания минимального разреза имеет решение,
а по первой теореме двойственности оптимальные значения целых
функций совпадают. Конструктивное доказательство этой теоремы дается
так называемой теоремой Форда-Фалкерсона о максимальном потоке и
минимальном разрезе.
9.3. Теорема Форда-Фалкерсона о максимальном потоке и
минимальном разрезе.
Теорема. Для любой сети величина v
*
максимального потока из s в t
равна пропускной способности
∗
),( RRr
минимального разреза
∗
),( RR
,
отделяющего s от t.
Для доказательства теоремы нам потребуется понятие увеличивающей
цепи, по которой можно увеличить поток из источника в сток.
Пусть удалось найти цепь, соединяющую вершины s и t, дуги которой
удовлетворяют следующим
>
условиям:
1) все дуги цепи, которые проходятся В направлении их ориентации
(прямые дуги), не насыщены;
2) на всех дугах цепи, которые проходятся в направлении, обратном
их ориентации (обратных дугах), поток больше нуля. На рис. 9.4
приведен пример такой цепи.
В рассматриваемой цепи можно переслать дополнительный поток из
источника в сток. Действительно, положим
Е
1
= min(r(V
i
, V
j
)
−
x(V
i
, V
j
)), (9.6)
где минимум берется по всем прямым дугам цепи;
Е
2
= min(x(V
i
, V
j
)), (9.7)
где минимум берется по всем обратным дугам цепи;
Е = min(Е
1
, Е
2
). (9.8)

Страницы