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

UptoLike

25
Глава 2. Строение полиэдров
В данной главе исследуется структура множества решений систем
линейных неравенств. Сначала, в разделе 2.2 рассмотрим случай
ограниченного множества решений, когда конус рецессивных направлений
состоит только из нулевого вектора. В этом случае, как будет доказано,
множество решений является политопом. Затем рассмотрим случай, когда
конус рецессивных направлений является конечным многогранным
конусом. Наконец, в разделе
2.3 будет рассмотрен общий случай, для
которого, как будет доказано, множество решений системы линейных
неравенств является суммой трех множеств: политопа, конечного
многогранного конуса и линейного подпространства.
2.1 Исходные определения
Объектом изучения в данной главе будет система линейных
неравенств
A
xb . (1)
Заданными являются матрица
A
размерности mn
×
с коэффициентами
, 1,,, 1,,
ij
ai m j n==KK и вектор
m
bR
. Искомые переменные
составляют вектор
n
x
R .
Множество решений системы (1) обозначим
{:}
n
XxRAxb=∈ .
Это множество выше было названо политопом.
В данной главе, не оговаривая особо, будем считать, что система (1)
совместная, т.е.
0X ≠/.
Свойства несовместных систем, способы их идентификации будут
изучаться позже, в частности, в главах 4 и 6.
Пусть
i
a
%
вектор
n
R
, образованный из коэффициентов i -ой строки
матрицы
A
, 1,,, 1,,.
i
jij
aaj ni m== =
%
KK
Тогда систему (1) можно записать в таком виде:
,,1,,.
i
i
ax b i m≥=
%
K
Далее, не оговаривая особо, будем считать, что все строки матрицы
A
ненулевые
0, 1, , .
i
ai m≠=
%
K
Определим взаимно ортогональные подпространстваобраз матрицы
T
A
и нуль-пространство
A
{:}
Tm
SxAuuR
== , (2)
{:0}
n
SxRAx=∈ =. (3)
Глава 2. Строение полиэдров
    В данной главе исследуется структура множества решений систем
линейных неравенств. Сначала, в разделе 2.2 рассмотрим случай
ограниченного множества решений, когда конус рецессивных направлений
состоит только из нулевого вектора. В этом случае, как будет доказано,
множество решений является политопом. Затем рассмотрим случай, когда
конус рецессивных направлений является конечным многогранным
конусом. Наконец, в разделе 2.3 будет рассмотрен общий случай, для
которого, как будет доказано, множество решений системы линейных
неравенств является суммой трех множеств: политопа, конечного
многогранного конуса и линейного подпространства.

                        2.1 Исходные определения
        Объектом изучения в данной главе будет система линейных
неравенств
                               Ax ≥ b .                         (1)
Заданными являются матрица A размерности m × n с коэффициентами
aij , i = 1, K, m, j = 1, K, n и вектор b ∈ R m . Искомые переменные
составляют вектор x ∈ R n .
    Множество решений системы (1) обозначим
                             X = {x ∈ R n : Ax ≥ b} .
Это множество выше было названо политопом.
    В данной главе, не оговаривая особо, будем считать, что система (1)
совместная, т.е.
                             X ≠ 0/ .
Свойства несовместных систем, способы их идентификации будут
изучаться позже, в частности, в главах 4 и 6.
    Пусть a% i – вектор R n , образованный из коэффициентов i -ой строки
матрицы A
                            a% ij = aij , j = 1, K, n, i = 1, K, m.
Тогда систему (1) можно записать в таком виде:
                              a% i , x ≥ bi , i = 1,K, m.
    Далее, не оговаривая особо, будем считать, что все строки матрицы A
ненулевые
                         a% i ≠ 0, i = 1,K, m.
    Определим взаимно ортогональные подпространства – образ матрицы
  T
A и нуль-пространство A
                         S ⊥ = {x = AT u :u ∈ R m } ,               (2)
                         S = {x ∈ R n : Ax = 0} .                  (3)

                                     25