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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

59
0≥
Τ
u
A
,
0
<
Τ
ub
. (37)
Теорема 15 имеет ясный геометрический смысл, иллюстрирующий
общий принцип “работы” теорем об альтернативах: если система (36)
несовместна, т.е. вектор b не является линейной комбинацией столбцов
матрицы
A
с неотрицательными коэффициентами, то существует такая
проходящая через нуль гиперплоскость
T
uv в пространстве
m
R
, что
векторы-столбцы матрицы
A
оказываются в положительном
полупространстве, образованном этой гиперплоскостью, а вектор b – во
внутренности отрицательного полупространства (рис. 6).
Рис. 6. Геометрическая иллюстрация леммы Фаркаша. Здесь векторы
1
,...,
n
aa
(векторы-столбцы матрицы
A
) находятся в полупространстве
{:0}
mT
HvRuv
+
=∈ >, а вектор b в полупространстве
{:0}
mT
HvRuv
−
=∈ <.
Теорема 16 (Гейла). Либо существует вектор
n
x
R
∈
такой, что
A
xb≥ ,
либо существует вектор
m
uR∈ такой, что
0
u
Τ
=
, 0u ≥ , 1bu
Τ
=
.
Задание 9. Доказать с помощью теоремы 13 теорему Гейла.
Теорема 17. Либо имеет решение система
b
Ax
≤
, 0≥
x
,
либо разрешима система
0≥
Τ
u
A
, 0≥u,
0
<
Τ
ub
.
Задание 10. Доказать теорему 17.
Таким образом, можно сформулировать следующие правила
формирования альтернативной системы к данной системе неоднородных
линейных неравенств.
1. Сначала исходную систему преобразуем путем введения
0
b
2
a
4
a
3
a
0
T
A
u =
+
-
1
a
                          AΤu ≥ 0 , b Τu < 0 .                           (37)
    Теорема 15 имеет ясный геометрический смысл, иллюстрирующий
общий принцип “работы” теорем об альтернативах: если система (36)
несовместна, т.е. вектор b не является линейной комбинацией столбцов
матрицы A с неотрицательными коэффициентами, то существует такая
проходящая через нуль гиперплоскость u T v в пространстве R m , что
векторы-столбцы     матрицы     A   оказываются    в   положительном
полупространстве, образованном этой гиперплоскостью, а вектор b – во
внутренности отрицательного полупространства (рис. 6).

                              a1
                                          a2

                                                         a3     a4
                     b

                                     0
                                                    +
                                                    -
                                                              AT u = 0
Рис. 6. Геометрическая иллюстрация леммы Фаркаша. Здесь векторы
a1,..., a n (векторы-столбцы матрицы A ) находятся в полупространстве
H + = {v ∈ R m : u T v > 0} , а вектор     b    в    полупространстве
H − = {v ∈ R m : u T v < 0} .
    Теорема 16 (Гейла). Либо существует вектор x ∈ R n такой, что
                          Ax ≥ b ,
либо существует вектор u ∈ R m такой, что
                          AΤu = 0 , u ≥ 0 , b Τu = 1 .
    Задание 9. Доказать с помощью теоремы 13 теорему Гейла.
    Теорема 17. Либо имеет решение система
                          Ax ≤ b , x ≥ 0 ,
либо разрешима система
                          AΤu ≥ 0 , u ≥ 0 , b Τu < 0 .
    Задание 10. Доказать теорему 17.
    Таким образом, можно сформулировать следующие правила
формирования альтернативной системы к данной системе неоднородных
линейных неравенств.
    1. Сначала исходную систему преобразуем путем введения


                                     59

Страницы