Критерий несовместности системы линейных неравенств.

Перейдем к рассмотрению неоднородных систем линейных неравенств.

ТЕОРЕМА 1.8. Система неравенств

несовместна тогда и только тогда, когда существуют действительные числа удовлетворяющие условиям

Доказательство. Предположим, что система (1) несовместна, и докажем, что существуют действительные числа, удовлетворяющие условиям (2). Пусть

Рассмотрим однородную систему неравенств

с переменными Неравенство

есть следствие системы (4). Действительно, если — произвольное решение системы (4), то

ибо при вектор был бы решением системы (4), а вектор - решением исходной системы (1), что противоречило бы предположению о несовместности этой системы.

Так как неравенство (5) есть следствие системы (4), то, по теореме Минковского, вектор можно представить в виде неотрицательной линейной комбинации векторов

т. е. существуют действительные числа такие, что

Ввиду (3) отсюда следует, что

т. е. выполняются условия (2).

Предположим теперь, что существуют действительные числа , удовлетворяющие условиям (2), и докажем, что система (1) несовместна. Рассмотрим неравенство

являющееся неотрицательной линейной комбинацией неравенств системы (1). Согласно предложению 1.1, это неравенство есть следствие системы (1). Ввиду (2) неравенство (7) можно записать в виде

Это неравенство не имеет решений и является следствием системы (1), поэтому система (1) несовместна.

Пусть для ,

ТЕОРЕМА 1.9. Неравенство

является следствием неравенства

тогда и только тогда, когда совместна система

Теорема 1.9 непосредственно следует из предложения 1.1 и теоремы 1.8.

ТЕОРЕМА 1.10. Система

(где b — столбец), совместна тогда и только тогда, когда для всякого .

Заменив в теореме 1.9 , соответственно на мы убедимся, что теорема 1.10 есть другая формулировка теоремы 1.9.