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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

26
Рангом системы линейных неравенств (1) будем называть
максимальное число линейно независимых строк матрицы
A
, т.е. векторов
i
a
%
. Это число обозначим r . Оно является рангом матрицы
A
и
размерностью линейного подпространства S
⊥
dimrS
⊥
= .
Следовательно,
dimnr S−= .
Ранг системы линейных неравенств не может превышать числа ее
переменных, т.е.
min{ , } .rmnn≤≤
В случае
rn=
имеем
систему линейных неравенств максимального ранга.
Отметим, что в случае системы линейных неравенств (1) полного ранга
,{0}
n
SRS
⊥
== и выполняется неравенство nm
≤
.
Если 0b
= , то система линейных неравенств (1) является однородной.
Если 0b
≠ , то (1) будет неоднородной системой линейных неравенств.
В общем случае, при любом значении вектора b , условие
0
A
x ≥ (4)
называется
однородной системой линейных неравенств, порождаемой
системой (1)
.
Множество решений системы (4) обозначим
{:0}
n
WxRAx=∈ ≥. (5)
Задание 1. Доказать, что множество решений однородной системы
линейных неравенств образует выпуклый конус.
Задание 2. Доказать, что
.XW X
+=
Это свойство означает, что прибавление к произвольному вектору
x
X∈ любого вектора yW∈ дает вектор
x
y
+
, также являющийся
решением системы (1).
Задание 3. Доказать, что определенное в (5) множество W является
конусом рецессивных направлений для множества решений системы
неравенств (1).
Для решения
x
X∈ множество номеров активных ограничений
обозначим
0
() {: , }.
i
i
xiaxb==
%
(6)
Множество номеров
неактивных ограничений обозначим
() {: , }.
i
i
I
xiaxb=>
%
Введем вектор
m
R
, зависящий от вектора
m
x
R
∈
() .rx Ax b
=
− (7) 
       Рангом системы линейных неравенств (1) будем называть
максимальное число линейно независимых строк матрицы A , т.е. векторов
a% i . Это число обозначим r . Оно является рангом матрицы A и
размерностью линейного подпространства S ⊥
                             r = dim S ⊥ .
Следовательно,
                             n − r = dim S .
       Ранг системы линейных неравенств не может превышать числа ее
переменных, т.е.
                             r ≤ min{m, n} ≤ n.
В случае
                             r=n
имеем систему линейных неравенств максимального ранга.
Отметим, что в случае системы линейных неравенств (1) полного ранга
S = R n , S ⊥ = {0} и выполняется неравенство n ≤ m .
       Если b = 0 , то система линейных неравенств (1) является однородной.
Если b ≠ 0 , то (1) будет неоднородной системой линейных неравенств.
       В общем случае, при любом значении вектора b , условие
                             Ax ≥ 0                                   (4)
называется однородной системой линейных неравенств, порождаемой
системой (1).
       Множество решений системы (4) обозначим
                             W = {x ∈ R n : Ax ≥ 0} .                 (5)
       Задание 1. Доказать, что множество решений однородной системы
линейных неравенств образует выпуклый конус.
       Задание 2. Доказать, что
                             X +W = X.
       Это свойство означает, что прибавление к произвольному вектору
x ∈ X любого вектора y ∈ W дает вектор x + y , также являющийся
решением системы (1).
       Задание 3. Доказать, что определенное в (5) множество W является
конусом рецессивных направлений для множества решений системы
неравенств (1).
       Для решения x ∈ X множество номеров активных ограничений
обозначим
                             I 0 ( x) = {i : a% i , x = bi }.         (6)
Множество номеров неактивных ограничений обозначим
                       I ( x) = {i : a% i , x > bi }.
    Введем вектор R m , зависящий от вектора x ∈ R m
                          r ( x) = Ax − b.                           (7)


                                    26

Страницы