Теория двойственности в выпуклом программировании.Рассмотрим задачу . Будем предполагать, что множество планов этой задачи регулярно. Тогда для нее справедлива теореме Куна-Таккера. По параметрам задачи (1) составим функцию Лагранжа, и будем строить две функции. (22) (23) называется прямой, – двойственной для задачи (1). Рассмотрим две задачи: (24) (25) Задачу (24) называют прямой, а (25) – двойственной для задачи (1). Множество называется множеством прямых планов, а множество – множеством двойственных планов. Рассмотрим множество прямых планов. По определению функции получаем: . Тогда видно, что множество прямых планов (24) в точности совпадает с множеством планов основной задачи выпуклого программирования и на этом множестве . Это означает, что задачи (24) и (1) идентичны (одинаковы). Замечание. Если в качестве выпуклой задачи рассмотреть каноническую задачу линейного программирования и построить для нее функцию Лагранжа, а затем пару из прямой и двойственной задач, то нетрудно убедиться, что они в точности совпадают с парой взаимодвойственных задач линейного программирования. Теорема. (Соотношения двойственности) 1) Справедливо неравенство , . (26) 2) Если оптимальный план задачи (24), то тогда – оптимальный план задачи (25), причем . (27) 3) Если – оптимальные планы задач (24), (25), то на них выполняется условие . 4) 4.1) Если на некоторой последовательности двойственных планов , то . 4.2) Если на некоторой последовательности , то множество двойственных планов пусто. 5) Для того чтобы были оптимальными планами (24), (25) необходимо и достаточно, чтобы пара была седловой точкой функции Лагранжа для задачи (1). 6) Если для некоторых планов выполняется , то они являются оптимальными планами (24), (25). Доказательство. 1) Из определений (22), (23) следует, что . Остальные соотношения (2)-(5) доказываются по той же логической схеме, что и соотношения двойственности в линейном программировании. Ч.т.д.
|