Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 97 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

99
6.2. Определение максимальной пропускной способности сети
Идея определения суммарной максимальной пропускной способности
сети
Σ,0
,lk
π
состоит в следующем.
После построения первого оптимального маршрута
1,0
,lk
μ
из
пропускных способностей
ji
c
,
дуг, вошедших в этот маршрут, вычитается
пропускная способность
0
,lk
π
. Полученная таким путём остаточная
матрица
2
c является исходной информацией для определения очередного
оптимального маршрута. При этом естественно, что пропускная
способность нового маршрута будет
не больше, чем у предыдущего
(
r
lk
r
lk
,0
,
1,0
,
ππ
≤
+
). Процесс оканчивается при получении остаточной матрицы
r
c
, уже не позволяющей построить маршрут от пункта
k
A к пункту
l
A .
Далее будем использовать обозначение номера
большой итерации
r
.
Например,
r
c – матрица пропускных способностей, используемая на
r
-й
большой итерации (при
1=
r
cc
=
1
– начальная матрица, при
1>
r
–
остаточные);
r
lk
,0
,
μ
,
r
lk
,0
,
π
– оптимальный маршрут и его пропускная
способность, полученные на
r
-й большой итерации;
t
– номер малой
итерации (шага)
;
rt
lk
,
,
π
– значение оценки для
r
lk
,0
,
π
на
t
-м шаге
r
-й
большой итерации и т.д.
Большая итерация от малой отличается тем, что дополнительно к
алгоритму (рис. 6) вначале
вычисляются элементы остаточной матрицы
1+r
с на основании полученного маршрута
r
lk
,0
,
μ
и матрицы
r
с по формуле
0,
, ( , ) ,
,,
1
,
0, 0,
, ( , ) .
,, ,
r
r
ñij
ij kl
r
ñ
ij
rr
r
ñij
ij kl kl
μ
πμ
⎧
∉
⎪
+
=
⎨
⎪
−∈
⎩
(6.7)
Порядок решения проиллюстрируем на примере сети, представленной
в табл. 40, при определении её максимальной пропускной способности
Σ,0
,lk
π
от пункта
k
A к
l
A как суммы пропускных способностей всех
R
возможных оптимальных маршрутов
r
lk
,0
,
μ
(
Rr ;1=
):
.
1
,0
,
,0
,
∑
=
Σ
=
R
r
r
lklk
ππ
(6.8)

Страницы