Теорема двойственности для стандартных задач.

В теории линейного программирования основными являются теоремы двойственности 2.7 и 2.8.

ТЕОРЕМА 2.7. Если обе взаимно двойственные стандартные задачи (С и С допустимы, то обе задачи имеют решения и значения этих задач совпадают. Если хотя бы одна из задач недопустима, то ни одна из задач не имеет решений.

Доказательство. Предположим, что обе задачи допустимы. Тогда совместна система

Первая часть теоремы будет доказана, если мы докажем существование таких решений у и Z соответственно (1) и (2) систем, что

Действительно, в этом случае, по предложению 2.5, допустимые векторы у и z удовлетворяют неравенству

Поэтому если у и z удовлетворяют еще и (3), то Следовательно, в силу критерия оптимальности векторы у и z будут оптимальными векторами соответствующих задач (С и С* и значения обеих задач будут совпадать. Таким образом, достаточно доказать совместность системы

Запишем эту систему в матричной форме:

По теореме 2.6, система (4) совместна тогда и только тогда, когда несовместна система

Эту систему можно записать в виде

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

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

что противоречит последнему неравенству (5).

Если же , то система (5) несовместна. Действительно, по условию, совместна система (1), (2), т. е. система

По теореме 2.6, из совместности системы (6) следует несовместность системы

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

Таким образом, система (5) несовместна и поэтому совместна система (4).

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

Недопустимость задачи С, т. е. несовместность системы

по теореме 1.12, влечет совместность системы

Следовательно, существует вектор х такой, что

На основании (1) и (2) заключаем, что для любого натурального выполняются неравенства

Значит, для любого натурального вектор является допустимым вектором первой задачи. Однако линейная форма не имеет минимума. Действительно,

и в сумме справа первое слагаемое есть некоторое действительнее число, а второе слагаемое ввиду может быть сделано при достаточно большом я меньше любого заданного числа. Следовательно, линейная форма минимума не имеет, т. е. первая задача не имеет решений.