XIV Аттетков и др. Методы оптимизации (1081420), страница 46
Текст из файла (страница 46)
Поэтому решений системы с Лб = О нет. Пусть Лб ф О. В этом случае мы можем взять для Лб любое ненулевое значение. Положим Лб = 1/2. Тогда из первых двух уравнений можно выразить гл1 и из и подставить в остальные. 318 7. АНАЛИТИЧЕСКИЕ МЕТОДЫ Получим систему трех уравнений 1лл(3+1лл — 1лз) = О /л2(3+122 — /лз) = О, 1лз(2+121+122 — 21лз) = О. Рассматривал различные варианты, .находим семь решений сисгемы (табл. 7.1).
Таблица 7.1 Первое решение соответствует точке локального минимума целевой функции, причем эта точка не попадает в допустимое множество й. Второе, третье и пятое решения соответствуют точкам условного локального минимума на сторонах треугольника, ограничивающего допустимое множество. Наконец, четвертое, шестое и седьмое решения соответствуют трем угловым точкам множества (вершинам треугольника). Сравнение значений функции показывает., что единственным решением рассматриваемой задачи является точка Аз с координатами хл = х2 = 2. К этим выводам легко прийти, осли учесть, что значением целевой функции в точке (тм хз) является квадрат расстояния от этой точки до точки (3, 3).
ф 7.4. Седлонан точка функции Лагранжа Рассмотрим задачу нслинейноео нросрамнирооания < У,(*) -+ лп1в; д,(в)(О, с=1,гп, (7.12) 74. Седлоааа точка фунаиии.лагранжа в которой нет ограничений хипа равенства. Предполагаем, что функции 1о(х) и д,(х), г = 1., ть определенные в Ж", могут быть недифференцируемыми. Как и выше, сформируем функцию Лагранжа 7(х 1х) = Уо(х) + ~~', р.д,(х), (7.13) где Р = (Р~ " Нт ) Е К~, К~ — неотрицательный ортант в Кт. Мы будем рассматривать функцию, Лагранжа как функцию всей совокупности переменных х и ул. Отметим, что в данном случае в функцию Лагранжа не включен множитель Ао. Определение 7.1. Точку (х*, ул"), где х* е 11, ул е К;а, называют седлоеой тпочной функции, Лагранжа х (х, и), если Цх',ул) < 7(х*,ул*) < 7Ах,хх')., х Е П, 1л б Б™„. (7.14) Теорема 7.7.
Если (х*, хь*) -- седловая точка функции,Лагранжа Цх, и), то х* — точка наименьшего значения функции А(х) на множестве П = (х Е Б!": д~(х) < О, г = 1, т) ~ Из определения функции Лагранжа вытекает, что для любых х Е Й и и Е Кт выполнЯетсЯ неРавенство Цх, и) < уо(х), так как и;д,(х) < О, г = 1, т, .х Е П. При этом указанное неравенство превращается в равенство, если и = О, т.е.
х (х,О) = уо1х). Поэтому если (х*, и*) — седловая точка функции Лагранжа, то для любой точки х Е Й Ь( ') = 7(х*,О) < И, '1л") < 7(х,аль) < Ых). Доказанная теорема указывает метод решения задачи нелинейного программирования (7.12). Достаточно определить седловую точку функции Лагранжа, чтобы прийти к решению задачи нелинейного программирования. Следующая теорема устанавливает критерий для седловых точек функции Лагранжа.
320 7. АНАЛИТИЧЕСКИЕ МЕТОДЫ Теорема 7.8. Точка (х*,м*), х* Е й, и' = (рм ..., р ) Е Е 2~, является седловой для функции Лагранжа Цх, и) в том и только в том случае, если выполнены условия Цх*,м*) =ш1пЦх,м*), еей н,д,1х') =О, 1=1,пь (7.15) (7.16) ~ Если (х*, и*) седловая точка функции Лагранжа, причем х" Е 11, и* Е 1я.„', то соотношение 17.15) верно в силу определения седловой точки. Кроме того, согласно этому определению, Цх*, и*) > Цх*,О), что равносильно неравенству Таким образом, ~р,'д,(х*) > О.
(7.17) Но из условия х* Е Й вытекает, что д,(х*) < О, а условие и* Е Б",' означает, что р,* > О, г = 1, пь Следовательно, каждое слагаемое суммы в неравенстве (7.17) неположительно. Поэтому и сумма, и каждое ее слагаемое равны нулю, т.е. верны соотношения (7.16). Теперь предположим, что выполнены условия (7.15) и (7.16). Тогда Цх',р,*) = Ях*) и в то же время Цх',р) < 1е(х') для любого и б Кш, откуда Цх"',р) < Цх*,н*). Это вместе с (7.15) приводит к неравенствам (7.14), т.е. к утверждению, что (х', и*) седловая точка функции, Лагранжа.
~ Теорему 7.7 можно использовать в широком круге задач нелинейного программирования. При этом на функции Тв(х) и д,(х), г = 1,пб не накладываются никакие ограничения. Однако следует иметь в виду, что достаточное условие, которое устанавливается теоремой 7.7,лишь заменяет одну задачу минимизации другой, которая в некоторых случаях может быть 321 7.5. Двойственная функция проще исходной. Действительно, поиск седловой точки функ- ции Лагранжа в соответствии с 17.15) овна иют минимизацию функции Лагранжа по переменным х.
7.5. Двойственная функция ю(1я) = шГ 7(х,1л). яей 17.18) Функции Ях) и и~(1я) связаны соотношением ю(1я) (Д(х), 1я б 2„, хай. 17.19) Действительно, функция Лагранжа удовлетворяет неравенству А1х, 1я) ( 1о1х), х б й, 1я Е 2т. Из этого неравенства вытекает, что ш(1я) = ш1 Цх,ре) ( ш1'Ях) (Ях). яЕЙ яЕЙ Теорема 7.9. Если для некоторых х' е й и 1я* е 2т верно равенство 1в1х*) = ю(1я*), то функция ув1х) в точке х' достигает наименьшего значения на множестве й, а функция и)(1л) в точке 1л* —. наибольшего значения на множестве 2т. ~ Из неравенства 17.19) для х = х* с учетом равенства Ях*) = = ю(1я*) заключаем, что и~(1я) ( ш(рЯ)., 1я Е 2, .
Это и означает, что значение функции ш(р) в точке 1я* является наибольшим на множестве 2'„". Рассмотрим задачу нелинейного программирования 17.12), не имеющую ограничений типа равенства,. предполагая, что целевая функция ув1х), а также функции д,;~х), 1 = 1, т, определены в 2". Как и выше 1см. 7.4), сформируем функцию Лагранжа 7(х,1я) в виде 17.13), определенную при х Е 2" и 1я е 2т, где 2т -- неотрииаяпельнмй ортант в 2т. На множестве 2„определим функцию 322 7. ЛНАЛИТИНЕСКИЕ МЕТОДЫ Аналогично, полагая в неравенстве (7.19) 1л = 1л* и учитывая, что ю(ул') = 1о(х*), находим Уа(х) ) Уо(х*), х Е- Й, т.е. в точке х* функция 1(х) достигает наименьшего значе- ния. ~ Любая точка локального максимума функции и~(р) на множестве К~ является точкой ее наибольшего значения на этом множестве.
'1тобы доказать это свойство функции ю(р), достаточно показать, что функция — юОл) выпукла на выпуклом мнолеестее Бт. Выберем произвольные несовпадающие точки ул', аале в 11, и произвольное число а е [О, 1]. Пусть 1л = = аул~ + (1 — а)р~. В соответствии с определением функпии ю(1л) для произвольного числа е > 0 существует такая точка х е й, что ю(р) > л (х, 1л) — е.
Из определения функпии Лагранжа (она линейна по множителям, Лагранжа) следует равенство Ь(х,ул) = Цх,аул +(1 — а)1л ) = а1 (х,1л ) +(1 — а)Ь(х.,1л ). С учетом этого равенства имеем ю(р) > а7(х,р ) + (1 — а)А(х, 1л ) — е > > аю(1л' ) + (1 — а) ю(1л ) — е. Ввиду того, что число е > 0 выбрано произвольно, заключаем, что ( ) > ( 1) + (1 ) ( 2) а это равносильно выпуклости функции — ю(р). Теорема 7.10.
Функция Лагранжа (7.13) имеет седловую точку (х*, 1и") тогда и только тогда, когда (7.20) ю(1л ) = 1о(х ) ~ Пусть (х*, 1л*) — — седловая точка функции Лагранжа. Тогда, согласно определению седловой точки, 1 (х', 1л') < 1 (х, 1л*), 323 7.5. Двойственная Функция х е й, т.е. при заданном и = 1т* функция Лагранжа достигает на множестве й наименьшего значения в точке х'.
Поэтому ю(р*) = 1 1х*,тт*). Далее, .снова используя определение седловой точки, .заключаем, что А1х*, и*) > ь1х',О) = 7я1х*), откуда 1е1х*) ( ю(,и*). Сопоставляя последнее неравенство с неравенством 17.19), получаем равенство 7я1х*) = ю(р*). Пусть для х* Е й и тт* е й!~ верно равенство 17.20). Тогда, согласно теореме 7.9., точка х* является точкой наименьшего значения функции Д(х) на Й, а точка и* -- точкой наибольшего значения функции тц(р) на Б,"'. При этом ш(р*) = 1пу Цх, тз*) ( 1,(х', р ) ( Уо1х') = ш(7з*). яен Следовательно, т 1х*, тт') = шГ А1х, тт'). яей Кроме того, Ь(х*,1т*) = 7я(х*), откуда, используя равенство 17.13), определяющее функцию Лагранжа, заключаем, что та где 1т* = (1тм ..., а,'„). Так как все слагаемые в этом равенстве слева неотрицательны, то они все равны нулю, т.е.
выполняется условие 17.16). Согласно теореме 7.8, точка 1х, тт) является седловой точкой функции, Лагранжа. ~ Функцию ц~(р), определенную на К'„"' соотношением 17.18), называют двойстпвенной амуницией по отношению к целевой функции 7я(х). Задачу поиска точки и' е Б~ наибольшего значения этой функции называют двойстпвенной задачей по отношению к задаче минимизации функции 7е1х) на множестве й, а теорему 7.10 тпеоремой двойстпвснностпи. Установленные свойства функции в(р) дают возможность вместо задачи поиска точки наименьшего значения целевой функции Т. АНАЛИТИЧЕСКИЕ МЕТОДЫ решать двойственную задачу, которая может быть проще исходной. Найденное решение двойственной задачи далее можно использовать в качестве набора множителей Лагранжа и затем решать задачу минимизации функции Лагранжа.
Пример 7.3. В задаче о х1+ х2 — ~ шш 2 2 2Х1+ х1+ 4 < О найдем функцию ш(р), двойственную по отношению к целевой фу ц Ь(: ) =х1~+: ~~. В данном случае допустимое множество П представляет собой полуплоскость 2х1 + хе+ 4 < О. Чтобы найти двойственную функцию, нужно определить наименьшее значение функции Лагранжа Цхм хя, .р) = х1+ хз + р(2х1+ х2+ 4) при ограничении 2х1+ хе+4 < О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
