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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

104
На итерации 6=
r
после пересчёта получена матрица
6
c
, записанная в
табл. 44 (
6
ij
c – над линиями). На итерации 6
=
r
получено два оптимальных
маршрута, пропускная способность каждого из которых равна 4 ед. Однако
совместно их использовать нельзя, т.к. они оба содержат общую
критическую дугу 4
1,5
=с .
При вычислении остаточной матрицы
7
с использован второй
маршрут (рис. 7), при этом изменившиеся элементы в табл. 43 выделены
жирным шрифтом и записаны в нижней части клеток. На итерации 7
=
r
построен последний маршрут, завершающий полное использование
пропускных способностей пункта-источника
5
A ( 0
7
,5
=
j
c для
j
∀ и
табл. 40):
.80171322820
1
,55
=++++==
∑
=
n
j
j
н
с
π
(6.12)
Всё множество маршрутов, обеспечивающих максимальную
пропускную способность сети от пункта
5
A к пункту
3
A , представлено в
табл. 45:
Таблица 45
r
r,0
3,5
μ
r,0
3,5
π
1
3,4,2,5
23
2
36,,5
17
3
3,1,5
16
4
3,2,6,4,5
13
5
3,2,5
5
6
36,,1,5
4
7
3;5
2
Из табл. 45 следует, что суммарная пропускная способность
маршрутов (6.8) соответствует возможностям пункта-источника
5
A (6.12);
можно установить маршруты, которые целесообразно задействовать,
чтобы использовать их с полной нагрузкой для пропуска заданного потока
с плотностью
k
λ
. Например, поток с плотностью 30
3,5
=
λ
ед. можно
направить по маршрутам с номерами }4;2{}{
=
r
или }7,5,1{.

Страницы