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

Рассмотрим канонические задачи :

К. Найти решение системы , которое минимизирует линейную форму

К. Найти решение неравенства которое максимизирует линейную форму

Задача К равносильна следующей стандартной задаче:

С. Найти решение системы

которое минимизирует линейную форму

Двойственной к является следующая задача:

С*. Найти решение системы

где которое максимизирует линейную форму

Нетрудно убедиться, что задача С равносильна задаче К. Действительно,

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

Следовательно, задача С равносильна следующей задаче (совпадающей с задачей К. Найти решение неравенства которое максимизирует линейную форму

Стандартные задачи Q и взаимно двойственны, и для них верна теорема двойственности. Задачи К и К равносильны соответственно задачам Q и С. Поэтому теорема двойственности имеет место также для задач К и К, т. е. верна следующая теорема.

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