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

                              A Τ u = c, b Τ u ≥ d , u ≥ 0 .            (6)
    Доказательство. Если и только если неравенство (1) не является
следствием системы (2), то при некотором x ∈ R n
                              Ax ≥ b, (c, x) < d .                     (7)
    А это возможно в том и только том случае, если разрешима
следующая система строго однородных линейных неравенств с (n+1)-ой
переменной:
                              Ax − bxn+1 ≥ 0 ,                          (8)
                              − c Τ x + dxn+1 > 0, xn+1 > 0 ,           (9)
где x – вектор R n , xn+1 – дополнительная переменная. Отметим, что в (9)
оба неравенства заданы в строгой форме.
    Для того чтобы система (8), (9) имела решение, необходимо и
достаточно иметь решения для двух систем линейных неравенств,
являющихся ослаблением системы (8), (9) путем замены одного из строгих
неравенств в (9) на нестрогое. Итак, первая система включает в себя
условие (8) и неравенства
                              − c Τ x + dxn+1 > 0, xn +1 ≥ 0 .         (10)
    Вторая система включает условие (8) и неравенства
                              − c Τ x + dxn+1 ≥ 0, xn+1 > 0 .          (11)
     Решение системы (8), (9) будет решением обеих систем (8), (10) и (8),
(11). Наоборот, имея решение систем (8), (10) и (8), (11), суммируя их
покомпонентно, получим решение системы (8), (9).
     Альтернативной к (8), (10) по теореме Фаркаша 3.15 будет следующая
система линейных неравенств относительно вектора переменных u ∈ R m и
двух дополнительных переменных um+1 и um+2:
                   AT u − cum +1 = 0, − bT u + dum +1 + um + 2 = 0 ,   (12)
                   u ≥ 0, um +1 > 0, um + 2 ≥ 0 .                      (13)
    Альтернативной к (8), (11) по той же теореме 3.15 будет система с
таким же составом переменных включающая условия (12) и неравенства
                              u ≥ 0, u m+1 ≥ 0, u m+ 2 > 0 .           (14)
     Итак, неравенство (1) будет следствием системы (2), если и только
если разрешима система неравенств (12), (13) или (12), (14). Подчеркнем,
для утверждения о наличии следствия достаточно разрешимости любой из
этих систем. Чтобы утверждать отсутствие следствия, необходимо, чтобы
обе системы не имели решения.


                                        65