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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

98
Таблица 41. Совмещенная матрица
0
0
kl
kl
π
μ
6 5 4 3 2 1
=
j
22
2,5,1
22
3,2,5,1
22
4,2,5,1
22
5;1
22
6,3,2,5,1
6,4,2,5,1
23
1,3,4,2
1,3,6,4,2
23
3;4;2
23
4,2
27
5;2
23
6,4,2
6,3,4,2
23
1;3
24
2,5,3
23
4,2,5,3
24
5;3
29
6;3
23
1,3,4
24
2,5,3,4
30
3;4
24
5,3,4
29
6,3,4
23
1,3,4,2,5
1,3,6,4,2,5
28
2;5
23
3,4,2,5
3,6,4,2,5
23
4,2,5
23
6,4,2,5
23
1,3,6
24
2,5,3,6
26
3;6
23
4,5,3,6
24
5,3,6
Блок-схема алгоритма построения оптимального маршрута
представлена на рис. 6. Получение начальной и улучшенной оценок
(
00
5 ;2 ) соответственно проиллюстрировано числовым примером
[см. (6.2), (6.5)]. Любой из двух полученных маршрутов (6.6) способен
пропустить поток с плотностью
λ
, не превышающей пропускную
способность маршрута
0
,lk
π
(
lk,
π
λ
≤
). Для выбора одного из множества
оптимальных маршрутов лицо, принимающее решение, (ЛПР) может
использовать какую-то дополнительную информацию, например, длину
маршрута и т.п.
Если реальный поток с плотностью
λ
превышает пропускную
способность маршрута, то по маршруту может быть пропущена только
часть потока. Оставшаяся часть
0
,lk
πλ
−
может быть направлена от пункта
k
A к
l
A по другим маршрутам, при этом могут использоваться и участки
(дỳги (),
j
i ) уже построенного маршрута, пропускная способность которых
использована неполностью (
0
,lkij
c
π
> ). Это позволит увеличить общую
пропускную способность от пункта
k
A к
l
A , т.е. пропускную способность
сети.
6
5
4
3
2
1=i

Страницы