Вопросы для проверки остаточных знаний по курсу «Методы оптимизации»

1. Для каких одномерных функций эффективно применение методов дихотомии, золотого сечения, Фибоначчи?
2. Изложите алгоритм метода дихотомии. Проиллюстрируйте графически.
3. Изложите алгоритм метода золотого сечения. Проиллюстрируйте графически.
4. Изложите алгоритм метода Фибоначчи. Проиллюстрируйте графически.
5. Изложите алгоритм Гаусса минимизации функции n переменных, формализовав последовательность действий.
6. Изложите алгоритм Хука и Дживса минимизации функции n переменных, выделив этапы и формализовав последовательность действий.
7. Изложите основную идею метода вращающихся координат Розенброка. Проиллюстрируйте идею алгоритма графически.
8. Изложите основную идею, лежащую в основе симплексного метода Нелдера-Мида поиска по деформируемому многограннику. Укажите возможные действия по преобразованию многогранника.
9. Дайте определение сопряженных направлений. Для каких функций n переменных использование сопряженных направлений гарантирует решение задачи минимизации за n шагов.
10. Сформулируйте теорему, лежащую в основе алгоритм Пауэлла. Проиллюстрируйте графически.
11. Изложите алгоритм наискорейшего спуска, записав основные итерационные соотношения.
12. Запишите основные итерационные соотношения для метода сопряженных градиентов Флетчера-Ривса. Проиллюстрируйте графически.
13. Запишите основные итерационные соотношения для метода сопряженных градиентов Полака-Рибьера. Проиллюстрируйте графически.
14. Соображения, лежащие в основе алгоритмов многопараметрического (градиентного) поиска.
15. Запишите итерационную формулу метода Ньютона, итерационную формулу модифицированного метода Ньютона.
16. Запишите последовательность действий в алгоритмах метода переменной метрики (основные итерационные соотношения).
17. Метод (внешних) штрафных функций. Запишите задачу нелинейного программирования и сформулируйте эквивалентную ей последовательность безусловных задач.
18. Приведите примеры функций штрафа для ограничений в форме равенств и неравенств.
19. Метод барьерных функций. В чем его отличие от метода штрафных функций. Приведите примеры барьерных функций для ограничений в форме нравенств.
20. Опишите алгоритм простого случайного поиска экстремума функции n переменных. Какой вид экстремума (локального или глобального) позволяет искать данный алгоритм?
21. Что такое направленный и ненаправленный случайный поиск экстремума функции n переменных? Приведите 1-2 примера алгоритмов направленного случайного поиска. Проиллюстрируйте алгоритмы.
22. Сформулируйте алгоритм и приведите необходимые соотношения для метода статистического градиента.
23. Проиллюстрируйте и поясните алгоритм случайного поиска с направляющим гиперквадратом.
24. Приведите и проиллюстрируйте некоторый пример алгоритма глобального поиска.
25. Приведите запись задачи линейного программирования а общем виде, в канонической форме.
26. Сформулируйте основную теорему линейного программирования.
27. Дайте определение опорного плана, оптимального плана задачи линейного программирования. Сколько положительных компонент должно быть в невырожденном опорном плане.
28. Последовательность действий при поиске опорного плана симплекс-методом.
29. Последовательность действий при поиске оптимального плана симплекс-методом.
30. Запишите в общем виде пару двойственных задач линейного программирования.
31. Сформулируйте основную (первую) теорему двойственности задач линейного программирования.
32. Сформулируйте вторую теорему двойственности линейного программирования.
33. Последовательность действий при поиске псевдоплана в методе последовательного уточнения оценок.
34. Последовательность действий при поиске опорного (оптимального) плана в методе последовательного уточнения оценок.
35. Сформулируйте транспортную задачу линейного программирования.
36. Поясните суть алгоритма построения опорного плана транспортной задачи методом северо-западного угла.
37. Изложите алгоритм построения опорного плана транспортной задачи методом минимального элемента.
38. Сформулируйте теорему, лежащую в основе метода потенциалов для решения транспортной задачи.
39. Сформулируйте теорему, позволяющую проверить на вырожденность транспортную задачу ЛП.
40. Сформулируйте транспортную задачу ЛП с ограничениями на пропускные способности путей.
41. Сформулируйте условия, которым должна удовлетворять «оптимальная» транспортная таблица при использовании метода потенциалов.
42. Из каких этапов состоит алгоритм метода потенциалов для построения опорного плана транспортной задачи с ограничениями.
43. Сформулируйте транспортную задачу ЛП по критерию времени.
44. Сформулируйте задачу о максимальном потоке в транспортной сети.
45. Сформулируйте теорему Форда-Фалкерсона, лежащую в основе алгоритма построения максимального потока в транспортной сети.
46. Сформулируйте задачу параметрического линейного программирования. Поясните, в чем может заключаться исследование задачи линейного программирования с параметром в целевой функции.
47. Сформулируйте определение функционала.
48. Сформулируйте основную теорему вариационного исчисления.
49. Сформулируйте уравнение Эйлера.
50. Сформулируйте уравнение Эйлера-Пуассона.
51. Что представляют собой достаточные условия Якоби существования экстремума функционала?
52. Что представляют собой достаточные условия Лагранжа существования экстремума функционала?

А) Возможны несложные вопросы, предполагающие построение очередной симлекс-таблицы в методе последовательного улучшения плана на этапе построения опорного плана, на этапе построения оптимального плана; в методе последовательного уточнения оценок на этапе построения псевдоплана, на этапе построения (оптимального) опорного плана.

Б) Задачи по вариационному исчислению, например, вида “Найти экстремум функционала и определить его тип: , y(2)= 4, y(3) = 9”.