341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 49
Текст из файла (страница 49)
Модифицированный метод Ньютона обеспечивает более устойчивую сходимость послодовательностн приближений к тоню минимума, чем метод Ньютона. Если начальное приближение хбй выбрано недостаточно близким к точке минимума х*, то даже для выпуклой функции /(х) последовательность (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, ..., гн, т=! Кроме того, количество сплава дол вно согтавлять бо кг, поэтому и ~,'ту=бе.
т=! Таким образом, математическое описание задачи об оптимальном составе сплава принимает вид у(х) = ~ с,х, -+ шш !=1 а„.х, < 6н Е у=! в а!ух >11, (г=1,...,н!), (7) (8) ху = бо, (9) о„х, +хв, — — 6„ Е !=! обх; — хвевьы = А Е т=! (!=1,.,.,ш), = бо, т=! х, > О, у = 1, ..., н + 2гп. с т=! х, ) О, у = 1, ...,и. Запишем эту задачу линейного программирования в каноническом виде. Среди ограничений (7)-(9) на переменные х содержится 2т неравенств (7), (8). Для преобразования пх в ограничении-равснства введем 2т дополнительных неотрицательных переменных хв.ь! и х„ьв,.~!, т=1, ..., ш. Прибавив переменные х„„, и левым частям соответствующих неравенств (7) и вычтл переменные хьч ь, из левых частей неравенств (8), получим задачу линейного программирования в каноническом виде ~а у(х) = у с,х -+ шш, т=! 356 Пл.
17. Методы оптимизации Составить математическое описание задач оптимизации 17.182-17.187, представив полученные задачи линейного программировании в каноническом виде: 17.182. Для изготовлении сплава из меди, олова и пинка в качестве сырья используют два сплава тех же металлов, отличающиеся составом и стоимостью.
Данные от этих сплавах приведены в таблице ЗА. Таблипа ЗД Получаемый сплав должен содержать не более 2 кг меди, не менее 3 кг олова, а содержание цинка может составлять от 7,2 до 12,8 кг. Определить количества х, 2 = 1, 2, сплавов каждого вида, обеспечивающие получение нового сплава с минимальными затратами на сырье.
17.183*. Длл изготовления двух видов изделий А~ и А2 завод использует в качестве сырья алюминий и медь. На изготовлении изделий заниты токарные и фрезерные станки. Исходные данные задачи приведены в таблице 3.2. Таба и па 3.2 Определить количества х, з = 1, 2, изделий А, которые необходимо изготовить для достижения максимальной прибыли. 17.184. Из одного города в другой ежедневно отправляютсл пассажирские и скорые поезда. В таблице 3.3 указаны: состав поезда '3 3. Линейное программирование 357 каждого типа, количество имеющихсн в парке вагонов различных видов для формировании поездов и максимальное число пассажиров, на которое рассчитан вагон каждого вида. Табл и па 3.3 Определить число скорых хс и пассажирских хт поездов, которые необходимо формировать ежедневно из имеюшегосн парка вагонов, чтобы число перевозимых пассажиров было максимальным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
