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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

32
Если
,0, (),
i
az i Ix=∈
%
(25)
то zS
⊥
∈ . А это противоречит (19). Следовательно, существует ()iIx∈
,0.
i
az
≠
%
Если для всех ()iIx∈
,0,
i
az≥
%
то заменим вектор
z на вектор z
−
.
Итак, можем считать, что для данного
z
выполняются условия (23),
(24) и при этом
() 0.
L
z
≠
/
Следовательно,
(, ) 0.
x
z
λ
>
Для вектора
(, )
x
xxzz
λ
=+
%
будет выполняться соотношение (22). Действительно, в силу (24)
00
() ().
I
xIx⊆
%
При этом номер (, )ixz будет входить в множество
0
()
x
%
и не будет
входить в множество
0
().
I
x
Лемма 2 доказана.
Лемма 3. Если (1) – система линейных неравенств максимального
ранга, то число ее решений с максимальными набороми активных
ограничений конечно.
Доказательство. Для каждого решения
x
X
∈
множество номеров
ограничений {1, , }mK разбивается на два непересекающихся
подмножества
0
(), ().
I
xIx Согласно лемме 2 у решений с максимальными
наборами активных ограничений эти разбиения должны быть различными.
Число различных разбиений множества из m элементов на два
подмножества конечно и равно
2
m
.
Лемма 3 доказана.
Задание 8. Доказать, что у каждого решения с максимальным
набором активных ограничений системы линейных неравенств (1)
максимального ранга число активных ограничений не меньше n.
Задание 9. Доказать, что число решений с максимальным набором
активных ограничений системы линейных неравенств (1) максимального
ранга не превышает числа сочетаний из m элементов по ,n
!
.
!( )!
n
m
m
C
nm n
=
−
    Если
                               a% i , z = 0, i ∈ I ( x),                (25)
то z ∈ S ⊥ . А это противоречит (19). Следовательно, существует i ∈ I ( x)
                               a% i , z ≠ 0.
    Если для всех i ∈ I ( x)
                               a% i , z ≥ 0,
то заменим вектор z на вектор − z .
     Итак, можем считать, что для данного z выполняются условия (23),
(24) и при этом
                               L( z ) ≠ 0.
                                         /
Следовательно,
                              λ ( x, z ) > 0.
     Для вектора
                               x% = x + λ ( x, z ) z
будет выполняться соотношение (22). Действительно, в силу (24)
                               I 0 ( x) ⊆ I 0 ( x% ).
При этом номер i ( x, z ) будет входить в множество I 0 ( x% ) и не будет
входить в множество I 0 ( x).
     Лемма 2 доказана.
     Лемма 3. Если (1) – система линейных неравенств максимального
ранга, то число ее решений с максимальными набороми активных
ограничений конечно.
     Доказательство. Для каждого решения x ∈ X множество номеров
ограничений     {1, K, m}           разбивается на два непересекающихся
подмножества I 0 ( x), I ( x). Согласно лемме 2 у решений с максимальными
наборами активных ограничений эти разбиения должны быть различными.
Число различных разбиений множества из m элементов на два
подмножества конечно и равно 2m .
     Лемма 3 доказана.
     Задание 8. Доказать, что у каждого решения с максимальным
набором активных ограничений системы линейных неравенств (1)
максимального ранга число активных ограничений не меньше n .
     Задание 9. Доказать, что число решений с максимальным набором
активных ограничений системы линейных неравенств (1) максимального
ранга не превышает числа сочетаний из m элементов по n,
                                            m!
                              Cmn =                   .
                                        n!(m − n)!




                                               32

Страницы