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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Какой бы путь из s в t мы не рассматривали, хотя бы одна его дуга
входит в данный разрез ),( RR . Это следует из того, что s и t принадлежат
разным множествам. Следовательно, если удалить все дуги разреза
),( RR
, то в сети не останется ни одного пути из s в t. Поэтому и
говорят, что разрез отделяет источник от стока.
Пропускной способностью разреза называется сумма пропускных
способностей дуг, составляющих разрез
r
),( RR
=
∑
)(
ji
VVr ,
(V
i
, V
j
)∈ ),( RR . (9.4)
Разрез сети, имеющий наименьшую пропускную способность,
называется минимальным.
Для примера рассмотрим транспортную сеть, показанную на рис. 9.2.
Числа над дугами означают их пропускные способности.
Для данной сети можно построить 8 разрезов. Назовем некоторые из
них. Пусть R
1
={s, V
1
}, тогда
1
R
={V
2
, V
3
, t},
),(
11
RR
={(s, V
2
), (s, V
3
), (V
1
, V
2
), (V
1
, t)}.
r ),(
11
RR =4+2+2+6=14.
Пусть R
2
={s, V
2
, V
3
}, тогда
},,{
2
tVR
=
),(
22
RR
={(s, V
1
), (V
2
, V
1
), (V
3
, t)};
r ),(
22
RR =3+5+3=11.
Пусть R
3
={s}, тогда
};,,,{
3213
tVVVR =
r
.9),(
33
=RR
=),(
33
RR
{(s,V
1
), (s,V
2
), (s,V
3
)}.
Легко убедиться, что минимальным для этой сети является разрез
),(
33
RR
с пропускной способностью равной 9.
Задача отыскания минимального разреза для данной транспортной
сети и есть задача, двойственная задаче о максимальном потоке. Из
основного неравенства теории двойственности следует, что величина
произвольного потока v и величина пропускной способности
произвольного разреза ),( RR в той же транспортной сети связаны
соотношением
).,( RRrv
≤
(9.5)
Этот неравенство также непосредственно следует из того факта, что
в любой путь, из источника в сток входит, по крайней мере, одна дуга
разреза.

Страницы