Неотрицательные решения системы линейных уравнений и системы линейных неравенств.

Систему линейных уравнений

можно записать в матричной форме

где .

При рассмотрении задач линейного программирования возникает вопрос об условиях, при которых система (1 имеет хотя бы одно неотрицательное решение. Этот вопрос равносилен вопросу о совместности системы

ТЕОРЕМА 1.11. Система (1) совместна тогда и только тогда, когда несовместна система

Доказательство. Согласно теореме 1.10, система (1) совместна тогда и только тогда, когда

Нетрудно видеть, что

Таким образом, система (1) совместна тогда и только тогда, когда для каждого у

Следовательно, система (1) совместна тогда и только тогда, когда несовместна система (2).

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

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

Доказательство. Пусть А — -матрица и Нетрудно видеть, что система (1) совместна тогда и только тогда, когда совместна система

Пусть Е — единичная -матрица, тогда

Поэтому систему (1) можно записать в виде

Согласно теореме 1.11, система (1') совместна тогда и только тогда, когда несовместна система

т. е. несовместна система

Следовательно, система (1) совместна тогда и только тогда, когда несовместна система (2).