1. Исследование функции на безусловный экстремум 3

• Название: 1. Исследование функции на безусловный экстремум 3
• Дата: 20.12.2018
• Размер: 0.69 Mb.
• Имя файла: 1541130846473078.docx
• Тип: Исследование; #61169
• страница: 6 из 6

Контрольные задания

Задания 1-6 содержат параметр V = 2, который определяет вариант заданий.

Задание 1. Линии уровня

1.1. Приведите определение и свойства линии уровня функции нескольких переменных.

1.2. Укажите связь между линиями уровня и градиентами.

1.3. Постройте линии уровня U_α для функции

y = -V*x₁ + 2V*x₂

при α=0, α=1, α=2.

1.4. Постройте линию уровня U_α при α=3 для функции

y = x₁^2 –V*x₁*x₂ +2*x₂^2 + V*x₁.

Вычислите и нарисуйте градиент этой функции в точке (1; 1).

Задание 2. Числовые характеристики симметричной квадратной матрицы.

2.1. Приведите определения и геометрическую интерпретацию числовых характеристик квадратной матрицы:

• 
  определитель,
  
• 
  число обусловленности,
  
• 
  собственные числа,
  
• 
  собственные векторы,
  
• 
  сингулярные числа.
  

2.2. Найдите гессиан H функции f(x, y) = Vx^2 +4xy+5y^2 в точке (1; 0).

Постройте множество точек, в которое оператор с матрицей H отображает единичную окружность S₁ с центром в точке (0; 0). Этот образ является эллипсом. Полуоси являются собственными векторами матрицы H, а длины полуосей – собственными числами _i.

2.3. Постройте линию уровня U_α=1 функции f(x, y) в точке (1, 0). Линия уровня также является эллипсом, полуоси которого – собственные векторы, а длин полуосей являются сингулярными числами матрицы и обратно пропорциональны квадратному корню из соответствующего собственного числа, то есть равны 1/_i^0,5. В некотором смысле, два эллипса из пунктов 5.2 и 5.3 являются ортогональными и взаимно-обратными.

Задание 3. Формула Тейлора для функции нескольких переменных

3.1. Приведите формулу Тейлора для функций одной и нескольких переменных

3.2. Проведите квадратичную аппроксимацию в точке (1; 1) для функции

F(x, y) = (x + y - V) e ^{– (x^2 – xy + y^2)}

Задание 4. Нахождение локальных экстремумов

4.1. Используя критерии оптимальности, найдите экстремумы для функции

F(x, y) = (x + y - V) e ^{– (x^2 – xy + y^2)}

4.2. Проверьте правильность нахождения точек экстремума двумя свойствами:

• 
  с помощью графика этой функции,
  
• 
  путем случайного перебора точек в малой окрестности точки локального экстремума.
  

Задание 5. Одномерная оптимизация

Найти точки экстремума функции

F(x) = x⁶ – Vx⁵ + Vx³ – 10x² + x.

Задание 6. Многомерная оптимизация по направлению

Найти точку локального минимума функции

F(x) = x₁² +Vx₂² + x₃² +3x₁x₂ – Vx₁x₃ – x₂x₃ + x₁ – Vx₂ + x₃

Задание 7. Методы безусловной оптимизации

1. 
   Аналитически найти стационарные точки заданной функции, области выпуклости/вогнутости функции. Найти точку глобального минимума. Оценить «овражность» исследуемой функции в окрестности точки минимума.
   
2. 
   Построить график функции, используя средства EXCEL или MATLAB.
   
3. 
   Решить задачу минимизации численным методом из нескольких начальных точек. Сделать вывод об эффективности выбранного метода.
   
4. 
   При выполнении задания на языке СИ написать классы для работы с векторами и матрицами.
   

, метод наискорейшего спуска.

Контрольные вопросы

Объяснить алгоритмы следующих методов

1. 
   Метод конфигураций (Хука-Дживса).
   
2. 
   Метод деформируемого многогранника (Нелдера Мида).
   
3. 
   Метод наискорейшего спуска.
   
4. 
   Метод сопряженных направлений и его модификации.
   
5. 
   Метод Ньютона и его модификации.
   
6. 
   Метод дробления шага.
   

Задание 8. Методы условной оптимизации

1. 
   Решить задачу минимизации функции методом множителей Лагранжа.
   
2. 
   Решить ЗНП методом седловой точки. Промежуточную задачу решения СЛАУ решить, используя EXCEL.
   
3. 
   Решить задачу численным методом [8]. Метод условной минимизации выбрать самостоятельно (см. 1.4.-1.6). Сравнить результат с теоретическим решением.
   

.

Ограничения:



.

Контрольные вопросы

1. 
   Активные и пассивные ограничения. Регулярная задача.
   
2. 
   Теорема Куна-Такера.
   
3. 
   Достаточные условия минимума в задачах математического программирования.
   
4. 
   Седловая точка.
   
5. 
   Метод седловой точки для задачи квадратичного программирования.
   

Задание 9. Задача линейного программирования и симплекс-метод

Вариант 2. Четыре различных предприятия могут выпускать любой из четырёх видов продукции. Производственные мощности предприятий позволяют обеспечить выпуск продукции каждого вида 50, 70, 100 и 30 тыс. шт., а плановое задание составляет соответственно 30, 80, 20 и 100 тыс. шт. Матрица



характеризует себестоимость единицы k-го вида продукции при производстве его на i-ом предприятии.

Найти оптимальное распределение планового задания между предприятиями.

