Рабочая программа По дисциплине "Методы оптимизации " Для направления 010500 «Прикладная математика и информатика»

Вид материала

Содержание

1. Цели и задачи дисциплины и ее место
2. Содержание дисциплины
3.Формы самостоятельной работы
4. Учебно-методические материалы по дисциплине
Рейтинговая система оценки знаний

Подобный материал:

Федеральное агентство по образованию

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

УТВЕРЖДАЮ

Проректор по учебной работе

Л.А. Боков

2008 г.

Р А Б О Ч А Я П Р О Г Р А М М А

По дисциплине “Методы оптимизации "

Для направления 010500 «Прикладная математика и информатика»

(бакалавр)

Факультет систем управления

Профилирующая кафедра «Автоматизированных систем управления»

Учебный план набора 2005 года

курс четвертый

семестр седьмой

Распределение учебного времени (Всего часов)

лекции 36 час.

практические занятия - 18 час.

всего аудиторных занятий – 54 час.

самостоятельная работа - 48 час.

общая трудоемкость – 102 часа

экзамен 5 семестр

2008

Рабочая программа по дисциплине «Методы оптимизации» составлена с учетом требований Государственного образовательного стандарта высшего и профессионального образования по специальности 010500 – Прикладная математика и информатика, утвержденного 23 марта 2000г.

Рабочая программа рассмотрена и утверждена на заседании кафедры АСУ.

Протокол от " 03 " октября 2008 г.

Разработчик

профессор кафедры АСУ А.А. Мицель

Зав. обеспечивающей

каф. АСУ А.М. Кориков

Рабочая программа согласована с факультетом, профилирующей и выпускающей кафедрой специальности

Декан

факультета систем управления Н.В. Замятин

Зав. профилирующей кафедрой АСУ А.М. Кориков

1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ И ЕЕ МЕСТО

В УЧЕБНОМ ПРОЦЕССЕ

Дисциплина "Методы оптимизации" читается студентам специальности 010500 - " Прикладная математика и информатика ". Данная дисциплина" является одним из основных спецкурсов, оказывающих существенное влияние на чтение дисциплин по вопросам моделирования, управления, автоматизации проектирования, разработки программного обеспечения.

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

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

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

Дисциплина читается в течение одного семестра. Изучение завершается сдачей экзамена.

2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

2.1 Наименование тем, объем в часах, содержание.

Тема 1. Введение.

Лекции - 2 часа

Методологические основы оптимизации. Применение методов оптимизации в инженерной практике. Связь с теорией автоматического управления. Исторический путь становления различных методов оптимизации. Цель, задачи и содержание курса.

Тема 2. Постановка и классификация задач.

Лекции - 2 час, самостоятельная работа - 2 часа.

Содержательные и формализованные постановки задач оптимизации. Критерии качества и ограничения. Классификация задач оптимизации по виду целевой функции, критерию и типу ограничений. Задачи математического программирования и управления.

Тема 3. Анализ экстремальных задач (минимизация функций). Лекции - 4 часа, самостоятельная работа - 2 часа.

Необходимые и достаточные условия существования экстремума функций без ограничений (скалярный и векторный случаи). Необходимые и достаточные условия существования условного экстремума в задачах с ограничениями. Теорема Сильвестра. Квадратичные формы. Функция Лагранжа. Условия оптимальности в терминах седловых точек функции Лагранжа. Теорема Куна - Таккера. Принцип двойственности в задачах математического программирования.

Тема 4. Методы минимизации функций. Лекции - 4 часа, самостоятельная работа - 2 часа.

4.1. Методы одномерного поиска

Математическая постановка задачи. Унимодальность и основные свойства унимодальных функций. Глобальная и ассимптотическая сходимость. Методы исключения интервалов: равномерного поиска, дихотомии, Фибоначчи, золотого сечения, метод ломанных. Полиномиальная аппроксимация и методы точечного оценивания. Методы оптимизации с использованием производных. Сравнительные оценки методов.

