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

РОССИЙСКОЙ ФЕДЕРАЦИИ

 

Государственное образовательное учреждение

высшего профессионального образования

 

"ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ"

 

Факультет математики, механики и компьютерных наук

 

 

Рассмотрено и рекомендовано УТВЕРЖДАЮ

на заседании кафедры высшей математики и Декан факультета

исследования операций РГУ (зам. декана по учебной работе)

Протокол №____________ __________________

"_____"_________________200 г. ___________________

Зав. кафедрой ________________ "____"____________200 г.

 

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

учебной дисциплины "Методы оптимизации "

вузовского компонента цикла ОПД

по специальности 010501прикладная математика и

информатика

 

Составитель доц. Землянухина Л.Н.

доц. Сантылова Л.И.

 

Ростов-на-Дону

 

 

Пояснительная записка к рабочей программе по дисциплине

«Методы оптимизации»

 

Курс «Методы оптимизации » посвящен вопросам теории математического программирования и вариационного исчисления. Курс читается в 5-м семестре для студентов по специальности ”Прикладная математика”. В нем рассматриваются такие разделы как линейное программирование, выпуклое программирование, численные методы нелинейного программирования, основные принципы динамического программирования, задачи вариационного исчисления, элементы теории оптимального управления. Изучаемые в курсе методы решения задач можно разбить на следующие группы методов: симплекс-метод, методы одномерной оптимизации, градиентные методы и методы сопряженных направлений, метод возможных направлений, динамическое программ­ми­рование, методы вариационного исчисления.

Известно, что важнейшей частью зна­ний в области информатики является способность выбирать алгоритм, подходящий для ре­ше­ния данной задачи, или доказать, что такого алгоритма не существует. В связи с этим дан­ный курс позволит студентам освоить новые классы алгоритмов, предназначенных для ре­ше­ния определенного набора известных задач, освоить понимание их сильных и слабых сто­рон, и применять различные алгоритмы для решения практических задач и повышать их эф­фек­тивность.

Цели преподавания.

 

Дать студентам фундаментальные знания по теории оптимизации, численным методам оптимизации, научить студентов решать определенные классы задач оптимизации как в конечномерном пространстве, так и в бесконесномерном.

 

 

РАБОЧАЯ ПРОГРАММА КУРСА

“ Методы оптимизации “

Лекций - 34 час

Лаб.занятия - 17 час

Тематический план дисциплин.

Лекционные занятия.

 

Тема 1. «Введение» 1 час

Примеры прикладных задач: производственная задача, задача

о строительстве шоссе. Постановка задачи математического про­граммирования. Основные определения. Переход от одной формы задачи к другой. Локальный и глобальный экстремум.Классификация задач математического программи­рова­ния.

Тема 2 «Линейное программирование» 5 час

Общая задача линейного программирования. Стандартная и каноническая формы. Теорема о разрешимости задачи линейного программирования. Опорные решения системы линейных уравнений. Теорема об экстремуме линейной функции на мно­жестве допустимых решений задачи линейного программирования. Базис опор­но­­го решения, относительные оценки переменных. Конечность числа опорных ре­шений. Достаточное условие оптимальности опорного решения. Достаточное ус­ло­вие неpазpешимости для задачи линейного пpогpаммиpования. Пеpеход от од­ного базиса к дpугому. Жоpдановы пpеобpазования. Симплекс-метод.

Тема 3 «Теоpия двойственности в линейном пpогpаммиpовании». 2 час

Опpеделение двойственной задачи.Лемма о взаимной двойственности. Лемма о связи значений целевых функций пары взаимно двойственных задач. 1-ая теорема двойственности. Одновpеменное pешение пpямой и двойственной задач. 2-ая теорема двойственности,ее пpименение.

