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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

91
оптимальности (табл. 38, строки 25 – 28). Объем вычислений при отказе от
использования условий доминирования увеличился примерно вдвое.
Рассмотренный тестовый пример иллюстрирует достаточно высокую
эффективность указанных методов. Это обусловлено тем, что для
формирования решения и в методах
расширения текущего цикла, и в
методах последовательного
наращивания решения, как правило,
используются кратчайшие маршруты. Оптимизация по критерию длины
цикла (табл. 39, строки 1 – 4) обеспечила точное решение данного примера
только при использовании модифицированного метода расширения цикла.
В двух случаях (стрóки 1; 3) погрешность равнялась 5 % и после
улучшения решения в ходе проверки необходимых условий
оптимальности снизилась до 2,4 %.
Таблица 38. Динамика процесса решения тестового примера
обобщенной задачи коммивояжера
модифицированным методом решения цикла
3=
t
,
{}
5;3
3
=G
, 1,4,6,2,1
2
1
=
μ
, 78
2
1
=Э
№ 1 2 3 4 5 6 7 8
r
γ
rr
jj ,
1−
),(
1
γμ
r
t
),(
γ
rЭ
t
),(
γ
rn
t
),(
γε
r
t
t
G
15 1 3 1;2 1,4,5,3,2,6,4˙,1 513 2 217,5
∅
16 1 5 1;2 1,4,5,4,1,2,6,4˙,1 433 1 355,5 3
17 2 3 2;6 1,2,3,2,6,4,1 317 1 239,5 5
18 2 5 2;6 1,2,6,4,5,6˙,4,1 164 1 86,0 3
19 3 3 6;4 1,2,6,4,5,3,4,1 263 2 92,5
∅
20 3 5 6;4 1,2,6,4,5,4˙,3,1 268 2 95,0
∅
21 4 3 4;1 1,2,6,4,5,3,4,1 263 2 92,5
∅
22 4 5 4;1 1,2,6,4,5,4,1 164 1
86,0
3
4=
t
,
{}
3
4
=G
, 1,4,5,4,6,2,1
3
1
=
μ
, 164
3
1
=Э
23 1 3 1;2 1,4,5,3,2,6,4˙,5˙,4˙,1 513 1 349
∅
24 2 3 2;6 1,2,3,2,6,4,5,4,1 720 1 556
∅
25 3 3 6;4 1,2,6,4,5,3,4,5˙,4˙,1 263 1 99
∅
26 4 3 4;5 1,2,6,4,5,3,4,5˙,4˙,1 263 1 99
∅
27 5 3 5;4 1,2,6,4,5,4˙,5˙,3,4,1 263 1 99
∅
28 6 3 4;1 1,2,6,4,5,4˙,5˙,3,4,1 263 1 99
∅

Страницы