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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

73
Подсоединяя далее к (4.29) маршрут 3;4
3,4
=
μ
(табл. 29, i = 4),
получим
(
)
.104 ,3,4,5,2,13;41,2,5,4 :
4
3,1
4
3,1
===∪=
μμ
Э4t (4.31)
Остаётся к маршруту (4.31) подключить элемент 1
=
j
, замыкающий
цикл. Переходя к строке 3=
i (табл. 29), видим, что искомым является
маршрут
1,3
μ
. После подключения его к (4.31) получаем оптимальное
решение (см. табл. 27):
(
)
.120 ,1,3,4,5,2,1 :
0
1
5
1,1
0
1
====
μμμ
Э5t (4.32)
В ряде случаев число шагов может быть уменьшено, если ввести и
применить
принцип доминирования, состоящий в следующем. Из строки
1=
i (табл. 29) видно, что маршрут 5,2,1
5,1
=
μ
включает в себя
(поглощает) все элементы исходного маршрута
2;1
2,1
=
μ
, и при этом
его удельные энергозатраты
10
5,1
=
ε
превышают только удельные
затраты поглощенного маршрута
(4
2,1
=
ε
). В этом случае маршрут
5,1
μ
доминирует над маршрутом
2,1
μ
(
2,15,1
μ
μ
f ). Аналогичным образом
маршрут
4,1
μ
превосходит маршрут
5,1
μ
(табл. 29, 1
=
i ), и поэтому в
качестве исходного можно использовать сразу маршрут 4,5,2,1
4,1
=
μ
,
полученный ранее только на шаге 3
=
t
, (4.29). Далее принцип
доминирования не срабатывает, и после двух последующих шагов )5;4( =
t
получаем решение (4.32).
Формально
условия доминирования маршрута
ks
μ
над маршрутом
γ
μ
k
запишутся в виде
μμ,
k,s k, γ
μμ
ε min ε
ks k
γ
k,s k, j
j γ
⊃
⎫
⎪
⇒
⎬
=
⎪
∀≠
⎭
f
. (4.33)
Условие (4.33) означает, что маршрут
sk,
μ
содержит в себе все
элементы маршрута
γ
μ
,k
, и при этом его удельные энергозатраты
являются наименьшими, чем у остальных маршрутов, исключая
доминируемый (второе условие).
Рассмотренный метод последовательного наращивания цикла по

Страницы