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.