microbik.ru
1
Методы оптимизации ФИТ 2011-2012


  1. Метод внешних штрафов. Лекция № 10, [6]

  2. Конус возможных направлений. Конусы внутренней и внешней аппроксимации. Теорема о замыкании конуса возможных направлений.

  3. Метод покоординатного спуска. Лекции № 10, [2, 3]

  4. Теория двойственности нелинейного программирования. Лекция № 2 (Теорема 1, леммы 1, 2, следствия 1, 2) , [5]

  5. Критерий разрешимости задачи ЛП. Лекция № 3 (Теорема 4, следствия 3 и 4), [4]

  6. Теорема Куна–Таккера (нелокальная форма). Лекция № 8 (Теорема 14) , [5]

  7. Симплекс – метод. Элементарное преобразование б.д.р. (начиная с формул (10)), базиса и симплекс-таблицы, конечность алгоритма для невырожденной задачи. Лекции № 4-5 (Леммы 4, 5 и 6) , [4]

  8. Лексикографический симплекс – метод. Элементарное преобразование б.д.р. (начиная с формул (10)), базиса и симплекс-таблицы, конечность алгоритма. Лекции № 4-5 (Леммы 4, 5 и 6) , [4]

  9. Метод ветвей и границ. Лекция № 12, [1]

  10. Метод искусственного базиса. Лекция № 6

  11. Первая и вторая теоремы двойственности линейного программирования. Лекция № 6, [4]

  12. Метод покрытия (метод ветвей и границ для липшицевых функций на гиперкубе). Лекция № 12 (Теорема 16) , [2]

  13. Теорема Куна–Таккера (локальная форма). Лекция № 8 (Теорема 12), [5]

  14. Теорема Куна–Таккера для линейных ограничений (локальная форма). Лекция № 8 (Теорема 13), [5]

  15. Необходимые условия Куна–Таккера (нелинейный случай). Лекция № 8 (Теоремы 8, 9, 10, лемма 7), [5]

  16. Теорема Фаркаша-Минковского. Лекция № 6, (Теорема 7)

  17. Теорема Гордана. Лекция № 6, (Следствия 5 и 6)

  18. Метод внутренних штрафов. Лекция № 11, (Теорема 21), [6]

  19. Градиентные методы. Первая теорема сходимости. Лекция № 9 (Теорема 15), [4]

  20. Вторая теорема сходимости градиентных методов Лекция № 9 (Теорема 16), [4]

  21. Метод Ньютона. Теорема о его сходимости. Лекция № 10, [4]

  22. Метод Келли или метод секущих плоскостей. Формула метода. Лекция № 11 (Теорема 15), [6]

  23. Двойственные задачи линейного программирования. Лекция № 2 ( включая вывод задачи (8)-(9), теорему 2 и общую схему формирования двойственных задач), [4]

  24. Лагранжева теория двойственности. Лекция № 2 (Леммы 1, 2, Теорема 1) [2, 3]

  25. Лагранжева теория двойственности. Лекция № 2 (Следствия 1, 2) [2, 3]

  26. Базисно допустимые решения, крайние точки, ребра и грани. Лекции № 3 и 4 (определения, лемма 3, Теорема 3)


ЛИТЕРАТУРА


  1. Береснев В.Л. «Дискретные задачи размещения и полиномы от булевых переменных», Н.: Издательство ИМ СО РАН, 2005.

  2. Васильев Ф.П. «Методы оптимизации», М.: Факториал Пресс, 2002.

  3. Васильев Ф.П. «Численные методы решения экстремальных задач», М.: Наука, 1980

  4. Глебов Н.И. и др. «Методы оптимизации», НГУ, 2000.

  5. Карманов В. Г. «Математическое программирование», М.: Наука, год любой.

  6. Мину М. «Математическое программирование. Теория и алгоритмы», М.: Наука, 1990.

  7. Моисеев Н.Н. и др. «Методы оптимизации», М.: Наука, 1978.

  8. Муртаф Б. «Современное линейное программирование», М.: Мир, 1984.