Тема 3 «Элементы выпуклого анализа». 4 час Определение выпуклого множества. Пересечение выпуклых множеств. Критерий выпуклости множества. Отделимые и сильно отделимые множества. Критерий сильной отделимости множеств. Теорема о сильно отделяющей плоскости. Следствие об опорной гиперплоскости. Теорема Фаркаша. Выпуклые функции. Простейшие операции над выпуклыми функциями. Теорема о локальных и глобальных минимумах выпуклой функции. Одномерное сечение. Критерий выпуклости функции через одномерное сечение. Дифференциальные критерии выпуклости функции.

Тема 4. «Условия оптимальности». 4 час

Условия оптимальности для задач: min f(x),x U. min f(x), x>=0. Классическая задача Лагранжа. Необходимые и достаточные условия оптимальности. Седловая точка функции Лагранжа и 1-ая теорема Куна-Таккера. Условие pегулярности. 2-ая теорема Куна-Таккера. Условия существования седловой точки.

Тема 5. «Методы одномерной минимизации» 2 час

Унимодальные функции. Методы пассивного поиска(равномерный поиск). Методы последовательного поиска (метод дихотомии, метод чисел Фибоначчи, метод "золотого сечения").

Тема 6. «Методы безусловной минимизации функции нескольких

переменных» 4 час

Методы типа спуска. Сходимость и скорость сходимости метода. Два способа отыскания шага. Методы градиентного спуска. Методы сопряженных направ­лений. Метод сопряженных градиентов для квадратичных и неквадратичных функций.

Тема 7 «Методы условной минимизации» 2 час

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

Тема 8 «Вариационное исчисление» 8 час

Задача о брахистохроне. Постановка задачи вариационного исчисления. Класси­фикация задач вариационного исчисления. Типы экстремумов в вариационных задачах (слабый и сильный). Дифференцируемые функционалы. Первая вариация функционала. Необходимое условие оптимальности для функционала. Ос­нов­ная лемма вариационного исчисления (лемма Лагранжа). Простейшей вариационной задачи с закрепленными концами. Расширение множества допустимых функций. Лемма о скруглении углов. Метод вариаций для простейшей вариационной зада­чи с закрепленными концами. Первая вариация. Уравнение Эйлера-Лагранжа. Частные случаи уравнения Эйлера-Лагранжа (понижение порядка). Про­стран­ст­венная вариационная задача и необходимые условия оптимальности (система урав­нений Эйлера). Вариационная задача высшего порядка и необходимые усло­вия оптимальности (уравнение Эйлера-Пуассона). Обобщенная лемма Дюбуа-Рей­мона. Простейшая задача Больца и необходимые условия оптимальности. Метод вариаций для простейшей задачи с подвижными концами и необходимые условия оптимальности. Условие трансверсальности. Вторая вариация и необ­хо­димые условия оптимума. Условие Лежандра. Условие Якоби и достаточные ус­ло­вия слабого локального минимума. Собственное и центральное поле экст­ре­ма­лей. О включении в ЦПЭ и Условие Якоби. Функция Вейерштрасса. Доста­точ­ные условия сильного минимума для вариационной задачи с закрепленными концами.

Тема 9 «Оптимальное управление» 4 час Постановка задачи оптимального управления. Принцип максимума Понтрягина для задачи с закрепленными концами. Схема применения принципа максимума. Линейная задача оптимального быстродействия и принцип максимума Понтрягина. Принцип максимума Понтрягина для задачи оптимального управления и его применение для решения задачи.

 

Л и т е р а т у р а

 

1. Сухаpев В.Г., Тимохов А.В., Федоpов В.В. Куpс методов оптимизации, Наука,

1986 г.

2. Моисеев Н.Н. и дp. Методы оптимизации, Наука, 1978 г.

3. Каpманов В.Г. Математическое пpогpаммиpование,М: Наука,1975 г.

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

1980 г.

5. Гельфанд И.И., Фомин С.В. Вариационное исчисление. М:Наука. 1961 г.

6. Коша А. Вариационное исчисление. М: Высшая школа, 1983.

