Изучение математических дисциплин в компьютерной среде, страница 8

Формулировать, объяснять и формализовывать стратегию решения задачи НП при отсутствии ограничений с использованием численных методов:— градиентного спуска;— наискорейшего спуска;— покоординатного спуска;— Гаусса—Зейделя;— сопряженных градиентов (Полака—Рибьера);— переменной метрики Дэвид она1—Флетчера—Пауэлла (Дт-Ф—П);— Ньютона;— Марквардта;— Хука—Дживса (метод конфигураций);— Нелдера—Мида;— случайного поиска с постоянным радиусом;5.

Использовать численные методы для практического решениязадач НП на ПЭВМ с применением лабораторного практикума;6. Анализировать и объяснять результаты численного решения задач.434.3. Порядок самостоятельной! работы студента над изучениемматериала с использованием компьютерного курса1. Выберите один из трех разделов для изучения.2. Ознакомьтесь с составом требуемых знаний по выбранному разделу (см. разд.

4.2).3. Изучите необходимый материал, пользуясь конспектом лекций,отметив непонятные места.4. Составьте план дальнейшей работы, перечислив те действия,которые Вы хотите осуществить с помощью КК. В состав этих действий может входить:— ознакомление с оглавлением КК;— работа со справочным материалом по накоплению информации;— ознакомление с порядком изучения темы путем анализа ееструктурной модели;— проверка знания формулировок определений, теорем, алгоритмов;— выработка понимания теории;— самостоятельное решение упражнений;— обучение решению упражнений;— выработка умения решать типовые задачи минимизации ФМП сиспользованием лабораторного практикума.Информация об этих возможностях содержится в главном менюКК.5.

Осуществите намеченные виды работ с использованием КК. Информацию о последовательности действий Вы найдете в меню КК,расположенном в нижней части экрана дисплея. Если «знаний», заложенных в КК, окажется недостаточно, для того чтобы Вы полностьюусвоили изучаемый материал, обратитесь для получения интересующей Вас информации к [7, 9].6. По завершении работы с КК, ознакомьтесь с ее результатами.,Вы можете:t— узнать перечень вопросов, на которые Вы дали неверные ответы в ходе контроля Ваших знаний;•— уточнить круг вопросов, над пониманием которых Вам следуетпродолжить работу;— ознакомиться с названием разделов КК, работу над которымиследует продолжить.Эту информацию Вы получите в КК по своему запросу по окончании контроля понимания теории.7. Для закрепления пройденного материала по каждому из трехразделов Вы должны выполнить дополнительные задания с использованием КК в качестве справочного материала, а также в режиме, лабо44раторного практикума.

Список дополнительных заданий приведен вразд. 4.4. В случае затруднений при самостоятельном выполнении задания^ обратитесь за консультацией к преподавателю.4.4. Дополнительные задания для самостоятельного выполнения покурсу «Задачи нелинейного программирования при отсутствииограничений»Раздел 1. «Постановка задачи НП при отсутствии ограничений»Задание.1. Запищите постановку задачи НП при отсутствии ограничений ипроверьте правильность записи по КК.2. Проверьте по КК знание понятий: множество допустимых решений, минимум функции, нижняя грань функции.3.

Проверьте, знаете ли Вы, чем отличается задача НП при отсутствии ограничений от вариационной задачи.4. Классифицируйте следующие задачи:) —> min; х = (х i ,х2,. ■ - , х п ) т ;Ь)/О) = х3 —> min; х < 3;с)/(х)>min; функция/(х) определена на множествеd)f(x) =x\ + xl X=R n . -> min .fX2О т в е т : задачи а, с, d — задачи безусловной минимизацииf(x), задача b — задача условной минимизации/(х) при ограничениитипа неравенств.Раздел 2. «Аппарат необходимых и достаточных условийэкстремума ФМП»Задание.1.

Пользуясь КК, проверьте знание:— формулировок теорем о необходимых и достаточных условияхминимума ФМП;— понятий: градиент функции, матрица Гессе, собственное числоматрицы, определенно положительная, полуопределенная, знаконеопределенная матрица, стационарная точка функции, точка минимума,выпуклая функция, разложение функции в ряд Тейлора;— формулировок критерия Сильвестра, критериев выпуклостифункций.2. Проверьте свое умение решать задачи НП при отсутствии ограничений с использованием аппарата необходимых и достаточных ус45Задача 1.

f(x)=3x2 +2х\+х\-2ххх2-2х\х3+2х2х3-Ьхх-Ах2-2х3 —> min . Задача 2.Определите тип квадратичной формы: а)/(*)=*?+2* |-Зхз-6* 1*2 + *Х\Хъ-4х 2 ху,А, В, С>0;c)f(x)=x^+5x%+3xj+4x1x2-2x2x3-2xlx3 .ловий. Бели Вы испытываете затруднения, обратитесь к КК инаучитесь решать типовые упражнения в режиме пошаговогообучения.3. Решите самостоятельно, используя КК как справочник,следующие задачи, проверив результаты решения по табл. 4.1.Таблица 4.1НомерОТВЕТ1х* = (2, 1, 2)т — точка минимума2Квадратичная форма: а) знаконеопределена в)отрицательно полуопределена с) положительноопределена3Тип точки х * : a), d) — точка минимума; Ь), е) —точка максимума; с) — седлоЗадача 3.

