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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

89
Для проверки условий (4.33) в графе 7 (табл. 37,
t = 2)
определяется ближайший к минимальному (
2
ε
(3;4 ) = 39,0) элемент
2
ε
(3;5) = 62,5. Соответствующий этому элементу маршрут
2
1
μ
(3;5)
включает в себя все элементы маршрута
2
1
μ
(3;4). Условия (4.33)
выполнены и, следовательно, маршрут, записанный в строке 14,
доминирует над маршрутом строки 13, который и выбывает из
дальнейшего рассмотрения (знак минус в графе 7 строки 13). Процесс
проверки на доминирование продолжается.
Ближайшее к
2
ε
(3;5) = 62,5 удельное приращение энергозатрат
2
ε
(2;5) = 64,0 соответствует текущему циклу, в который входит такое же
множество элементов (см. строки 14 и 11, графа 8), следовательно,
)5;2()5;3(
2
1
2
1
μμ
f и исключается доминирующий вариант из дальнейшего
анализа (табл. 37, знак минус в графе 7 строки 11).
Таблица 37. Динамика процесса решения
обобщенной задачи коммивояжера
модифицированным методом расширения цикла
1
=
t
,
{}
6,5,4,3,2
1
=G , 1;1)(
0
1
=
γμ
, 0
0
1
=Э
№ 1 2 3 4 5 6 7 8
r
γ
rr
jj ,
1−
),(
1
γμ
r
t
),(
1
γ
rЭ
t
),(
γ
rn
t
),(
γε
r
t
),(
2
γ
rG
1 1 2 1;1 1,2,6,1 39 2
14,5
3,4,5
2 1 3 1;1 1,4,5,3,4,1 134 3 44,3 2;6
3 1 4 1;1 1,4,1 19 1 19,0 2,3,5,6
4 1 5 1;1 1,4,5,4,1 75 2 37,5 2,3,6
5 1 6 1;1 1,2,6,1 39 2 14,5 3,4,5
2=
t
,
{}
5,4,3
2
=G , 1,6,2,1
1
1
=
μ
, 39
1
1
=Э
),(
3
γ
rG
6 1 3 1;2 1,4,5,3,2,6,1 513 3 158
∅
7 1 4 1;2 1,4,1,2,6,1 157 1 118 3;5
8 1 5 1;2 1,4,5,4,1,2,6,1 433 2 197 3
9 2 3 2;6 1,2,3,2,6,1 400 1 361 4;5
10 2 4 2;6 1,2,4,1,2,6,1 166 1 127 3;5
11 2 5 2;6 1,2,6,4,5,6˙,1 167 2 64,0 – 3
12 3 3 6;1 1,2,6,4,5,3,4,1 263 3
74,7 ∅
13 3 4 6;1 1,2,6,4,1 78 1
39,0 –
3;5
14 3 5 6;1 1,2,6,4,5,4,1 164 2 62,5 – 3
3=
t
,
∅=
3
G
, 1,4,3,5,4,6,2,1
2
1
=
μ
,
263
2
1
=Э
Очередным ближайшим к
2
ε
(3;5) = 62,5 элементом является
2
ε
(3;3) =

Страницы