Пусть имеем пару двойственных задач ЛП вида:
Задача 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.