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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

83
Начальное звено цикла 2;1 соответствует минимальному значению
удельного расстояния (1
2,1
=
ε
), однако согласно принципу доминирования
(4.33) выбирается маршрут 6,2,1 (табл. 31, строка 1
=
i ).
Очередной присоединяемый участок цикла следует найти в строке
6=
i табл. 31, однако вначале пересчитываются значения
j,6
ε
, 5;1=
j
. С
учетом того, что элементы
{
}
6,2,1 уже вошли в наращиваемый цикл и
теперь не
являются активными, согласно (5.1) имеем
,
2,61,6
∞=
=
ε
ε
7.6
3,6
=
ε
, 11
4,6
=
ε
, 9
5,6
=
ε
.
Например, присоединение к маршруту
6,2,1 участка 2,1,6
0
2,6
=
μ
не
добавит ни одного активного элемента, так как элементы 1=
j
и 2 уже
включены в маршрут
0
6,1
μ
и, значит, знаменатель в (5.1) равен нулю.
В соответствии с минимальным значением
ε
к первому звену цикла
6,2,1 присоединяется недоминируемый маршрут =
0
3,6
μ
3,5,4,1,6
(табл. 31), в котором содержатся остальные активные элементы {3,4,5}. К
элементу 3=
j
остается присоединить маршрут
0
1,3
μ
, замыкающий цикл.
1,4,3
0
1,3
=
μ
(табл. 31), поэтому окончательно получим
1,4,3,5,4,1,6,2,11,4,33,5,4,1,66,2,1
1
=
∪∪=
μ
,
(
)
42
1
=
μ
L . (5.5)
Первое необходимое условие оптимальности выполнено по
построению. Второе необходимое условие оптимальности также
соблюдено, однако позволяет из решения удалить внутренний элемент
1=
j
. Его наличие связано с неоднозначностью кратчайшего пути
0
4,6
μ
(табл. 31).
Решение (5.5) фактически совпадает с решениями, полученными
методом расширения цикла (табл. 32). Его погрешность равна 2,4 %.
Наряду с рассмотренным неформальным подходом, опирающимся на
физические условия и специфику задачи коммивояжера, возможны и
другие принципы формирования цикла, учитывающие те или иные
особенности задачи. Важным фактором при этом является
количество
активных элементов
, присоединяемых к циклу на каждом шаге процесса.
На первом шаге их количество может быть увеличено, если использовать
свойство
инвариантности оптимального решения к исходному пункту
цикла
. Это позволяет выбрать исходный пункт цикла таким образом,
чтобы в начальный участок цикла вошло
как можно большее число
активных элементов
, при этом выбор начального участка цикла
осуществляется в таком порядке.

Страницы