Что можно сказать о точке х *, если в ней градиентфункции равен нулю и при этом: &)/(*) — выпуклая функция;Ь)/(х) — вогнутая функция;c) Н(х *) — знаконеопределена;d) Н (х *) — определено положительная;e) Н (х *) -г- определенно отрицательная.Задача 4. В результате решения задачи?45**=(!,1)т6х* = ЧА7х * = (0,0) т — седло8Функция экстремума не имеет9х* = ( 1 , 1 ) т , #(х*)>010111246Тип точки х : х ', х 4 — не являютсястационарными точками; х — точка минимума;х — седло21) 2 ] —>eXtFнайдены следующие точки:а)* 1 = ( 0 , 0 ) т ; b) JC2 =(0,1)т;d)*( , )Классифицируйте эти точки.З а д а ч а 5 .

f (x ) = 1 0 0 ( x 2 - x f ) 2 + ( 1 - X j )-> min2Типы линий уровня1 а), Ь) — эллипс; с) —однополостный гиперболоидТипы стационарных точек а) х * =( 0 , 0 ) т — точка минимума Ь)дс= ( 0 , 0 ) т — точка минимума с)х* =( 0 , 0 ) т —седлоЗадача 6.f(x) = 2x + 16/х —> min .Задача 7.f(x) = * 2 -18*l --> extr .Задача 8. Имеет ли функция/(х) = 1+х+х2 + ( \/Ъ)хъ экстремум?Задача 9.f(x) = -(x 2 -x l ) 4 + ( 1 - х , ) 2 —> min .Задача 10. Укажите типы линий уровня с уравнением/(х) = 5, ес-ли:2;Ъ)/(х)=х +2х1х2+х2;lc/=/(**)+ (V/(x*) $) + (l/2)*aiHT(x )£),где/(ж*) , = 1 ,)=(2,-1)т#(**) = Уf(xl 4 3'-3 -2АЛЗадача 11.

В задаче 10 определите типы стационарных точек функций и их координаты.Задача 12. Аппроксимируйте в точке х к = ( 1,1) т функциюf {x)=x\ + Х \Х 2 -х \х \ к в адр ат ич но й ф о р м о й / (£ ).Раздел 3. Численные методы решения задач НПпри отсутствии ограниченийЗадание 1.1. Назовите градиентные методы 1-го порядка и проверьте правильность ответа по структурной модели КК.2. Проверьте знание алгоритмов градиентных методов 1-го порядка и умение применять их к решению упражнений и задач, используяКК.3. Укажите сходства и различия методов градиентного и наискорейшего спуска.4.

Укажите сходства и различия методов покоординатного спускаи Гаусса—Зейделя.5. Входит ли алгоритм градиентного наискорейшего спуска в процедуру метода Полака—Рибьера?6. Совпадают ли методы Полака—Рибьера и Флетчера—Ривса, если минимизируемая функция квадратична?7.f(x) = 48xi+xix 2 +lSx2. Какой из двух методов (Флетчера—Ривса или градиентного наискорейшего спуска) позволяет найти точкуминимума за 1 шаг из любой начальной точки?8. Докажите, что в точках последовательности {хк, Аг = 0,1,... } , построенной для решения задач минимизации функции/ (JC)=JCT* А *х,А > 0 будут справедливы утверждения:*)) = 0;9. Повторите определение понятия Н- со пряженных направлений.10.

Повторите теоремы сходимости алгоритмов методов:— градиентного спуска;— наискорейшего спуска;—покоординатного спуска;— Гаусса—Зейделя;— сопряженных градиентов.11. Решите следующие задачи градиентными методами 1-го порядка и проверьте правильность решения по табл. 4.2.48Таблица 4.2НомерОТВЕТ1х * = ( - 3 / 1 6, -1/ 8 ) т2х1 = {-\.г,г\ьу3Число итераций л = 1, х * = (0,0)т...х е = (*?, 0 ) т , где*?—любоечиело456х* = ( 0 , 0 ) т7.Достаточные условия минимума выполняются8х * = (0,0,0)т, задача решается методом Флетчера—Ривса9/• = 010Применение метода градиентного спуска не будет успешным, /*= -~.11Проекции вектора d 2 удовлетворяют уравнению3d?+3d?+d3=012Направления d ° и d' являются Я-сопряженнымиЗадача 1.

f(x)=4x\ +Ъх\-4х i*2+x i —> min , x]= ( 0 , 0 ) T.Найти x * методом Флетчера—Ривса.Задача 2. f(x)=8x^+4xiX2 +5x2 —> min , х = (10,10)т. Найтиточку х ^методом градиентного наискорейшего спуска.Задача 3. /(х)=х? + 48х| —> min, x° = ( 0 , 1 0 ) т . За сколькоитераций найдется решение задачи методом градиентного наискорейшего спуска? Определите координаты точки х *.Задача 4. Запишите координаты точки х , из которой можно найти стационарную точку функции/(х)=х\-х\ методом градиентногоспуска.Задача-5./(*) = In(х) —> inf.

Решите задачу методом градиентного спуска.49Задача 6. f(x) = (x j -a \ *x\)(xx-a\*x\), ax, a 2 >0. В ка кой2точке x * кривой с уравнением х \ = 0.5ia + a2)x2 Функция/(дс) достигает максимума?Задача 7. fix)-2хf + 4х \х\- Юл: \Х2+х\ -*-> min. Решите задачу методом Полака—Рибьера и проверьте выполнение достаточныхусловий минимума в точке х *.Задача 8. f(x) =х? + 100х\ + ЮООх\ + 42х \Х2 + 88л;2х3 —>min.Определите метод, позволяющий найти решение задачи за наименьшее число итераций. Найдите координаты точки х *.Задача 9. Функция f(x) не является ограниченной снизу. Что будет результатом решения задачи fix) —>min методом Флетчера—Ривса?Задача 10.