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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

113
возможного смещения точек
r
x
. Проиллюстрируем методику решения
задачи на примере размещения двух баз на ориентированном графе (табл.
46).
Базу 1
=
r
следует разместить (табл. 46) в пункте
4
A (4
1
=
k
), т.к. при
этом сумма длин минимальна (26
4
=
Σ
L ). В группу
4
1
=k
включаются
пункты с номерами
{} { }
4
4
6,5,4=
′
j
. Длины кратчайших маршрутов к ним
соответственно равны
{
}
{
}
2,3,0
0
,4
=
j
L . Сумма длин использованных
маршрутов равна 5230
=++ . Исправленные значения сумм записаны в
нижних частях тех же клеток в правой части табл. 46. Минимальному их
значению соответствует строка
3
2
=
=
k
i
, поэтому вторая база (2
=
r
)
размещается в пункте
3
A
. Согласно условию (7.7) все n пунктов
последовательно, начиная с
1
A (1
=
j
), разбиваются на 2
=
подмножества:
{}
1
k
j ,
{}
2
k
j (3,4
21
== kk ). Сохраняя запись индексов, в
соответствии с (7.7) и табл. 46 имеем
()
{}
6,45,44,43,32,41,3
0
,
2,3,0,0,6,5=
⎭
⎬
⎫
⎩
⎨
⎧
n
jk
RL
r
. (7.8)
Из (7.8) для полученного размещения баз
(
)
(
)
()
3;4,
21
== kkk
r
следует
{
}{}
{
}
{
}
{
2
3
1
4
;1,6,5,,2
21
=
=
=
=
=
=
r
k
r
k
jj 34
43421
. (7.9)
Первые индексы в (7.8) указывают номера
r
k
i
=
пунктов размещения
баз и позволяют выделить множества номеров пунктов, обслуживаемых с
соответствующих баз (вторые индексы в (7.8)). На основании (7.8) и (7.9)
для (7.5) имеем
(
)
()
(
)
(
)
(
)
165110523062,
3241
0
21
=+=+++++=
====
Σ
3214434421
krkr
L x
,
где суммируемые элементы в табл. 46 выделены шрифтом.
Множество
{} { }
6,5,4
4
=
′
j , сформированное до введения второй базы,
согласно (7.7) уточнено [см. (7.9)].
Перебор всех 15
2
6
=C возможных вариантов подтвердил
оптимальность размещения баз в пунктах
4
A и
3
A (их номера в (7.9)
выделены шрифтом).

Страницы