3 часть (1081356), страница 60
Текст из файла (страница 60)
Для решения задач (61) можно использовать методы безусловной минимизации, рассмотренные в 3 2. Если в задаче (62) г" (х) — выпуклая квадратичная функция, а д,(х), 1 = 1,, тп, — линейные функции, то точное решение вспомогательной задачи (61) можно найти из системы линейных уравнений д(ь(х)/дху = О, у = 1,..., п, опредсляюших стационарную точку функция !ь(х).
3 4. Нелинейное программирование 415 Пример 7. Методом штрафных функций решить следуюшую задачу нелинейного программировании: ,/(х) = 2хэс + тээ -~ ппп, дс(х) = -хс — тэ + 2 4 О, дэ(х) = тс — 2тэ + 1 ( О, дэ(х) = — 2зс + хэ ( О. (65) уь(х) = /(х) + /с[д,(х) + дэ(х) + дэ(х)[ = = (2 + 6/с)хс~ + (1 + 6/с)хэ э— бйхс хэ — 2/схс — 8/схэ + 5й. Решив систему уравнений — = (4 + 12/с)хс — б/схэ — 2/с = О, д/ь(х) дхг — = — бйх, + (2+ 12/с)хэ — 8й = О, дуь(х) дХ2 находим 18йэ + й ОО 27/сэ + 8/с 27И+18И+ 2' 27И+ 181+ 2 Так как дэ(х ' ) = -2х, + хэ = , < О при всех /ц Оц Оц -Ой + 6/с 271л + 18/с+ 2 /1 = 1, 2, ..., то предположение дэ(х/ц) > О не подтвердилось.
2. Предположим, что д,(хрй) < О, с = 2, 3, дс(хбц) > О. Тогда д+(хрй) = О, с = 2, 3; д+(хсЦ) = дс(хбй), поэтому считаем, что /ь(х) = = /(х) + /сдсэ(х) = (2 + /с)хэ + (1 + й)хээ + 2йтс та — 41зс — 4/стэ + 4й, откуда находим 2/с /ц 4й Зй+ 2' э ЗА+ 2' (66) Э Целевая функция /(х) является выпуклой (проверьте!) квадратичной функцией, а ограничения, определяюшие допустимое множество задачи, линейны. Поэтому решение хбй вспомогательной задачи (61) для любого й = 1, 2,... может быть найдено точно из условия /ь(хбЦ) = О.
Так как функция ссь(х) из (63) в различных областях пространства Е задана по-разному, то при составлении вспомогательной функции уэ(х) следует сделать определенное предположение о расположении ее точки минимума хрй. 1. Предположим, что в точке хОЦ безусловного минимума функции /ь(х) все ограничения задачи (65) нарушаются, т.е.
д;(хрй) > О, 1 = 1, 2, 3. Тогда д[ь(хбц) = д;(х/Ц), 1 = 1, 2, 3, поэтому считаем, что Гл. 17. Методы оптимизации 416 Легко проверить, что сделанное предположение подтверждается, т.с. равенства !66) определяют точку безусловного минимума х1ь! вспомогательной функции Уь(х) из 161) (убедитесь!). /2 41 .. 8 Окончательно находим х' = 1цп хр6 = ~ —; -(, у* = 1!х') = —. в ~со 3 3 3 Отметим, что для решения вспомогательных задач !61) можно было использовать и приближенные !например, градиентные) методы безусловной минимизации 1см.
З 2). Тогда, если требуемая точность решения задачи нелинейного программирования !65) задана числом г нз !64), равным, например, 0,01, то получим х* и хнто! = !0,6630; 1,3260), у' и Дхнзе1) = 2,6373, так как ((хите! — х!ао1(! = 0,01. !> Решить задачи нелинейного программирования 17.323 — 17.332 методом штрафных функций, полагая х* -х! "1 прн !!х!" 1 — х!"/з) !! < < 0,05: 17.323. у!х) = х~~ + х~ ~— 20хг — ЗОхз -+ пнп 2хг + Зхз — 13 ( О, 2хг + хз — 10 < О.
17.324. Дх) = х~г + х~ ~— 10хг — 15хз -+ пнп, бх~ + 13хз — 51 ( О, 15хг + 7хз — 107 < О. 17.325. Дх) = х~+ ха~ — 5х~ — 4хз — > ппп, 2х! + Зхз+ хз = 6. 17.326. Дх) = х~~ + хз ~— 5х~ — 10хз -+ ппп, 9хг + 8хз — 72 < О, хг + 2хз — 10 ( О. 17.327.
Дх) = х~г — 2хг — хз -ь ппп, 2хг+ Зхг — 6 < О, 2х~+ ха — 4 < О. 17.328. у (х) = х~ ~— 2хз + 2хг + хз -+ гп)п, хг + Зхз + 2хз — 6 < О, Зх~ + ха+ хз — 2 ( 0 17.329. Дх) = — хг + хз ~— 2хз — ч ппп, Зх~~ + 2х~~ — 6 ( О. 17,330. Дх) = х~г + х~ ~— бхг — Зхз -+ гпш х, + х2 29 < О. э 4. Нелинейное программирование 417 17.331. 7(х) = тс+.т~з — Зхт -+ шсп, — 2хс .!. г~ ~< О .тч — 2хг < О. 17.332. у'(х) = — хс — 4тт — ~ шш хс +ха — 1 < О, — жс + аз ~< О. у(х) -+ шш, д(х)<0, с=1,...,п.
(67) Половсим ссь(х) = -са(х), 1. = 1, 2, ..., 1 (68) где ьь ср(х) = ~]д„(х)] ', р > О, ~=1 (69) или са(х) = — ~~с 1п ] — дз(х)]. (70) Выравсиия (68)-(70) определяют последовательность барьерных функций допустимого множества У задачи (67) (проверьте!). Пусть хрй — решение задачи безусловной минимизации (61), где функция Сьь(х) определена равенствами (68), (69) или (68), (70). Полагая х' = х!'с, У* у(хСЫ) для достаточно большого )с, находим прнблиасеннос решение задачи нелинейного программирования (67) мета- В зсепсодс барьерных функций исходная задача нелинейного програьслсирования также сводится к последовательности задач безусловной минимизации (61), но функции саь(х) выбираются таким образом, стобы при больших Й функции гь(х) из (61) мало отличались от 1'(х) во внутренних точках х допустимого множества У и в то всс время прп приближении точки х б У к границе множества У эги функции неограниченно возрастали. Определение.
Пусть мновсство У С Е„задано. Последовательность функцссй (!аь(х)), определенных во всех внутренних точках множества У, называется послсдоааспсльностью барьерных функций этого множества, если выполняются условия: 1. !цп срь(х) = 0 длн любой фиксированной внутренней точки х умнохссства Г: 2. 1пп Уь(хС'!) =+со длЯ любой последовательности (х!"!) внУ- трснних точек множества У, сходяшсйся к какой-либо граничной точке этого мновсества. Рассьсотриьс некоторые варианты метода барьерных функций решения слсдуюшей задачи нелинейного программирования: 418 Гл.
17. Методы оптимизации дом барьерных функций. Для контроля достигнутой точности решения можно использовать критерий (64). Пример 8. Решить следующую задачу нелинейного программирования методом барьерных функций, полагая х' х' ' при 00 !!х~ь1 — х("ух~ Ц < 0,002: ,Г"(х) = хх + 2хте -> ппп, д~(х) = -х~ + хх < О, рх(х) = 1 — х~ — хт < О. з Используем последовательность барьерных функций (68),(70). Тогда задача (61) принимает вид уь(х) = х, + 2хх — -[!и (х~ — хг) + 1и (х, + хх — 1)) -~ ш1п, х Е Е„.
2 2 й Решая ее методом Ньютона (см. а 2) при (с = 500 и 1 = 1000, получаем х(ьоо) (О 6696; 0,3319) хОооо) (О 6682; 0,3326). Так как Цх1юао — х1ъоо)// 165 10 — з < 0002, полагаем х' в хОооо~ (06696. 0 3319) У = Дх1 )) = 0,6687. > Решить задачи нелинейного программирования 17.333-17.339 методом барьерньгх функций, полагая х* = х(ь) при бх(") — х(ьУз) (~ < < 0,05: 17.333. Дх) = хе~ — 2хз — хг -+ ппп, х~~ + х~ ~— 4 < О. 17.334. У" (х) = хзг + х~ ~— 10х~ — 8хз + 3 -+ пцп, хг + 2хз ~— 2 < О, 2хг + хз — 2 ~< О. 17.335. у'(х) = — 2х~ + х~~ — хз + 2 -+ ппп, 2х~~ + Зх~ ~— 6 < О. 17.336.
у (х) = хз, + х~ ~— 8хг — 4хз + 3 — + ппп, х~+хз — 8<0. 17.337. )'(х) = х~ + хз ~— Зх~ + 1 — ~ ш)п, хе~ — 2хз < О, — 2х~+хг <О. 17.338. У(х) = — хг — бхай -+ шш х,+ха — 1<О, — хг+2хз <О. 9 5. Дискретное динамическое лрограмми ование 419 17.339. у(х) = 9(х) — 5)- + 4(хз — 5) -+ )шц, х)~ — 2х) — хз + 1 < О, — х) +хз — 1 <О, х) — хз < О. 9 5. Дискретиое динамическое лрограммиронаиие В этом параграфе рассматриваются многошогооые задачи оптимизации, т. е, задачи, оптимизацию в которых молгно представить в виде рлда последовательных этапов (шагов). Предположим, что состояние некоторого процесса илп объекта описывается и-мерным вектором х = (хм хэ, ..., х„), нли, что то же самое, то и ой х пространства Е„, которое называют фазовым пространством, Будем считать, что процесс является Л-шаговьгм, т.е.
его эволюция происходит в М этапов (шагов) в соответствии со следующей схемой: хбо -э -) х)ь ') — > х~ь) -+ — ) х)к) ь-й жаг Переход между состояниями на я-ы шаге происходит в соответствии с уравнением состояний 1)ь)(х)ь — 3) н)ь)) где и'" б Е,„— т-мерный вектор управления, выбираемый на )с-м ОО шаге, Г ) (х, и) — заданная и-мерная вектор-функция аргументов х б (ь) б Ев, цбЕ„,.
Таким образом, предполагаотся, что в результате 9-го шага процесс переходит в состояние х)ь), которое опрелеляется только начальным состоянием х)ь ') этого шага и выбранным на нем вектором управления н1 1 и нс зависит от «предыстории» процесса до Й-го шага, т.е. от (ь) х<о) ., х'"-з) и ни) ... ц)ь-". Покааателем эффективности )с-го шага является заданная числовая характеристика (целевая функция этого шага),Уь = дь(х)ь-') пИ)) 9— =1,2,...,М. Прелположим, что эффективность всего процесса в целом характеризуется целевой функцией вида ,У(х, й) = ~ дь(х) ' '), ц)ь)), (2) где х = (х~ ), х) 1, ..., х) ~) — набор состояний, называемый )))озавой траекторией процесса, а й = (и, и,, и ) — набор векторов г и) )2) )М) управления, который называется управлением процессом.
Таким образом, рассматриваются только аддитианьсе целевые функции,У, представимые в виде суммы целевых функций шагов дь. Гл. 17. Методы оптимизации 420 Предположим далее, что на фазовую траекторию и выбор управлений наложены ограничения хр« сХя к — 1, ° ° ° М 1, (3) ирй б Суь(х~ «), к = 1,..., Х, (4) где Хь и Сгь(х~а «) — заданные множества в пространствах Г„и с;ь соответственно, причем множество (Уя зависит, вообще говоря, от начального состояния х~ь «к-го шага. Ограничения на начальное н конечное состояния процесса х~ 1 Е Хо, х~ ~ Е Х,ч д(т, й) = г дь(х~ь 1~, нр«) — > схсгв), (5) хр« = Грб(х~я «п~ь~) 1 = 1 (б) х~ь~ Е Хя, ц~ь~' Е 1Уь(х~ь «), хйй Е Хо, х1в« ~ Хп. Й = 1, ..., 11у — 1, (7) (8) (9) ) Символом ехьг мы будем обозначать минимум кян максимум соответствующей функции, э зависимости от смысла задачи. Несмотря ка то, что задачу на максимум целевой функции д всегда можно свести к задаче минимизации — д -э ппц, мы будем рассматривать н задачи на максимум, используя обозначекне д -у плах, чтобы математические постановки этих задач соответствовали их прикладному смыслу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
