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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

0≥
ij
w . (9.18)
Положим
1,,2,
,0
,1
−=
⎩
⎨
⎧
∈
∈
= ni
Ri
Ri
p
i
L
.
Иначе говоря,
1=
i
p
, если вершина
i
− помечена,
0
=
i
p
, если вершина
i − не помечена. Поэтому 0)(;1)1(
=
=
n
p
p
, так как источник помечен, а
сток − не помечен.
Положим
⎪
⎩
⎪
⎨
⎧
∉
∈
=
*
*
),(),(,0
),(),(,1
RRji
RRji
w
ij
,
j
in
j
ni
≠
=
−
=
;,,2;1,,1 LL .
Покажем, что построено допустимое решение задачи (9.14 − 9.18).
Пусть 0,1 ==
ji
pp . Тогда вершина
i
− помечена, вершина
−
j
непомечена. Значит, дуга ),(
j
i принадлежит разрезу
*
),( RR
, поэтому
1=
ij
w , 0=
+
+−
jiji
wpp .
Пусть
0=
i
p
. Значит, вершина
i
− не помечена, тогда дуга ),1( i
принадлежит разрезу
*
),( RR
, следовательно,
1
1
=
i
w
,
1
1
=
+
ii
wp
.
Пусть
0
1
=
i
w
, тогда вершина
i
− помечена, что влечет
1
=
i
p
,
1
1
=+
ii
wp
.
Пусть
1=
i
p
, тогда вершина i − помечена, но сток не помечен, поэтому
1=
in
w
,
0
=
+−
ini
wp
.
Осталось показать, что выполнены условия дополняющей
нежесткости.
Пусть njix
ij
≠≠> ,1,0. Разберем 4 случая.
1. Вершина
i
− помечена, вершина
−
j
помечена. Тогда
0,1,1 ===
ijji
wpp ; 0
=
+
+
−
ijji
wpp .
2. Вершина
i
− не помечена, вершина
−
j
помечена. Случай
невозможен, вершина
i
по обратной дуге метится от вершины
j
,
ведь 0>
ij
x .
3. Вершина
i
− помечена, вершина
−
j
не помечена. Тогда
1,0,1 ===
ijji
wpp ; 0
=
+
+
−
ijji
wpp .

Страницы