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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

74
принципу минимальных удельных энергозатрат, так же как и по
принципу убывания веса, является неформальным, а следовательно, в
зависимости от конкретных условий задачи каждый из них может
привести к худшему или лучшему решению. Поскольку оба принципа
реализуют достаточно простые вычислительные процедуры, то в ходе
расчетов целесообразно получить решения на основе обоих принципов и
выделить из них лучшее.
Выводы
1. Обобщение классической задачи коммивояжера, связанное с
требованием доставки
j
a ед. груза в пункт
j
A , существенно усложняет
решение задачи.
Критерий энергозатрат в равной степени учитывает и
вес груза ),1( nja
j
= , и расстояние, на которое он перевозится.
Оптимальное решение (цикл), как правило, отличается от цикла
минимальной длины. Классическая задача коммивояжера соответствует
частному случаю обобщенной задачи:
1 ,0 :1
1
=
=
≠
∀
aaj
j
.
2. Немодифицированный метод расширения цикла обеспечивает
получение решения только при полной (
1
=
ϕ
) матрице расстояний. В
полученном решении каждый элемент
j содержится только по одному
разу
, за исключением начального.
3. Необходимое условие оптимальности решения, полученного
методом расширения цикла, состоит в том, что
каждая пара смежных
вершин (их номеров в цикле) является кратчайшим маршрутом
.
Невыполнение указанного условия открывает возможность
улучшения решения путём замены в цикле той пары элементов
),(
j
i ,
которая не образует кратчайшего маршрута, на кратчайший маршрут с
теми же граничными элементами
),(
j
i . После улучшения в цикле
появятся
повторяющиеся элементы.
4. Модифицированный метод расширения цикла обеспечивает
получение решения классической и обобщенной задач коммивояжера при
неполной
)1( ≤
ϕ
, но полносвязной матрице расстояний c. Специфика
модифицированного метода расширения цикла обеспечивает выполнение
необходимого условия оптимальности (раздел 2, 1-й вывод). При этом в
решении, как правило,
появляются повторяющиеся элементы j .
5. Необходимым условием оптимальности решения, полученного
модифицированным методом расширения цикла, является
невозможность
его улучшения путём удаления любого элемента, содержащегося в
конечном цикле более одного раза
. Согласно этому условию, решение
классической задачи коммивояжера, полученное модифицированным

Страницы