3 часть (1081356), страница 50
Текст из файла (страница 50)
у(х) = 2х) — 5хг + е*!+1*'. 17.161. у(х) = 2 3+ хг+ 2хгг+ хгз т) — хз. 17.162. Дх) = хг) + 2хгг + хгхг г+ хз + е*г+хг — хг + хз. 17.163. у(х) = 4 1+хг+хгг+ Зхз+ х) 2хг. 17 164. г (х) = 2х'", + хг + хгхг + хз + х) хз + х) + хг. 17.165. гг(х) = хг) + 5хгг + 2хз г+ сов (х) †.тг + хз). 17.166. у(х) = ес1+ '2 +1п(4+ хг ф 2хг), зг г.2 2 17.167. у (х) = х) + хг — 5хз + е*) ьгг'ге* . 17.138.)))=: 3 5.:, -5/5~.152),5:,5щ. г . 7' г)г+ гг — хзг) 17.169. Дх) = 2хг) +хгг+ 4хзг — 2в)п ( ). 2 17 173.
Д*) = 2 77й 5 гс) 5 3 5 *,, — .:, — . 17.171. Дх) = хг -)- хг -~- ез) сгг ~*э + хг — хг. 17172 Д ) = ., !), 3- 3 3 3~)ь 5 75 1 ... *'е- . 17!73.7) )=2;5 '.51 ) 5 )5835*'15*2. 17.174. г'(х) = х) + 10хг — Зхз + е* +'г-)* . 3. Методы безусловной минимизации, использующие вторые производные функции. Если при построении последоватсльности приближений в точно минимума фуннпии у(х) использовать инфориапию, содсржащук)с)! в значениях нс только первых, но и вторых производных у (х), то при определенных условипх можно обеспечип более быструю, чсл! в градиентных методах, сходимость втой последовательности. 3 2, Бсзусловнал минимизация функций многая переменных 351 Метод Ньютона применяется для безусловной минимизации выпуклых дважды диффсрснцирусмых функций.
В этом методе последовательные приближения х~ 4 к точке минимума функции /(х) строятся с ь) использованием первых и вторых производных слсдуюшим образом: х~ь" 0 = х00 — (/и(хйй)]-'У (хйй), ~ = О, 1, (13) где х~о~ 6 б„— начальное приближение, (/" (хйй)] ' — матрица, обратная матрипе вторых производных функции /(х) в точке х~"'>. 1(ритерием достижения требуемой точности вычислений обычно слув'ат неравенства (6). Если начальное приближение хйй достаточно блиако к точке минимума х*, то метод Ньютона сходится, как правило, гораздо быстрее гзетодов минимизации, использующих первые производные /(х), поэтому его часто используют на завсршаюшсм этапе минимизации при уточнении приближения к точке х', найденного другим, более простым методом.
Пример 7. Используя решение примера 4 в качестве начального прибли'кения метода Ньютона, найти точку минимума функции /(х) = = хе + 2хэ+ е*'ь*' с точностью]д/(хйб)/дх1] ( 10 ', 1= 1, 2. < Р1спользуя результаты решения примера 4, запишем 00 У 0 3012259~ у 69 У 2 6226об 1 .
10 з (о) 70~39319151 0~628678351 (,0,62867835 0,22329787/ ' Найдем ( си э Ййн-1 / 0 39319151 5 3404226 ' 10 1-5,3404226 10 э 0,22329787 откуда 7-0,30122591 ( 0,39319151 -5,3404226 10 э (,-0,1629096/ ( -5,3404226 10 ' 0,22329787 у 2,622655 1 10 э 7-0,31276411 " (,-2,296005/ ' (,-0,1563821/ ' Вычислив Г'(хы~) = (7,9 10 е, 7,9.10 ь), убеждаемся, что условие точности выполнено, т. с.
х' х0~ = ( — 0,3127641, — 0,1563821). Модифицированный метод Ньютона обеспечивает более устойчивую сходимость послодовательностн приближений к тоню минимума, чем метод Ньютона. Если начальное приближение хбй выбрано недостаточно близким к точке минимума х*, то даже для выпуклой функции /(х) последовательность (13) может нс сходиться к х*. Этот недостаток л1етода Ньютона Гл. 17. Методы оптимизации 352 будет устранен, если последовательность приближений (хйн) строить по модифицированной формуле х~~+О = хйо — аь[/" (хрй)) ~Г'(х®), 5 = О, 1, ..., (1!) где аь находится подобно (8) и (11): Фь(аь) = пйп Фь(а), а>0 Фь(а) = /(хйо — а[/л(хйй)] 'Г'(хйй)). Кроме того, для последовательности (14) всегда выполняется неравенство /(х~~4 0) < /(хйй), й = О, 1, ..., которое может нарушаться в случае (13) .
17 175. Показать, что точка минимума выпуклой квадратичной функции с помощью одной итерации метода Ньютона из произвольного начального приближения х ° Е Е„. (о) 17.176. Используя результат задачи 17.175, показать, что для нахождения точки минимума выпуклой квадратичной функции достаточно одной итерации модифипированного метода Ньютона при произвольном х( ) Е Е„. 17.177. Минимизировать одну из квадратичных функций задач 17.129 — 17.144 с помощью одной итерации метода Ньютона. 17.178.
Минимизировать функцию У(х) из задачи 17.148 методом Ньютона, используя произвольное начальное приближснис х() ЕЕ4. 17.179. Используя в качестве начального приближения решение одной из задач 17,149-17.174, полученное методом сопряженных градиентов, уточнить вто решение с помощью метода Ньк>- тона, заканчивая вычисления при [д/(х(ь))/дт,[ < 10 е, 4' = 1, 17.180. Показать, что если матрица /л(х(")) положительно определена и /'(х(~)) ф О, то направление р" = -[у" (х(ь))) ' 1'(х(ь~) является направлением убывания /(х) в точке х("), 17,181. Выбрав произвольное начальное приближение, минимизировать одну из функций задач 17.149-17.174 модифицированным методом Ньютона, используя критерий точности решения [д/(х(') )/дЦ ( 10 ~, 1 = 1, 2, ..., и. '3 3.
Линейное программирование 353 3 3. Линейное программирование аох, =6;, Е >=1 >=1,2,...,1; аох, < 6! ! = 1+ 1, ..., т; >=! х, >О, (2) найти те, а которые !рункцил у(х) = ~ ~с х принимает минималь>=1 ное значение, и определить это значение. Отметим, что в условии задачи линейного программирования могут содерв>аться неравенства и противоположного, чеы в (2), знава, однако такие неравенства легко сводятся к виду (2) умножением на — 1. Если в условии задачи линейного программирования нс содержатся ограничения-неравенства (2), т.е. в (1) 1 = т, то она называется задачей линейного программироаанил в каноническом виде.
Вводя дополнительные переменные хьь, > О, ! = 1 + 1, ..., т, ограничения-неравенства (2) можно записать в виде равенств аох, + х„~.! — — 6б Е >=1 ! =1+1,..., т. 1. Постановки задач линейного программирования. Графический метод решения. Задача минимизации функции и переменных у(х) = = у(х>, ...., х„) на некотором л>ножсстве У с б,ы не совпадаюшем со всем пространством сь и заданном с помошью ограничений (равенств и неравенств) на координаты х, т>гизи х б б>о называется задачей математлнческого программироаанил.
При этом функцик> 1(х) называют целевой д>ункцией, а ынол>ество 1! — допус>лимым множеством. Решение аадач математического программирования, как правило, связано со значительно ббльшими трудностями, чем решение задач безусловной минимизации, рассмотренных в 3 2. Простейшим частным случаем задачи математического программирования является задача линейного программирован! л, состояшая в минимизации линейной целевой функции у(х) = у(х>, ..., х„) п с>х, на множестве У С б>о заданном системой линейных ограни>=! чений (равенств и (или) неравенств) на координаты х, (у = 1, 2, ..., и).
Задача линейного программирования формулируется следуюшим образом. Среди точек х = (х>, ..., х„) б б„, удоалетаорлютцих ограниче- ниям Гл. 17. Методы оптимизации 354 Таким образом, любая залача линейного программирования может быть ааписана в каноническом виде и у(х) = ~~ сух, -+ пнп '), «=1 (3) абху=бь ь=1,...,т, Е у=! (4) (5) ху > О. Часто используется векторная запись задачи (3) — (5): у'(х) = (с, х) — ! пнп, Ах = Ъ, х>О, (6) веществ будет равна ~ ~с,х, руб. у=! ) Символ у(х) -ь ппп в записи условия задачи математического программирования используется вместо слов «минимизировать фрнкяою у(х)я. Далее указываются ограничения, опрелеляюшне допустимое множество.
где х = (хг, ..., х„) — вектор неизвестных, с = (с!, ..., с„) — вектор коэффициентов целевой функции из (3), А = (ай) — прямоугольнан матрица размера т х и, Ъ = (Ьг, ..., 6 ) — вектор правых частей системы (4), а х > 0 — краткая запись условий неотрицательности (5). Математические модели многих важных для практики задач оптимизации представляют собой задачи линейного программирования. П р и м е р 1. Составить математическое описание следующей задачи об оптимальном составе сплава и представить полученную задачу линейного программирования в каноническом ниле. Для приготовления 6о кг сплава с заданными свойствами используют вещества А,, у' = 1, ..., и. В х кг вещества А! содержится айх кг химического элемента Вн ! = 1,..., га.
Содержание элемента В, в сплаве должно заключаться в йределах от !3! до 6, кг. Стоимость 1 кг вещества А составляет с руб. Требуется определить такой состав для приготовления сплава, при котором общая стоимость израсходованных веществ минимальна.
з Обозначим х количество кг вещества Ау, используемое для приготовления сплава (очевидно х > О, у = 1, 2, ..., и). Тогда содержание о элемента В! в славе составит ~~ айх вг, а стоимость израсходованных у=! 3 3. Линейное прогрэ!,!!миров!!нис 355 Поэтому, с у югом огранич! ний на содержание элсмс!гсов В, в сплаве, ддя величин:г, получим следующие неравенства: ь Д! < ~~ а; ху < 6„1 = 1, ..., гн, т=! Кроме того, количество сплава дол вно согтавлять бо кг, поэтому и ~,'ту=бе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
