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

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

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

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

y = -9*x₁ + 29*x₂

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

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

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

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

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

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

• определитель,

• число обусловленности,

• собственные числа,

• собственные векторы,

• сингулярные числа.

2.2. Найдите гессиан H функции f(x, y) = 9x^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 - 9) e ^{– (x^2 – xy + y^2)}

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

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

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

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

• с помощью графика этой функции,

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

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

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

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

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

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

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

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

1. Аналитически найти стационарные точки заданной функции, области выпуклости/вогнутости функции. Найти точку глобального минимума. Оценить «овражность» исследуемой функции в окрестности точки минимума.

2. Построить график функции, используя средства EXCEL или MATLAB.

3. Решить задачу минимизации численным методом из нескольких начальных точек. Сделать вывод об эффективности выбранного метода.

4. При выполнении задания на языке СИ написать классы для работы с векторами и матрицами.

Задание выбирать в соответствии с порядковым номером фамилии студента в списке группы.

1. exp[1-], метод сопряженных направлений.

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

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

1. Метод конфигураций (Хука-Дживса).

2. Метод деформируемого многогранника (Нелдера Мида).

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

4. Метод сопряженных направлений и его модификации.

5. Метод Ньютона и его модификации.

6. Метод дробления шага.

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

1. Решить задачу минимизации функции методом множителей Лагранжа.

2. Решить ЗНП методом седловой точки. Промежуточную задачу решения СЛАУ решить, используя EXCEL.

3. Решить задачу численным методом [8]. Метод условной минимизации выбрать самостоятельно (см. 1.4.-1.6). Сравнить результат с теоретическим решением.

Задания выбирать в соответствии с порядковым номером студента в журнале.

1. ,

Ограничения (для всех вариантов):

.

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

1. Активные и пассивные ограничения. Регулярная задача.

2. Теорема Куна-Такера.

3. Достаточные условия минимума в задачах математического программирования.

4. Седловая точка.

5. Метод седловой точки для задачи квадратичного программирования.

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

Вариант 1. Для изготовления четырёх видов продукции (А, Б, В и Г) используется три вида сырья (I, II и III). Ресурсы сырья, нормы его расхода на единицу продукции и получаемая прибыль от единицы продукции заданы в следующей таблице:

Определить оптимальный план выпуска продукции из условия максимизации прибыли.

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

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

Литература

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-мерное изображение функции, а Контурная диаграмма представляет вид сверху на поверхностную диаграмму и является аналогом линий уровня исследуемой функции.