Кафедра дискретного анализа и исследования операций
Новосибирский
государственный университет
Кафедра
дискретного анализа и исследования
операций
Вопросы
к экзамену по курсу
Методы оптимизации
3
курс, ФИТ,
НГУ, Зимняя сессия, 2009 г.
ВОПРОСЫ В БИЛЕТАХ
1. Метод внешних штрафов. (Лекция № 16 (Теорема 21), [1, 7])
2. Метод покоординатного спуска. (Лекция № 17 (Теорема 23) , [1, 3, 4])
3. Теория двойственности нелинейного программирования. (Лекция № 4 (леммы 5, 6), Лекция № 5 (Теорема 10, следствия 1 – 3) , [6])
4. Критерий разрешимости задачи ЛП. (Лекция № 6 (Теорема 14, следствия 4 и 5), [5])
5. Теорема Куна–Таккера (нелокальная форма). (Лекция № 4 (Теорема 9) , [6])
6. Понятия базиса, базисного решения, б.д.р. и крайней точки (вершины) (Лекция № 5 (Лемма 7), Лекция № 6 (Теорема 12), [1, 5]). Элементарное преобразование б.д.р. (начиная с формул (21)), базиса и симплекс-таблицы (необходимо знать содержательную интерпретацию). Симплекс – метод. (Лекция № 7 (Лемма 8), Лекция № 8 (Леммы 9, 10) , [1, 5])
7. Метод ветвей и границ. (Лекции № 12, 13, [1, 2])
8. Лексикографический двойственный симплекс - метод. (Лекция № 10 (включая обоснование конечности метода) , [1, 5])
9. Метод искусственного базиса. (Лекция № 9 , [1])
10. Первая и вторая теоремы двойственности линейного программирования. (Лекция № 7, [5])
11. Метод покрытия (метод ветвей и границ для липшицевых функций на гиперкубе). (Лекция № 11 (Теорема 18) , [1, 3], Лекция № 12)
12. Необходимые условия Куна–Таккера (линейный случай). Условия регулярности - лемма 4 (линейность ограничений) (Лекция № 3 (лемма 4), Лекция № 4 (Теорема 6) , [6])
13. Первый алгоритм Гомори. ( Лекция № 11 (включая комментарии до обоснования его конечности), [1, 5])
14. Теорема Куна–Таккера (локальная форма). (Лекция № 4 (Теорема 7 достаточные условия), Лекция № 4 (Теорема 5 - необходимые условия), [6])
15. Теорема Куна–Таккера для линейных ограничений (локальная форма). (Лекция № 4 (Теорема 6 необходимые условия, Теорема 8 достаточные условия), [6])
16. Необходимые условия Куна–Таккера (нелинейный случай). (Лекция № 3 (Теорема 4) [6])
17. Теорема Фаркаша-Минковского. (Лекция № 2 (Теорема 1 и лемма 1)
18. Метод внутренних штрафов. (Лекция № 17, (Теорема 22), [7])
19. Лексикографический симплекс-метод. (Самостоятельно [1, 5, 8].)
20. Необходимые условия Куна–Таккера (выпуклый случай). (Лекция № 4 (Теорема 5, Лекция № 3 лемма 3), [6]) Условие регулярности – условие Слейтера
21. Сильно выпуклые функции и их свойства. (Лекция № 14 (лемма 13 - 15), [1, 5])
22. Градиентные методы. Первая теорема сходимости. (Лекция № 14 (Теорема 19), [5])
23. Вторая теорема сходимости градиентных методов (Лекция № 15 (Теорема 20), [5])
24. Метод Ньютона. Теорема о его сходимости. (Лекция № 16 (Теорема 21) (без доказательства), [1, 5])
25. Метод Келли или метод секущих плоскостей. (Лекция № 17 (Теорема 24), [7])
26. Первый алгоритм Гомори. (Лекция № 12 (обоснование его конечности), [1, 5])
27. Анализ чувствительности: возмущение целевой функции и правых частей. (Лекция № 9, [9])
28. Двойственные задачи линейного программирования. (Лекция № 5 ( включая теорему 11), [5])
29. Анализ чувствительности: возмущение матрицы ограничений. (Лекция № 10 (Теорема 16), [9])
30. Теорема о замыкании конуса возможных направлений (Лекция № 3 ). Интерпретация условий регулярности теоремы 4 (линейная независимость градиентов активных ограничений) (Лекция № 3 ), леммы 4 (линейность ограничений) (Лекция № 3 ), теоремы 5 (условия Слейтора) (Лекция № 4 )
ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ
1. Классификация задач математического программирования. (Лекция № 1)
2. Понятие экстремальной задачи. (Лекция № 1)
3. Конус возможных направлений. Его внутренняя и внешняя аппроксимация. (Лекция № 2, 3)
4. Теорема о замыкании конуса возможных направлений. (Лекция № 3)
5. Условия регулярности: независимость градиентов активных ограничений; условие Слейтера; линейность ограничений. (Лекция № 3, 4).
6. Необходимые условия оптимальности в геометрической форме. (Лекция № 3. Теорема 2).
7. Необходимые условия оптимальности Фритца-Джона. (Лекция № 3. Теорема 3).
8. Необходимые условия оптимальности Куна-Таккера. (Лекция № 3. Теорема 4).
9. Теория двойственности нелинейного программирования. (Лекция № 4, 5)
10. Двойственные задачи линейного программирования (ЛП). (Лекция № 5)
11. Первая и вторая теоремы двойственности ЛП. (Лекция № 7)
12. О сводимости задачи ЛП общего вида к задаче ЛП в канонической форме. ([10] стр. 44 – 50)
13. Схема формирования двойственных задач ЛП. ([10] стр. 94 – 100)
14. Эквивалентность понятий б.д.р. и вершины многогранного множества. Понятие вырожденной и невырожденной б.д.р. Примеры. (Лекция № 5, [1, 8] )
15. Понятие ребра многогранного множества. Пример. (Лекция № 7, [1])
16. Элементарное преобразование базиса и с.-т. Представление об элементарном преобразовании как движении из текущей вершины по ребру. Случай ограниченного ребра. (Лекция № 8, [1])
17. Интерпретация неразрешимости задачи ЛП в с.-м. как перемещения из текущей вершины по неограниченному ребру в направлении убывания целевой функции. (Лекция № 8, [1])
18. Вывод теоремы Гордана из теоремы Фаркаша-Минковского. (Лекция № 2)
ЛИТЕРАТУРА
Алексеева Е.В., Кутненко О.А., Плясунов А.В. «Численные методы оптимизации», НГУ, 2008 (на сайте лаборатории К5). Пособие pdf.file 3Mb
Береснев В.Л. «Дискретные задачи размещения и полиномы от булевых переменных», Н.: Издательство ИМ СО РАН, 2005.
Васильев Ф.П. «Методы оптимизации», М.: Факториал Пресс, 2002.
Васильев Ф.П. «Численные методы решения экстремальных задач», М.: Наука, 1980
Глебов Н.И., Кочетов Ю.А., Плясунов А.В. «Методы оптимизации», НГУ, 2000.
Карманов В. Г. «Математическое программирование», М.: Наука, год любой.
Мину М. «Математическое программирование. Теория и алгоритмы», М.: Наука, 1990.
Моисеев Н.Н. и др. «Методы оптимизации», М.: Наука, 1978.
Муртаф Б. «Современное линейное программирование», М.: Мир, 1984.
Ларин Р.М., Плясунов А.В., Пяткин А.В. Методы оптимизации. Примеры и задачи. Учебное пособие. Новосибирск: Новосибирский государственный университет, 2003.
Лектор к.ф.м.н., доцент А.В. Плясунов
Редакция 14.01.2009