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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

112
{}
Ij
R
r
k
r
=
=
U
1
,
{}
{
}
∅=
I
ir
kk
jj ,
r
i
≠
,
nn
R
r
r
=
∑
=
1
,
где
r
n – число элементов множества
{
}
r
k
j .
Для получения точного решения задачи с
R
базами необходимо
рассмотреть все
R
n
C возможных вариантов размещения баз (точек
r
x
,
Rr ,1= ). При каждом из этих вариантов разбиение n пунктов по
R
группам осуществляется в следующем порядке. Последовательно, начиная
с первого пункта
()
1=j , для каждого столбца совмещенной матрицы
кратчайших маршрутов пункт
j
A включается в группу
{}
r
k
j
,
обслуживаемую
r
-й базой (пункт
r
k
i
), согласно условию
{}
{
}
{
}
RrjrknjLL
r
r
R
r
k
r
jk
ji
ki
,1,,,,1,min
0
,
0
,
=⇒==
∈
. (7.7)
Условие (7.7) означает, что пункт с номером
j
(
j
A ) включается в
обслуживание
ближайшей
r
-й базой, расположенной в пункте
r
k
A
.
После получения оптимального
разбиения (7.7) из матрицы кратчайших
маршрутов берутся их длины и вычисляется сумма (7.5). Из всех
R
n
c
вариантов, полученных таким путем, выбирается лучший, что и
определяет оптимальное размещение
R
баз.
При больших значениях
n и
R
перебор
R
n
C
вариантов окажется
весьма громоздким (задача NP-полная), поэтому для решения задачи
размещения баз примéним следующий неформальный подход: первая
(
1=
r
) база (точка
1
x
) помещается в пункте
1
k
i
=
с минимальной
суммарной длиной маршрутов
(7.4). Из строки
1
k
i
=
выбирается
несколько наименьших элементов
0
1
k
L , и по соответствующим им
индексам
j
предварительно формируется первая группа пунктов
{}
1
1
k
j
.
Далее вычисляются суммы длин
Σ
k
L оставшихся маршрутов. По
уточненным суммарным длинам
Σ
k
L определяется точка размещения
2
x
второго склада (
2
r
). Группа
{
}
2
k
j формируется уже с учетом двух баз,
согласно условию (7.7). Далее цикл повторяется, пока не будут размещены
все
R
базы и сформированы
R
группы.
После этого проверяется возможность улучшить решение путем

Страницы