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

Глава 4. Три области приложения теорем об альтернативных
системах линейных неравенств

    В данной главе рассмотрим три области применения теорем об
альтернативах:
    – для конструирования критериев определения несовместности систем
линейных уравнений и неравенств;
    – для идентификации избыточных неравенств;
    – для выявления решений с минимальным набором активных
ограничений.
4.1 Критерий     несовместности      ограничений   систем   линейных
неравенств
    Возможен случай, когда данная система линейных неравенств не
имеет решения – ограничения системы являются противоречивыми или,
как еще говорят, несовместными. Иногда этот случай несложно выявить.
Например, можно доказать графически, что следующая система с двумя
неизвестными не имеет решения
                          x1 + x2 = −1
                          x1 ≥ 0, x2 ≥ 0.
    Действительно, прямая на плоскости, состоящая из точек,
удовлетворяющих первому условию, не пересекает неотрицательный
ортант.
    Для систем, состоящих из многих ограничений и переменных, как
правило, априори не очевидно имеют они решения или нет. В любом
случае, поскольку поиск решения систем линейных неравенств
осуществляется на ЭВМ, необходимо иметь четкий алгоритмический
критерий для выявления случая несовместности ограничений систем
равенств и неравенств.
    Этот критерий дают теоремы об альтернативных системах линейных
неравенств. Для того чтобы доказательно утверждать о противоречивости
ограничений данной системы достаточно установить наличие решения
альтернативной системы линейных неравенств. Так, согласно теореме
Фаркаша, для доказательства несовместности приведенной выше системы
достаточно найти какое-либо решение системы неравенств относительно
одной переменной
                          u ≥ 0, u ≥ 0, − u < 0.
Очевидно, что ее решением будет любое положительное число.
    Для того чтобы воспользоваться теоремами об альтернативных
системах линейных неравенств в качестве конструктивного критерия


                                   62