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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

82
5.3. Решение тестового примера задачи коммивояжера
комбинированным методом расширения цикла
Суть комбинированного метода расширения цикла состоит в том, что,
начиная с начального цикла
kk
H
;=
μ
, по критерию
ε
выполняется
первый шаг
модифицированного метода расширения цикла. Полученный
при этом текущий цикл является начальным циклом для последующего
решения
немодифицированным методом расширения цикла. Для
иллюстрации метода используем полученные ранее результаты.
На первом шаге (табл. 33) получено текущее решение
(
)
{
}
5,4,3 ,10 ,1,6,2,1
21
1
1
1
=== GL
μμ
.
Далее процесс осуществляется по методу расширения цикла, его
динамика представлена в первой строке табл. 32. После следующих трех
шагов получено решение (табл. 32, нижняя строка в рубрике к = 1)
.43)( ,1,4,3,5,6,2,1
5
1
5
1
==
μμ
L
Его улучшение на основе первого необходимого условия
оптимальности приводит к окончательному решению, совпадающему с
решением (5.4). Погрешность составляет 2,4 %.
Комбинированный метод расширения цикла обеспечивает некоторое
уменьшение объема вычислений, тем большее, чем большее количество
элементов будет включено в текущий цикл на первом шаге процесса.
5.4. Решение тестового примера задачи коммивояжера
методом последовательного наращивания цикла
Метод последовательного наращивания цикла ранее был рассмотрен
применительно к решению обобщенной задачи коммивояжера. В обычной
задаче коммивояжера изменится только смысл величины
ij
ε
: теперь это не
удельные энергозатраты (средние энергозатраты на доставку груза к
одному пункту (4.17)), а
удельное расстояние (среднее расстояние между
пунктами в цикле (5.1)). Принцип доминирования (4.33) остается
справедлив для обеих задач, несмотря на то, что физический смысл
величины
ij
ε
в каждом случае разный. Методом последовательного
наращивания цикла по критерию
ε
найдем решение задачи коммивояжера,
выходящего из пункта
1
A (табл. 30). Для получения решения достаточно
иметь совмещенную матрицу, представленную в табл. 31.

Страницы