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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

110
Рассмотренный пример позволяет предельно упростить процедуру
поиска оптимальной точки
0
x
: достаточно на основе совмещенной
матрицы, согласно (7.4), вычислить суммарные длины маршрутов
()
nL
k
,1,
Σ
; минимальной из этих длин будет соответствовать оптимальное
положение точки
(
)
0
kix = :
{
}
0
1
1
0
,
,min,
0
0
kiALLLL
k
k
k
nk
n
j
jkk
=⇒==
ΣΣ
≤≤
=
Σ
∑
, (7.4)
где
0
k
– номер пункта размещения базы.
Матрица кратчайших маршрутов для неориентированного графа,
полученного из рис. 1 путем добавления дуг противоположного
направления, представлена в табл. 47. Матрица
c (табл. 1) при этом станет
симметрической (
()
ijji
ccji
,,
:,
=
∀ ). Расширение возможностей
транспортной сети позволило существенно сократить длины кратчайших
маршрутов, однако оптимальное размещение базы осталось прежним.
Таблица 46. Совмещенная матрица (ориентированный граф)
0
,
0
,
0
,
jiji
ji
ЭL −
μ
j
i, k
1 2 3 4 5 6
Σ
k
L
Σ
k
Э
max
k
L
1
1,4,6,2
9-36
1,4,6,3
8-16
1;4
3-3
1;5(1,4,5)
6-18
1,4,6
5-25
31
17
128
48
9
2
2,3,1
11-66
2;3
6-12
2,3,4
9-9
2,3,4,5
12-36
2,3,4,6
11-55
49
17
178
104
12
3
3;1
5-30
3,4,6,2
9-36
0
3;4
3-3
3,4,5
6-18
3,4,6
5-25
28
14
112
55
9
4
4,6,3,1
10-60
4,6,2
6-24
4,6,3
5-10
0
4;5
3-9
4;6
2-10
26
21
113
69
10
5
5,2,3,1
17-102
5;2
6-24
5,2,3
12-24
5,2,3,4
15-15
5,2,3,4,6
17-85
67
35
250
102
17
6
6,3,1
8-48
6;2
4-16
6;3
3-6
6,3,4
6-6
6,3,4,5
9-27
0
30
15
103
75
9
()
()
15,3,1,2,4,6 ==
T
j
aa

Страницы