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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

105
Требуемая пропускная способность любой дуги, используемой в
различных маршрутах от
k
A до
l
A , должна соответствовать её начальным
возможностям. К примеру, дуга (6;3) используется в маршрутах }6;2{}{ =
r
,
что требует от неё пропускной способности 21417
3,6
=
+
≥c ед. (табл. 45).
Её начальная пропускная способность удовлетворяет (табл. 40) этому
требованию (26
3,6
=
c ), при этом 5 ед. неиспользованной пропускной
способности соответствуют полученному результату (
5
8
3,6
=c , табл. 44).
Из табл. 44
8
c
следует, что сумма неиспользованных пропускных
способностей пункта-приёмника
3
A
равна:
∑
=
=++=
n
i
i
c
1
8
3,
.16574
Сложив сумму неиспользованных пропускных способностей пункта-
приемника
3
A с найденной пропускной способностью сети от
5
A до
3
A (80
ед.), получим начальную пропускную способность пункта-приёмника
(табл. 40):
96262302216
1
,
=++++==
∑
=
n
i
il
п
lk
с
π
. (6.13)
Используя (6.12) и (6.13), можно, не производя расчётов, получить
оценку сверху для пропускной способности сети от источника
k
A к
приёмнику
l
A :
}.;min{
,,
,0
,
п
lk
н
lk
lk
πππ
≤
Σ
Для рассмотренного примера оценка соответствует оптимальному
решению.
Блок-схема алгоритма получения совокупности маршрутов,
обеспечивающих максимальную пропускную способность сети,
представлена на рис. 7, динамика его работы – в табл. 42 – 44. На восьмой
итерации после вычисления элемента
0
8
3,5
=с
(пункт
0
5) выполняется
достаточное условие останова (пункт
0
6), и процесс прекращается.
Необходимое и достаточное условие останова состоит в невозможности
построения маршрута
lk,
μ
при остаточной матрице
1
+
r
с и любой оценке,
меньшей или равной
1
,
+r
lk
π
.

Страницы