Задание 10. Транспортная задача

Решить транспортные задачи, заданные матрицами перевозок

Вар.2		В1	В2	В3	В4	В5	В6	В7
		250	40	100	170	80	100	65
А1	35	2	5	8	11	3	1	5
А2	60	7	4	3	12	5	9	8
А3	120	1	10	5	1	4	6	2
А4	250	4	4	4	М	4	4	4
А5	180	9	6	5	3	2	1	5

Учесть, что по маршруту 3-7 должно быть перевезено ровно 50 единиц груза

Литература

1. 
   Стандарт предприятия: Общие требования и правила оформления дипломных и курсовых проектов (работ). СТП УГТУ-УПИ 1-96. Екатеринбург, 1996.
   
2. 
   Акулич И.Л. Математическое программирование в примерах и задачах. – М.; Высшая школа, 1993. – 335 с.
   
3. 
   Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации - М.; Издательство МГТУ им. Н.Э. Баумана, 2004. - 432 с
   
4. 
   Васильев В.П. Численные методы решения экстремальных задач. - М.: Наука, 1980. - 518 с.
   
5. 
   Габбасов Р., Кириллова Ф.М. Методы оптимизации. – Минск: Изд-во БГУ, 1981. -
   
6. 
   Дьяконов В. Matlab: учебный курс / В. Дьяконов. СПб.: Питер, 2001. 560 с.
   
7. 
   Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.; Высшая школа, 2005. – 544 с.
   
8. 
   Васин В.В., Еремин И.И. Операторы и итерационные процессы фейеровского типа (теория и приложения). Москва-Ижевск: Институт компьютерных исследований, НИЦ «Регулярная и хаотическая динамика», 2005. – 200 с.
   
9. 
   Визильтер Ю.В., Горбацевич В.С. Описание формы объектов на изображениях при помощи гибких структурирующих элементов // Сборник трудов научно-технической конференции «Техническое зрение в системах управления 2011». М.: ИКИ РАН. 2011. С. 162-167.
   
10. 
    Горбацевич В.В. Современное линейное программирование (Сборник задач с решениями на MAPLE5). М.: 1999 – 34 с.
    
11. 
    Калихман И.Л. Сборник задач по математическому программированию. Изд. 2-е доп. и перераб. М., «Высш. школа», 1975. 270 с. с ил.
    
12. 
    Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т. 1: Пер. с англ. – М.: Мир, 1991. – 360 с., ил.
    
13. 
    Филатов А.Ю. Развитие алгоритмов внутренних точек и их приложение к системам неравенств: Автореф. дис. ... канд. физ.-матем. наук. Иркутск, 2001. 19 с.
    

Приложение. Рекомендации по использованию EXCEL и MATLAB

П1. Построение графиков

Для построения графика функции y=f(x₁,x₂) могут быть использованы следующие инструменты:

1. 
   В EXCEL – Мастер диаграмм, подтип Поверхность.
   
   • 
     Используя автозаполнение, на листе EXCEL в столбец А и первую строку с выбранным шагом ввести соответственно значения переменных x₁ и x₂, для которых будут вычисляться значения функции.
     
   • 
     В ячейку В2 ввести выражение для вычисления функции f(x₁,x₂) в точках $A2, B$1 (знак $ - признак абсолютной адресации, при которой будут зафиксированы первый столбец– перебор значений переменной x₁ и первая строка – перебор значений переменной x₂) и нажать одновременно три клавиши Ctrl, Shift, Enter, поскольку формула используется для обработки массивов. В строке формул должны появиться фигурные скобки.
     
   • 
     Выделить ячейку В2 и, протянув маркер заполнения сначала вниз, пробегая все ячейки, заполненные в столбце А. а затем вправо, пробегая все ячейки, заполненные в строке 1, заполнить массив значений функции в узловых точках области построения графика.
     
   • 
     На вкладке Стандартные Мастера диаграмм выбрать Поверхность. Поверхностная диаграмма дает 3-мерное изображение функции, а Контурная диаграмма представляет вид сверху на поверхностную диаграмму и является аналогом линий уровня исследуемой функции.
     
2. 
   В MATLAB – функции plot3, mesh, surf, surfl.
   
   • 
     С помощью функции meshgrid получить двумерные массивы координат узловых точек области построения графика: u=a:∆₁:b; v=c: ∆₂:d; [x,y]=meshgrid(u,v);
     
   • 
     Задать исследуемую функцию: f= f(х,у);
     
   • 
     Применяя указанные выше функции, получить трехмерное изображение: plot3(x,y,f) или mesh(x,y,f), surf(x,y,f), surfl(x,y,f).
     

П2. Действия с матрицами

Для нахождения собственных значений и собственных векторов матрицы Гессе могут быть использованы следующие инструменты MATLAB

• 
  λ = eig(a) - функция eig(a) возвращает собственные значения заданной матрицы a. Пример задания матрицы 4х4: a = [16 3 2 13; 5 10 11 8; 9 6 7 12; 4 15 14 1] .
  
• 
  [v,d] = eig(a) – при таком обращении функция возвращает собственные векторы v и собственные значения как элементы диагональной матрицы d.
  

Для нахождения матрицы, обратной матрице Гессе могут быть использованы следующие инструменты:

1. В EXCEL – функция МОБР возвращает обратную матрицу для матрицы, хранящейся в массиве.

2. В MATLAB – функция y=inv(a) возвращает обратную матрицу для матрицы a.