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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

34
Доказательство. Докажем, что любое решение
x
X∈ можно
представить в виде выпуклой комбинации векторов ,1,,.
p
t
τ
τ
= K
Пусть вектор
x
представляется в виде выпуклой комбинации набора
векторов ,1,,
s
x
sN= K таких, что
00
() ( ), 1, , .
s
I
xIxs N⊆=K (28)
Можем считать, что первоначальный рассматриваемый набор состоит
из одного вектора, только из исходного вектора .
x
Покажем, что если вектор
s
x
не является решением системы (1) с
максимальным набором активных ограничений, то его можно представить
в виде выпуклой комбинации двух векторов
12
,yXyX∈∈таких, что
12
0000
() (), () ().
ss
xIyIxIy⊂⊂ (29)
Возьмем в качестве
1
y решение системы (1) с максимальным набором
активных ограничений, для которого
1
00
() ().
s
I
xIy⊂ (30)
Пусть
1
.
s
zx y=−
Из (30) следует, что
0
,0, ()
is
az i I x=∈
%
,
0.z
≠
По условиям теоремы направление
z не может быть рецессивным,
следовательно, существует положительная величина
(,)
s
x
z
λλ
=
такая, что для вектора
2 s
yx z
λ
=+
будет выполняться соотношение
2
00
() ()
s
I
xIy⊂ .
В набор
0
()
s
I
x
не входит номер (, )ixz . В набор
2
0
()
I
y
этот номер входит.
Итак, соотношения (29) доказаны.
Поскольку
1
2
,
,
s
s
yxz
yx z
λ
=−
=+
то
12
(1 )
s
x
yy
αα
=+−
при
/(1 ),
α
λλ
=+
т.е. вектор
s
x
является выпуклой комбинацией векторов
12
,.yy 
    Доказательство. Докажем, что любое решение x ∈ X можно
представить в виде выпуклой комбинации векторов pτ , τ = 1,K, t.
    Пусть вектор x представляется в виде выпуклой комбинации набора
векторов x s , s = 1, K, N таких, что
                          I 0 ( x) ⊆ I 0 ( x s ), s = 1, K, N .      (28)
     Можем считать, что первоначальный рассматриваемый набор состоит
из одного вектора, только из исходного вектора x.
     Покажем, что если вектор x s не является решением системы (1) с
максимальным набором активных ограничений, то его можно представить
в виде выпуклой комбинации двух векторов y1 ∈ X , y 2 ∈ X таких, что
                              I 0 ( x s ) ⊂ I 0 ( y1 ), I 0 ( x s ) ⊂ I 0 ( y 2 ).   (29)
     Возьмем в качестве y1 решение системы (1) с максимальным набором
активных ограничений, для которого
                         I 0 ( x s ) ⊂ I 0 ( y1 ).               (30)
     Пусть
                         z = x s − y1 .
Из (30) следует, что
                           a% i , z = 0, i ∈ I 0 ( x s ) ,
                            z ≠ 0.
По условиям теоремы направление z не может быть рецессивным,
следовательно, существует положительная величина
                        λ = λ ( xs , z)
такая, что для вектора
                         y2 = xs + λ z
будет выполняться соотношение
                        I0 ( xs ) ⊂ I0 ( y2 ) .
В набор I 0 ( x s ) не входит номер i ( x, z ) . В набор I 0 ( y 2 ) этот номер входит.
Итак, соотношения (29) доказаны.
    Поскольку
                              y1 = x s − z ,
                              y 2 = x s + λ z,
то
                              x s = α y1 + (1 − α ) y 2
при
                              α = λ /(1 + λ ),
т.е. вектор x s является выпуклой комбинацией векторов y1 , y 2 .




                                               34

Страницы