Метод, при котором вначале симплекс-методом решается одна из взаимно двойственных задач, а затем оптимум и оптимальное решение другой задачи находятся с помощью теорем двойственности, называется двойственным симплекс-методом.
Теорема 1 (Первая теорема двойственности). Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и
другая, причем оптимальные значения их целевых функций равны:
. (7.1)
Если целевая функция исходной задачи не ограничена, то система ограничений двойственной задачи несовместна.
Примечание: утверждение, обратное по отношению ко второй части первой теоремы двойственности, в общем случае неверно.
Установим соответствие между переменными взаимно двойственных задач.
Теорема 2. Компоненты оптимального плана двойственной задачи (обладающие условием неотрицательности) равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
Компоненты оптимального плана двойственной задачи (не ограниченные по знаку) равны значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
Теорема 3. Положительным (ненулевым) компонентам оптимального решения одной из задач симметричной двойственной пары соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых 
и 
:
Теорема 4 (Третья теорема двойственности). Компоненты оптимального плана двойственной задачи равны значениям частных производных линейной функции 
по соответствующим аргументам, т.е.
. (7.2)
Экономическая интерпретация третьей теоремы двойственности: компоненты оптимального плана двойственной задачи показывают, на сколько денежных единиц изменится максимальная прибыль (выручка) от реализации продукции при изменении запаса соответствующего ресурса на одну единицу.
Пример 9.1. На основе решения примера 5.2 (файл «Алгоритм и примеры симплекс-метода») определим двойственным симплекс- методом оптимальное решение двойственной задачи.
Исходная задача | Двойственная задача |
|
|
Данная двойственная пара является симметричной. Задачи записаны в стандартной форме, приведем их к каноническому виду:
Исходная задача | Двойственная задача |
|
|
Установим соответствие между переменными взаимно двойственных задач.
На основе решения примера 5.2. симплекс-таблица последней итерации (таблица 5.10) имеет вид:
Таблица 9.3
Симплекс-таблица оптимального решения исходной задачи
В соответствии с теоремой 2, оптимальные значения переменных 
и 
будут равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
По таблице 9.3 выпишем целевую функцию исходной задачи, выраженную через свободные переменные ее оптимального решения:
.
Следовательно, 
, 
.
Переменные 
, 
, 
и 
не присутствуют в целевой функции (т.е. коэффициенты при них равны нулю), следовательно, оптимальные значения соответствующих им переменных 
, 
, 
и 
равны нулю.
В соответствии с теоремой 1, 
.
Таким образом, оптимальное значение целевой функции 
, которое достигается при 
.
Ответ: 
, 
.
Пример 9.2. На основе решения исходной задачи найти оптимальное решение двойственной задачи используя двойственный симплекс-метод.
|
Исходная задача | Двойственная задача |
|
|
Данная двойственная пара является несимметричной. Приведем к каноническому виду двойственную задачу.
|
Исходная задача | Двойственная задача |
|
|
Для установления соответствия переменных двойственной пары введем в исходную задачу две недостающие фиктивные переменные.
|
Исходная задача | Двойственная задача |
|
|
Установим соответствие между переменными взаимно двойственных задач.
Таблица 9.4
Соответствие переменных двойственной пары
Решим исходную задачу симплекс-методом.
Используя метод Жордана-Гаусса, выделим в системе ограничений исходной задачи в качестве базисных переменные 
и 
(примечание: не использовать в качестве базисных фиктивные переменные).
В результате преобразований получим следующую матрицу коэффициентов:
.
Система ограничений исходной задачи примет следующий вид:
Выразим базисные переменные через свободные, в результате исходная задача примет следующий вид:
Подставив полученные значения базисных переменных в целевую функцию, она примет следующий вид:
В результате решения симплекс-методом преобразованной исходной задачи на последней итерации получим следующую симплекс-таблицу:
Таблица 9.5
Симплекс-таблица оптимального решения исходной задачи
|
СП БП |
|
|
|
|
|
| 3 | -1/3 | 5/3 | -1/3 | 2/3 |
| 3 | 1/3 | 4/3 | -2/3 | 1/3 |
| 12 | 5/3 | 23/3 | -7/3 | 5/3 |
Примечание: при проверке признаков несовместности системы ограничений, неограниченности целевой функции, оптимальности найденного допустимого базисного решения, а также определении разрешающего элемента, колонки фиктивных переменных не учитываются.
В соответствии с теоремой 3, оптимальные значения переменных 
и 
будут равны абсолютным значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
Так как переменные 
, 
не ограничены по знаку, то их оптимальные значения будут равны значениям коэффициентов при соответствующих переменных целевой функции исходной задачи, выраженной через свободные переменные ее оптимального решения.
.
Согласно таблице соответствия переменных (таблица 9.4):
, 
, 
, 
.
Переменные 
и 
не присутствуют в целевой функции (т.е. коэффициенты при них равны нулю), следовательно, оптимальные значения соответствующих им переменных 
и 
равны нулю.
В соответствии с теоремой 1, 
.
Таким образом, оптимальное значение целевой функции 
, которое достигается при 
.
Ответ: 
, 
.
