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

дополнительных переменных к виду (30), т.е. у преобразованной системы
ограничения на линейные комбинации переменных будут иметь вид
системы однородных (с нулевым вектором в правой части) линейных
уравнений. Все переменные ограничены условием неотрицательности, а
одна из переменных имеет фиксированное единичное значение. Это
переменная при фиксированном векторе исходной системы неравенств. Из
полученной системы вида (30) с расширенным составом переменных и
некоторой специфической матрицей формируем альтернативную систему
вида (31). Затем путем преобразований, используя специфику имеющейся
матрицы, можем перейти к конкретной альтернативной системе.
    Выше это правило было использовано при доказательстве теоремы 14.
    Доказывается этим способом и теорема 15. Система (36) равносильна
системе неравенств
                          Ax − bxn+1 = 0 ,
                          x ≥ 0, xn+1 = 1.
    Альтернативной этой системе по теореме 13 будет следующая система
линейных неравенств
                          AΤ u ≥ 0, − b Τu = 1 .
    Данная система имеет решение в том и только том случае, если имеет
решение строго однородная система линейных неравенств (37). Тем самым
доказана теорема 15.
    Аналогично можно доказать теоремы 16 и 17.
    Таким же способом могут формулироваться и доказываться другие
теоремы об альтернативных неравенствах, в том числе внешне более
сложного вида. Приведем пример такой теоремы.
    Теорема 18. Для любых матриц A 1 , A2 размерности m × n1 и m × n 2
и любого вектора b ∈ R m либо разрешима система уравнений и неравенств
относительно векторов переменных x1 ∈ R n1 , x 2 ∈ R n2
                          A1 x1 + A2 x 2 = b , x1 ≥ 0 ,
либо разрешима следующая система                  уравнений          и   неравенств
относительно вектора переменных u ∈ R m
                          ( A1 )Τ u ≤ 0 , ( A2 )Τ u = 0 , b Τu = 1
    Задание 11. Доказать теорему 18.




                                     60