Утверждаю
| Вид материала | Рабочая программа |
- Утверждаю утверждаю, 21.26kb.
- «утверждаю» «утверждаю», 262.03kb.
- Утверждаю утверждаю, 393.06kb.
- «Утверждаю» «Утверждаю» Председатель Совета доу заведующий мдоу №25, 113.74kb.
- Кикбоксинг против наркомании и детской преступности «Утверждаю» «Утверждаю», 78.29kb.
- Утверждаю: утверждаю, 156.74kb.
- «утверждаю» «утверждаю» Председатель республиканского Директор маоудод «цдтт №5» совета, 42.86kb.
- Утверждаю» «Утверждаю», 163.81kb.
- «Динамо», 49.89kb.
- Утверждаю: утверждаю: Председатель Глава администрация оо «Гомельский рыболовный клуб», 78.23kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
УТВЕРЖДАЮ
Декан ФПМК А.М. Горцев
"_____"__________________2011 г.
Рабочая программа дисциплины
Методы оптимизации
Направление подготовки
010400 Прикладная математика и информатика
Квалификация выпускника
Бакалавр
Форма обучения
Очная
Томск
2011
1. Цели освоения дисциплины
Целью освоения дисциплины «Методы оптимизации» является формирование у студентов знаний по основам теории оптимизации и знаний об основных подходах к практическому решению оптимизационных задач. Обучаемый знакомится с классификацией задач оптимизации, методами решения этих задач и применением методов для решения конкретных задач.
2.Место дисциплины в структуре ООП бакалавриата
Дисциплина «Методы оптимизации» входит в базовую (общепрофессиональную) часть профессионального цикла ООП Б3; изучается в 5-ом семестре. Для изучения этой дисциплины необходимо знание дисциплин «Линейная алгебра», «Математический анализ». Знания, полученные при освоении дисциплины «Методы оптимизации», используются при изучении дисциплины «Исследование операций», при выполнении курсовых и квалификационных работ.
3 Компетенции обучающегося, формируемые в результате освоения дисциплины Методы оптимизации :
способность владеть культурой мышления, умение аргументировано и ясно строить устную и письменную речь (ОК-1);
способность владения навыками работы с компьютером (ОК-11);
способность приобретать новые научные и профессиональные знания, используя образовательные и информационные технологии (ПК-2);
способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-3).
В результате освоения дисциплины обучающийся должен:
- Знать:
- классификацию задач оптимизации;
- теоретические положения, лежащие в основе построения методов решения;
- основные методы решения типовых оптимизационных задач.
- Уметь:
- выбрать метод для решения конкретной задачи оптимизации;
- использовать типовые алгоритмы для решения задач;
- оценить качество работы алгоритма при решении задачи.
- Владеть навыком корректировки процесса решения задачи изменением параметров алгоритма.
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 5,1 зачетных единиц, 183 часа.
| № п/п | Раздел Дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | |||
| | | | | Лекц. | Пр. | Лаб. | СРС | |
| 1 | Безусловная минимизация функций | 5 | 1 | 2 | 12 | 20 | 20 | Контрольная работа на 6 неделе |
| 2 | Линейное программирование | 5 | 2-6 | 10 | 12 | 10 | 20 | Контрольная работа на 12 неделе |
| 3 | Дискретное программирование | 5 | 7-8 | 4 | 2 | 2 | 10 | |
| 4 | Классич.задача на условный экстремум | 5 | 9-10 | 4 | 2 | | 6 | |
| 5 | Нелинейное программирование | 5 | 11-16 | 12 | 4 | | 4 | Зачет 5 семестр Экзамен 5 семестр |
| | ИТОГО: | | | 32 | 32 | 32 | 60 | 27 |
Лекции:
1. Предмет курса. Классификация, примеры задач оптимизации .
2. Формулировка, формы записи задачи линейного программирования. Геометрическая интерпретация.
3. Свойства решений. Симплекс-метод решения задачи линейного программирования.
4. Симплекс-таблицы. Метод искусственного базиса. Модифицированный симплекс-метод. Двойственные задачи линейного программирования.
5. Теорема двойственности. Двойственный симплекс-метод. Устойчивость решения.
6. Транспортная задача в матричной постановке. Условия разрешимости. Метод потенциалов для решения транспортной задачи, обоснование. Транспортные задачи с запретами и с ограничениями на перевозки.
7. Постановка задачи дискретного программирования. Линейные задачи дискретного программирования. Методы отсечения.
8. Правильное отсечение, первый алгоритм Гомори. Метод ветвей и границ для линейных задач дискретного программирования.
9. Классическая задача на условный экстремум. Необходимые условия экстремума (метод множителей Лагранжа). Минимаксные свойства функции Лагранжа.
10. Прямые методы решения задач с ограничениями-равенствами. Метод проекции градиента. Метод штрафных функций. Теорема Гермейера.
11. Седловая точка функции при знаковых ограничениях на переменные. Необходимые условия седловой точки.
12. Достаточные условия седловой точки Теорема Куна-Таккера.
13. Теорема Куна-Таккера.
14. Условия регулярности Куна-Таккера.
15. Прямые методы решения задач нелинейного программирования. Методы линейной аппроксимации. Метод скользящего допуска. Методы последовательной безусловной оптимизации (внутренний штраф, внешний штраф).
16. Задача квадратичного программирования. Метод Била.
Практические занятия:
1. Необходимые и достаточные условия экстремума функции многих переменных. Градиентные методы.
2. Градиентные и овражные методы .
3. Метод Ньютона. Метод сопряженных градиентов. Квазиньютоновские методы .
4. Одномерный поиск.
5. Многомерный поиск. Метод деформируемого многогранника, метод Розенброка .
6. Контрольная работа .
7. Формы записи, свойства решений задач линейного программирования.
8 Симплекс-таблицы. Метод искусственного базиса.
9. Двойственные задачи линейного программирования. Двойственный симплекс-метод .
10. Устойчивость решения задачи линейного программирования .
11. Транспортная задача. Построение первого плана перевозок. Метод потенциалов .
12. Контрольная работа .
13. Линейные задачи дискретного программирования. 1-ый алгоритм Гомори. Метод ветвей и границ .
14. Прямые методы решения классической задачи на условный экстремум .
15. Седловая точка функции.
16. Необходимые и достаточные условия экстремума в задачах нелинейного программирования .
Лабораторные работы:
1. Вводное занятие. Знакомство с программным обеспечением лабораторных работ. Инструктаж .
2. Лабораторная работа 1. Градиентные методы.
3 Градиентные методы.
4.Градиентные методы.
5. Лабораторная работа 2. Овражные методы.
6. Овражные методы.
7. Лабораторная работа 3. Поисковые методы. Одномерный поиск.
8. Лабораторная работа 4. Многомерный поиск. Метод деформируемого многогранника, метод Розенброка .
9. Многомерный поиск.
10. Лабораторная работа 5. Решение задач линейного программирования симплекс-методом.
11. Лабораторная работа 6. Двойственный симплекс-метод.
12. Двойственный симплекс-метод.
13. Лабораторная работа 7. Анализ устойчивости решения задачи использования ресурсов по вектору запасов сырья .
14. Лабораторная работа 8. Решение открытых транспортных задач, задач с запретами и ограничениями на перевозки методом потенциалов .
15-16. Лабораторная работа 9. Решение линейных задач дискретного программирования 1-ым алгоритмом Гомори и методом ветвей и границ.
5. Образовательные технологии
Предусмотрено использование в учебном процессе активных форм проведения занятий (семинары в диалоговом режиме, дискуссии, разработка конкретных ситуаций, групповые дискуссии). Одной из основных активных форм обучения профессиональным компетенциям является семинар, действующий на регулярной основе, к работе которого привлекаются ведущие исследователи и преподаватели
При выполнении лабораторных работ используется разработанный на кафедре исследования операций комплекс программ «Оптимизация».
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
Самостоятельная работа студентов организуется как подготовка к выполнению лабораторных работ и выполнение индивидуальных домашних заданий.
Контрольные вопросы:
1. Необходимые условия экстремума функции многих переменных.
2. Метод Ньютона.
3. Метод сопряженных градиентов.
4. Градиентные методы.
5. Одномерный поиск.
6. Метод деформируемого многогранника.
7. Метод Розенброка.
8. Формы записи задач линейного программирования.
9. Геометрическая интерпретация. Графический способ решения задач линейного программирования.
10. Свойства решений задач линейного программирования.
11. Симплекс-метод.
12. Метод искусственного базиса.
13. Двойственные задачи линейного программирования.
14. Теоремы двойственности.
15. Двойственный симплекс-метод.
16. Модифицированный симплекс-метод.
17. Транспортная задача в матричной постановке.
18. Условия разрешимости транспортной задачи.
19. Метод потенциалов.
20. Способы построения первого опорного плана перевозок.
21. Обоснование метода потенциалов.
22. Формулировка задачи дискретного программирования.
23. Методы отсечения. Понятие правильного отсечения.
24. Первый алгоритм Гомори.
25. Метод ветвей и границ для линейных задач дискретного программирования.
26. Необходимые условия в классической задаче на условный экстремум. Минимаксные свойства функции Лагранжа.
27. Метод проекции градиента.
28. Метод штрафных функций. Теорема Гермейера.
29.. Седловая точка функции при наличии знаковых ограничений на переменные.
30. Необходимые условия седловой точки.
31. Достаточные условия седловой точки.
32. Теорема Куна-Таккера.
33. Условия регулярности Куна-Таккера .
34. Методы линейной аппроксимации.
35. Метод аппроксимирующего программирования.
36. Метод Заутендейка.
37. Метод скользящего допуска.
38. Методы последовательной безусловной оптимизации. Внутренний штраф, внешний штраф.
7. Учебно-методическое и информационное обеспечение дисциплины (модуля)
а) основная литература:
1. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. - М.: Наука, 1978.-357с.
2. Химмельблау Д. Прикладное нелинейное программирование. -М.: Мир, 1975. -534с.
3. Васильев Ф.П. Лекции по методам рещения экстремальных задач. М.: МГУ, 1974. -374с.
4 Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. -М.: Высшая школа, 1976. -352с.
5.Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. -М.: Наука, 1969. -384с.
6. Банди. Линейное программирование. -М. 1988. -276с.
7. Хедли Дж. Нелинейное и динамическое программирование. -М. Мир, 1967.-391с.
б) дополнительная литература:
1. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. –М. Высшая школа, 2002. -284с.
2. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной оптимизации. -Мир, 1972. -240с.
3. Вагнер Г. Основы исследования операций, Т.2. -Мир, 1973.
4. Акулич И.Л. Математическое программирование в примерах и задачах. -М.: Высшая школа, 1993. - 387с.
5. Гендрина И.Ю., Катаева С.С., Рыжаков А.П. Методы решения линейных задач дискретного программирования. Томск, ТГУ, 2003.-26с.
6. Гендрина И.Ю., Катаева С.С., Рыжаков А.П. Решение задач линейного программирования симплекс-методом. Томск, ТГУ, 2003.-24с.
7. Гендрина И.Ю., Катаева С.С., Рыжаков А.П. Транспортная задача. Томск, ТГУ, 2003.-26с.
8. . Гендрина И.Ю., Катаева С.С., Рыжаков А.П. Градиентные и овражные методы безусловной минимизации. Томск, ТГУ, 2008.-30с.
в) программное обеспечение и Интернет-ресурсы
Комплекс программ «Оптимизация» для выполнения лабораторных работ.
8. Материально-техническое обеспечение дисциплины
В распоряжении преподавателей и обучающихся имеется основное необходимое материально-техническое оборудование, а именно компьютеры с соответствующим компьютерным обеспечением, Интернет-ресурсы, доступ к полнотекстовым электронным базам, книжный фонд (3,8 млн. экземпляров) Научной библиотеки Томского университета.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки 010400 - Прикладная математика и информатика
Автор к.т.н. Рыжаков А.П.
Рецензент к.т.н. Шмырин И.С.
Программа одобрена на заседании Ученого совета ФПМК
от ___________ 2011 года, протокол № ________.