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

                            ( x + AΤ u ) > 0 .

    Поиск решения с минимальным набором активных ограничений.
Для нахождения таких решений могут использоваться те же алгоритмы,
что применяются для поиска любого решения систем линейных
неравенств. Рассмотрим систему линейных неравенств с ( n + m − 1 )-й
переменной:
                             AΤu ≥ 0, b Τu = 0 ,                        (23)
                             Ax − xn+1b = 0, x ≥ 0, xn+1 ≥ 1 ,          (24)
                            ( x j + ( AΤu ) j ) ≥ 1,   j = 1,..., n .   (25)
    Заметим, если и только если система (21) совместная, то данная
система имеет решение. Пусть векторы u~ ∈ R m , ~x ∈ R n , и величина ~
                                                                      xn+1 ,
являются решением системы (23) – (25). Тогда вектор
                                 1
                             x= ~ ~  x
                                xn+1
будет решением системы (21) с минимальным набором активных
ограничений, вектор u~ будет решением системы (22) с минимальным
набором активных ограничений.
    Конечно, поиск относительно внутренней точки множества решений
системы линейных неравенств (21) путем решения системы (23) – (25)
выглядит несколько громоздко. У системы (23) – (25) значительно больше
переменных и уравнений, чем у исходной системы (21). Следует отметить,
что имеются такие алгоритмы решения систем линейных неравенств,
которые всегда приводят к решениям с минимальным набором активных
ограничений. Это алгоритмы внутренних точек.

Задания и упражнения к главе 4

1. Пусть задана система однородных линейных неравенств
   2 x1 − 8 x2 = 0     (1)
   x1 + x2 = 0         (2) .
   x1 ≥ 0, x2 > 0 (3), (4)
 Показать справедливость теоремы 3.8 для данной системы.
2. Проверить, имеют ли уравнения
   2 x1 − 8 x2 = 0 (1)
    x1 + x2 = 0 (2)
 полуположительные решения (применить теорему Гордана).
3. Показать, используя теорему Штимке, что система

                                        72