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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

124
Решение обратной задачи можно получить, решив несколько раз (при
различных значениях
R
) прямую задачу. Далее рассмотрим возможный
подход к решению прямой задачи при
1>
R
. На примере табл. 47 найдем
решение для случая 2=
R
.
Основная идея решения состоит в том, чтобы путем попарного
(2=
R
) сравнения строк (их элементов
0
, ji
L ) найти такую пару, при
которой согласно (7.7) будет возможно максимально
уменьшить
наибольшие
элементы
0
, ji
L
. Далее такое сравнение производится до
смещения точек
r
x
от их пунктов размещения (проверка на такое
смещение является заключительным этапом решения).
Из строки 6=
i табл. 47 видно, что наибольшие элементы
0
1,6
L и
0
5,6
L
можно уменьшить, если базу
2
=
r
(точка
2
x
) поместить в пункте
4
A . При
полученном текущем решении
(
)
(
)
46
2
, AAx
r
= согласно (7.7) имеем
()
{
}
()
2;6
0
,
6;65;44;4
3;4
2;61;4
0
,
4max,0,3,0,3,4,3 =
⎭
⎬
⎫
⎩
⎨
⎧
=
⎭
⎬
⎫
⎩
⎨
⎧
RLRL
jk
j
n
jk
rr
Т
ji
Э
,
Элемент 4
2;6
=
L из всех значащих элементов столбца 2=
j
является
наименьшим, поэтому уменьшить его значение можно только путем
перемещения точки
1
x
из пункта
6
A
в пункт
2
A
. При решении
(
)
()
42
2
, AAx
r
= имеем
()
()
4
,
2
:
0
,3
6;4
2 ,
5;4
3 ,
4;4
0 ,
3;4
3 ,
,2;2
0 ,
1;4
3max2,
AAx
m
L x=
⎭
⎬
⎫
⎩
⎨
⎧
=
. (7.21)
Уменьшить значение
(
)
32, =x
m
L возможно только путем введения
еще трех дополнительных точек
r
x в пунктах
531
,, AAA , при этом
получим
()
25, =x
m
L .
Улучшить решение путем смещения любой из точек
()
(
)
4
2
,
2
1
AxAx
также невозможно. Сдвиг
2
х
, например, по дуге (4;5) на 0>
Δ
x
приведет к
увеличению на
x
Δ
расстояний до пунктов
1
A и
3
A (табл. 47, 4
=
i ).
Решение (7.21) оптимально.
Получим решение обратной задачи. Например, при 5,43 <≤
доп
L
условие (7.20) будет выполнено при двух (2
=
R
) пунктах обслуживания,
размещенных в точках
4
A и
2
A (7.21).

Страницы