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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

109
то смещение точки
x
, в силу линейного характера (7.3), следует
продолжить в том же направлении до ближайшей вершины графа. При
знаке < в (7.3) точку
x
следует смещать в противоположном направлении
до ближайшей вершины, что снова уменьшит суммарную длину
маршрутов. Из достигнутой вершины снова даются пробные приращения
x
Δ в каждом из возможных направлений, при этом значения
1
n и
2
n будут
меняться, что в каждом случае определит и знак неравенства (7.3). Если
для каждого возможного направления будет получено
12
nn < , то берется
0=Δ
x
– решение оптимально. При
12
nn
=
вся соответствующая грань
содержит оптимальные решения.
Поскольку решение, как правило, соответствует одной из вершин, то
достаточно построить все множество кратчайших маршрутов (раздел 2) и
начальную точку
x
разместить в любой из вершин
()
nkA
k
,1= . Далее
точки
x
по каждой из дуг, исходящих из вершины
k
A
, смещаются на
x
Δ
.
Если смещение точки
x
от вершины
k
A
по дуге
(
)
jk, к вершине
j
A ,
согласно (7.3), приводит к уменьшению суммы длин маршрутов, то точка
x
перемещается в вершину
j
A . Процесс заканчивается, если смещение по
дуге к любому смежному объекту ведет только к увеличению общей
длины маршрутов (условие локального минимума). Порядок решения
задачи (7.1), (7.2) проиллюстрируем на примере определения одной
()
1
=
R
точки
x
и ориентированного графа, представляющего транспортную сеть
(рис. 1).
На основе матричного представления сети (табл. 1) эстафетным
методом (раздел 2) строится все множество кратчайших маршрутов,
которое и представлено в табл. 46 (и табл. 9). Пусть в качестве исходного
положения точки
x
взята вершина
2
A
, которой соответствует сумма длин
кратчайших маршрутов 49
2
=
Σ
L .
Из пункта
2
A
возможен переход только к пункту
3
A , что видно из
начальных дуг маршрутов, исходящих из пункта
2
A
(
(
)( )
3;2; =jk , табл. 46,
строка 2=
k
). При смещении точки
1
x
в вершину
3
A
суммарная длина
маршрутов уменьшится до
28
3
=
Σ
L
.
Из
3
A
возможен переход к вершинам с номерами {1;4}, но только
смещение точки
x
в вершину
4
A
обеспечит дальнейшее уменьшение
суммы длин маршрутов (
31
1
=
Σ
L
,
26
4
=
Σ
L
, табл. 46). Дальнейший переход
от вершины
4
A
к
6
A или
5
A приведет только к увеличению суммарной
длины маршрутов, следовательно, оптимальное размещение базы (точки
x
) соответствует пункту
4
A (рис. 1).

Страницы