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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

48
маршруты
j1
μ
доставки грузов как частей цикла
1
μ
(4.3) формализуются
следующим образом:
μ
(Э
1
) =
∑
=
n
j
jj
La
1
1
(
μ
)→
1
min
μ
(4.1)
{
}
,
11
μ
μ
∈
(4.2)
.;1 ,
11
nj
j
=⊂
μμ
(4.3)
Длина каждого частного маршрута определится как сумма длин дуг,
входящих в маршрут:
.,1 ,)(
1
),(
,11
njcLL
j
ji
jijj
===
∑
∈
μ
μ
(4.4)
Поскольку в процессе решения гамильтонов цикл сформируется
только к концу процесса расширения цикла, то в ходе решения некоторые
обозначения в (4.1) – (4.4) потребуется дополнить индексом
t
,
обозначающим номер шага (итерации) процесса МРЦ.
Когда для
1≠
∀
имеем 1 ,0
1
=
=
aa
j
, задача вырождается в
обычную задачу коммивояжера.
4.2. Алгоритм решения обобщённой задачи коммивояжера
методом расширения цикла при полной матрице расстояний (φ = 1)
и пример расчёта
Схема решения остаётся такой же, что и в методе расширения цикла,
при этом изменится только порядок определения приращения величины
энергозатрат на текущем (
t
-м) шаге процесса.
Получим формулу для вычисления приращения энергозатрат на
t
-м
шаге процесса при включении индекса
γ
в
r
-й интервал
(
)
rr
jj ÷
−1
цикла.
Энергозатраты при этом повысятся
из-за увеличения общего
перевозимого груза
на величину
γ
a и вследствие изменения длины
цикла
на величину
rrrr
r
j
r
j
jjjj
L
ccc
,,,
11
,,
1
−−
−
−+=
γγ
γ
δ
. (4.5)
Прирост энергозатрат по первой причине определится по формуле

Страницы