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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

72
4)( ,2;1:
1
2,1
1
2,1
===
μμ
Э1t . (4.27)
На втором шаге из пункта
2
A маршрут с минимальными удельными
энергозатратами
0
5,2
μ
(табл. 29, 8
5,2
=
ε
, строка 2
=
i ) подсоединяется
справа к маршруту (4.27) и после шага 2
=
t
получаем удлинённую часть
искомого цикла:
.20)( ,5,2,15;21;2 :
2
5,1
2
5,1
===∪=
μμ
Э2t (4.28)
Так как маршрут оканчивается в пункте
5
A , то, переходя к строке
5=
i (табл. 29), находим очередной присоединямый кратчайший маршрут
4;5
3
4,5
=
μ
, которому соответствуют минимальные удельные
энергозатраты (10
4,5
=
ε
)
1)
. Подсоединяя
3
4,5
μ
к (4.28), после.20третьего
шага получим
50)( ,4,5,2,14;55,2,1 :
3
4,1
3
4,1
3
4,5
2
5,1
===∪=∪=
μμμμ
Э3t
. (4.29)
Переходя далее к строке 4
=
i , снова уточняем табличные значения
величин
3
,4
j
ε
, учитывая тот факт, что к моменту получения маршрута
(4.29) часть активных элементов уже вошла в него, и фактически осталось
включить только элемент 3
=
j
(не считая замыкающий 1=
j
). Пересчет
производится по формуле
1−
−
=
′
ij
kkij
ij
n
LaЭ
ε
, (4.30)
где
k
– номер исключаемого (уже вошедшего в (4.29)) элемента.
Уточнённые значения удельных энергозатрат, согласно (4.30), равны:
,
0
0
ε
1,4
=
′
,18
12
9236
ε
2,4
=
−
⋅
−
=
′
18εε
3,43,4
=
=
′
.
Из этих элементов выбирается элемент
3,4
ε
, так как ему соответствует
маршрут
3,4
(табл. 29, 4=i ).
1
Удельные энергозатраты 7
1,5
=
ε
после шага 2
=
t
должны быть пересчитаны, так как
элемент
1=
j
уже вошёл в (4.28) и при пересчёте из 1,4,5
1,5
=
μ
должен быть исключён
как повторный, а потому уточнённое значение удельных энергозатрат равно
10ε
1,5
=
′
.

Страницы