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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

источника и стока, равен суммарному потоку, вытекающему из этой
вершины.
Условие (9.2) означает; что поток на каждой дуге ограничен ее
пропускной способностью.
Пример транспортной сети с заданными потоками на дугах
показан на рис. 9.1. Числа над дугами означают пропускные
способности, числа в скобках − потоки.
Рис. 9.1. Пример транспортной сети
Дуга (V
i
, V
j
) называется насыщенной, если x(V
i
, V
j
) = r(V
i
, V
j
), и
ненасыщенной в противном случае. На рис. 9.1 насыщенными
являются дуги (V
4
, V
5
), (V
1
, V
2
), (V
5
, V
2
), (V
5
, V
6
). Остальные дуги −
ненасыщенные.
Из условия сохранения потока (9.1) следует, что суммарный поток,
вытекающий из источника, равен суммарному потоку, втекающему в
сток.
∑
∑
←∈
→∈
=
=
ti
Sj
EV
i
EV
j
vtVxVsx .),(),(
(9.3)
Для доказательства формулы (9.3) достаточно просуммировать
потоки на дугах транспортной сети двумя способами. Первый раз
суммировать потоки на дугах, считая, что каждая дуга выходит из
некоторой вершины. Второй раз нужно вычислить ту же сумму,
полагая, что каждая дуга выходит из некоторой вершины. Затем
применить (9.1).
Число v называется величиной потока, или просто потоком в
транспортной сети. На рис. 9.1 показана транспортная сеть с
потоком величины v = 5 + 3 = 6 + 2 =8.
1
(
1
)
7(4)
4
(
0
)
8
(
3
)
3(1)
12(6)
14(2)
15(3)
t
s
6(6)
V
4
10(5)
V
5
V
6
V
1
V
2
V
3
2(2)
1(1)
3(2)

Страницы