Eng | Rus | Ukr
Исследование операций
30.01.2005

<< prev | ^up^ | next >>

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.

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004