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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

115
()
1119463600:
14
1
>=+++++=⎯→⎯
Σ
xLAA
x
,
()
1118463005:
34
1
>=+++++=⎯→⎯
Σ
xLAA
x
,
()
1114200363:
54
1
>=+++++=⎯→⎯
Σ
xLAA
x
,
()
1113030343:
64
1
>=+++++=⎯→⎯
Σ
xLAA
x
.
Перебор всех 15
2
6
=C вариантов размещения баз подтверждает
оптимальность решения (7.10). При оптимизации размещения очередной
1+
R
-й базы исходной информацией является вариант с размещением
R
баз (7.8), и к нему последовательно добавляется каждый из
R
n
−
возможных вариантов размещения
1
+
R
-й базы. Из этих вариантов
выбирается лучший (с минимальной суммой длин
Σ
k
L ).
Для дальнейшего уменьшения объема вычислений вместо оценки и
сравнения
Rn −
вариантов в вычислительной схеме (табл. 48) использован
метод перемещений при начальном размещении
3
=
r
базы в одном из
пунктов
{} { }
6,5,2,1, =iA
i
(табл. 46, ориентированный граф).
Таблица 48
t №
j
1 2 3 4 5 6
R
()
RxL ,
Σ
1
()
RL
jk
r
0
,
5
3
6
4
0
3
0
4
3
4
2
4
2 16
2
0
,6 j
L
8 4 3 6 9 0 - -
1
3
()
1
0
,
+RL
jk
r
5
3
4
6
0
3
0
4
3
4
0
6
3 12
4
0
,2 j
L
11 0 6 9 12 11 - -
2
5
()
1
0
,
+RL
jk
r
5
3
0
2
0
3
0
4
3
4
2
4
3 10
Примечание. В строках 1, 3, 5 сохранены только первые индексы
(номера пунктов – баз). Вторые индексы вынесены в верхнюю часть
таблицы.
В первой строке табл. 48 записана исходная информация (7.8). Длины
маршрутов
0
,6
j
L от третьей базы (6
3
=
k
) взяты из табл. 46, 6=i (строка 2
табл. 48). «Свертка» этих строк в соответствии с (7.7) дает улучшенный
результат, записанный в строке № 3 табл. 48.

Страницы