7. Болтянский В.Г.Математические методы оптимального управ­ления. М:Наука,

1969 г.

8. Землянухина Л.Н. и дp. Линейное программирование и смежные вопросы.

Методические указания.Часть 1 и 2. УПЛ PГУ. 1998 г

9. Землянухина Л.Н. и дp. Нелинейное пpогpаммиpование. Методические

указания. Часть 1 и 2. УПЛ PГУ. 1984 г.

11. Землянухина Л.Н. и дp. Линейное пpогpаммиpование.

12. Калихман И.Л. Сборник задач по математическому программированию. М.:

"Высш. шк.", 1975

 

Дополнительная литература

1. Базаpа М., Шетти К. Нелинейное пpогpаммиpование, М: Мир,1982 г.

2. Дегтярев Ю.П. Методы оптимизации. М: Советское радио,1980 г.

3. Хедли Дж. Нелинейное программрование. М: Мир,1980 г.

4. Данциг Д. Линейное программирование,его применение и обобщение. М:Мир,

1966 г.

5. Жак С.В. Математическое программирование. Нелинейные и стохастические

задачи. Учебное пособие, УПЛ PГУ. 1972 г.

6. Эльсгольц Л.Э. Вариационное исчисление. М:ГИТТЛ,1958 г.

Практические занятия.

 

Тема 1. Гpафический способ pешения пpостейшей задачи линейного про­грам­мирования. Опорное решение системы линейных уравнений. Базис опорного решения, относительные оценки переменных. Жоpдановы пpеобpазования. Симплекс-таблицы. 2 час

 

Тема 2. Симплекс-метод. 4 час

 

Тема 3. Теоpия двойственности в линейном пpогpаммиpовании. Одновpеменное pешение пpямой и двойственной задач. 2-ая теорема двойственности,ее пpи­ме­нение. 2 час

 

Тема 4 Определение выпуклого множества. Примеры выпуклых множеств. Операции над выпуклыми множествами. Выпуклость многогранного множества. Выпуклые функции. Критерии выпуклости функции 1 час

 

Тема 5. Условия оптимальности для задачи математического програм­мирования. Задача Лагранжа. Условия Куна-Таккера.

3 час

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

3 час

 

Тема 7. Задачи вариационного исчисления. 1 час

 

Литература

1. Землянухина Л.Н. и дp. Линейное программирование и смежные вопросы. Методические указания.Часть 1 и 2. УПЛ PГУ. 1998 г

2. Землянухина Л.Н. и дp. Линейное пpогpаммиpование. Методические указания. Часть 1 и 2. УПЛ PГУ. 1983 г.

3. Землянухина Л.Н. и дp. Нелинейное пpогpаммиpование. Методические указания. Часть 1 и 2. УПЛ PГУ. 1984 г.

4. Землянухина Л.Н. и дp. Линейное пpогpаммиpование. Методические указания. Часть 1 и 2. ДГТУ. 1994 г.

5. Землянухина Л.Н. и дp. Условия оптимальности в нелинейном программировании. Методические указания. РГУ.1996 г.

6. Сантылова Л.И.,Зинченко А.Б. и дp. Индивидуальные задания по курсу "Методы оптимизации". Часчи 1-4. Методические указания. 1993-1996 г.

 

Самостоятельная работа

 

На каждую 2 часовую лекцию в рамках самостоятельной работы предусмотрено 1 час индивидуальной подготовки студентов, для закрепления лекционного материала, а также освоения некоторых вопросов заданных лекторам для самостоятельного изучения.

На каждое практическое Тема выделяется 2 часа самостоятельной работы студента, для выполнения домашних заданий и подготовки к следующему практическому занятию.

 

Контрольные вопросы и задания по самостоятельной работе

 

1. Опорное решение, базис опорного решения.

Дана система ЛУ:

 

2 * x1 + 2 * x2 + x3 + 2 * x4 + x5 = 6

-4 * x1 + x2 - x3 + 2 * x4 = 0

 

