 |
 |
 |
 |
|
 |
 |
56
2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
2.2.1. Понятие седловой точки. В настоящем параграфе мы кратко остановимся на некоторых
фундаментальных моментах теории нелинейного программирования. Отправной точкой для них
является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств:
где X — некоторая область в пространстве R
n
.
По аналогии с п. 2.1.2 определим для задачи (2.28) функцию Лагранжа:
Пара векторов (х, u) называется седловой точкой функции Ф(х, и) в некоторой области X x U, если
для любых x ? X и u ? U
Неравенства (2.30) также называют неравенствами седловой точки.
В качестве примера седловой точки может быть приведена точка (0, 0) для функции Ф(х,и) = -х² + и²,
определенной на множестве R х R. В самом деле, Ф(0,0)=0, Ф(х,0)=-х², Ф(0, и) = и², а для любых x?R и
u?R выполняются неравенства –х² ? 0 и 0
?
и².
На рис. 2.7 изображен график функции Ф(х,и) (гиперболический параболоид), и, как видно, в
окрестности точки (0,0) он действительно по форме напоминает седло, чем и объясняется
происхождение соответствующего термина.
2.2.2. Теорема Куна—Таккера. Центральное место в теории нелинейного программирования
занимает теорема Куна— Таккера, которая связывает решение ЗНП с наличием седловой точки у
соответствующей функции Лагранжа.
Теорема 2.3. (Достаточное условие экстремума).
Если (х, и) — седловая точка функции Лагранжа, в области x?X?D,
и
?
0,то х является
оптимальным планом задачи (2.28), причем справедливо так называемое
правило дополняющей
нежесткости: