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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

50
цикла, то выбирается конкретный исходный пункт (пусть 1=
k
).
Промежуточным пунктом
m
A в исходном цикле
1
1
μ
может быть выбран
любой из оставшихся пунктов (пусть 3
=
m ). Согласно
0
3 для исходного
цикла )1,3,1(
1
1
=
μ
имеем
1,3,1 },5,4,2{}3,1{\}5,4,3,2,1{
1
1
1
===
μ
G
,
.100)1517(1174)()(
1,33,113,13
1
1
1
1
=+⋅+⋅=++== ccacaЭЭ
μ
Промежуточные данные расчётов, полученные для всех трёх шагов
процесса решения методом расширения цикла, приведены в табл. 19.
Например, при включении номера
2
2 G∈=
γ
во второй интервал (2=
r
)
текущего )2( =
t
цикла )(
2
1
γμ
полное приращение энергозатрат )2(
2
2
Δ
согласно
0
5 (рис. 4) равно:
.1078522)3128)(14()83(2
))(()(1,3,2,4,1)2()(
1,21,33,2132,44,12
2
2
=+=−++++
=−++++=Δ=Δ=Δ
cccaacca
t
r
γ
Согласно пункту
0
6 минимальный прирост энергозатрат на шаге
2
=
t
соответствует включению в интервал 1
2
=
r номера пункта
2
A
(2
1
2
==
γ
γ
r
)
1
.
Примечание. В табл. 19 включаемые в текущий цикл номера
пунктов и минимальные приросты энергозатрат выделены жирным
шрифтом.
Из табл. 19 видна динамика решения обобщенной задачи
коммивояжера методом расширения цикла.
На первом шаге согласно пункту 6
0
процесса (1
=
t
) в текущий цикл
был включен элемент
4
1
=
γ
(интервал
4
=
r
), при этом энергозатраты не
только не увеличились, но даже уменьшились (046)4(
1
<−=ΔЭ ).
Физически это обусловлено тем, что включение элемента 4
1
=
γ
в
интервал 1
=
r
сократило длину пути перевозки грузов к пунктам
)4(
33
=aA и )1(
11
=aA на 11 ед. [см. формулу (4.5)]:
1
Отрицательный прирост энергозатрат может быть получен в том случае, если включение в
цикл номера
t
r
приводит к уменьшению длины пути к последующим пунктам, что имеет
место, например, на шаге
1=
t
(табл. 19).

Страницы