Перечень вопросов, выносимых на экзамен

1. Постановка задачи математического программиро вания. Основные опре­де­ле­

ния. Переход от одной формы задачи к другной.

2. Локальный и глобальный экстремум. Классификация задач математического

программирования.

3. Общая задача линейного программирования. Стандартная и каноническая

формы.

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

5. Oпорные решения системы линейных уравнений.

6. Теорема об экстремуме линейной функции на множестве допустимых решений

задачи линейного программирования.

7. Базис опорного решения, относительные оценки переменных. Конечность

числа опорных решений.

8. Достаточное условие оптимальности опорного решения.

9. Достаточное условие неpазpешимости для задачи линейного пpогpам­миpо­ва­

ния.

10. Пеpеход от одного базиса к дpугому. Жоpдановы пpеобpазования.

11. Симплекс-метод.

12. Опpеделение двойственной задачи. Лемма о взаимной двойственности.

13. Лемма о связи значений целевых функций пары взаимно двойственных задач.

14. 1-ая теорема двойственности.

15. Одновpеменное pешение пpямой и двойственной задач.

16. 2-ая теорема двойственности,ее пpименение.

17. Определение выпуклого множества. Пересечение выпуклых множеств. Линей­

ная комбинация выпуклых множеств. Выпуклость многогранного множества.

18. Выпуклая оболочка. Критерий выпуклости множества.

19. Отделимые и сильно отделимые множества. Условия отделимости.

20. Следствие об опорной гиперплоскости.

21. Теорема Фаркаша.

22. Выпуклые и сильно выпуклые с константой функции. Простейшие операции

над выпуклыми функциями.

23. Теорема о локальных и глобальных минимумах выпуклой функции.

24. Три критерия сильной выпуклости функции: в терминах приращения фун­к­

ции, в терминах первых производных, в терминах вторых производных.

Критерий выпуклости квадратичной функции. Дифференциальные критерии

выпуклости функции.

25. Одномерное сечение. Критерий выпуклости функции через одномерное сече­

ние.

26. Условия оптимальности для задачи: min f(x), x (U.

Условия оптимальности для задачи: min f(x), x>=0.

28. Классическая задача Лагранжа. Необходимые и достаточные условия опти

­маль­ности.

29. Седловая точка функции Лагранжа и 1-ая теорема Куна-Таккера.

30. Условие pегулярности. 2-ая теорема Куна-Таккера.

31. Условия существования седловой точки.

32. Унимодальная функция. Лемма о сужении интервала локализации.

33. Методы одномерной минимизации унимодальных функций (метод

дихотомии, метод чисел Фибоначчи, метод "золотого сечения").

34. Методы минимизации. Сходимость и скорость сходимости метода. Выбор

шага из условия минимизации функции вдоль заданного направления.

35. Метод дробления шага. Лемма об ограничении на длину шага метода мини­

мизации.

36. Градиентные методы минимизации. Условия сходимости.

37. Понятие сопряженных направлений и их свойства.

38. Методы сопряженных направлений. Конечный метод минимизации

квадратичной функции.

39. Метод сопряженных градиентов для квадратичных функций.

Свойства градиентов и направлений минимизации.

40. Метод сопряженных градиентов для неквадратичных функций.

41. Метод возможных направлений. Выбор направления. Выбор шага

42. Метод динамического программирования для задачи сепарабельного про­грам­-

­ми­ро­вания.Принцип включения.Принцип оптимальности.Функциональное

уравнение Беллмана.

43. Вариация аргумента. Первая вариация функционала.

43. Необходимое условие оптимальности функционала на банаховом простран­

стве.

44. 1-ая основная лемма вариационного исчисления (лемма Лагранжа).

45. 2-ая основная лемма вариационного исчисления (лемма Дюбуа-Реймона).

46. Простейшей вариационной задачи с закрепленными концами. Постановка.

Типы экстремумов: слабый и сильный минимум.

46. Метод вариаций для простейшей вариационной задачи с закрепленными

концами. Первая вариация. Вывод уравнения Эйлера-Лагранжа с помощью

леммы Лагранжа.

47. Вывод уравнения Эйлера-Лагранжа с помощью леммы Дюбуа-Реймона.

48. Частные случаи уравнения Эйлера-Лагранжа (понижение порядка).

49. Пространственная вариационная задача и система уравнений Эйлера.

50. Вариационная задача высшего порядка и необходимые условия оптималь­но­-

сти (уравнение Эйлера-Пуассона).

51. Определение второй вариации функционала в простейшей задаче ВИ.

Необходимое условие оптимальности через вторую вариацию.

52. Условие Лежандра и необходимое условие оптимальности.

53. Условие Якоби и достаточные условия слабого локального минимума.

54. Простейшая задача Больца и необходимые условия оптимальности.

55. Простейшая изопериметрическая задача и необходимые условия оптималь­-

ности.

56. Оптимальное управление. Основные понятия. Постановка задачи

оптимального управления с закрепленными концами. Принцип

максимума Понтрягина для задачи с закрепленными концами.

Схема применения принципа максимума.

Экзаменационные билеты

Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет математики, механики и компьютерных наук Кафедра исследования операций   Экзаменационный билет № 1 По курсу «Методы оптимизации»   1.Опорное решение, относительные оценки переменных. Достаточное условие оптимальности опорного решения.   2. Решить симплекс-методом одновременно прямую (дана) и двойственную задачи   3. Теорема Фаркаша..   4. При каких значениях k точка x =(0,1) является оптимальным решением за­­дачи |.   5. Простейшей вариационной задачи с закрепленными концами. Поста­нов­ка 6. Определение первой вариации функционала. Найти первую вариацию и экстремали функционала:     Зав. кафедрой _______________Экзаменатор __________________   10 января 2006 г.

Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет математики, механики и компьютерных наук Кафедра исследования операций   Экзаменационный билет № 2 По курсу «Методы оптимизации»   1. Задача линейного программирования. Теорема о разрешимости задачи линейного программирования.   2.. При каких значениях параметра l вектор является оптимальным решением задачи ЛП 3. Теорема о локальных и глобальных минимумах выпуклой функции.   4.. Сделать один шаг методом возможных направлений: если   5. Сформулировать основную лемму вариационного исчисления Найти первую вариацию и экстремали функционала:   6. Вторая вариация. Условие Лежандра.   Зав. кафедрой _______________Экзаменатор __________________   10 января 2006 г.

Федеральное агентство по образованию Российской Федерации Государственное образовательное учреждение высшего профессионального образования «РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Факультет математики, механики и компьютерных наук Кафедра исследования операций   Экзаменационный билет № 3 По курсу «Методы оптимизации»   1. Теорема о разрешимости задачи линейного программирования.   2. Решить прямую (дана) задачу графически, а двойственную задачу – используя 2-ую теорему двойственности   3. Одномерное сечение. Критерий выпуклости функции через одномерное сечение.   4. Определение унимодальной функции. Найти третью точку в методе ”золотого сечения”, примененного к задаче Сколько потребуется шагов (итераций). чтобы локализовать минимум с точностью e = 0.001   5. Метод динамического программирования для задачи сепарабельного програм­мирования.   6. Решить задачу   Зав. кафедрой _______________Экзаменатор __________________   10 января 2006 г.