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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

122
длина маршрутов к которым возрастает при этом. Номер
B
j концевого
пункта
B
j
A
наибольшего по длине маршрута находится из условия
{}
{
}
B
jkjk
jk
jj
jLL
BB
B
,max
0
,
0
,
0
,
μ
⇒=
∈
. (7.17)
Для рассматриваемого примера согласно (7.15), (7.17) имеем
(
)
62,1,4,5
10
2;6
0
,
0
1;6
0
,
======== kkjjLLLL
B
jkjk
Bm
.
При смещении точки
x
от пункта
6
A
по дуге (6;4) величина
смещения
x
Δ определяется из условия, что длина убывающего маршрута
сравняется с длиной возрастающего маршрута:
(
)
1
,,
0
,
0
,
,.., kkxLxLетLL
Bm
Bm
jkjk
jxjx
=Δ+=Δ−= . (7.18)
Из (7.18) для рассматриваемого примера имеем
()
5,0455,05,0
0
,
0
,
11
=−=
⎟
⎠
⎞
⎜
⎝
⎛
−=Δ
Bm
jkjk
LLx . (7.19)
Оптимальное положение точки
x находится на расстоянии 0,5 ед. от
пункта
6
A
по дуге (6;4), (рис.1). При этом длина каждого из множества
{}
m
j
убывающих маршрутов уменьшится на 0,5 ед., а возрастающих –
увеличится на 0,5 ед. Длины кратчайших маршрутов из оптимальной точки
0
x станут равными (сравни с
0
,6 j
L ; табл. 47):
Таблица 49
j
1 2 3 4 5 6
0
,
0
jx
L
4,5 4,5 3,5 1,5 4,5 0,5
Длина маршрута до наиболее удаленного пункта при этом
минимальна и равна
(
)
5,4
0
=xL ед.

Страницы