Вторая теорема двойственности

Тесная связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций, о чем утверждалось в первой (основной) теореме двойственности.

Пусть даны две взаимно двойственные задачи: I — (6.1)-(6.3) и II — (6.4)-(6.6). Если каждую из этих задач решать симплексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений (6.2 задачи I (в краткой записи ) следует ввести т неотрицательных переменных , а в систему ограничений (6.5) задачи II () — п неотрицательных переменных , где i (/') — номер неравенст ва, в которое введена дополнительная переменная ()•.

Системы ограничений каждой из взаимно двойственных задач примут вид:

(6.12).

(6.13).

Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (табл. 6.2).

Теорема. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального

Таблица 6.2

Переменные исходной задачи I.
Первоначальные.	Дополнительные.
Дополнительные.	Первоначальные.
Переменные двойственной задачи II.

решения другой задачи, т. е. для любых г = 1,2, т и j = = 1,2,…, п: если , то ; если то ;

и аналогично, если ', то i; если , то

? Выразим дополнительные переменные из систем ограничений (6.12) исходной задачи I и (6.13) двойственной задачи II, представленных в каноническом виде:

(6.15).

(6.16).

Умножая каждое равенство системы (6.15) на соответствующие переменные и складывая полученные равенства, найдем.

(6.17).

Аналогично, умножая каждое равенство системы (6.16) на соответствующие переменные Xj >0 и складывая полученные равенства, найдем.

(6.18).

Равенства (6.17) и (6.18) будут справедливы для любых допустимых значений переменных, в том числе и для оптимальных значений . В силу первой теоремы двойственности (6.11) или , поэтому из записи правых частей равенств (6.17) и (6.18) следует, что они должны отличаться только знаком. С другой стороны, из неотрицательности выражений , входящих в выражения (6.17) и (6.18), следует, что? те же правые части этих равенств должны быть неотрицательны.

Эти условия могут выполняться одновременно только при равенстве этих правых частей для оптимальных значений переменных нулю:

(6.19).

В силу условия неотрицательности переменных каждое из слагаемых в равенствах (6.19) должно равняться нулю:

откуда и вытекает заключение теоремы. ¦

Из доказанной теоремы следует важный вывод о том, что введенное ранее соответствие (6.14) между переменными взаимно двойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными пулю) переменными другой задачи, когда они образуют допустимые базисные решения.

Рассмотренная теорема является следствием следующей теоремы.

Вторая теорема двойственности^[1]. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения.

6.5. Убедиться в справедливости второй теоремы двойственности для взаимно двойственных задач I и II, приведенных в задаче 6.2.

Решение. На основании выражения (6.14) установим следующее соответствие между переменными:

В гл. 5 обе задачи были решены симплексным методом. На последнем шаге решения каждой задачи (см. с. 74 и 77) получено:

!!!в исходной задаче I в двойственной задаче II.

, (6.20) , (6.21).

при оп- при оптималь тимальном базисном решеном базисном решении нии i.

Компоненты оптимального решения двойственной задачи равны (по аб солютной величине) коэффициентам при соответствующих переменных линейной функции (6.20), которую можно представить в виде ,.

!!!

а компоненты оптимального решения исходной задачи.

равны коэффициентам при соответствующих переменных линейной функции (6.21), которую можно представить в виде.

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

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

6.6. Решить симплексным методом задачу.

при ограничениях:

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

Решение. Решая задачу симплексным методом, получим па последнем шаге решения (рекомендуем читателю убедиться в этом самостоятельно): , т. е. Fmm =10 при оптимальном базисном решении X* = (4; 7; 0; 0; 6; 6).

В данной задаче соответствие (6.14) между переменными примет вид:

Наосновании первой теоремы двойственности . На основании второй теоремы двойственности оптимальное решениедвойственной задачи У* = (2/7; 3/7; 0; 0; 0; 0), так как , т. е. равна коэффициенту при соответствующей переменной х3 в выражении линейной функции F (x), , т. е. равна коэффициенту при переменной (из-за отсутствия соответствующих переменных х., хб, xv х2 в выражении F (x) их коэффициенты равны нулю). Итак, в двойственной задаче при . >

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

• [1] В ряде работ по математическому программированию под второй теоремой двойственности фактически понимается предыдущая теорема (с. 108).