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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

111
Таблица 47. Совмещенная матрица (неориентированный граф)
0
,
0
,
ji
ji
L
μ
j
i, k
1 2 3 4 5 6
Σ
k
L
max
k
L
1
0;0
0
1,4,6,2
9
1,4,6,3
8
1;4
3
1;5(1,4,5)
6
1,4,6
5
31
9
9
2
2,6,4,1
9
0
2;3
6
2,6,4
6
2,6,4,5
9
2;6
4
34
0
9
3
3;1
4
3;2
6
3;4
3
3,4,5
6
3;6
6
26
6
6
4
4;1
3
4,6,2
6
4;3
3
0
4;5
3
4;6
2
17
6
6
5
5;1
6
5,4,6,2
9
5,4,3
6
5;4
3
5,4,6
5
29
9
9
6
6,4,1
5
6;2
4
6;3
3
6;4
2
6,4,5
5
19
4
5
Если количество баз 1
>
R
, то задача распадается на
R
подзадач, с
одним складом каждая. При этом необходимо n пунктов так разделить на
R
групп, каждая из которых обеспечивается со своего
r
-го склада
(
r
xточкаRr −= ,1), чтобы суммарная длина маршрутов со всех
R
баз
была минимальной. Формальная постановка задачи с
R
базами может
быть представлена в виде
()
{}
0
,
1
,min,
r
r
k
R
kj
rjj
LR L
Σ
=∈
=→
∑∑
x
õ
(7.5)
{
}
{}
,.. , 1,,
ir
AA òåik j r R
r
k
n
∈= = ∈ =õ
(7.6)
где
х
(
)
R
r
x=
–
r
x
– точка размещения
r
-й базы, обслуживающей
множество пунктов
r
-й группы с номерами
{
}
r
k
j ;
r
k
– номер пункта
r
k
,
в котором размещается
r
-я база;
0
,
jk
r
L – длина кратчайшего пути от
пункта
r
k
до пункта
j
A .
Подмножества
{}
r
k
j , ( Rr ,1= ) являются разбиением полного
множества
{
}
nI ,1= :

Страницы