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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

81
Однако над обоими этими вариантами доминирует вариант с включением
в интервал
r
= 1 элемента
γ
= 3 (строка 7). Для этого варианта
выполняются условия доминирования (4.33): значение удельного
приращения
2
ε
(1;3) = 10,3 – минимальное среди всех оставшихся
вариантов (кроме
ε
= 9), и он включает в себя любой из других
вариантов
, так как соответствующий ему цикл содержит множество всех
элементов (
∅
=
2
G
, графа 9, строка 7). Ближайший к нему по значению
удельного приращения (
2
ε
(3;3) = 10,7) вариант равносилен только по
первому условию (4.33), а потому не доминирует над ним. Следовательно,
решение будет получено при включении элемента
3
=
γ
в интервал 2;1
маршрута
1
1
μ
(строка 6), при этом попутно в составе соединяющих
кратчайших маршрутов в цикл войдут и два других
активных элемента
(4=
j
и 5), завершая построение цикла. Решение получим, если участок
2;1 в текущем решении
1
1
μ
(табл. 33, строка 6,) заменим расширенным
участком
2,3,5,4,1 (строка 7). Полученное решение записано в строке 16
табл. 33, при этом длина цикла найдется по рекуррентной формуле (5.3):
.413110)3;1()(
1122
1
=+=+==
δμ
LLL
Аналогично найдется решение, например, и для конкурирующего
варианта (табл. 33, строка 13):
1,,3,5,,6,2,11,4,3,5,4,62;1
2
1
44=∪=
μ
, (5.4)
.423210)3;3(
212
=+=+=
′
δ
LL
Полученные решения могут быть найдены (табл. 32) и
немодифицированым методом расширения цикла, при этом в ряде случаев
решения могут быть улучшены при проверке
первого необходимого условия
оптимальности
. При решении задачи модифицированным методом
расширения цикла в такой проверке не возникает необходимости, но при
появлении в решении повторяющихся элементов для них проверяется
второе необходимое условие оптимальности, позволяющее в ряде случаев
улучшить решение.
Однако, как отмечалось ранее, основным достоинством
модифицированного метода расширения цикла является не столько
некоторое сокращение объема вычислений, сколько возможность решения
задачи при
неполной (
ϕ
< 1) матрице расстояний.

Страницы