5.4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ОПТИМИЗАЦИ
Задача линейного программирования как задача Лагранжа
Использование понятия седловой точки позволяет установить взаимосвязи между прямой и двойственной задачами в математическом программировании. Прежде чем рассмотреть общий случай нелинейного программирования, исследуем эти взаимосвязи для линейного программирования.
Пусть имеем пару двойственных задач ЛП вида:
|
Задача 1 |
Задача 2 |
||
|
|
(5.4.1) |
|
(5.4.3) |
|
|
(5.4.2) |
|
(5.4.4) |
|
|
|
Для удобства запишем ограничения задачи 1 в виде
Для исследования связи прямой и двойственной задачи введем функции Лагранжа. Образуем функцию Лагранжа для задачи 1:
(5.4.5)
Так как ограничения линейны, то выполняются условия регулярности теоремы Куна-Таккера. Следовательно, условия дополняющей нежесткости запишутся так:
(5.4.6)
Образуем функцию Лагранжа для задачи 2, преобразовав ее сначала в эквивалентную задачу минимизаци 
. Для этого введем множители Лагранжа 
.
Условия регулярности вновь, как и в задаче 1, выполняются, и поэтому имеем
(5.4.7)
Заметим, что если положить 
, то 
. Таким образом, если переменные 
трактовать как множители Лагранжа в задаче 1, а 
- как множители Лагранжа в задаче 2, то целевые функции обеих задач будут равны по величине и противоположны по знаку.
Используя функцию Лагранжа 
, можно показать, что задачу 1 можно записать в виде
(5.4.8)
при ограничениях
Аналогично задачу 2 можно записать так:
(5.4.9)
при ограничениях
(5.4.10)
Воспользовавшись соотношением , получим для задачи 2
(5.4.11)
при ограничениях
(5.4.12)
Используя соотношения (5.4.8) - (5.4.12), мы получаем следующее представление пары двойственных задач с помощью функции Лагранжа :
|
Задача 1 |
Задача 2 |
||
|
|
(5.4.13) |
|
(5.4.15) |
|
при ограничениях |
при ограничениях |
||
|
|
(5.4.14) |
|
(5.4.16) |
При этом для оптимальных решений 
выполняются условия, аналогичные (5.4.6), (5.4.7):
(5.4.17)
Справедлива следующая теорема, устанавливающая связь между оптимальными решениями двойственных задач ЛП и седловой точкой [18].
Теорема 5.12. Вектор 
является оптимальным решением ЛП-задачи 1 тогда и только тогда, когда существует такой вектор 
, что пара является седловой точкой функции Лагранжа , то есть для всех 
(5.4.18)
Доказательство. Докажем сначала достаточность условий теоремы. Пусть - седловая точка, тогда левое неравенство (5.4.18) выполняется при всех 
и, в частности, при 
. Однако поскольку 
, то левое неравенство
(5.4.19)
будет возможно только в том случае, если
Учитывая это, из правого неравенства (5.4.18) получим
Таким образом, для всех допустимых 
справедливо 
, что доказывает оптимальность вектора .
Докажем теперь необходимость условий теоремы, то есть то , что из оптимальности вектора следует существование такого вектора , что пара будет седловой точкой функции .
Согласно теореме [2.5] главы 2, из оптимальности следует существование такого , что 
, где - оптимальное решение двойственной задачи. Тогда, согласно теореме [2.6] главы 2 должно выполняться равенство Но так как - допустимое решение, то 
, откуда для любого
Таким образом, справедливо неравенство
(5.4.20)
Следовательно, левое неравенство (5.4.18) для седловой точки установлено. Аналогично можно доказать и правое неравенство. Теорема доказана.
Таким образом, на основании теоремы 5.12 приходим к выводу, что отыскание решения для пары двойственных задач ЛП эквивалентно нахождению седловой точки соответствующей функции Лагранжа.
Покажем, что этот вывод справедлив и для некоторых классов задач НП.
Задача нелинейного программирования
как задача о седловой точке
Выше были получены соотношения (5.4.13) - (5.4.16), связывающие пару двойственных задач ЛП. Рассмотрим теперь задачу НП в виде:
минимизировать 
(5.4.21)
при ограничениях
(5.4.22)
Введя функцию Лагранжа 
, можно записать эту задачу в эквивалентном виде
минимизировать 
(5.4.23)
при ограничениях
(5.4.24)
По аналогии с линейным программированием назовем следующую задачу:
максимизировать 
(5.4.25)
при ограничениях
(5.4.26)
y ³ 0
двойственной к задаче (5.4.23), (5.4.24).
Справедлива теорема, аналогичная теореме двойственности ЛП, впервые доказанная П.Вулфом [2].
Теорема 5.13. Пусть функции , 
, выпуклы и дифференцируемы в 
и выполняются условия регулярности. Если прямая задача (5.4.21), (5.4.22) имеет решение , то в двойственной задаче (5.4.26) существует такой вектор , который является ее оптимальным решением и при этом экстремумы пары двойственных задач равны между собою.
Для иллюстрации этой теоремы рассмотрим задачу квадратичного программирования:
максимизировать 
(5.4.27)
при ограничениях
(5.4.28)
где С- симметричная, отрицательно определенная матрица. Преобразуем (5.4.27), (5.4.28) в эквивалентную задачу минимизаци и построим функцию Лагранжа
(5.4.29)
Исходную задачу можно сформулировать в виде:
минимизировать 
(5.4.30)
x ³ 0
при ограничениях
(5.4.31)
Нетрудно показать, що задача (5.4.30), (5.4.31) эквивалентна задаче (5.4.27), (5.4.28).
По аналогии с линейным программированием запишем двойственную задачу для задачи квадратичного программирования:
максимизировать (5.4.32)
y ³ 0
при ограничениях
(5.4.33)
Подставляя выражение для из (5.4.29) в (5.4.32) и (5.4.33), получим следующую запись двойственной задачи:
(5.4.34)
при условии
(5.4.35)
Оптимальные решения и связаны между собою соотношениями
(5.4.36)
(5.4.37)
Используя выражение (5.4.29) и подставляя его в (5.4.36) и (5.4.37), получим соответственно
(5.4.38)
(5.4.39)
Покажем, что задачи (5.4.27), (5.4.28) и (5.4.34), (5.4.35) на самом деле являются двойственными и выполняется утверждение теоремы о том, что
(5.4.40)
Поскольку 
связаны между собою соотношениями (5.4.38), (5.4.39), то имеем
или
Таким образом установлена справедливость соотношения (5.4.40) и теоремы 5.13.
