Методы оптимизации

Дисциплина «Методы оптимизации»

Учебно-методическое обеспечение
Для успешного освоения дисциплины Вам необходимо изучить следующие учебные материалы:
1. Мицель Артур Александрович, Грибанова Екатерина Борисовна, Романенко Владимир Васильевич. Методы оптимизации. Электронный курс. Томск, ФДО, ТУСУР, 2018
2. Мицель Артур Александрович, Шелестов Александр Андреевич, Романенко Владимир Васильевич. Методы оптимизации. Учебное пособие. Томск : ФДО, ТУСУР, 2018. – 197 с.
3. Мицель Артур Александрович, Романенко Владимир Васильевич, Грибанова Екатерина Борисовна. Методы оптимизации. Учебно-методическое пособие. Томск : ФДО, ТУСУР, 2018. – 445 с.
Примечание: Доступ к материалам осуществляется из вкладки "Учебные материалы".

Контрольные мероприятия
По дисциплине «Методы оптимизации» в течение семестра предусмотрены следующие контрольные мероприятия:

Контрольная работа:
1. Компьютерная контрольная работа № 1. Контрольная работа выполняется только в режиме онлайн.

Лабораторные работы:
1. Текстовая лабораторная работа № 1 «Безусловная оптимизация». Задание на лабораторную работу № 1 размещено: Учебно-методическое пособие по выполнению контрольных и лабораторных работ (стр. 387).
2. Текстовая лабораторная работа № 2 «Условная оптимизация». Задание на лабораторную работу № 2 размещено: Учебно-методическое пособие по выполнению контрольных и лабораторных работ (стр. 392).

Примечание: Доступ к контрольным и лабораторным работам осуществляется из вкладки "Аттестация". С правилами выполнения и оформления контрольных и лабораторных работ Вы можете ознакомиться в Гиде студента.
14.12.2019

Задание на лабораторную работу № 1
Целью выполнения лабораторной работы № 1 «Безусловная оптимизация» является закрепление на практике реализации численных алгоритмов безусловной оптимизации на языках высокого уровня или в математических пакетах.
Задание состоит из двух этапов:
1. Минимизации функции одной переменной.
2. Минимизации функции многих переменных (многомерная оптимизация без ограничений).
Реализация задания должна удовлетворять следующим требованиям:
– Содержать подробные комментарии по всем этапам решения.
– Позволять модифицировать входные параметры методов – ЦФ,
начальный интервал или начальную точку, точность решения и т. п.
– Отображать подробный ход решения с указанием всех промежуточных результатов.
– Включать графическую интерпретацию решения (не требуется для
консольных программ).
– Не использовать готовые библиотеки или функции, реализующие
лабораторное задание.
9.1.1 Одномерный поиск
Реализовать в программе или математическом пакете один из методов минимизации функции одной переменной согласно варианту.
Всего 8 вариантов:
1. Метод равномерного поиска.
2. Метод деления отрезка пополам.
3. Метод Фибоначчи.
4. Метод золотого сечения.
5. Метод Пауэлла.
6. Метод Ньютона – Рафсона.
7. Метод средней точки.
8. Метод с использованием кубической аппроксимации.
В варианте задания 6 допускается использовать любую итерационную формулу – Стефенсена, Уолла и т. д.
Входные данные:
– целевая функция;
– начальный интервал (для метода Пауэлла – начальная точка, для
метода с использованием кубической аппроксимации – либо интервал, либо точка);
– точность решения по функции и по аргументу (для метода Фибоначчи – только по аргументу);
– дополнительный параметр N для метода равномерного поиска;
– дополнительный параметр ? для метода деления отрезка пополам
и метода Фибоначчи.
Выходные данные:
– точка оптимума * x и оптимальное значение ЦФ * f ;
– количество итераций;
– количество вычислений функции и ее производных;
– коэффициент сходимости
где параметр p ?1 для методов с линейной и суперлинейной сходимостью,
p ? 2 для методов с квадратичной сходимостью и т. д.;
– графическая интерпретация решения;
– результаты всех промежуточных вычислений (интервалы, приближения точки экстремума, значение функции и ее производных во всех промежуточных точках и т. д.).

9.1.2 Многомерный поиск
Реализовать в программе или математическом пакете один из методов минимизации функции многих переменных согласно варианту.
Всего 13 вариантов:
1. Симплексный метод.
2. Метод Хука – Дживса.
3. Метод сопряженных направлений Пауэлла.
4. Метод наискорейшего спуска (Коши).
5. Метод Ньютона.
6. Модифицированный метод Ньютона.
7. Метод Марквардта.
8. Метод сопряженных градиентов для квадратичных функций.
9. Метод Флетчера – Ривза.
10. Метод Полака – Рибьера.
11. Метод Миля – Кентрелла.
12. Метод Дэвидона – Флетчера – Пауэлла.
13. Метод Бройдена – Флетчера – Гольдфарба – Шенно.
Для реализации одномерного поиска в вариантах задания 4, 6, 9–13
использовать метод из первой части задания.
Входные данные:
– размерность задачи;
– целевая функция;
– начальная точка;
– точность решения по функции и по аргументу;
– дополнительные параметры 0 ? и ? для симплексного метода
и метода Хука – Дживса;
– дополнительный параметр ?0 для метода Марквардта.
Выходные данные:
– точка оптимума * x и оптимальное значение ЦФ * f ;
– количество итераций;
– количество вычислений функции, градиента, гессиана (или его
приближения в квазиньютоновских методах);
– графическая интерпретация решения – линии уровня, траектория
спуска, одномерный поиск и т. п.;
– результаты всех промежуточных вычислений (приближения точки
экстремума, значение функции и градиента всех промежуточных точках
и т. д.).

