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

условию (1).
    Геометрически это означает, что полиэдр X , задаваемый системой
неравенств (2), располагается в положительном полупространстве,
образуемом гиперплоскостью c Τ x = d (рис. 7).

                                        c
                         X



                      H +
                             -
Рис. 7. Полиэдр X , состоящий из множества решений системы
неравенств (2) и лежащий в положительном полупространстве
(обозначим это полупространство H cd+ ), задаваемом неравенством-
следствием (1).
    Сначала рассмотрим наиболее простой для доказательства случай,
который хорошо иллюстрирует технику построения и обоснования
критериев для идентификации избыточных неравенств.
    Теорема 1 (случай однородных неравенств). Для того чтобы
неравенство
                             cΤ x > 0                               (3)
являлось следствием системы
                             Ax ≥ 0,                                (4)
необходимо и достаточно существование вектора u ∈ R m такого, что
                             A Τ u = c, u ≥ 0 .                     (5)
    Доказательство. Неравенство (3) не является следствием системы (4)
в том и только том случае, если имеет решения следующая система
линейных неравенств:
                             Ax ≥ 0,        − cΤ x > 0 .
     По теореме 3.15 (Фаркаша), в которой поменяли местами матрицы A
   T
и A , а вектор x заменили на вектор u , данная система не имеет решения
в том и только том случае, если имеет решение система (5).
     Теорема 1 доказана.
     Задание1 . Доказать, что из теоремы 1 следует теорема Фаркаша
3.15.
     Теорема 2 (Минковского-Фаркаша, общий случай). Пусть система
(2) совместна. Неравенство (1) будет следствием системы (2), если при
некотором u ∈ R m


                                        64