ВУЗ:
Составители:
Рубрика:
76
вариантов (
1
Р = 5/15 = 0,33). Чтобы лучшее из m полученных решений
(с различными начальными циклами) можно было бы с гарантией
99,0
г
=Р считать оптимальным, необходимо 11
=
m раз решить задачу, что
следует из (3.4):
.11
67,0lg
01,0lg
)1lg(
)1lg(
1
г
≈=
−
−
=
p
P
m
Из 15 вариантов в 5 случаях (табл. 32) получено точное решение
(
41=
L
), в 8 случаях погрешность равна 4,9 % ( 43
=
L
)Ю, и в двух случаях
погрешность достигла величины 34 % ( 55
=
L
). В двух последних столбцах
табл. 32 записаны решения, улучшенные на основе проверки
первого
необходимого условия оптимальности
1
. Элементы, включенные в цикл
после проверки указанного условия (табл. 31), выделены жирным шрифтом
в предпоследнем столбце. Указанные выше погрешности снизились
соответственно до 2,4 % и 14,6 %.
Заметим, что в улучшенных решениях появились
повторяющиеся
(транзитные) элементы. В проверке для них второго необходимого условия
оптимальности нет необходимости, так как включенные элементы по
условию принадлежат кратчайшим маршрутам.
Таблица 30.
ij
с ,
1
=
ϕ
j
i
1 2 3 4 5 6
1 1 16 5 22 9
2 12 21 10 27 3
3 23 18 14 24 29
4 4 8 30 7 25
5 20 28 2 13 17
6 6 15 26 11 19
1
Каждая смежная пара индексов в конечном цикле должна образовывать кратчайший
маршрут. Проверка условия 2-НОУ сделает оба худших решения (табл. 32, L = 47)
оптимальными путём замены
3,2,1 на 4,1 (табл. 31).
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
