XIV Аттетков и др. Методы оптимизации (1081420), страница 47
Текст из файла (страница 47)
Такую задачу можно решить, используя теорему Куна -- Таккера: для функции Е(хм хезби), считая р фиксированным, построить функцию Лагранжа (т.е. функцию Лагранжа для функции Лагранжа), для чего необходимо ввести параметры Ле и р; затем на основании теоремы Куна Таккера записать систему четырех уравнений относительно неизвестных хм хз, Ав и в и решить ее; среди найденных точек путем сравнения выбрать ту, в которой функция Х(хмхз,ц) принимает наименьшее значение. Учитывая, что функция Е(хмх2, р) при фиксированном р является квадратичной с положительно определенной матрицей, а значит, сильно выпуклой функцией (см. пример 3.13), .можно утверждать, что она достигает на полуплоскости 2х1+ хе+ 4 < О (зто выпуклое множество) наименьшего значения (см. теорему 3.19).
Следовательно, выбранная точка будет точкой наименьшего значения функции Е(хмхзор). Значение функции Е(хмх2,р) в выбранной точке, зависящее от р, и есть значение функции ю(р) при фиксированном р. 325 7.аь двойственная функция Мы, однако, отступим от этой стандартной последовательности действий и учтем специфику рассматриваемой задачи. В выражении для функции, Лагранжа А1х1,хз,р) выделим полные квадраты по переменным х1 и х2 и запишем эту функцию следующим образом: х'1х1,хг;р) = 1х1+р) + 1х2+р/2) +40 — — р 21 — р) + ( — — ) + 4 < О., 2 или р ) 8/5. Расстояние р(р) от точки ( — р, — 12/2) до прямой 2х1+ х2+ 4 = О равно [ПЦ ! — 2р, — р/2+ 4! ъ'5 Следовательно, (4 — 5р/2) 2 16 5 р '1 р) = = — — 4р+ -р'. 5 4 В результате получаем 1б (и) = 4 б 2 О<р<-.; 8 8 р > В.
Из этого представления вытекает, что значением функции Лагранжа является квадрат расстояния от точки ( — р,, — р/2) до точки 1х1, х2) плюс величина 4р — — р, не зависящая от 2 точки 1хм х2). Следовательно, .наименьшее значение функции Лагранжа (т.е. значение двойственной функции ю1р) ) равно квадрату расстояния от точки 1 — р, — р/2) до полуплоскости й плюс 412 — — р . Если точка 1 — р, — р/2) попадает в й, то 2 расстояние от нее до й равно нулю. Если же 1 — р, — р/2) ф й, то это расстояние есть расстояние от точки 1 — р, — р/2) до границы множества й -- прямой 2х1+ х2+4 = О.
Условие ( — р, — р/2) Е й означает, что 7. АНАЛИТИИЕСИИЕ МЕТОДЫ 7.6. Геометрическое программирование В общей задаче геометрического программирования УО(х) -+ щйц уь(х) < 1, к = 1., К, тоь ув(х) = 2~~ евгрвь(х), 1=1 (7.21) где св; Е К„ь, 1 = 1, тв, ~о~ РОАх) — П х ", ь = 1, то, а=1 (7.22) а, Е 2„1 = 1, тв, 1 = 1, и. <О) Аналогично оч уь(х) =~ еирь,(х), й=1,К, (7.23) где сы Е Б',, к = 1, .К, 1 = 1, тв, П р~:,1х) = Пх,", й = 1, К, ~ = 1, ть, (7.24) а, некоторые действительные числа.
(ь) Особенность сформулированной зада ~и оптимизации в том, что целевая функция и левые части ограничений определены не на всем п-мерном линейном арифметическом пространстве. и целевая функция уе(х), и левые части ограничений уь(х), Й = 1, К, являются позиномами, определенными на положи; тельном орп~анте Кнь. Поэтому мы можем записать 327 7.6.
Геометрическое программирование Еуе>-П( —,"„;.) ' т=! !=! где у! > О, !о! > О, ! =1, гао и !о! = 1. г=! В данном случае удобно преобразовать неравенство таким образом, чтобы в нем не использовались нормированные веса. Для этого выполним замену и(! = Л,/Л, ! = 1, и!, где Л = Л! +... ... + Л,. Тогда неравенство взвешенных средних можно записать в виде (7 2о) Используем это неравенство для оценки позиномов уь(х). Выберем в качестве весов произвольные числа Лы > О, ! = 1, и!еэ й = О, К, и положим чае л =~ л„,;, г=! й = О, К.
Тогда, учитывая запись позиномов уь(ж) в виде суммы функций еырь!(х) специального вида, из неравенства 17.25) получаем т! уе!,х) >ЛуП( ), 1=О,К. (7.26) л„, Поэтому непосредственное использование приемов решения общей задачи нелинейного ироераммирования !см. 7.3 — 7.5) в данном случае невозможно. Выходом из положения может быть замена переменных х = е!!, ! = 1, н, преобразующая навином в функцию, определенную на всем линейном арифметическом пространстве. Однако в задачах геометрического программирования проще использовать другой подход, базирующийся на неравенстве вове!венных средних 328 7. АНАЛИТИЧЕСКИЕ МЕТОДЫ К К т), Пу"(х) ~П""П("'р'*))" в=1 я=1 Лы Для точек х допустимого мноо(сества й выполняются нера- венства уь(х) ( 1, й = 1, К.
Значит, левая часть записанного неравенства но превышает единицы и '- П"'П('""*') "' В=) 1=1 Умножая это неравенство на неравенство (7.26) для целевой функции ро(х) (т.е. при й = О), возведенное в степень Ло, заключаем, что ,„ло~ ) П л„П(сыры(,х) ) х" й=.о 1=1 Лы (7.27) Напомним, что последнее неравенство верно при произвольном выборе чисел Лы > О, 1=1,. тпь, 1 = 0, К. Пусть числа Ло„1 = 1, )па, связаны равенством РПО Л, = ~Л„=1. (7.28) Тогда, используя выражения 17.22) и (7.24) для рь,(х), 1 = 1, 1оы 1с = О, К, неравенство 17.27) можно преобразовать к виду 7 (')~ (П(",.) ") П~" П(',"',) П',"' о~9) 2=0 Ь=1 1=1 7,=1 Все части этих неравенств положительны. Поэтому, возведя обе части неравенства для позинома Иь(х), й = 1, К, в степень Ль и перемножив левые и правые части всех полученных неравенств, получим новое неравенство 7.6. Гвоиотрииеоиов прогривьиироиииие где ав — — 7 Л а, ЛЫ, до=1,п.
00 (7.30) в.=о ~=1 Пусть числа Лоб й = 1, К, т' = 1, ты выбраны так, что выпол- няются ус.вопия ортогоналиности, т.е. о, = О, д = 1., и. Тогда правая часть в (7.29) не будет зависеть от переменных х и мы придем к соотношению Си.: Евдокимов А.Г. где ю Е К",' .
точка с неотрицательными координатами Лы ) О, Й = О,К, г =1,тп~, тп = гпо+ т, + ... +7пк. Функцию сУю), как и в случае задачи минимизации позинома без ограничений, называют двойственной функцией по отношению к позиному Уо1х)- Ксли множество И'* точек ю С К~, координаты которых удовлетворяют равенству (7.28) и равенствам (7.30) с о = О, у = 1, п, не пусто, то целевая функция уо(х) на И", согласно (7.31), ограничена снизу и имеет конечную точную нижнюю грань М ) О, причем М) о~(ю) для любого ю С И'*.
Выбрав произвольную точку ю е И'*, можно использовать значение й(ю) в качестве оценки снизу точной нижней грани целевой функции. Очевидно, что если ро(х*) = о(ю*) для некоторых точек х* Е Й и ю* е И", то в точке х* целевая функция достигает наименьшего значения в Й, а в точке ю* двойственная функция достигает наибольшего значения в И"'. Можно показать',.
что верно и обратное: если целевая функция достигает в Й наименьшего значения в точке х", а двойственная функция достигает в И" наибольшего значения в точке ю', то уо(х*) = о(ю*). Таким 7. ЛНАЛИТИНЕСКИЕ МЕТОДЫ й(ю) -+ шзх: то ЛОя — 1~ 1=1 К па а.~~Л; = О, 1 = 1, и. О=О =-~ Значение д* является наименьшим значением функции РО(,в), которое она принимает в точке х*. Эту точку можно найти, исходя из равенства рО(ж*) = д*. Отметим, что неравенство УО(ж) ) д(н1) получено путем многократного применения неравенства взвешенных средних (7.25), которое обращается в равенство при выполнении условий РНЛ/Л; = 1, г = 1, т. Следовательно, равенство рО(:и*) = = И(ш*) означает, что все неравенства (7.26) превращаются в равенства, причем уь(ж*) = 1, к = 1, Л.
А зто возможно лишь при выполнении условий =1 1=1 ты 1=0,К. Лы Таким образом, точку ш' можно найти как решение системы уравнений РОА~) = ЛОг СОО Рь(ю) = Льсы ' г = 1, то, (7.32) 1=1,ты Й=1,Л, где учтено, что в соответствии с (7.28) ЛО = 1. Заменой т1 = = ООз, у' = 1, и, и последующим логарифмированием система образом, решение задачи минимизации функции уО(ж) в Й можно искать, решая задачу поиска точки максимума двойственной функции. Точку ш*и максимальное значение й" = д(ш') двойственной функции п(ш) находят как решение задачи 7.6. Геометринееное програиииронание Ях) = уг(х) + уз(х)(уз(х)), х Е К+, (7.33) где у;(х), г = 1, 2, 3, — позиномы, а !3 > О, в общем случае не является позиномом (она будет позиномом либо в случае, когда уз(х) состоит лишь из одного слагаемого, либо в случае натурального Д). Покажем, что задача минимизации функции Д(х) в К" равносильна задаче геометрического программирования у(я) = у! (х) + уз(х):~~ ! — ~ ппп., д(я) = <1, уз(х) хп-е ! (7.34) гДе Я = (х, хо е! ) = (хг, хзи ..., хо ег) Е К~~ .
Отметим, что если х* б К"' точка минимума функции !в1х), то точка я* = (х*, х,', г!) Е К"„', где х'„, = у!г(х*), удовлетворяет ограничению задачи (7.34). Поэтому эта точка принадлежит допустимому множеству й задачи (7.34) и 1о(х*) =Их*)+уз(хе)(уз(хе)) = = уг(х') + уз(х*Нх*„г!) = у!я*) > в!!ну(я). (7.35) ней В то же время из ограничения задачи вытекает, что для любой точки я = (х, .хо е!) е Й верно неравенство х„е! > Уз(х).
Следовательно, У(Я) = Уг1х) + Уз(х)хо-~-! > >у!(х)+уз(х)(у!г(х)) =Ях) > 7о(х*) и наименьшее значение функции у(я) на множестве Й не может быть меньше !"о(х*). (7.32) преобразуется в систему гп линейных игебраических уравнений относительно гг неизвестных ~ ., г = 1, п. К задаче геометричоского программирования сводятся некоторые задачи оптимизации, в которых целевая функция не является позиномом.
Например, функция 7. АНАЛИТИЧЕСКИЕ МЕТОДЫ Таким образом, задача минимизации функции Д(х) в К~~ и задача геометрического программирования (7.34) эквивалентны. Пример 7.4. Найдем минимум функции а Уо(х1,х2) =, +6 х', +х,'., х, > О, х2 > О, Х1:1 2 предполагая, что коэффициенты а, 6 положительны. Целевая функция рассматриваемой задачи имеет вид (7.33), где у1(х) = а((х1~х2), у2(х) = б, уз(х) = х21+ х2~,,3 = 1/2, х = = (х1, х2). В соответствии с изложенным выше сформулированная задача равносильна задаче геометрического програм- мирования а 11(х) = 2 + бзУхз — 1 шш Х1Х2 2 2 — + — (1, '1 2 хз хз (7.3б) ю = (Ло1, Лоз, Л11., Л12) Е 2„. Для упрошения выкладок введем обозначения Ло1 = ю1, Лоз = = ю2, Л11 = юз и Л12 = ю1.
Тогда условие нормировки (7.28) и условия ортогональности -- уравнения (7.30) при о, = О--- где х =(х1, х2, хз) бФ . Сопоставляя вид целевой функции у(х) с представлениями (7.21) и (7.22), а вид левой части ограничения с представлениями (7.23) и (7.24), определяем, что в данном случае п = 3, т~1 = 2, (31 (о) (о1 (о) (о1 (о) сш = а, со2 = Ь, а„= — 2, а,2 = — 1, а13 — — а2, — — а22 — — О, а23 —— (Ц 1Ц (Ц <Ц <Ц <Ц = 1,12, Л = 1, ш1 = 2, с11 — — с12 — — 1, а11 —— а22 — — 2, а12 — — а21 — — О (ц ю И О13 О23 Перейдем к задаче максимизации двойственной функции 11(ю). Так как то = т1 = 2, то 333 7.6.
Геометрическое програииироиаиие приводят к системе уравнений и11+ю2 = 1, — 2ю1 + 2юз = О, — и11+2ю4 = О, О,бюз — юз — ш1 = О. Множество решений этой системы есть множество И'*., на котором необходимо найти наибольшее значение двойственной функции. В системе четыре уравнения и четыре неизвестных. Несложно убедиться в том, что система имеет единственное решение ю1 = юз = 1/4, ю2 = 3/4, ю4 = 1/8. Таким образом, множество И'* содержит единственную точку ю' = = (1/4, 3/4, 1/4, 1/8), а задача поиска максимального значения двойственной функции оказывается тривиальной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
