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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

114
Примечание. Решая
R
частных задач, соответствующих
разбиению (7.9), можно убедиться, что перемещение базы из пункта
4
A в любой из пунктов
5
A ,
6
A (табл. 46, 4
=
i ) только ухудшит
решение. Например, переместив базу
1
=
r
из
4
A
в
6
A
, получим
(табл. 46)
ΣΣ
=>=++=++=
4
0
5;6
0
4;6
0
2;66
1619964 LLLLL .
Рассмотренным методом получим решение для случая
неориентированного графа (
2
=
R
). Базу 1
=
r
следует поместить в пункт
4
A (табл. 47, 4
1
==
k
i ). В начальное множество
{
}
4
j
включены почти все
элементы
j
(кроме 2=
j
). Действительно, в каждом из столбцов
{
}
4
jj ∈
длина маршрута
0
,4 j
L наименьшая (исключая ноль). После уточнения сумм
длин оставшихся маршрутов (
′
Σ
k
L
записаны в нижних частях клеток
столбца
Σ
k
L (табл. 47)) определяется минимальная длина 0
2
=
′
Σ
L . Ей
соответствует строка 2
2
==
k
i и
{
}
{
}
2
2
=
j .
Согласно полученному решению базы размещаются в пунктах
4
A и
2
A (
{
}
{}
2;4=
r
k
), при этом множества номеров групп
{
}
r
k
j обслуживаемых
объектов и суммы длин маршрутов, согласно (7.7) и (7.5), равны:
{}
{
}
{}
2;4,2,3,0,3,0,3
6;45;44;43;42;21;4
0
,
==
⎭
⎬
⎫
⎩
⎨
⎧
R
r
n
jk
kL
r
,
{}
{
}
{
}
{
}
2,6,5,4,3,1
24
=
= jj , (7.10)
()( )
{
110230332,
2
1
=
+
+
+
+
+
=
=
=
r
r
L
4434421
x
.
Поскольку для формирования множества баз
{
}
R
r
k использовался
неформальный сокращенный метод, то полученное решение следует
попытаться улучшить методом перемещений. Такую попытку в данном
случае требуется сделать для группы маршрутов, исходящих от базы 1
=
,
расположенной в пункте
4
A .
Из строки 4
1
==
k
i (табл. 47) по начальным дугам маршрутов видно,
что переход точки
1
x возможен к пунктам
{
}
6,5,3,1. Каждый из этих
переходов дает увеличение суммы длин маршрутов:

Страницы