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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

38
Требуется доказать, что для любого
x
W
∈
существуют ,0vV
β
∈≥
%
такие,
что
.
x
v
β
=
Если 0
x
= , то данное утверждение справедливо при 0
β
= и любом
.vV∈
%
Пусть 0.
x
≠ Поскольку
x
W
∈
, то
0
A
x ≥
и из условия rn= следует, что
,0
i
ax>
%
для некоторого номера {1, , } .im= K Следовательно, величина
1
,
m
ax
β
+
=−
%
– положительная.
При
1
vx
=
будут выполняться соотношения
1
0,
(,)1,
m
A
v
av
+
≥
=
−
%
т.е. данный вектор v находится в V
%
и для него справедливо равенство (33)
при
0.
β
>
Лемма 6 доказана.
Теорема 2. Пусть (1) – система линейных неравенств максимального
ранга, ,1,,
p
t
τ
τ
= K – решения этой системы с максимальным набором
активных ограничений, ,0,1,,
l
vl k= K – множество направлений,
образующих конечный многогранный конус рецессивных направлений для
рассматриваемой системы линейных неравенств. Тогда любое решение
системы (1) представимо в виде суммы выпуклой комбинации векторов
,1,,
p
t
τ
τ
= K и конусной комбинации векторов ,1,,
l
vl k= K
{ , 1, , } { , 0,1, , }.
l
XCop t Conevl k
τ
τ
==+ =KK
Доказательство. По лемме 6
{, 1, ,}.
l
W Cone v l k==K
Из выпуклости X следует, что
{, 1, ,} .Co p t W X
τ
τ
=+⊆K
Требуется доказать справедливость обратного включения.
Пусть .
x
X∈ Необходимо доказать, что существует вектор zW
∈
,
величины
0, 1, ,
i
it
λ
≥=K такие что
1
i
λ
=
∑
,
при которых 
Требуется доказать, что для любого x ∈W существуют v ∈V% , β ≥ 0 такие,
что
                          x = β v.
     Если x = 0 , то данное утверждение справедливо при β = 0 и любом
v ∈V% .
     Пусть x ≠ 0. Поскольку x ∈W , то
                          Ax ≥ 0
и из условия r = n следует, что
                           a% i , x > 0
для некоторого номера i = {1,K, m}. Следовательно, величина
                         β = − a% m+1 , x
– положительная.
    При
                              1
                         v=       x
                              β
будут выполняться соотношения
                        Av ≥ 0,
                            (a% m+1 , v) = −1,
т.е. данный вектор v находится в V% и для него справедливо равенство (33)
при β > 0.
      Лемма 6 доказана.
      Теорема 2. Пусть (1) – система линейных неравенств максимального
ранга, pτ , τ = 1, K, t – решения этой системы с максимальным набором
активных ограничений, vl , l = 0, 1, K, k – множество направлений,
образующих конечный многогранный конус рецессивных направлений для
рассматриваемой системы линейных неравенств. Тогда любое решение
системы (1) представимо в виде суммы выпуклой комбинации векторов
 pτ , τ = 1, K, t и конусной комбинации векторов vl , l = 1,K, k
                  X = Co{ pτ , τ = 1, K, t} + Cone{vl , l = 0,1,K, k}.
    Доказательство. По лемме 6
                           W = Cone{vl , l =1,K, k}.
Из выпуклости X следует, что
                            Co{ pτ , τ = 1, K, t} + W ⊆ X .
Требуется доказать справедливость обратного включения.
    Пусть x ∈ X . Необходимо доказать, что существует вектор z ∈W ,
величины λi ≥ 0, i = 1,K, t такие что
                         ∑λ   i   = 1,
при которых

                                         38

Страницы