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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Рис. 9.3. Пример потока, который можно увеличить
Рис. 9.4. Пример увеличивающей цепи
Ясно, что E >0. Для нашего примера E
1
= min(4 − 2; 3 − 2; 5 − 1)=1;
E
2
= min(3, 2)=2; E = min(1, 2)=1.
Увеличим поток на всех прямых дугах на число E и уменьшим поток
на всех обратных дугах на E (рис. 9.3). Из определения числа E следует,
что такая операция не нарушит условий (9.4), (9.5), а величина потока
увеличится при этом на E. Каждая цепь s в t, по которой могут быть
посланы дополнительные единицы потока, называется увеличивающей
цепью. Если в транспортной сети можно найти увеличивающую цепь,
поток в сети не является максимальным.
Докажем теорему Форда-Фалкерсона.
Пусть в сети задан максимальный поток, величина которого равна v*.
Определим разрез
∗
),( RR
, указав вершины множества R.
Положим s∈R.
Если V
i
∈R и x(V
i
, V
j
) < r(V
i
, V
j
), то V
j
∈R,
Если V
i
∈R и x(V
j
, V
i
) > 0, то V
j
∈R. (9.9)
s
t
V
1
V
3
V
2
V
4
5(5)
5(1)+1
v
1
=5, v
2
=6
2(2)
−
1
4(3)
−
1
3(2)+1
4(2)+1
3(3)
1(1)
S
t
4(2)+1 V
1
3(2)+1 V
2
4(3) – 1 V
3
2(2) – 1 V
4
5(1)+1

Страницы