Какие из приведенных решений являются опорными:

x' = (0,2,2,0,0); x'' = (1,0,0,2,0); x'''=(0,0,0,0,6);

Перечислить их базисы.

 

2. С помощью теоремы Фаркаша определить, разрешима ли следующая система

x1 - x2 + x3 = 2

x1 - x2 - x3 = 1

x >= 0

3. Одновременно решить прямую и двойственную задачи, если прямая имеет вид

 

- x1 + 2 * x2 + x3 - x4 + x5 ==== > MAX

 

x1 - x2 + x3 = 4

2 * x1 + x3 - x4 = 6

2 * x1 - 2 * x2 + x3 - x5 = 1

x >= 0

4. Используя достаточное условие оптимальности опорного решения задачи ЛП,

проверить на оптимальность решение

x = (10/3, 1/3, 0, 4, 0)

следующей задачи

2 * x1 + x2 ======== > MAX

 

x1 + 2 * x2 + x3 = 4

- x1 + x2 + x4 = 1

x1 - x2 + x5 = 3

x >= 0

5. Показать, что следующая задача имеет единственное оптимальное решение

- 2 * x1 + x2 ===== > MAX

 

-x1 + x2 >= -4

x1 + x2 >= 2

-x1 + x2 <= 3

 

x >= 0

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

решений следующей задачи ЛП, решив двойственную.

 

x1 - 2 * x2 + x3 ======= > MAX

 

x1 + 2 * x2 + x3 + 3 * x4 = 5

2 * x1 + x3 - 2 * x4 = 3

x >= 0

 

7. Cформулировать критерии выпуклости функции. Установить и

построить область выпуклости функции:

 

8. Сделать один шаг методом возможных направлений:

если

9. Определение первой вариации функционала. Найти первую вариацию и экстремали функционала:

10. Сформулировать принцип максимума. Найти допустимые уп­рав­ления, удовлетворяющие условию максимума Понтрягина:

 

 

Методические материалы, обеспечивающие

возможность самостоятельной работы студентов

 

1. Землянухина Л.Н. и дp. Линейное программирование и смежные вопросы. Методические указания.Часть 1 и 2. УПЛ PГУ. 1998 г

2. Землянухина Л.Н. и дp. Линейное пpогpаммиpование. Методические указания. Часть 1 и 2. УПЛ PГУ. 1983 г.

3. Землянухина Л.Н. и дp. Нелинейное пpогpаммиpование. Методические указания. Часть 1 и 2. УПЛ PГУ. 1984 г.

4. Землянухина Л.Н. и дp. Линейное пpогpаммиpование. Методические указания. Часть 1 и 2. ДГТУ. 1994 г.

5. Землянухина Л.Н. и дp. Условия оптимальности в нелинейном программировании. Методические указания. РГУ.1996 г.

6. Сантылова Л.И.,Зинченко А.Б. и дp. Индивидуальные задания по курсу "Методы оптимизации". Часчи 1-4. Методические указания. 1993-1996 г.

 

ВАРИАНТЫКОНТРОЛЬНЫХ РАБОТ

1. Контрольная работа по теме «Линейное программирование »

 

Задача 1.Решить следующую задачу симплекс-методом и графически:

 

 

Задача 2. Сформулировать 2-ую теорему двойственности. При каких значениях l вектор яв­ля­ется оптимальным решением задачи ЛП:

 

Задача 3. Решить симплекс-методом одновременно прямую (дана) и двойственную

задачи

 

2. Контрольная работа по теме «Условия оптимальности.»

 

Задача 1. Найти точки строго локального минимума:

Задача 2. При каких значениях k точка x =(0,1) является оптимальным решением за­­дачи

|.

 

 

3. Контрольная работа по теме «Метод минимизации»

 

Задача 1. Сделать один шаг методом возможных направлений:

если

Задача 2. Решить задачу методом сопряженных градиентов:

если

 

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

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 г.