Системы линейных неравенств. Зоркальцев В.И - 29 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

29
Рис.2 Множество допустимых решений системы линейных неравенств
(16), векторы
112 2
,
x
ex e== – решения системы с максимальными
наборами активных ограничений.
2.2 Максимальный шаг движения по заданному направлению, не
выводящий из множества решений системы линейных неравенств
Пусть ,,0.
n
xXzR z∈∈ ≠ Обозначим (,)
x
z
λ
максимальную
вещественную величину
R
λ
∈ , при которой вектор
x
z
λ
+
принадлежит
X
, т.е.
zX
λ
+∈ при (,)
x
z
λ
λ
= и
x
zX
λ
+
∉ при любом (,).
x
z
λ
λ
>
Если
zX
λ
+∈ при любом 0
λ
> , то полагаем (,)
x
z
λ
=∞. Во всех
случаях (,) 0
x
z
λ
≥ .
Величину (,)
x
z
λ
будем называть максимальным шагом движения из
точки
x
по направлению
z
в области .X
Отметим, что условие
(,)
x
z
λ
≠
∞
выполняется в том и только том случае, если
() 0,
L
z
≠
/ (17)
где
() {: , 0}.
i
Lz i a z=<
%
В случае (17)
()
(,) min : ()
(,)
i
i
rx
x
ziLz
az
λ
⎧
⎫
−
=∈
⎨
⎬
⎩⎭
%
. (18)
Номер
i
, на котором в (18) достигается значение (,),
x
z
λ
обозначим (,)ixz.
Ограничение с номером (,)ixz является активным в точке (,).
x
xzz
λ
+
Если и только если
0
() () 0,Lz I x
≠
/I
то
(,) 0.
x
z
λ
=
В этом случае
X
12
1
x
x
+
≥
2
x
1
x
2
e
1
e
                       x2

                                                 X

                       e2


                                                             x1
                                       e1
                                                     x1 + x 2 ≥ 1
Рис.2 Множество допустимых решений системы линейных неравенств
(16), векторы x1 = e1, x 2 = e2 – решения системы с максимальными
наборами активных ограничений.

     2.2 Максимальный шаг движения по заданному направлению, не
  выводящий из множества решений системы линейных неравенств
       Пусть x ∈ X , z ∈ R n , z ≠ 0. Обозначим λ ( x, z ) максимальную
 вещественную величину λ ∈ R , при которой вектор x + λ z принадлежит
   X , т.е. x + λ z ∈ X при λ = λ ( x, z ) и x + λ z ∉ X при любом λ > λ ( x, z ).
    Если x + λ z ∈ X при любом λ > 0 , то полагаем λ ( x, z ) = ∞ . Во всех
случаях λ ( x, z ) ≥ 0 .
    Величину λ ( x, z ) будем называть максимальным шагом движения из
точки x по направлению z в области X .
    Отметим, что условие
                           λ ( x, z ) ≠ ∞
выполняется в том и только том случае, если
                           L( z ) ≠ 0,/                              (17)
где
                           L( z ) = {i : a% i , z < 0}.
    В случае (17)
                                             ⎧ − ri ( x)               ⎫
                            λ ( x, z ) = min ⎨    i
                                                         : i ∈ L ( z ) ⎬.  (18)
                                             ⎩ (a% , z )               ⎭
Номер i , на котором в (18) достигается значение λ ( x, z ), обозначим i ( x, z ) .
Ограничение с номером i ( x, z ) является активным в точке x + λ ( x, z ) z.
    Если и только если
                          L( z ) I I 0 ( x) ≠ 0,
                                               /
то
                          λ ( x, z ) = 0.
В этом случае


                                            29

Страницы