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

Переход к двойственной задаче не обязателен, т.к. если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках – двойственная. Причем оценками плана исходной задачи является C_j, а оценками плана двойственной - b_i. Решим двойственную задачу по симплексной таблице, в которой записана исходная задача.

Если некоторый набор свободных переменных двойственной задачи определяет ее оптимальное решение, то соответствующий набор базисных и свободных переменных исходной задачи дает оптимальное решение исходной задачи. Тем самым вопрос об отыскании оптимального решения исходной задачи сводится к определению оптимального решения двойственной задачи

Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом. Им можно решать ЗЛП, системы ограничений которых при положительном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размеры симплексной таблицы.

Пусть необходимо решить исходную задачу, поставленную в общем виде: L(X)=CX®max при AX=A₀, X³0. Тогда двойственная: Z(Y)=YA₀®min при YA£C.

Почти допустимым опорным решением (ПДОР) ЗЛП называется такой n-мерный вектор Х=(x₁, x₂ , _…, x_m, 0,…,0), который удовлетворяет системе ограничений задачи, не удовлетворяет условиям неотрицательности переменных и для которого векторы условий А₁, А₂,…,А_m линейно независимы.

В двойственном симплексном методе рассматриваются ПДОР, при которых оценки целевой функции по базису ПДОР соответствуют признаку оптимальности, т.е. в задаче на максимум – положительные, в задаче на минимум – отрицательные.

ПДОР является оптимальным, если оно является допустимым (признак оптимальности ПДОР).

Алгоритм двойственного симплексного метода:

1. Привести задачу к каноническому виду.

2. Найти ПДОР Х=(x₁, x₂ , _…,х_к,…, x_m, 0,…,0) с базисом из единичных векторов. Вычислить оценки целевой функции по базису этого решения. Если они согласуются с признаком оптимальности, решить задачу двойственным симплексным методом.

3. Если ПДОР не имеет отрицательных компонент, то оно является допустимым и оптимальным.

4. Пусть ПДОР имеет хотя бы одну отрицательную компоненту (например, х_к<0).

Просматриваем (к)-ю строку. Если в ней не содержатся отрицательные компоненты, т.е. все а_kj³0 для любого j, то линейная функция двойственной задачи не ограничена на многограннике решений, а исходная задача не имеет решения ввиду несовместности системы ограничений. Решение задачи прекращается.

5. Если имеется хотя бы одна отрицательная компонента х_к<0 и при этом в (к)-ой строке найдутся отрицательные коэффициенты x_kj <0, то для столбцов, содержащих эти отрицательные значения, вычисляем q_0j=min

Контрольные вопросы

1. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов.

2. Взаимно двойственные задачи линейного программирования (симметричные и несимметричные) и их свойства.

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

4. Первая теорема двойственности.