9.2 Задание на лабораторную работу № 2
Целью выполнения лабораторной работы № 2 «Условная оптимизация» является закрепление на практике реализации численных алгоритмов
условной оптимизации на языках высокого уровня или в математических
пакетах.
Задание состоит из двух этапов:
1. Решение задачи линейного программирования.
2. Решение задачи нелинейного программирования.
Реализация задания должна удовлетворять следующим требованиям:
– Содержать подробные комментарии по всем этапам решения.
– Позволять модифицировать входные параметры методов – ЦФ,
размерность задачи, начальную точку, точность решения и т. п.
– Отображать подробный ход решения с указанием всех промежуточных результатов.
– Включать графическую интерпретацию решения (не требуется для
консольных программ).
– Не использовать готовые библиотеки или функции, реализующие
лабораторное задание.
9.1.2 Линейное программирование
Реализовать в программе или математическом пакете ряд методов решения ЗЛП согласно варианту.
Всего 17 вариантов:
1. Методы:
– метод северо-западного угла;
– метод потенциалов с выделением базиса методом северо-западного
угла.
2. Методы:
– графический метод решения ЗЛП;
– метод Гомори.
3. Методы:
– метод Фогеля;
– симплекс-метод решения задачи о назначении с выделением базиса
методом Фогеля.
4. Методы:
– графический метод решения ЗЦП;
– симплекс-метод с выделением начального базиса методом
Жордана – Гаусса.
5. Методы:
– метод наименьшей стоимости;
– метод потенциалов с выделением базиса методом наименьшей стоимости.
6. Методы:
– венгерский метод.
7. Методы:
– метод Фогеля;
– метод потенциалов с выделением базиса методом Фогеля.
8. Методы:
– графический метод решения ЗЛП;
– симплекс-метод с выделением начального базиса методом
Жордана – Гаусса.
9. Методы:
– метод наименьшей стоимости;
– симплекс-метод решения ТЗ с выделением базиса методом
наименьшей стоимости.
10. Методы:
– графический метод решения ЗЦП;
– метод Гомори.
11. Методы:
– метод наименьшей стоимости;
– симплекс-метод решения задачи о назначении с выделением базиса
методом наименьшей стоимости.
12. Методы:
– графический метод решения ЗЦП;
– симплекс-метод с выделением начального базиса методом искусственного базиса.
13. Методы:
– метод северо-западного угла;
– симплекс-метод решения ТЗ с выделением базиса методом северозападного угла.
14. Методы:
– симплекс-метод для ЗЛП в СФ.
– метод Гомори.
15. Методы:
– метод северо-западного угла;
– симплекс-метод решения задачи о назначении с выделением базиса
методом северо-западного угла.
16. Методы:
– графический метод решения ЗЛП;
– симплекс-метод с выделением начального базиса методом искусственного базиса.
17. Методы:
– метод Фогеля;
– симплекс-метод решения ТЗ с выделением базиса методом Фогеля.
В заданиях, где указан метод Гомори, реализации симплекс-метода не
требуется, т. е. на вход подается уже оптимальное решение ЗЛП, но не удовлетворяющее условию целочисленности .
Входные данные:
– размерность задачи;
– целевая функция для ЗЛП или ЗЦП;
– ограничения задачи для ЗЛП или ЗЦП (в виде матрицы или системы
равенств и неравенств, не обязательно приведенных к СФ), исключение для
метода Гомори оговорено выше;
– список базисных переменных для ЗЛП или ЗЦП.
– матрица перевозок для ТЗ;
– матрица назначений для ЗоН.
Выходные данные:
– точка оптимума и оптимальное значение ЦФ ;
– проверка выполнения ограничений задачи в точке ;
– графическая интерпретация решения для графического метода;
– результаты всех промежуточных вычислений (этапы выделения базиса, модификации симплекс-таблиц, матриц перевозок и назначений и т. д.).
Тестовые варианты исходных данных:
См. задачи в заданиях 7–8 контрольной работы.
9.1.3 Нелинейное программирование
Реализовать в программе или математическом пакете ряд методов решения ЗНП согласно варианту.
Первая часть задания имеет 6 вариантов:
1. Метод множителей Лагранжа.
2. Метод Куна – Таккера.
3. Метод штрафных функций, квадратичный штраф.
4. Метод штрафных функций, логарифмический штраф.
5. Метод штрафных функций, штраф типа обратной функции.
6. Метод штрафных функций, штраф типа квадрата срезки.
Вторая часть задания имеет 7 вариантов:
1. Метод линеаризации.
2. Метод Франка – Вульфа.
3. Метод допустимых направлений Зойтендейка.
4. Метод условного градиента для линейных ограничений.
5. Метод условного градиента для нелинейных ограничений.
6. Метод проекции градиента для линейных ограничений.
7. Метод проекции градиента для нелинейных ограничений.
Для поиска проекции точки на ОДР в вариантах задания 5 и 7 использовать метод из первой части задания.
Входные данные:
– размерность задачи;
– целевая функция;
– ограничения;
– начальная точка;
– точность решения по функции и по аргументу;
– начальное значение параметра для методов штрафов.
Выходные данные:
– точка оптимума и оптимальное значение ЦФ ;
– проверка выполнения ограничений задачи в точке ;
– графическая интерпретация решения – линии уровня, траектория
спуска, одномерный поиск, нахождение проекций на ОДР и т. п.;
– результаты всех промежуточных вычислений (приближения точки
экстремума, значение функции и выполнение ограничений в промежуточных точках и т. д.).
Тестовые варианты исходных данных:
См. задачи в заданиях 9–10 контрольной работы