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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

27
Отметим, что для
x
X∈
() 0,rx≥
0
() 0, (),
i
rx i I x
=
∈
() 0, ().
i
rx i Ix>∈
Лемма 1. Если
x
X∈ , y X∈ , то для вектора
(1 )
x
xy
λ
λ
=+−
%
(8)
при
(0,1)
λ
∈ (9)
справедливы соотношения
000
() () ()
I
xIxIy
=
%
I , (10)
() () ()
I
xIxIy
=
%
U
. (11)
Доказательство. Из (7), (8) следует, что
() () (1 )().rx rx ry
λ
λ
=
+−
%
(12)
Действительно,
( (1 ) ) ( ( ) ) ((1 ) ) (1 )
xybAxbAy b
λ
λλλλλ
+− −= − + − −− =
()(1)().
A
xb Ayb
λ
λ
=−+− −
Согласно (9)
0, (1 ) 0.
λ
λ
>−> (13)
Из условий
x
X∈ , yY∈ следует, что
() 0, () 0rx ry≥≥
и в силу (12)
() 0,rx≥
%
т.е. .
x
X∈
%
При этом из (12), (13) следует, что () 0
i
rx
=
%
для некоторого номера
ограничения i в том и только том случае, если
() 0
i
rx
=
и () 0
i
ry= , что дает
соотношение (10). Если хотя бы одна из величин ()
i
rx или ()
i
ry больше
нуля (вторая может равняться нулю или быть положительной), то,
согласно (12), (13),
() 0
i
rx>
%
. Это дает соотношение (11).
Лемма 1 доказана.
Вектор
x
X∈ будет решением системы линейных неравенств (1) с
максимальным набором активных ограничений
, если не существует
вектора yX∈ , все активные ограничения которого являются активными
ограничениями для
x
и при этом хотя бы одно активное ограничение у
решения y не является активным для решения
x
, т.е.
00
() ().
I
xIy⊂ (14)
Отметим, что решения с максимальным набором активных ограничений
можно также назвать
решением с минимальным набором неактивных
ограничений
. Для такого решения
x
X
∈
не существует вектора yX
∈
,
при котором 
Отметим, что для x ∈ X
                           r ( x) ≥ 0,
                           ri ( x) = 0, i ∈ I 0 ( x),
                           ri ( x) > 0, i ∈ I ( x).
      Лемма 1. Если x ∈ X , y ∈ X , то для вектора
                           x% = λ x + (1 − λ ) y                                   (8)
при
                              λ ∈ (0,1)                                            (9)
справедливы соотношения
                                I 0 ( x% ) = I 0 ( x) I I 0 ( y ) ,                  (10)
                                I ( x% ) = I ( x) U I ( y ) .                        (11)
     Доказательство. Из (7), (8) следует, что
                                r ( x% ) = λ r ( x) + (1 − λ )r ( y ).               (12)
Действительно,
               A(λ x + (1 − λ ) y ) − b = ( A(λ x) − λb) + A((1 − λ ) y ) − (1 − λ )b =
                                = λ ( Ax − b) + (1 − λ )( Ay − b).
Согласно (9)
                                λ > 0, (1 − λ ) > 0.                                 (13)
Из условий x ∈ X , y ∈ Y следует, что
                                r ( x) ≥ 0, r ( y ) ≥ 0
и в силу (12)
                                r ( x% ) ≥ 0,
т.е. x% ∈ X .
     При этом из (12), (13) следует, что ri ( x% ) = 0 для некоторого номера
ограничения i в том и только том случае, если ri ( x) = 0 и ri ( y ) = 0 , что дает
соотношение (10). Если хотя бы одна из величин ri ( x) или ri ( y ) больше
нуля (вторая может равняться нулю или быть положительной), то,
согласно (12), (13), ri ( x% ) > 0 . Это дает соотношение (11).
     Лемма 1 доказана.
     Вектор x ∈ X будет решением системы линейных неравенств (1) с
максимальным набором активных ограничений, если не существует
вектора y ∈ X , все активные ограничения которого являются активными
ограничениями для x и при этом хотя бы одно активное ограничение у
решения y не является активным для решения x , т.е.
                                        I 0 ( x) ⊂ I 0 ( y ).                        (14)
Отметим, что решения с максимальным набором активных ограничений
можно также назвать решением с минимальным набором неактивных
ограничений. Для такого решения x ∈ X не существует вектора y ∈ X ,
при котором


                                           27

Страницы