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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

39
1
.
t
i
i
i
x
pz
λ
=
=+
∑
(37)
Воспользуемся методом, примененным при доказательстве теоремы 1.
Пусть
x
yz=+, (38)
где
zW∈ .
Вектор y является выпуклой комбинацией векторов ,1,,
s
x
Xs N∈=K
таких что
00
() ( ), 1, , .
s
I
xIxs N⊆=K
Итак,
1
,
N
s
s
s
yx
λ
=
=
∑
где
0, 1, ,
1.
s
s
s
N
λ
λ
≥=
=
∑
K
Первоначально можем считать, что
1
0, , 1, .zyxNxx== = =
Предположим, что вектор
s
при некотором {1, , }
s
N
∈
K не является
решением системы (1) с максимальным набором активных ограничений.
Тогда существует вектор
p
τ
, являющийся решением системы (1) с
максимальным набором активных ограничений, такой что
00
() ( ).
s
I
xIp
τ
⊂
Пусть
.
s
zx p
τ
=−
Возможны два случая:
1. Если направление
z – рецессивное
() 0,
L
z
=
/
то заменим в представлении (38) вектор
z на вектор
zzz=+
%
и вектор y на вектор
.yyz=−
%
Исключим из набора вектор
s
и введем вместо него вектор
p
τ
. Далее в
качестве вектора
z будем использовать вектор .z
%
2. Если
() 0,
L
z
≠
/
то существует
(,)0.
s
xz
λ
> 
                               t
                          x = ∑ λi p i + z.                       (37)
                              i =1
      Воспользуемся методом, примененным при доказательстве теоремы 1.
      Пусть
                         x = y + z,                               (38)
где
                      z ∈W .
Вектор y является выпуклой комбинацией векторов x s ∈ X , s = 1,K, N
таких что
                      I 0 ( x) ⊆ I 0 ( x s ), s = 1,K, N .
Итак,
                               N
                          y = ∑ λs x s ,
                              s =1
где
                          λs ≥ 0, s = 1,K, N
                          ∑λ = 1.
                              s

Первоначально можем считать, что
                       z = 0, y = x, N = 1, x1 = x.
     Предположим, что вектор x s при некотором s ∈{1,K, N } не является
решением системы (1) с максимальным набором активных ограничений.
Тогда существует вектор pτ , являющийся решением системы (1) с
максимальным набором активных ограничений, такой что
                         I 0 ( x s ) ⊂ I 0 ( pτ ).
Пусть
                         z = x s − pτ .
Возможны два случая:
     1. Если направление z – рецессивное
                         L( z ) = 0,  /
то заменим в представлении (38) вектор z на вектор
                         z% = z + z
и вектор y на вектор
                          y% = y − z .
Исключим из набора вектор x s и введем вместо него вектор pτ . Далее в
качестве вектора z будем использовать вектор z%.
     2. Если
                         L( z ) ≠ 0,  /
то существует
                         λ ( x s , z ) > 0.


                                       39

Страницы