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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

87
5.6. Решение тестового примера обобщенной задачи коммивояжера
методом расширения цикла
Исходные данные остаются теми же. Они представлены в табл. 34 и
вектором грузов
а )(
j
a
=
.
Промежуточные и конечные результаты расчетов при решении задачи
методом расширения цикла, блок-схема алгоритма которого представлена
на рис. 4, приведены в табл. 36. В подразделе 4.2 даны подробные
пояснения и обоснования к алгоритму метода расширения цикла.
С начального цикла (табл. 36)
1,3,1
1
=
H
μ
(выбран произвольно) к
началу пятого шага процесса множество номеров пунктов, еще не
включенных в цикл, стало пустым (
∅
=
5
G
). Полученное решение
несколько не совпадает с решениями, полученными методами
последовательного наращивания цикла (5.8). Однако если отказаться от
жесткого условия об однократности посещения пунктов, то, проверив
первое необходимое условие оптимальности и заменив неоптимальный
участок
1;3 в решении (табл. 37) на оптимальный 1,4,3 (табл. 35),
получим решение (5.8).
Объем вычислений оказался значительным, однако для получения
решения не потребовалось прибегать к использованию матрицы
кратчайших маршрутов (табл. 35, 31).
Совпадение решений укрепляет уверенность в их оптимальности,
однако не дает полной гарантии этого, так как каждый из методов
содержит элементы неформального подхода.
Таблица 36
1t =
{}
6,5,4,2
1
=G
1031,3,1
1
=Э
3t
=
{}
5;4
3
=G
2021,3,6,2,1
3
=Э
r
)(
1
γμ
t
)(
γ
t
ЭΔ
r
)(
1
γμ
t
)(
γ
t
ЭΔ
1 1 1,2,3,1 5+30=35 1 1,4,2,6,3,1 10+192=202
2 1 1,4,3,1 10+95=105 1 1,5,2,6,3,1 66+784=850
3 1 1,5,3,1 66+40=106 2 1,2,4,6,3,1 22+66=88
4 1 1,6,3,1 54+95=149 2 1,2,5,6,3,1 84+451=535
5 2 1,3,2,1 170+7=177 3 1,2,6,4,3,1 30+75=105
6 2 1,3,4,1 60+4=64 3 1,2,6,5,3,1 69 – 25=44
7 2 1,3,5,1 120+21=141 4 1,2,6,3,4,1 88 – 5=83
8 2 1,3,6,1 270+12=282 4 1,2,6,3,5,1 162+21=183
9
2t =
{}
6,5,4
2
=G
1381,3,,1
2
=2Э
4
=
t
{}
4
4
=G
2461,3,,6,2,1
4
=5Э

Страницы