4.2. Методы поиска экстремума функций многих переменных.

Методы покоординатного спуска, метод Хука-Дживса, метод сопряженных направлений Пауэлла. Градиентные методы: метод Коши, метод Ньютона, метод Флетчера-Ривза. Алгоритмы с самонастройкой параметра длины рабочего шага. Проблемы вычисления элементов матрицы Гессе. Квазиньютоновские методы, методы с переменной метрикой. Алгоритмы Дэвидона-Флетчера-Пауэлла, Поллака-Рибьера, Бройдена-Флетчера-Шенно. Сравнение методов и результатов вычислительных экспериментов.

Тема 5. Модели и методы линейного программирования. Лекции - 6 часов, самостоятельная работа - 2 часа.

Математическая постановка и особенности задач ЛП. Основные формы записи задач ЛП. Приведение задач ЛП к стандартной и канонической форме. Графический метод решения задач ЛП, характеристика экстремальных точек. Симплекс-метод. Оптимальные планы и их определение. Симплекс-таблица. Критерий оптимальности симплекс - таблицы и процедура улучшения плана. Метод искусственного базиса. Двойственная задача ЛП, двойственный симплекс-метод. Анализ чувствительности в линейном программировании. Задачи целочисленного ЛП. Метод Гомори. Метод ветвей и границ. Способы построения дополнительных ограничений. Рекомендации составления моделей и решения задач ЛП.

Тема 6. Методы нелинейного программирования для задач с ограничениями. Лекции - 8 час, самостоятельная работа - 2 часа.

Математическая постановка и особенности задач НП. Задачи выпуклого программирования. Метод неопределенных множителей Лагранжа. Задачи квадратичного программирования. Практические приложения алгоритмов к решению экономических задач. Метод допустимых направлений Зойтендака. Сепарабельное программирование. Метод отсекающих плоскостей, метод линейных комбинаций. Методы штрафных и барьерных функций. Стохастическое программирование. Проблемы многокритериальной оптимизации.

Тема 7. Вариационное исчисление. Лекции - 6 часов, самостоятельная работа - 2 часа.

Функционалы. Основные понятия. Вариационные задачи с закрепленными концами, уравнения Эйлера, уравнения Эйлера Пуассона. Прямые методы решения вариационных задач.

Тема 8. Основы теории оптимального управления. Лекции – 4 часа, самостоятельная работа – 2 часа.

Задача оптимального управления, математическая модель объекта, критерий оптимальности, допустимое управление, ограничения на вектор состояния. Метод Лагранжа Понтрягина. Методы динамического программирования.

2.2. Практические занятия. Наименование тем и их объемы

Тема 1. Элементы выпуклого анализа. Выпуклые множества,

выпуклые функции - 2 часа

Тема 2. Минимизация функций одной переменной - 3 часа

Тема 3. Минимизация функции многих переменных - 3 часа

Тема 4. Линейное программирование - 3 часа

Тема 5. Решение условных задач нелинейного программирования - 3 часа

Тема 6. Квадратичное программирование - 2 часа

Тема 7. Динамическое программирование - 2 часа

Общее количество практических занятий 18 часов

3.Формы самостоятельной работы

№ п/п	Наименование работы	Кол-во час.	Форма контроля
1	Проработка лекционного материала	14	Экзамен
2	Подготовка к практическим занятиям	12	Опрос на занятиях. Проверка домашних работ.
3	Подготовка и проработка теоретического материала для выполнения контрольных работ	10	Оценка выполненных контрольных работ на основе собеседования.
4	Темы для самостоятельной работы. Метод ломанных одномерного поиска. Одномерная оптимизация с использованием кубической аппроксимации. Алгоритмы многомерного поиска Дэвидона-Флетчера-Пауэлла, Поллака-Рибьера, Бройдена-Флетчера-Шенно. Двойственная задача линейного программирования Метод Гомори решения задачи целочисленного программирования	12	Опрос. Оценка качества выполненных работ.

