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

либо имеется вектор u ∈ R m такой, что
                           AΤ u ≥ 0 , ( AΤu ) k = 1 .            (31)
    Приводимое ниже утверждение иногда используют в качестве одного
из этапов доказательства теорем об альтернативных системах линейных
неравенств. Здесь мы его докажем как следствие теоремы 13. В
формулируемых далее теоремах 15 – 18 считаются заданными матрица A
размерности m × n и вектор b ∈ R m .
    Теорема 14 (Фредгольма). Либо существует вектор x ∈ R n , такой
что
                           Ax = b ,                              (32)
либо существует вектор u ∈ R m такой, что
                           AΤu = 0, b Τu ≠ 0 .                   (33)
     Доказательство. Приведем доказательство этого утверждения на базе
теоремы 13, которое демонстрирует приемы, полезные для построения и
доказательства других формулировок теорем об альтернативных системах
неравенств для неоднородных случаев.
    Представим (32) в виде системы линейных уравнений и неравенств от
2n + 1 -ой переменной, в качестве которых выступают компоненты
векторов x1 , x 2 из R n и величина xn +1

                           Ax1 − Ax 2 − xn +1b = 0,
                                                                 (34)
                            1         2
                          x ≥ 0, x ≥ 0, xn +1 = 1.
    Систему (33) представим в виде условия из 2n неравенств и одного
равенства относительно компонент вектора u из R m . При этом вместо
условия bΤu ≠ 0 можно зафиксировать какое-то конкретное ненулевое
значение bΤu . Имеем систему
                           AΤu ≥ 0 , − AΤu ≥ 0 , −bΤu = 1.       (35)
    Утверждение об альтернативности систем (32) и (33) равносильно
утверждению об альтернативности систем (34) и (35). Применим теорему
13 к расширенной матрице A% = [ A, − A, b] размерности m × (2n + 1) .
Получаем требуемое: одна и только одна из систем (34) или (35) имеет
решение.
    Теорема 14 доказана.
    Теорема 15 (лемма Фаркаша). Либо имеет решение система
                           Ax = b , x ≥ 0 ,                      (36)
либо разрешима система


                                      58