Линейное неравенство
Лине́йное нера́венство, неравенство вида
или вида
где , – любые действительные числа, .
В более широком смысле это неравенство вида
или вида
где – линейная (т. е. аддитивная и однородная) функция на действительном векторном пространстве ) со значениями из поля действительных чисел и . Дальнейшее обобщение понятия линейного неравенства получается, если вместо поля взять произвольное упорядоченное поле . На основе именно такого обобщения построена современная теория линейного неравенства (Черников. 1968).
К исследованию систем линейных неравенств сводится ряд важных вопросов аналитической механики, геометрии чисел, приближения функций. Весьма важные приложения находят результаты, относящиеся к системам линейных неравенств, в экономических исследованиях. В таких приложениях возникло, в частности, линейное программирование. К решению конкретных систем линейных неравенств сводятся многие практические задачи технико-экономического и планово-экономического характера, что в значительной мере определило современное направление исследований в области линейных неравенств.
На этом пути возник, в частности, основной принцип теории линейных неравенств – принцип граничных решений, установленный сначала (Черников. 1944) для конечных систем линейных неравенств в модульной форме, т. е. для систем вида
, где все , – в самом общем случае элементы поля комплексных чисел, а все – неотрицательные действительные числа, .
Принцип граничных решений заключается в следующем. В любой совместной системе вида (5) ранга можно выделить такую подсистему ранга из неравенств, что хотя бы одно решение последней, обращающее в равенства все её неравенства, удовлетворяет всем неравенствам системы (5), иначе говоря, является решением системы (5).
Принцип граничных решений распространён (Черников. 1953) на системы вида
, над полем (т. е. на системы с действительными ) в виде следующего, более сильного утверждения. В совместной системе (6) ранга можно выделить такую подсистему ранга из неравенств, что любое решение этой подсистемы, обращающее в равенства все её неравенства, удовлетворяет всем неравенствам (6) [для систем вида (6) это утверждение оказывается эквивалентным предыдущему утверждению]. Рангом системы линейных неравенств называется наибольшее число линейно независимых форм , входящих в её неравенства.
Принцип граничных решений распространён также на системы вида (6) над произвольным упорядоченным полем и даже на более общие системы, составленные из конечного числа линейных неравенств вида (3) над полем (Черников. 1966). Из этого принципа вытекает следующее условие совместности систем вида (6) над произвольным упорядоченным полем. Система (6) ранга тогда и только тогда совместна, когда в матрице её коэффициентов существует такой отличный от нуля минор порядка , что для определителей , , получаемых при окаймлении его с помощью -й строки этой матрицы и столбца элементов , все отношения неотрицательны. В случае совместной системы линейных уравнений , , такие отношения равны нулю для любого отличного от нуля минора порядка матрицы её коэффициентов.
Разработка теории линейных неравенств началась в конце 19 в. Одно из первых предложений общего характера, установленное в исследованиях (Minkowski. 1896 и Farkas. 1902), – теорема Минковского – Фаркаша является и теперь одной из ключевых теорем теории линейных неравенств: если все решения совместной системы (6) над полем удовлетворяют некоторому неравенству
, , то существуют такие неотрицательные числа , что имеет место тождественное относительно соотношение
В начале 20 в. в исследованиях Г. Ф. Вороного, посвящённых квадратичным формам целочисленных переменных, возникла одна из основных задач теории линейных неравенств – задача изучения свойств выпуклого многогранника, определяемого в пространстве решениями совместной конечной системы линейных неравенств отличного от нуля ранга. Основная теорема Вороного (Черников. 1968) выражает условия невырожденности такого многогранника или, иначе говоря, условия совместности конечной системы, составленной из неравенств вида (2). Задачей изучения многогранника решений систем вида (6) и результатами Г. Минковского (Minkowski. 1896) и Д. Фаркаша (Farkas. 1902) на долгое время определилось основное направление исследований по линейным неравенствам (Dines. 1933).
В дальнейшем выяснилось, что все результаты теории линейных неравенств, относящиеся к конечным системам неравенств вида (6), и в частности упоминавшиеся выше результаты Минковского, Фаркаша и Вороного, могут быть выведены из принципа граничных решений дискретными методами, т. е. без использования топологических свойств поля действительных чисел (или каких бы то ни было следствий этих свойств), причём дискретными методами доказан и сам принцип граничных решений (Черников. 1968). Поэтому в качестве основного поля при построении теории конечных систем линейных неравенств оказалось возможным вместо поля взять произвольное упорядоченное поле . Таким образом было подготовлено построение чисто алгебраической теории линейных неравенств, пользующейся только дискретными методами.
Продолжительное время теория линейных неравенств не имела эффективных методов для нахождения решения конечных систем линейных неравенств. Метод, состоящий в непосредственном использовании принципа граничных решений, малоэффективен. Эффективные методы для нахождения отдельных решений конечной системы линейных неравенств (в частности, симплексный метод) появились с возникновением линейного программирования.
В 1960–1965 гг. разработан т. н. метод свёртывания систем линейных неравенств, позволяющий по любой конечной системе, составленной в общем случае из неравенств вида (3) и (4), в частности из неравенств вида (1) и (2), и по заданному подпространству связанного с ней пространства находить некоторую новую конечную систему линейных неравенств, множество решений которой совпадает с той или иной проекцией множества решений рассматриваемой системы на взятое подпространство (Черников. 1968). Разработанный на этой основе алгоритм фундаментального свёртывания [особый алгоритм для последовательного исключения неизвестных из системы (6)] позволяет получать общие формулы, определяющие всё множество решений совместной системы вида (6). Метод свёртывания может быть использован в задачах линейного программирования для уменьшения числа неизвестных, а также для получения общих формул, определяющих всё множество оптимальных решений (Черников. 1968). Показано также (Черников. 1963), что с помощью метода свёртывания можно выделять максимальные совместные подсистемы в несовместной конечной системе линейных неравенств, составленной в общем случае из неравенств вида (3) и (4), в частности из неравенств вида (1) и (2), что позволяет использовать его при одном из подходов к решению задач распознавания образов (Красовский. 1973).
Среди бесконечных систем линейных неравенств выделен и изучен особый класс – полиэдрально замкнутые системы (Черников. 1968). В случае действительного векторного пространства полиэдрально замкнутые системы определяются как бесконечные системы вида с топологически замкнутым в пространстве сопряжённым конусом, т. е. конусом, порождённым элементами
где – нулевой элемент пространства . Бесконечные полиэдрально замкнутые системы линейных неравенств сохраняют ряд свойств конечных систем линейных неравенств, и, в частности, для таких систем справедлива теорема Минковского – Фаркаша. Полиэдрально замкнутые системы линейных неравенств используются в теории приближения функций, в выпуклом программировании, в теории управления (Красовский. 1973).