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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

56
удельных энергозатрат nЭ )(
0
1
μ
при constn
=
. Вычислительную схему
проиллюстрируем на примере графа, заданного в табл. 18, что даёт
возможность сравнить решение с решением, полученным ранее методом
расширения цикла (4.16). Для удобства расчетов на основании табл. 18
вычислено и записано семейство кратчайших маршрутов (табл. 20),
полученное эстафетным методом. Вычисления модифицированным
методом и основные результаты представлены в табл. 21.
На первом шаге )1(
=
t
в качестве начального используется нулевой
цикл
1;1
1
=
н
μ
, в единственный интервал которого поочередно
вставляются элементы
{
}
5,4,3,2
1
=∈G
γ
, соединённые с границами
интервала через кратчайшие маршруты, взятые из табл. 20. Например,
пробный цикл
)3;1(),(
1
11
μγμ
=r
t
, записанный в графе 4 второй строки,
получен путём включения в интервал 1
=
r
элемента 3
=
γ
с помощью
двух кратчайших маршрутов, взятых из табл. 20:
.1,4,2,3,4,11,4,2,33,4,1)3;1(
0
1,3
0
3,1
1
1
=∪=∪=
μμμ
(4.18)
Согласно 1-му выводу (раздел 2) любой частный подмаршрут,
лежащий слева и справа от стыкующего элемента 3
=
γ
, является
оптимальным (кратчайшим), поэтому
неоптимальность возможна
только в районе стыковки кратчайших маршрутов
. Действительно,
обращаясь к табл. 20, видим, что стыковочный подмаршрут
2,,4 3 не
является оптимальным:
62,1,4 ,7432,3,4
2,33,4
=
=
+
=
+
=
LноccL
– КМ.
Таким образом, принудительное включение элемента 3
=
γ
в
интервал 1
=
r
привело к увеличению длины маршрута. В полученном
маршруте коммивояжер дважды пройдет пункт 4
=
j
: при первом
посещении в нём будет оставлен груз
. 3
4
едa
=
, второе посещение
обусловлено необходимостью уменьшения длины текущего цикла
t
1
μ
1
(табл. 21; строка 2).
Для полученных в графé 4 пробных текущих циклов вычисляются
энергозатраты (4.1), при этом удобно использовать вычислительную
схему, иллюстрируемую на примере вычисления энергозатрат )3;1(
1
1
Э
(табл. 21; строка 2, графа 5).
1
Первое посещение пункта именуется в дальнейшем активным («нетранзитным»),
последующие –
транзитными. Аналогично один и тот же пункт (или его номер) в первом
случае именуется
активным, в последующих – транзитным.

Страницы