ЛИНЕЙНОЕ НЕРАВЕНСТВО

неравенство вида

или вида

где а- любые действительные числа, В более широком смысле - это неравенство вида

или вида

где f(x) - линейная (т. е. аддитивная и однородная) функция на действительном векторном пространстве со значениями из поля действительных чисел и Дальнейшее обобщение понятия Л. н. получается, если вместо поля взять произвольное упорядоченное поле Р. На основе именно такого обобщения построена современная теория Л. н. (см. [1]).

К исследованию систем Л. н. сводится ряд важных вопросов аналитич. механики, геометрии чисел, приближения функций. Весьма важные приложения находят результаты, относящиеся к системам Л. н., в экономич. исследованиях. В таких приложениях возникло, в частности, линейное программирование. К решению конкретных систем Л. н. сводятся многие практич. задачи технико-экономич. и планово-экономич. характера, что в значительной мере определило современное направление исследований в области Л. н.

На атом пути возник, в частности, основной принцип теории Л. н.- принцип граничных решений, установленный сначала (см. [4]) для конечных систем Л. н. в модульной форме, т. е. для систем вида

j=1, 2, . . ., т, где все - в самом общем случае элементы поля комплексных чисел, а все d_j- неотрицательные действительные числа, j=1, 2, . . ., т.

Принцип граничных решений заключается в следующем. В любой совместной системе вида (5) ранга r>0 можно выделить такую подсистему ранга г из г неравенств, что хотя бы одно решение последней, обращающее в равенства все ее неравенства,

удовлетворяет всем неравенствам системы (5), иначе говоря, является решением системы (5).

Принцип граничных решений был распространен (см. [5]) на системы вида

j=1,2,..., т, над полем (т. е. на системы с действительными ) в виде следующего более сильного утверждения. В совместной системе (6) ранга r>0 можно выделить такую подсистему ранга r из r неравенств, что любое решение этой подсистемы, обращающее в равенства все ее неравенства, удовлетворяет всем неравенствам (6) (для систем вида (6) это утверждение оказывается эквивалентным предыдущему утверждению). Рангом системы линейных неравенств наз. наибольшее число линейно независимых форм входящих в ее неравенства.

Принцип граничных решений был распространен также на системы вида (6) над произвольным упорядоченным полем Ри даже на более общие системы, составленные из конечного числа Л. н. вида (3) над полем Р(см. [6]). Из этого принципа вытекает следующее условие совместности систем вида (6) над произвольным упорядоченным полем. Система (6) ранга r>0 тогда и только тогда совместна, когда в матрице ее коэффициентов существует такой отличный от нуля минор порядка r, что для определителей 2, . . ., т, получаемых при окаймлении его с помощью j-й строки этой матрицы и столбца элементов а _j, все отношения неотрицательны. В случае совместной системы линейных уравнений j=1, 2, . . ., т, такие отношения равны нулю для любого отличного от нуля минора порядка г матрицы ее коэффициентов.

Разработка теории Л. н. началась в конце 19 в. Одно из первых предложений общего характера, установленное в исследованиях [3] и [9], - теорема Минковского - Фаркаша является и теперь одной из ключевых теорем теории Л. н.: если все решения совместной системы (6) над полем удовлетворяют нек-рому неравенству

то существуют такие неотрицательные числа что имеет место тождественное относительно x=(x₁,..., х _n).соотношение

В начале 20 в. в исследованиях Г. Ф. Вороного, посвященных квадратичным формам целочисленных переменных, возникла одна из основных задач теории Л. н.- задача изучения свойств выпуклого многогранника, определяемого в пространстве решениями совместной конечной системы Л. н. отличного от нуля ранга. Основная теорема Вороного (см. [1]) выражает условия невырожденности такого многогранника или, иначе говоря, условия совместности конечной системы, составленной из неравенств вида (2). Задачей изучения многогранника решений систем вида (6) и результатами Г. Минковского [3] и Ж. Фаркаша [9] на долгое время определилось основное направление исследований по линейным неравенствам (см. [10]).

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

свойств поля действительных чисел (или каких бы то ни было следствий этих свойств), причем дискретными методами был доказан и сам принцип граничных решений (см. [1] и [6]). Поэтому в качестве основного поля при построении теории конечных систем Л. н. оказалось возможным вместо поля взять произвольное упорядоченное поле Р. Таким образом, было подготовлено построение чисто алгебраич. теории Л. н., пользующейся только дискретными методами.

Продолжительное время теория Л. н. не имела эффективных методов для нахождения решения конечных систем Л. н. Метод, состоящий в непосредственном использовании принципа граничных решений, мало эффективен. Эффективные методы для нахождения отдельных решений конечной системы Л. н. (в частности, симплексный метод).появились с возникновением лилейного программирования.

В 1960-65 был разработан т. н. метод свертывания систем линейных неравенств, позволяющий по любой конечной системе, составленной в общем случае из неравенств вида (3) и (4), в частности из неравенств вида (1) и (2), и по заданному подпространству связанного с ней пространства находить нек-рую новую конечную систему Л. н., множество решений к-рой совпадает с той или иной проекцией множества решений рассматриваемой системы на взятое подпространство (см. [1]). Разработанный на этой основе алгоритм фундаментального свертывания (особый алгоритм для последовательного исключения неизвестных из системы (6)) позволяет получать общие формулы, определяющие все множество решений совместной системы вида (6). Метод свертывания может быть использован в задачах линейного программирования для уменьшения числа неизвестных, а также для получения общих формул, определяющих все множество оптимальных решений (см. [1]). Показано также [7], что с помощью метода свертывания можно выделять максимальные совместные подсистемы в несовместной конечной системе Л. н., составленной в общем случае из неравенств вида (3) и (4), в частности из неравенств вида (1) н (2), что позволяет использовать его при одном из подходов к решению задач распознавания образов (см. [8]).

Среди бесконечных систем Л. н. выделен и изучен особый класс - полиэдрально замкнутые системы (см. [1]). В случае действительного векторного пространства Rⁿ полиэдрально замкнутые системы определяются как бесконечные системы вида с топологически замкнутым в пространстве сопряженным конусом, т. е. конусом, порожденным элементами

тде - нулевой элемент пространства Бесконечные полиэдрально замкнутые системы Л. н. сохраняют ряд свойств конечных систем Л. н. и, в частности, для таких систем справедлива теорема Минковского - Фаркаша. Полиэдрально замкнутые системы Л. н. используются в теории приближения функций, в выпуклом программировании, в теории управления (см.

[8]).

Лит.:[1] Ч е р н и к о в, С. Н., Линейные неравенства, М., 1968; [2] Линейные неравенства и смежные вопросы, пер. с англ., .М., 1959; [3] М i n k о w s k i H., Geometrie der Zatilen, Lpz., 1896; [4] Черников С. Н., "Матем. сб.", 1944, т. 15, № 3, с. 437-48: [5] его же, "Успехи матем. наук", 1953, т. 8, № 2, с. 7-73; [6] его же, "Укр. матем. ж.", 1967, т. 19, .№ 1, с. 36- 80; [7] его же, "Доповда АН УРСР. Сер. А", 1969, № 1, с. 32-35; [8] К р а с о в с к и и Н. Н., Е р е м и н И. И., "Укр. матем. ж.", 1973, т. 25, № 4, с. 465-78; [9] F a r k a s J., "J. reine und angew. Math.", 1902, v. 124, S. 1-27; [10] D i n e s L. L., М сС о у N. Н., "Trans. Roy. Soc. Canada. Sec. 3", 1933, v. 27, p. 37-70. С. Н. Черников.