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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

125
Ориентированный граф
(
)
MAG , отражает более жесткие требования
к сети (городская дорожная сеть), и при прочих равных условиях решение
не может улучшиться. Например, из табл. 46 точка
(
)
1=Rx
может быть
расположена в одном из трех пунктов
631
,, AAA , при этом расстояние до
любого из других пунктов не превысит 9 ед. Из этих пунктов предпочтение
может быть отдано одному, исходя из каких-либо иных соображений.
Например, полагая, что все n маршрутов будут использоваться с
одинаковой частотой
n
/
1, можно найти среднюю длину маршрута по
формуле
{
}
6,3,1, ∈=
Σ
knLL
k
ср
k
.
В этом случае предпочтение должно быть отдано варианту
размещения точки
x
в пункте
6
A , т.к. при этом средняя длина маршрута
будет минимальна.
При размещении точки
x в любом из пунктов ее смещение может
быть целесообразно, как правило, только
по ребру, что дает право
транспортным средствам двигаться в обоих направлениях. Проверим, что
поместив точку
x в пункте
3
A , невозможно далее уменьшить самый
длинный маршрут
9
0
2,3
=L
и улучшить решение. Действительно, сдвинув
точку
x от пункта
3
A по дуге (3;4) на величину 0>Δ
x
, получим
уменьшение длин маршрутов к пунктам
6542
,,, AAAA
(табл. 46, строка
3=
i ) на величину
x
Δ , однако длины маршрутов к пунктам
1
A и
3
A
намного увеличатся:
()
() ()
3,1013103
0
1,44,3
0
1,3
<Δ>Δ−=+Δ−=+Δ−=
′
xxxLxсL .
Ухудшение решения обусловлено тем, что при смещении точки
x
от
пункта
3
A к пункту
4
A добираться к пункту
1
A придется окольным путем
через пункт
4
A .
Примечание. Если на участке от
3
A до
4
A разрешить
двухстороннее движение (дугу (3;4) заменить ребром 3
5,44,3
=
= сc ),
то согласно (7.19) получим 2
=
Δ
x
и решение улучшится:
()
{
}
73,4,1,2,7,7max1,
1
=
=
≤≤ nj
xL
.
Наибольшее улучшение решения аналогичным путем будет

Страницы