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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

31
Рис. 3. Направление
1
z приводит к решению на границе области
допустимых решений системы линейных неравенств (16 ). Направление
2
z
является рецессивным.
2.3 Структура множества решений системы линейных неравенств
при отсутствии рецессивных направлений
В данном и следующем параграфах рассмотрим свойства множества
решений системы линейных неравенств (1), когда ранг системы совпадает
с числом переменных, т.е. когда
.rn=
В этом случае
,{0},
n
SR S
⊥
== (19)
где S и S
⊥
– линейные подпространства, введенные в (2), (3).
Лемма 2. Если (1) – система линейных неравенств максимального
ранга, то не существует двух разных решений системы с максимальными
наборами активных ограничений, у которых наборы активных
ограничений совпадают.
Доказательство. Пусть имеется два разных решения ,
x
Xy X∈=
x
y≠ (20)
с одинаковыми наборами активных ограничений
00
() ().
I
xIy
=
(21)
Требуется доказать, что векторы
x
и y не могут быть решениями с
максимальными набором активных ограничений. Докажем, что существует
вектор
x
X∈
%
, для которого
00
() ().
I
xIx⊂
%
(22)
Введем вектор
.zyx=−
Из (20), (21) следует
0,z ≠ (23)
0
,0, ().
i
az i Ix=∈
%
(24)
11
(, )
x
xz z
λ
+
1
z
2
z
x
1
2
x
                 x2


                                          1   1
                                                       z2
                              x + λ ( x, z ) z    z1
                                                       x



                                                            x1
Рис. 3. Направление z1 приводит к решению на границе области
допустимых решений системы линейных неравенств (16 ). Направление z 2
является рецессивным.
    2.3 Структура множества решений системы линейных неравенств
                  при отсутствии рецессивных направлений
     В данном и следующем параграфах рассмотрим свойства множества
решений системы линейных неравенств (1), когда ранг системы совпадает
с числом переменных, т.е. когда
                           r = n.
В этом случае
                           S ⊥ = R n , S = {0},                   (19)
           ⊥
где S и S – линейные подпространства, введенные в (2), (3).
     Лемма 2. Если (1) – система линейных неравенств максимального
ранга, то не существует двух разных решений системы с максимальными
наборами активных ограничений, у которых наборы активных
ограничений совпадают.
     Доказательство. Пусть имеется два разных решения x ∈ X , y = X
                           x≠ y                                   (20)
с одинаковыми наборами активных ограничений
                           I 0 ( x) = I 0 ( y ).                  (21)
Требуется доказать, что векторы x и y не могут быть решениями с
максимальными набором активных ограничений. Докажем, что существует
вектор x% ∈ X , для которого
                           I 0 ( x) ⊂ I 0 ( x% ).                 (22)
     Введем вектор
                           z = y − x.
Из (20), (21) следует
                           z ≠ 0,                                 (23)
                             a% i , z = 0, i ∈ I 0 ( x).          (24)


                                   31

Страницы