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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

64
указанным способом (по убыванию веса
j
a ) требует более тщательной
проверки.
Применим указанный принцип формирования цикла для случая
полной (
ϕ
=1) матрицы расстояний (табл. 18).
Таблица 24
1=t ,
{
}
6,5,4,3,2
1
=G , 1;1
0
1
=
μ
, 0
1
1
=Э
№ 1 2 3 4 5 6 7
r
γ
rr
jj ;
1−
(
)
γμ
,
1
r
t
(
)
ut
ЭrЭ
11
/,
γ
()
γ
t
r
n
()
u
r
t
r
εγε
/
1 1 2 1;1 1,4,6,2,3,1 125 / - 4 31,3 / -
2 1 3 1;1 1,4,6,3,1 79 / - 3 28,3 / -
3 1 4 1;1 1,4,6,3,1 79 / - 3 28,3 / -
4 1 5 1;1 1,4,5,2,3,1 143 / - 4 35,8 / -
5 1 6 1;1 1,4,6,3,1 79 / - 3 28,3 / -
2=t
,
{}
5;2
2
=G , 1,3,6,4,1
1
1
=
μ
,
(
)
793;1
2
1
=Э
6 1 2 1;4 1,4˙,6˙,2,3˙,4,6,3,1 133 / - 1 54 / -
7 1 5 1;4 1,4˙,5,2,3˙,4,6,3,1 289 / - 2 105 / -
8 2 2 4;6 1,4,6,2,3,4,6,3,1 133 / - 1 54 / -
9 2 5 4;6 1,4˙,5,2,3˙,4,6,3,1 289 / - 2 105 / -
10 3 2 6;3 1,4,6,2,3,1 125 / - 1 46 / -
11 3 5 6;3 1,4˙,6,3˙,4,5,2,3,1 207 / - 2 64 / -
12 4 2 3;1 1,4˙,6˙,3˙,4˙,6,2,3,1 128 / - 1 49 / -
13 4 5 3;1 1,4˙,6,3˙,4,5,2,3,1 207 / - 2 64 / -
3=t ,
{}
5
3
=G ,
(
)
1,3,2,6,4,12;3
2
1
=
μ
, 125
1
=Э
14 1 5 1;4 1,4˙,5,2˙,3˙,4,6,2,3,1 296 / 289 1 171 / 164
15 2 5 4;6 1,4,5,2,3˙,4,6,2,3,1 296 / 289 1 171 / 164
16 3 5 6;2 1,4,6,3,4,5,2,3,1 207 / - 1 82 / -
17 4 5 2;3 1,4˙,6,2˙,3˙,4˙,5,2˙,3˙,1 248 / 207 1 123 / 82
18 5 5 3;1 1,4,6,2˙,3,4,5,2,3,1 248 / 207 1 123 / 82
4=t , Ø
4
=G , 1,,2,5,,3,6,4,1
3
1
0
1
34==
μμ
,
(
)
207
0
11
=
μ
Э ,
(
)
31
0
1
=
μ
L
Упорядочим номера
j
пунктов
j
A по убыванию веса доставляемых
грузов
j
a :
(
j
): 3, 4, 2, 5, 1.
(
j
a ): 4, 3, 2, 1, 1.

Страницы