скачать Федеральное агентство по образованию ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Р А Б О Ч А Я П Р О Г Р А М М А По дисциплине “Методы оптимизации " Для направления 010500 «Прикладная математика и информатика» (бакалавр) Факультет систем управления Профилирующая кафедра «Автоматизированных систем управления» Учебный план набора 2005 года курс четвертый семестр седьмой Распределение учебного времени (Всего часов) лекции 36 час. практические занятия - 18 час. всего аудиторных занятий – 54 час. самостоятельная работа - 48 час. общая трудоемкость – 102 часа экзамен 5 семестр 2008 Рабочая программа по дисциплине «Методы оптимизации» составлена с учетом требований Государственного образовательного стандарта высшего и профессионального образования по специальности 010500 – Прикладная математика и информатика, утвержденного 23 марта 2000г. Рабочая программа рассмотрена и утверждена на заседании кафедры АСУ. Протокол от " 03 " октября 2008 г. Разработчик профессор кафедры АСУ А.А. Мицель Зав. обеспечивающей каф. АСУ А.М. Кориков Рабочая программа согласована с факультетом, профилирующей и выпускающей кафедрой специальности Декан факультета систем управления Н.В. Замятин Зав. профилирующей кафедрой АСУ А.М. Кориков ^ В УЧЕБНОМ ПРОЦЕССЕ Дисциплина "Методы оптимизации" читается студентам специальности 010500 - " Прикладная математика и информатика ". Данная дисциплина" является одним из основных спецкурсов, оказывающих существенное влияние на чтение дисциплин по вопросам моделирования, управления, автоматизации проектирования, разработки программного обеспечения. Целью дисциплины является наиболее полное овладение студентами основных подходов к решению оптимизационных задач, начиная от методов минимизации функций одной переменной и кончая методами, применяемыми для решения нелинейных задач условной оптимизации большой размерности, задачами вариационного исчисления и оптимального управления. В результате изучения данной дисциплины студент должен знать основные идеи и алгоритмы оптимизации, уметь разрабатывать модели и алгоритмы и программно реализовывать их на ЭВМ. Для изложения методологических основ теории оптимизации требуется привлечение важнейших разделов теории матриц, элементов линейной алгебры и дифференциального исчисления, а также основных положений математического анализа. Весь материал дисциплины сформирован таким образом, что в первую очередь исследуется идейная сторона методов, связь их с другими методами. При необходимости доказываются основополагающие теоремы и лишь после этого рассматриваются конструктивные особенности алгоритмов. Большинство методов излагаются с учетом их последующей реализации на ЭВМ. При этом внимание уделяется практически важным вопросам: построение математической модели, ее реализации, подготовка к решению, выбор стратегии оптимизации и т.д. Дисциплина читается в течение одного семестра. Изучение завершается сдачей экзамена. ^ 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 часов ^
Всего часов самостоятельной работы по дисциплине 48 ^ 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. Общие положения
Рейтингу 60–79 соответствует оценка «удовлетворительно»; Рейтингу 80–99 соответствует оценка «хорошо»; Рейтингу 100–120 соответствует оценка «отлично». Экзамен «автомат» студент получает при условии: а) выполнил все практические задания; б) написал две контрольные работы; в) набрал не менее 80 баллов.
Тема 1. Элементы выпуклого анализа. Выпуклые множества, выпуклые функции - 6 баллов Тема 2. Минимизация функций одной переменной - 10 баллов Тема 3. Минимизация функции многих переменных - 10 баллов Тема 4. Линейное программирование - 10 баллов Тема 5. Решение условных задач нелинейного программирования - 10 баллов Тема 6. Квадратичное программирование - 10 баллов Тема 7. Динамическое программирование - 10 баллов Всего за практические занятия студент может получить 66 баллов.
За каждое практическое домашнее задание студент может получить по 2 балла. Максимальное количество баллов за практику составляет 14.
В течение семестра студенты выполняют две контрольные работы по лекционному курсу в период контрольных точек. Максимальное количество баллов за каждую контрольную работу составляет 15. Студент может получить дополнительно 10 баллов за регулярное посещение лекций.
|