Выше было показано, что для получения решения исходной задачи можно перейти к двойственной и, решив ее, определить оптимальное решение исходной.
Переход к двойственной задаче не обязателен, т.к. если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках – двойственная. Причем оценками плана исходной задачи является Cj , а оценками плана двойственной - bi. Решим двойственную задачу по симплексной таблице, в которой записана исходная задача.
Если некоторый набор свободных переменных двойственной задачи определяет ее оптимальное решение, то соответствующий набор базисных и свободных переменных исходной задачи дает оптимальное решение исходной задачи. Тем самым вопрос об отыскании оптимального решения исходной задачи сводится к определению оптимального решения двойственной задачи
Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом.Им можно решать ЗЛП, системы ограничений которых при положительном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размеры симплексной таблицы.
Пусть необходимо решить исходную задачу, поставленную в общем виде: L(X)=CX®max при AX=A0, X³0. Тогда двойственная: Z(Y)=YA0®min при YA£C.
Почти допустимым опорным решением (ПДОР) ЗЛП называется такой n-мерный вектор Х=( x1, x2 , …, xm, 0,…,0), который удовлетворяет системе ограничений задачи, не удовлетворяет условиям неотрицательности переменных и для которого векторы условий А1, А2,…,Аm линейно независимы.
В двойственном симплексном методе рассматриваются ПДОР, при которых оценки целевой функции по базису ПДОР соответствуют признаку оптимальности, т.е. в задаче на максимум – положительные, в задаче на минимум – отрицательные.
ПДОР является оптимальным, если оно является допустимым (признак оптимальности ПДОР).
Алгоритм двойственного симплексного метода:
1. Привести задачу к каноническому виду.
2. Найти ПДОР Х=( x1, x2 , …,хк,…, xm, 0,…,0) с базисом из единичных векторов. Вычислить оценки целевой функции по базису этого решения. Если они согласуются с признаком оптимальности, решить задачу двойственным симплексным методом.
3. Если ПДОР не имеет отрицательных компонент, то оно является допустимым и оптимальным.
4. Пусть ПДОР имеет хотя бы одну отрицательную компоненту (например, хк<0).
Просматриваем (к)-ю строку. Если в ней не содержатся отрицательные компоненты, т.е. все аkj³0 для любого j, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решения ввиду несовместности системы ограничений. Решение задачи прекращается.
5. Если имеется хотя бы одна отрицательная компонента хк<0 и при этом в (к)-ой строке найдутся отрицательные коэффициенты xkj <0, то для столбцов, содержащих эти отрицательные значения, вычисляем q0j=min 
Контрольные вопросы
1. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов.
2. Взаимно двойственные задачи линейного программирования (симметричные и несимметричные) и их свойства.
3. Алгоритм составления двойственных задач.
4. Первая теорема двойственности.