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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Вершины множества R определяются одна за другой, начиная с
источника s. Некоторая вершина V
j
включается во множество R, если
существует увеличивающая цепь от s к V
j
. Так как поток v
*
−
максимальный, не существует увеличивающей цепи из s к t, поэтому
вершина t окажется во множестве R , мы действительно определили
разрез. Из правила (9.9) построения множества R следует, что если V
i
∈R,
,RV
j
∈
то x(V
i
, V
j
) = r(V
i
, V
j
), x(V
j
, V
i
) = 0. Чтобы доказать равенство
r
∗
),( RR
= v*, нам потребуется математическая модель двойственной
задачи.
Перепишем математическую модель задачи о максимальном потоке
по-другому, упростив обозначения. Пусть всего в транспортной сети n
вершин, включая источник и сток. Припишем источнику номер 1, стоку −
номер n, остальные вершины в произвольном порядке получают номера от
2 до 1−n . Дуги будем обозначать номерами вершин, которые они
соединяют. Поток на дуге ),(
j
i обозначим
ij
x ,
j
in
j
ni ≠=−= ;,,2;1,,1 LL . Пропускные способности дуг обозначим
ij
r , причем если дуга ),(
j
i отсутствует в транспортной сети, положим, что
ij
r = 0,
j
in
j
ni
≠
=
−
= ;,,2;1,,1 LL . Имеем
∑
=
→
n
j
j
x
2
1
max
; (9.10)
0
2
1
1
=−
∑∑
=
−
=
n
j
ij
n
j
ji
xx
; i
j
ni
≠
−
= ;1,,2 L ;
)(
i
p
(9.11)
ijij
rx ≤ ;
j
in
j
ni
≠
=−= ;,,2;1,,1 LL ; )(
ij
w (9.12)
0≥
ij
x ;
j
in
j
ni
≠
=−= ;,,2;1,,1 LL ; (9.13)
Обозначим через
i
p
, 1,,2
−
= ni L переменные двойственной задачи,
соответствующие ограничениям (9.11). Переменные, соответствующие
ограничениям (9.12) обозначим
ij
w ,
j
in
j
ni ≠
=
−
=
;,,2;1,,1 LL .
Математическая модель двойственной задачи такова
∑∑
−
==
≠→
1
12
)(min
n
i
n
j
ijij
jiwr
; (9.14)
0≥++−
ijji
wpp ;
j
in
j
ni
≠
−
=
−
= ;1,,2;1,,2 LL ; ( jix
ij
≠, ) (9.15)
1
1
≥+
ii
wp
; 1,,2 −
=
ni L ; (
i
x
1
) (9.16)
0≥+−
ini
wp
; 1,,2
−
= ni L ; (
in
x
) (9.17)

Страницы