Теорема двойственности для канонических задач.
Рассмотрим канонические задачи
:
К. Найти решение системы
, которое минимизирует линейную форму 
К. Найти решение неравенства
которое максимизирует линейную форму 
Задача К равносильна следующей стандартной задаче:
С. Найти решение системы

которое минимизирует линейную форму 
Двойственной к
является следующая задача:
С*. Найти решение системы

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

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