ВУЗ:
Составители:
Величина
U
i
χ является верхней оценкой для значения функции ),(
θ
ψ
d внутри области
)(ν
i
T . Поэтому
закономерно в качестве квазиоптимальной области выбрать область
)(ν
ν
k
T , для которой величина
U
i
χ при-
нимает наибольшее значение
U
i
i
U
k
χ=χ max .
Для проведения процедуры метода ветвей и границ на каждой итерации необходимо также знать
нижнюю границу значения величины ),()(
*
θψ=χ dd . Будем вычислять ее следующим образом [64]. Обо-
значим через
*
i
θ
решение задач (4.56) и найдем
).,,(maxmin),(
**
ij
j
z
i
zdgd θ=θψ
Для этого необходимо решить задачу:
;min
,
α
αz
).,1(,),,(
*
mjzdg
ij
=α≤θ
(4.57)
Вычислим ),(
*
i
d θψ для всех областей .),1(,
)(
ν
ν
= NiT
i
Введем величину
).,(max
*
)( j
j
L
d θψ=χ
ν
Очевидно, что
,),(max)(
)(ν
∈θ
≥θψ=χ Rdd
T
что и определяет
)(ν
R как нижнюю границу для максимального значения функции ),( θψ d . Пусть для не-
которой области выполняется соотношение
)()( νν
χ≥
U
l
R , тогда в соответствии с неравенством
),(max θψ≥χ
∈θ
d
i
T
U
l
имеем
)(
)(
),,(
ν
ν
∈θ∀θψ≥
l
TdR . Следовательно, точка
*
θ заведомо не принадлежит области
)(ν
l
T и в дальнейшем не рассматривается. Процедура прекращается при выполнении соотношения
ε≤χ−
ν
ν U
k
R
)(
,
где ε – малая величина.
Если речь идет об оценке гибкости ХТП, а не о вычислении
)(d
χ
, то описанная процедура может
окончится раньше, чем выполнится последнее условие. Действительно, пусть на
ν
-ой итерации выпол-
нится условие
0max ≤χ
i
i
,
тогда
.0≤χ
ν
k
Далее, на каждом шаге необходимо найти два значения
S
χ
и
q
χ
, соответствующих областям
)1( +ν
S
T и
)1( +ν
q
T
, на которые разбивается квазиоптимальная область
)(ν
ν
k
T . Для этого потребуется два раза решить
задачу (4.56) и кроме того, необходимо найти величины
),(
*
S
d θψ
и ),(
*
q
d θψ , дважды решив задачу (4.57)
для Si = и qi = .
Вернемся теперь к решению задачи (4.58) – (4.60):
Страницы
- « первая
- ‹ предыдущая
- …
- 129
- 130
- 131
- 132
- 133
- …
- следующая ›
- последняя »
