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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

123
Примечание. Был использован сокращенный метод смещения,
при котором начальное положение точки
x выбрано из условия
(7.16), что сокращает число смещений точки
x при оптимизации.
Например, при начале в пункте
1
A
будем иметь (табл. 47, i = 1):
{} { }
{
}
{
}
0,9.1,6,5,4,3,2
0
,1
0
,1
====
Bm
jj
Bm
LLjj
.
Согласно (7.19)
(
)
5,4095,0
=
−
=
Δx ед., однако
x
Δ не может
быть больше длины начальной дуги (1;4), 3
4,1
=
c , поэтому при
{}
33;5,4min ==Δx первое смещение точки x приводит к пункту
4
A .
Далее имеем
{} { } {} { }
25,1,3,6.5,4,3,1,6;2
6,4
0
,4
0
,4
=<=Δ==== CxLLjj
Bm
jj
Bm
Смещая точку
x по дуге (4;6) на 5,1
=
Δ
x
ед., приходим к тому
же решению
0
x
(табл. 49).
Начальным не может быть тот пункт, для которого смещение
0=Δ
x
(
3
A ).
В зависимости от исходных данных и в первую очередь размеров
района размещения
n пунктов, даже при оптимальном решении
0
x ,
расстояние
(
)
RL
m
,
0
x при 1
=
R
может оказаться больше максимально
допустимого значения
доп
L
, обусловленного некоторыми практическими
требованиями. Возникает задача такого
покрытия района сетью
обслуживающих точек
R
r
x=x , при котором выполняется условие
)
RrLRL
допm
,1,, =≤x , (7.20)
а количество
R
обслуживающих точек минимально (обратная задача
покрытия).
Примечание. Прямая задача покрытия состоит в таком
размещении заданного количества
R
точек
(
)
R
r
xx
,00
= , которое для
каждого (
Rr ,1= ) обслуживаемого участка района с пунктами
{}
r
k
j
jjA ∈, обеспечивает наименьшее расстояние (время
достижения) до наиболее удаленного пункта
(
)
1,
0
x
m
L
(7.14).

Страницы