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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

60
(табл. 21; строка 2, жирный шрифт). Однако участки 3,4,1 и 1,4,2 – это
кратчайшие маршруты (см. табл. 20), поэтому удаление любого элемента
4=
j
удлинит цикл и увеличит энергозатраты. Вычислять новые
(исправленные
и
Э
1
) значения энергозатрат и величины
u
1
ε
не имеет
смысла (прочерки в строке 2).
Иная ситуация имеет место в строке 9 табл. 21. Выделим участки
маршрута с элементами 2 и 4 и сравним их с соответствующими
кратчайшими маршрутами:
,1,4,2,3,4,2,4,2,3,4;1 :
,1,4,2,3,4,2,4,2,3,4,2,1
КМ
•
(4.19)
Из (4.19) видно, что только активный элемент 2=
j
нарушает
структуру кратчайшего маршрута
4;1, а следовательно, проверке
подлежит только элемент 2, отмеченный точкой. Изъятие этого элемента
уменьшит длину маршрута на 2 ед., однако сам активный элемент
переместится со второй позиции на пятую. Это увеличит энергозатраты
больше, чем они уменьшатся за счёт сокращения длины пути к другим
пунктам (табл. 21; графа 5, строка 9, с 70 до 72). Следовательно, удалять
активный
элемент
•
= 2j нецелесообразно.
Таким путём в строках 11, 12 табл. 21 найдено утерянное решение.
Однако если рассматривать задачу как двухкритериальную (Э и
L
) и из
всех эквивалентных по энергозатратам решений выбрать решение с
минимальной длиной цикла, то все три решения (табл. 21; стрóки
11 – 13), получаемые путём изъятия элементов, отмеченных точкой
сверху, (и оба решения (4.14)) сводятся к одному решению:
()
.31 ,1041,4,2,5,2,3,4,1
0
1
0
1
===
μμ
LЭЭ
Модифицированный метод расширения цикла в сочетании с
проверкой и корректировкой стыковочных участков цикла позволяет
получить если не оптимальное, то близкое к нему решение.
Однако основным достоинством модифицированного метода
расширения цикла является возможность получить решение обобщенной
задачи коммивояжера при
неполной матрице расстояний с )1( <
ϕ
.
Порядок решения проиллюстрируем на примере графа, представленного
на рис. 1.
В табл. 22 (переписанная табл. 1), отражающей граф в матричной
форме, представлена исходная информация. Вектор грузов записан под
(табл. 21),
(табл. 20).

Страницы