1.5.2. Основные теоремы двойственности

Между решениями прямой и двойственной задач существуют определённые зависимости, которые характеризуются леммами и теоремами.

Лемма 1. Если - некоторый план исходной задачи (1.16)-(1.18), а - произвольный план двойственной задачи (1.19) – (1.21), то значение целевой функции исходной задачи при плане не превосходит значения целевой функции двойственной задачи при плане , то есть,

.

Лемма 2. Если выполняется равенство

для некоторых планов задачи (1.16) - (1.18) и задачи (1.19) - (1.21), то - оптимальный план исходной задачи, а - оптимальный план двойственной задачи.

Теорема 1.5.1. (первая теорема двойственности). Если одна из пары двойственных задач (1.16) – (1.18) или (1.19) – (1.21) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, то есть

.

Если целевая функция одной из пары двойственных задач не ограничена (для исходной задачи на максимум – сверху, для задачи на минимум – снизу), то другая задача вообще не имеет планов.

Теорема 1.5.2. (вторая теорема двойственности). План задачи (1.16) – (1.18) и план задачи (1.19) – (1.21) являются оптимальными планами этих задач тогда и только тогда, когда для любого номера выполняются равенства

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

В этом случае можно таблицу строить следующим образом

Таблица 1.21

Прямая и двойственная задачи настолько тесно увязаны, что оптимальное решение одной задачи можно получить непосредственно (без дополнительных вычислений) из итоговой симплекс таблицы 1.21 другой задачи. Появляется возможность проведения вычислений именно по той задаче (прямой или двойственной), которая требует меньше вычислительных ресурсов. Например, если прямая задача имеет 10 переменных и 50 ограничений, то предпочтительнее нахождение оптимального решения двойственной задачи, т.к. она будет содержать только 10 ограничений (трудоемкость вычислений задачи линейного программирования в большей степени зависит от количества ограничений, чем переменных).

Пример 14. Найти решения прямой и двойственной задач, если даны следующие условия:

Решение. Прямая задача максимизирует целевую функцию, следовательно, задача, двойственная к исходной, имеет вид:

При решении прямой задачи после двух шагов симплексных преобразований от таблицы 1.26 приходим к таблице 1.27.

Таблица 1.26 Таблица 1.27

Таблицу 1.27 можно представить так, чтобы в ней получить решение двойственной задачи, учитывая условия соответствия . Базисным переменным исходной задачи и соответствуют свободные переменные двойственной и . Свободным переменным исходной задачи и , соответствуют базисные переменные двойственной и .

Таблица 1.28

Откуда видно, что решение двойственной задачи находится в F - строке таблицы 1.28. Таким образом, оптимальное решение прямой задачи- =(8/3;2/3), решение двойственной - =(1|3;8|3) и 56/3.