Теорема двойственности для канонических задач.
Рассмотрим канонические задачи 
:
К. Найти решение системы 
, которое минимизирует линейную форму 
К. Найти решение неравенства 
которое максимизирует линейную форму 
Задача К равносильна следующей стандартной задаче:
С. Найти решение системы
которое минимизирует линейную форму 
Двойственной к 
является следующая задача:
С*. Найти решение системы
где 
которое максимизирует линейную форму 
Нетрудно убедиться, что задача С равносильна задаче К. Действительно,
Любой 
-мерный вектор можно представить в виде разности двух неотрицательных 
-мерных векторов. Ввиду этого, если положить 
то z пробегает множество всех 
-мерных векторов из 
когда 
пробегают множество всех неотрицательных векторов из 
Следовательно, задача С равносильна следующей задаче (совпадающей с задачей К. Найти решение неравенства 
которое максимизирует линейную форму 
Стандартные задачи Q и 
взаимно двойственны, и для них верна теорема двойственности. Задачи К и К равносильны соответственно задачам Q и С. Поэтому теорема двойственности имеет место также для задач К и К, т. е. верна следующая теорема.
ТЕОРЕМА 2.8. Если обе взаимно двойственные канонические задачи (К и К допустимы, то обе задачи имеют решения и значения этих задач совпадают. Если хотя бы одна из задач недопустима, то ни одна из задач не имеет решений.
