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

определения несовместности ограничений нет необходимости отдельно
осуществлять поиск решения альтернативной системы от поиска решения
исходной системы. В любом из известных алгоритмов поиска решения
исходной системы в процессе улучшения решения (минимизации невязок,
т.е. некоторых измерителей степени нарушения ограничений) можно
определять показатели, являющиеся приближениями к множителям
Лагранжа ограничений систем. На основе этих показателей можно
осуществлять проверку совместности альтернативной системы линейных
неравенств. Если на очередной итерации получим допустимое решение
альтернативной системы, то можем констатировать несовместность
исходной системы. Более подробно эта общая идея будет
проиллюстрирована на конкретных алгоритмах в главе 6.

  4.2 Критерий для выявления избыточных линейных неравенств
     У систем линейных неравенств могут быть отдельные неравенства,
исключение которых из системы не влияет на множество решений. Во
многих случаях полезно уметь выявлять такие неравенства с тем, чтобы
упрощать путем их исключения рассматриваемую систему. На базе теорем
об альтернативных неравенствах можно строить конструктивные критерии
для выявления избыточных неравенств. Ниже приводятся два критерия:
сначала для однородной системы неравенств, затем для общего случая.
     Здесь теоремы об избыточных неравенствах будут доказаны как
следствия из теорем об альтернативных системах линейных неравенств
главы 3. Следует отметить, что теоремы о линейных неравенствах-
следствиях равносильны теоремам об альтернативных системах линейных
неравенств. Можно было, как это сделано в [15], дать независимое
доказательство утверждений о неравенствах-следствиях. На базе теорем о
неравенствах-следствиях можно получить теоремы об альтернативных
системах линейных неравенств.
     Ниже утверждение о неравенствах-следствиях, следуя Черникову и
Еремину, названо теоремой Минковского-Фаркаша. Этим подчеркивается,
что фундаментальный результат в теории линейных неравенств был
опубликован ранее Фаркаша в работах 1886 г. известного математика
Минковского.
     Считаем заданными матрицу A размерности m × n , векторы b ∈ R m ,
c ∈ R n и вещественную константу d.
     Определение. Линейное неравенство
                          cΤ x ≥ d                                (1)
назовем следствием системы линейных неравенств
                          Ax≥ b ,                                 (2)
если любой вектор x ∈ R n , удовлетворяющий системе (2), удовлетворяет


                                     63