ВОПРОСЫ К ЭКЗАМЕНУ

МЕТОДЫ ОПТИМИЗАЦИИ

1. Математическая постановка задачи оптимизации.

2. Понятие о численных методах оптимизации. Прямые методы. Методы поиска нулевого, первого и второго порядков. Пассивные и активные (последовательные) методы поиска.

3. Конечно шаговые и бесконечно шаговые методы поиска. Сходимость методов. Условия останова методов поиска.

4. Терема существования решения оптимизационной задачи.

5. Необходимые условия экстремума первого и второго порядков (гладкие функции одной переменной).

6. Достаточные условия экстремума (гладкие функции одной переменной).

7. Необходимые условия экстремума первого порядка (гладкие функции многих переменных).

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

9. Свойства унимодальных функций: 1) Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимум на отрезке [a,b]. 2) Функция, унимодальная на отрезке [a,b], унимодальна и на любом меньшем отрезке [c,d]⊂[a,b]. 3) Пусть f(x) унимодальна на [a,b] и a≤x1f(x2), то x*∈[x1,b] x a i i N

10. Пассивные методы поиска экстремума.

11. Метод перебора.

12. Алгоритм оптимального пассивного поиска.

13. Теорема об оптимальности пассивного поиска.

14. Последовательные методы поиска экстремума.

15. Поразрядный поиск.

16. Метод дихотомии.

17. Метод деления отрезка пополам.

18. Метод золотого сечения.

19. Метод чисел Фибоначчи.

20. Метод касательных.

21. Метод средних.

22. Метод хорд.

23. Метод Ньютона.

24. Многомерная безусловная оптимизация. Методы спуска.

25. Поиск по образцу.

26. Метод конфигураций.

27. Метод симплекса.

28. Метод циклического покоординатного спуска.

29. Градиент. Градиент и направление роста целевой функции. Градиент и линия уровня.

30. Градиентные методы.

31. Градиентный метод с постоянным шагом.

32. Градиентный метод с дроблением шага.

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

34. Методы покоординатного спуска.

35. Метод покоординатного спуска с постоянным шагом.

36. Метод покоординатного спуска с дроблением шага.

37. Метод Гаусса-Зейделя.

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

39. Способы перехода от одной формы задачи ЛП к другой.

40. Базисное решение задачи ЛП.

41. Связь базисных решений с угловыми точками (вершинами) множества допустимых решений.

42. Графический метод решения задачи ЛП.

43. Симплекс-метод решения задачи ЛП.

44. Метод искусственных переменных.

Расчетные задания на тестирование

Вычисления Nрасч по заданной точности для методов:

1. Метод перебора.

2. Алгоритм оптимального пассивного поиска.

3. Метод дихотомии.

4. Метод деления отрезка пополам.

5. Метод золотого сечения.

6. Метод чисел Фибоначчи.

Вычисления расчетной точности Ерасч по заданному N для методов:

1. Метод перебора.

2. Алгоритм оптимального пассивного поиска.

3. Метод дихотомии.

4. Метод деления отрезка пополам.

5. Метод золотого сечения.

6. Метод чисел Фибоначчи.

7. Метод перебора или равномерного поиска является простейшим методом минимизации и заключается в следующем. Разобьем отрезок [a, b] на N+1 равных частей точками деления ( ), 1, 1 i b a x a i i N N      . Вычислим значения f(x) в точках 𝑥𝑖 . Найдем точку xl , для которой значение целевой функции минимально 1 ( ) min ( ) l i i N f x f x    . Далее положим 𝑥̃= 𝑥𝑙 , 𝑦̃= 𝑓(𝑥𝑙 ). Точность найденного решения 𝑥̃определяется по формуле: | *| 1 гарант b a x x N       Если необходимо найти приближенное решение с заданной точностью ε, то минимальное число экспериментов N для достижения этой точности определяется из условия 1 min{ : 1}

Рекомендуемая литература

1. Гончаров, В.А. Методы оптимизации: учебное пособие- М.: Высшее образование, 2009. -191 с.

2. Аттетков, А.В. Введение в методы оптимизации: учеб. пособие / Аттетков А.В., Зарубин В.С., Канатников А.Н. - М.: Финансы и статистика, 2008. -272 с.

3. Пантелеев, А.В. Методы оптимизации в примерах и задачах. Учебное пособие для вузов. / Пантелеев А.В., Летова Т.А.- М.: Высшая школа, 2008. - 544 с.

3