Всего часов самостоятельной работы по дисциплине 48

4. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ

4.1. Основная литература.

1. Мицель А.А., Шелестов А.А. Методы оптимизации: Учеб. пособие – Томск: Изд-во ТУСУРа, 2005. – 256 с.

2. Методы оптимизации. Лабораторный практикум: Учеб. пособие / Мицель А.А., Шелестов А.А., Романенко В.В., Клыков В.В. – Томск: Изд-во Томск. гос. ун-та систем управления и радиоэлектроники, 2004. – 80 с.

3. Рубан А.И. Оптимизация систем. Учебное пособие.-Томск: Изд-во Томск. ун-та, 1984.

4. Сборник задач по математике для втузов. Ч.4. Методы оптимизации. /Вуколов и др.; под ред. А.В.Ефимова. - М.: Наука, 1990.

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

1. Реклейтис Г., Рейвиндран А., Рэгсдел К.Оптимизация в технике: В 2-х кн. Пер. с англ.- М.: Мир, 1986.

2. Габбасов Р., Кириллова Ф.М. Методы оптимизации. - Минск: Изд-во БГУ, 1988.

3. Карманов В.Г. Математическое программирование: Учебное пособие. - М.: Наука, 1989.

4. Химмельблау Д. Прикладное нелинейное программирование.- М.: Мир, 1991.

5. Аоки М. Введение в методы оптимизации. - М.: Наука, 1988.

6. Гилл Ф. и др. Практическая оптимизация. - м.: Мир, 1992.

7. Боглаев Ю.П. Вычислительная математика и программирование: Учебное пособие для студентов втузов. - М.: Наука, 1989.

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

5.1. РЕЙТИНГОВАЯ СИСТЕМА ОЦЕНКИ ЗНАНИЙ

ПО ДИСЦИПЛИНЕ «МЕТОДЫ ОПТИМИЗАЦИИ»

5.1. Общие положения

Максимальное количество баллов – 120;

Рейтингу 60–79 соответствует оценка «удовлетворительно»;

Рейтингу 80–99 соответствует оценка «хорошо»;

Рейтингу 100–120 соответствует оценка «отлично».

Экзамен «автомат» студент получает при условии: а) выполнил все практические задания; б) написал две контрольные работы; в) набрал не менее 80 баллов.

Баллы за практические задания начисляются за успешно выполненные домашние задания и сданные на следующем занятии после получения задания. Сдача домашних заданий после установленного срока баллами не оценивается.
Баллы за контрольные работы по лекционному материалу начисляются в размере от 0 до максимального в зависимости от знаний студента.
Студент может получить дополнительные баллы за регулярное посещение лекций

Рейтинг по практическим занятиям

Тема 1. Элементы выпуклого анализа. Выпуклые множества,

выпуклые функции - 6 баллов

Тема 2. Минимизация функций одной переменной - 10 баллов

Тема 3. Минимизация функции многих переменных - 10 баллов

Тема 4. Линейное программирование - 10 баллов

Тема 5. Решение условных задач нелинейного программирования - 10 баллов

Тема 6. Квадратичное программирование - 10 баллов

Тема 7. Динамическое программирование - 10 баллов

Всего за практические занятия студент может получить 66 баллов.

Рейтинг по домашним практическим заданиям

За каждое практическое домашнее задание студент может получить по 2 балла. Максимальное количество баллов за практику составляет 14.

Рейтинг по контрольным работам

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

Максимальное количество баллов за каждую контрольную работу составляет 15.

Студент может получить дополнительно 10 баллов за регулярное посещение лекций.

Blog

Рабочая программа По дисциплине "Методы оптимизации " Для направления 010500 «Прикладная математика и информатика»

Содержание