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

    Обозначим pτ , τ = 1,K, t – множество решений системы (1) с
максимальными наборами активных ограничений, где t – общее число
таких решений для рассматриваемого здесь случая r = n.
    Лемма 4. Решение с максимальным набором активных ограничений
системы линейных неравенств максимального ранга не может быть
представлено в виде выпуклой комбинации двух других решений данной
системы.
    Доказательство. Предположим, что при некоторых x ∈ X , y ∈ X
                    pτ = λ x + (1 − λ ) y,                       (26)

где
                         λ ∈ (0, 1),
 pτ – одно из решений системы (1) с максимальным набором активных
ограничений.
      В силу леммы 1,
                          I 0 ( pτ ) ⊆ I 0 ( x).
Выполнение в строгой форме этого соотношения противоречит тому, что
 pτ является решением с максимальным набором активных ограничений.
Выполнение этого соотношения в виде равенства невозможно в силу
леммы 2. Итак, получили что представление (26) невозможно.
      Лемма 4 доказана.
      Будем говорить, что система линейных неравенств не имеет
рецессивных ненулевых направлений, если их не имеет множество
решений данной системы, т.е. если порождаемая данной системой
однородная система линейных неравенств имеет только тривиальное
решение
                          W = {0}.                                (27)
      Лемма 5. Если система (1) не имеет ненулевых рецессивных
направлений, то она является системой максимального ранга.
      Доказательство. Из данного в разделе 2.1 определения множеств W
    ⊥
и S следует, что
                          S ⊂W.
Условие (27) означает, что
                          S = {0},
следовательно, r = n.
      Лемма 5 доказана.
      Теорема 1. Пусть система линейных неравенств (1) не имеет
ненулевых рецессивных направлений. Тогда множество решений этой
системы является политопом, образуемым выпуклой оболочкой решений
системы с максимальными наборами активных ограничений.



                                       33