341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 58
Текст из файла (страница 58)
61,6; °,1269 1,6' 1- 0,126 Из таблицы следует, что х' т!а! = (0,99998; — 0,00194), у* в у(х16!) = — 1. Отметим, что точное решение рассматриваемой задачи х* = (1, 0), у" = -1. с В задачах 17.299 — 17.303 найти проекцию вгР = Р12(г) точки И Е Еи На УКаЗаННЫЕ МНОжЕСтВа У 6 Е„: 17.299. У = (х Е Еи(тт > О, У = 1, ..., 96) (неотРицательный оптант пространства Еи). 17.300. У = (х Е Си~а, < ту < Ьм у = 1, ..., я) (и-мерный параллелепипед). и х Е Еи!~~6 (и. — х ) ( Ло (замкнУтый шаР 1=1 17.301.
12' = (о) радиуса Ло с центром в точке х ) 21 17302. 12'= хЕЕи)~~ аух, =Ь, а=(а1, ..., а„) ~0 1=1 (гипсрплоскость с нормальным вектором а). п 17.303. У = х Е Е„~ ~~6 а ж > Ь, а = (а1, ...,а„) ~ 0 2=1 (полупространство в 891). Требуемая точность нс достигнута, так как ах!!6 — х<т!(! = 0,298 > > 0,01. Результаты остальных шагов метода проекции градиента приведены в слсдуюшсй таблице: Гл. 17. Методы оптимизации 410 Используя результаты решения подходяьцих задач 17.299- 17.303, решить задачи нелинейного программировшшя 17.304- 17.313 методом проекции градиента. Вычисления завершить при !!х(" ') — х(~)!! < 0,01: 17.304. у'(х) = хз1 + 4х~ ~+ Зх1хз + 2х| + 16хз — + пцц, х1>0, хз>0.
17.305. Г(~) = 9хз1 + хз з— 54х1 + 4хз -+ шш, х1>0, хз>0. 17.306.,Г(х) = хз1 + 9хз з— 12х1 — Збхз — > пнп, — 1 < хг (~ 4, 1 (~ хз < 2. п.ЗОТ. 1( ) = 2 д + ~. 2 5 < х1 < 8, 1 < хз < 10. 17.308. у" (х) = 2х1+ хз -+ пцп, (х1 4) + (хз 2) 17.309. у(х) = хзз — 8х1+ хз з— ~ пнп, х1+ (хз — 4) < 9. 17.310. Дх) = хз1+ хаз+ ха~+ х1+ хе+ хз — у пнп, х1+ хе+ хз = 3. 17.311. Г(х) = хз1 + хз з+ хз з— 4х1 — бхз — 2хз -у шш, 2х1+хз = 2 17.312. у'(х) = (х1 — 2) + (хз — 1) -+ пнп, 2х1+хз <2. 17.313. ~(х) = хз1 — хз -~ пнп, 2х1 — 2хз < 1.
Второй метод (метпод условного градиента). Пусть хйй Е Гу— очередное приближение к решению гладкой задачи выпуклого программирования (51), причем Г'(хйй) ф О. Тогда в окрестности точки хрй функция Г(х) представима в виде Г(х) = Г(х~"~) + (Г'(хйй), х — хбф) + о(бх — хрй (О, и линейная функция Ге(х) = (Г'(х~ Ч), х — х~"~) является приближением разности Г(х) — Дх~ "1) с точностью до величины о(йх — х®(!) в некоторой окрестности точки х~~~. Поставим вспомогательную задачу минимизации на множестве ГУ линейной функции уь(х), т.е. Гь(х) = (Г'(хнй), х — хйй) -+ пнп, х Е К (57) 3 4.
Нелинейное программирование 411 х~ ~ ~ = х~ ~ + сгь(х~ ~ — х~ ~), иь Е (О; 1). (58) В силу выпуклости допустимого множества х~ ~ ) е Н. Величина аь из (58) в различных варпюггах лютода условного градиента вычпслпстся по-разному. Опишем два способа определения аы 1. оь —— пйп (1, ггь), где оь найдено из условия наискорейшего спуска по направлению т1ь~ — х~ь~: Фь(а*„) = ийп Фь(о), где Фь(о) = Г(хбй + а>о + гг(х(Ь) х00)] 2. В начале выполнения итерации (58) полагают оь = 1, после чего проверяют условие /(х~ь'ь") < Г(хри). (50) Если оно нарушаетсл, та оь уменьшают (дроблт) в 2 раза ц повторна проверяют (50).
Дробление аь производит до выполнснип неравенства (50), после чего переходят к следующей итсраднц (68). Условие окончанггл вычислений по методу условного градиента совпадает с аналогичным условием метода проекции градиента. Отметим, что вспомогательная задача (57) явлается, вообще говерл, задачей нелинейного программирования. 5каа.см случаи, когда поиск ее решения х~ ~ не представляет затруднений. 1. Допустимое множество Н задано линейными ограничениями и условием неотрицательности переменных.
Тогда (57) — зто задача линейного программированип и се решение можно найти с помощью симплекс-метода (см. з 3). 2. Допустимое множество Н = (х 6 С„)и~ < ху < 51, у = 1, ..., и)— и-мерный параллелепипед. Тогда сели д/(хйй)/дху ) О, сели дГ(х~"'~)/дт, < О, если д/(тнй)/дх = О. ху оу, бч оз + 5, 2 (60) 3. Допустимое множество Н = х ц 6„~~~ (тз — У, ) < Но 08 т ~=1 шар радиуса Но с центром в точке уш~. Тогда 00 (о) Г'(ХОО) !/Г'(х(ь>) Ц Пример 6. Решить следующую задачу нелинейного программировании методом условного градиента, завершая вычисления при Пусть хрй — решение втой задачи. Слсдук~щее прибли вские хаты~ к точке минимума х* функции /(х) на множестве (/ найдем по формуле Гл.
17. Методы оптимизации 412 'бх1" '> — х~">!) < 0,1: ,7(х) = хг — 4хг + хг г— 2хг -л ш1п, 0 < хг ( 1, 0 ~ (хг < 2. < В качестве начального приблигкения выберем, например, точку х1о> = = (О, О) Е Г Шаг 1. Найдем градиент Г'(х) = (2хг — 4, 2хг — 2) в точке х~~1: Г'(х1о1) = (-4, -2). Запишем вспомогательную задачу (57): уь(х) = (г'(хОО), х — хОО) = -4хг — 2хг -л пнп, 0(хг (1, 0(хг (2.
Зто аадача линейного программирования, ее можно решить симплекс-методом. Однако проще воспользоваться соотношениями (60), откуда следует х~а> = (1, 2). Найдем ао первым способам. В данном случае Фо(гг) = г"[х~о~ + гг(х~о~ — х~а~)) = у'(о, 2о) = бог — 8о. ИзусловияФо(а) = Онаходимгг = оо — — 0,8.Поэтому оо —— ш1п(1, 0,8) = = 0,8.
Вычислим очередное приближение хО~ по формуле (58): хбй = = (О, 0) + 0,8(1, 2) = (0,8; 1,6). Так как Цх~о> — хн>Ц = 1,79 ) 0,1, то требуемая точность не достигнута. Результаты вычислений на следующих шагах метода условного градиента приведены в следующей таблице: Онанчательно х* и х<е> = (0,957; 0,953), 7* г" (х~е1) = — 3,91. > Решить задачи нелинейного программирования 17.314-17.322 методом условного градиента, завершая вычисления при бх(~ — х(ь)'б < 0,1: г 4.
Нелинейное программирование 413 17.314. 1(х) = х1 + хг — бх1 — 4хг -+ ш!п, х1+ хг (2, х„х, >О. 17,315. Дх) = хг1 + 4хг г— 8х1 — 8хг -+ ппп, — 2 < х1 ( 2, 0<хг <3. 17.316. у (х) = е(г" *') + хг + хг г— 4х1 — 4хг -+ шш, 0 <х1<1, — 2<хг(3. 17.317. Дх) = )п (2+ хг1+ хг г— 2хг) + е(*' з*э) — ) ппп, х| > 3, хг>0.
17.318. Дх) = х1г+ хгг+ бх1 — 2хг -~ ппп, х1+хг > 1. 17.319. у'(х) = хг1 + хг г— 8х1+ 4хг -+ ппп, (х1 — 1)г+ (хг — 1)г > 1. 17.320. Дх) = 1п (хг1 + хг г-4х1 — бхг + 13) — 2х1 — хг -> ппп, (х1+ 2) +хг г< 4. 17,321. у'(х) = хг+ хг г— бх1 — Зхг + 5 -+ ппп, х1+хг (3, 2х1+ хг < 4, хыхг>0. 17.322.
Дх) = )п(хг+ хг г— бх1 — бхг+ 26) — х1 — хг -+ шш, х1+хг < 4, О < х1 < 3, 0(хг(2. 4. Методы штрафных и барьерных функций. Один из подходов к решению задачи нелинейного программирования Г(х) -~ пцп, х Е У основан на замене этой задачи последовательностью задач безусловной минимизации Д(х) = у'(х) + ~рь(х) — ~ пцп, х 6 Еп, Л = 1, 2, ..., (61) где уь(х) — функции, которые с ростом л во все большей степени учитывают ограниченин, определяющие допустимое множество У исходной задачи. В методе штрафньп функций функции дь(х) подбираются так, чтобы при больших к функцин уь(х) из (61) мало отличалась от 7(х) при х 6 У и быстро возрастала при удалении точки х 6 У от допустимого множества Г Гл.
17. Методы оптимизации 414 Определение. Пусть У С б„— заданное глножество. Последова- тельность функций (рь(х)), определенных в с„и обладаюших свойст- вом ~ О, если хбУ, !нп рь(х) = ь-~с ( +ос, если х ф (7, называется последоеаглельностыо шглрафкмх функций множества У.
Рассмотрим один из вариантов метода штрафных фуннций приближенного решения задачи нелинейного программирования Г(х) -ь го!и, д„.(х) = О, 1 = 1, ..., 1, д,(х) < О, 1=1+1,..., ти, (62) считая, что функции у'(х), д;(х), 1 = 1, ..., ш, ааданы во всем пространстве Г„. Полол~им ~рь(х) = )с~р(х), ус = 1, 2, ..., (63) где р(х) = ~~ д~(х) + ~ ~[ду(х))т, ( О, если д,(х) < О, д, (х) = с ( д;(х), если д,(х) > О. Равенства (63) определяет последовательность штрафных функций допустимого множества задачи (62) (проверьте!). При определенных условиях последовательность решений задач безусловной минимизации (61), (63) сходится к решению х* задачи (62), поэтому для достаточно больших Й полагают х" — х!ь!, т* у(хрй). Критерием достижения требуемой точности решенил задачи (62) может служить неравенство !)хйй х!ь!т!!! < е (64) где с > Π— - число, характеризуюшее точносттч й — — четное число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
