Рабочая программа учебной дисциплины ен. В. 01 Методы оптимизации Для направления 230200 «Информационные системы»(бакалавры)
| Вид материала | Рабочая программа |
- Рабочая программа учебной дисциплины дн. Ф. 13 Операционные системы Для направления, 227.68kb.
- Рабочая программа учебной дисциплины сд. 03 Администрирование в ис для направления, 124.98kb.
- Программа дисциплины «информационные сети» Индекс дисциплины по учебному плану: опд., 123.28kb.
- Программа курса для направления 230200. 68 «Информационные системы. Программа Базы, 59.28kb.
- Программа курса для направления 230200. 68 «Информационные системы. Программа Базы, 65.82kb.
- Рабочая программа дисциплины Теория информации рекомендована методическим Советом Урфу, 600.02kb.
- Рабочая программа дисциплины «корпоративные информационные системы» Рекомендуется для, 196.36kb.
- Рабочая программа дисциплины Теория информационных процессов и систем Рекомендована, 870.15kb.
- Рабочая программа для направления (специальности), 68.28kb.
- Рабочая программа учебной дисциплины ф тпу 1-21/01 федеральное агентство по образованию, 250.01kb.
ГОУ ВПО
«Воронежский государственный технический университет»
«Утверждаю»
Декан ЕГФ
_____________С.М.Пасмурнов
РАБОЧАЯ ПРОГРАММА
УЧЕБНОЙ ДИСЦИПЛИНЫ
ЕН.В.01 Методы оптимизации
Для направления _230200 «Информационные системы»(бакалавры)
форма обучения очная
срок обучения нормативный
Воронеж 2007
Дисциплина преподается на основании решения учебно-методического совета факультета.
Составитель программы проф.каф.САПРИС,д.т.н. С.Ю.Белецкая
Рабочая программа обсуждена на заседании кафедры «Системы автоматизированного проектирования и информационные системы»
Протокол №___ от _____________ 200 г.
Зав. кафедрой проф.каф.САПРИС,д.т.н Я.Е.Львович
Рабочая программа рассмотрена и одобрена методической комиссией ЕГФ _____________ 200 г.
Председатель МК,
доцент, к.т.н. О.Г.Яскевич
^ С О Д Е Р Ж А Н И Е РАБОЧЕЙ ПРОГРАММЫ ПРЕПОДА-
ВАНИЯ ДИСЦИПЛИНЫ
1. Цель и задачи дисциплины
Основной целью преподавания дисциплины является изучение основных классов экстремальных задач и методов их решения, овладение студентами типовыми приемами построения математических моделей прикладных задач оптимального выбора, получение ими практических навыков разработки и использования средств алгоритмической и программной поддержки процедур принятия оптимальных решений.
При изучении дисциплины предполагается знание студентами следующих дисциплин: высшей математики, дискретной математики, вычислительной техники и программирования.
^ 2.Требования к уровню освоения содержания дисциплины
В результате изучения дисциплины студенты должны:
- получить знания об основных классах задач оптимизации, их особенностях и взаимосвязях;
- овладеть приемами построения и типизации математических моделей для различных классов задач оптимального выбора;
- знать основные методы оптимизации, уметь определять области их применения и проводить их сравнительный анализ;
- уметь идентифицировать оптимизационные задачи и выбирать наиболее приемлемые алгоритмы их решения;
- знать принципы построения и особенности организации программных комплексов оптимизации;
- приобрести навыки разработки алгоритмических процедур и программных средств для решения экстремальных задач различных типов;
- иметь опыт использования стандартного программного обеспечения для решения прикладных задач оптимизации в автоматическом и интерактивном режимах;
- уметь оценивать эффективность оптимизационного процесса и качество полученных решений.
3. Обьем дисциплины и виды учебной работы
Форма обучения очное
Срок обучения нормативный
Курс 3
| Вид занятий | Всего часов | Семестры и Количество часов | | |
| ^ Общая трудоемкость | 149 | 5 | 149 | |
| Аудиторные занятия | 72 | 5 | 72 | |
| Лекции | 36 | 5 | 36 | |
| Практические занятия | 18 | 5 | 18 | |
| Лабораторные работы | 18 | 5 | 18 | |
| Самостоятельная работа | 77 | 5 | 77 | |
| Курсовая работа | 20 | 5 | 20 | |
| Работа над темами для Самостоятельного изучения | 57 | 5 | 57 | |
| Рубежи контроля знаний (экзамен, зачет) | Экзамен зачет | 5 | Экзамен зачет | |
4.Содержание дисциплины
4.1. Разделы дисциплины и виды занятий
| Nn/n | Разделы дисциплины | Лекции (час) | Практ. занятия (час) |
| 1 | Введение | 2 | |
| 2 | Формализация процесса принятия оптимальных решений | 4 | 4 |
| 3 | Решение задач линейного программирования | 6 | 4 |
| 4 | Специальные задачи линейного программирования | 4 | 2 |
| 5 | Методы решения задач дискретной оптимизации | 6 | 6 |
| 6 | Основные методы безусловной нелинейной оптимизации | 4 | |
| 7 | Решение нелинейных задач оптимизации с ограничениями | 4 | |
| 8 | .Задачи динамического программирования | 4 | |
| 9 | Программные средства оптимального выбора | 2 | |
4.2..Содержание разделов дисциплины.
РАЗДЕЛ 1. Введение (2час)
Лекция 1. Понятие оптимизации. Использование оптимизационных процедур в решении прикладных задач. Связь данной дисциплины с общепрофессиональными и специальными дисциплинами. Организационно-методические указания по изучению дисциплины.
РАЗДЕЛ 2. Формализация процесса принятия оптимальных решений(4час)
Лекция 2.-3. Постановка задач оптимального выбора. Виды критериев оптимальности. Понятие множества Парето. Классификация задач оптимизации и методов их решения. Структурная и параметрическая оптимизация. Характеристики экстремальных задач в проектировании. Понятие сходимости алгоритмов и эффективности решения.
Обобщенная схема процесса оптимального выбора. Процедуры анализа, синтеза, принятия решений, их взаимосвязь. Основные факторы, влияющие на эффективность оптимизационного процесса.
РАЗДЕЛ 3. . Решение задач линейного программирования(6час)
^ Лекция 4-5. Постановка задачи линейного программирования. Формы записи задач линейного программирования и их эквивалентность. Приведение задачи линейного программирования к канонической форме.
Прикладные задачи линейного программирования. Построение моделей прикладных задач.
Решение задач линейного программирования графическим методом. Симплексный метод решения задач линейного программирования. Метод искусственного базиса. Матричная форма симплекс-метода. Параметрические задачи линейного программирования и их решение.
^ Самостоятельное изучение. Двойственность в линейном программировании. Основные приемы построения двойственных задач. Основные теоремы двойственности. Экономическая интерпретация двойственных задач. Связь между решениями прямой и двойственной задач. Применение двойственных оценок для анализа решения задач линейного программирования. Двойственный симплекс- метод. Использование двойственного симплекс-метода для решения задач с возрастающим числом ограничений.
РАЗДЕЛ 4. Специальные задачи линейного программирования(4час)
^ Лекция 7-8. Задачи линейного программирования транспортного типа. Открытые и закрытые модели транспортных задач. Особенности транспортных задач линейного программирования. Решение транспортной задачи методом потенциалов. Прикладные задачи транспортного типа.
^ Самостоятельное изучение Задачи дробно-линейного программирования. Основные приемы
сведения задач дробно-линейного программирования к типовым моделям
линейного программирования.
РАЗДЕЛ 5. Методы решения задач дискретной оптимизации(6час)
^ Лекция 9-11. Постановка задач дискретной оптимизации, основные приемы преобразования моделей. Классификация задач. Понятие о комбинаторных задачах. NP-полные задачи.
Примеры прикладных задач дискретной оптимизации. Задача коммивояжера, задачи о ранце, о покрытии, о назначениях, их прикладные аспекты. Дискретные задачи теории расписаний. Использование дискретных моделей ля решения задач структурного синтеза.
^ Самостоятельное изучение Классификация основных методов решения задач дискретной оптимизации. Метод Гомори для решения полностью целочисленных и частично целочисленных задач. Метод ветвей и границ.
РАЗДЕЛ 6. . Основные методы безусловной нелинейной оптимизации(4час)
Лекция 12.-13. Постановка задачи безусловной оптимизации. Классификация задач безусловной оптимизации и методов их решения. Методы нулевого, первого и второго порядков. Поисковые методы оптимального выбора: Нелдера-Мида, Хука-Дживса, Розенброка. Градиентные методы оптимизации: метод наискороейшего спуска, метод сопряженных градиентов. Методы минимизации ньютоновского типа.
РАЗДЕЛ 7 Решение нелинейных задач оптимизации с ограничениями(4час)
^ Лекция 14-15. Постановка задач нелинейного программирования. Задачи выпуклого программирования. Функция Лагранжа, принципы ее построения. Метод множителей Лагранжа для решения задач на условный экстремум. Условия оптимальности для задач выпуклого программирования. Теорема Куна-Таккера.
^ Самостоятельное изучение Общие сведения о решении задач условной оптимизации. Сведение задач с ограничениями к задачам безусловной оптимизации. Метод штрафных функций. Внутренние и внешние штрафные функции. Метод проекции градиента.
РАЗДЕЛ 8. Задачи динамического программирования(3час)
Лекция 16. Общая характеристика задач динамического программирования, их геометрическая и экономическая интерпретации.
Самостоятельное изучение Нахождение решения задач распределения ресурсов методом динамического программирования.
РАЗДЕЛ 9. Программные средства оптимального выбора(2час)
Лекция 17. Принципы построения программных комплексов принятия оптимальных решений. Основные требования к системам оптимизации, классификация систем. Обобщенная архитектура диалоговых систем оптимизации, режимы их функционирования.
^ Самостоятельное изучение Примеры программных комплексов оптимального выбора. Адаптация программных средств для решения различных классов оптимизационных задач.
5.Лабораторный практикум.
| N n/n | N раздела дисциплины | Наименование лабораторной работы | Кол-во часов |
| 1 | 2 | Изучение методов одномерной оптимизации | 4 |
| 2 | 3 | Решение задач линейной оптимизации средствами EXCEL . | 2 |
| 3 | 4 | Решение задач транспортного типа средствами EXCEL | 2 |
| 4 | 5 | Решение задач дискретной оптимизации средствами EXCEL . | 2 |
| 5 | 6 | Решение задач нелинейного программирования средствами EXCEL | 2 |
| 6 | 6 | Решение оптимизационных задач различных классов с использованием системы Mathcad. . | 4 |
| 7 | 6 | Решение оптимизационных задач различных классов с использованием системы Matlab. | 2 |
6. Учебно-методическое обеспечение дисциплины
6.1. Рекомендуемая литература
а). основная литература
1. Белецкая С.Ю. Принятие оптимальных решений с использованием средств EXCEL: Учеб. пособие. - Воронеж, 2000.
2. Дискретно-непрерывные модели оптимального проектирования: Учеб. пособие для вузов. - Воронеж: ВГТУ, 1997. - 109с.: ил.
3.Овчинников Владимир Анатольевич. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. пособие / В.А.Овчинников. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 28с.: ил.
б)дополнительная литература
1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие. - М., 1986. - 317с.
2. Белецкая Светлана Юрьевна. Решение задач математического программирования: Учеб. пособие / С.Ю.Белецкая. - Воронеж: Изд-во ВГТУ, 2001. - 97с.
6.2. Средства обеспечения освоения дисциплины
Системы Mathcad, Matlab
7. Материально-техническое обеспечение дисциплины.
Лаборатории «Информационных технологий» 217/3, 212/3
ЭВМ Pentium IV .
8. Методические рекомендации по организации изучения дисциплины
8.1. Методические рекомендации для преподавателя
Работа преподавателя по организации изучению дисциплины заключается в чтении лекций в соответствии с рабочей программой, проведении лабораторных занятий и их прием у студентов, проведение промежуточных мероприятий по проверке знаний, проведение итогового контроля в виде экзамена и проведение контроля остаточных знаний. Самостоятельное изучение отдельных разделов дисциплины преподаватель должен организовать в соответствии с планом-графиком самостоятельной работы студентов. Основной учебный материал занесён в систему дистанционного обучения Афина.
^ 8.2. Методические рекомендации для студентов
Студенты очной формы обучения нормативного срока обучения изучают дисциплину "Методы оптимизации" в течение 5 семестра. Виды и объем учебных занятий, формы контроля знаний приведены в табл. 1. Темы и разделы рабочей программы, количество лекционных часов и количество часов самостоятельной работы студентов на каждую из тем приведены в табл. 2. В первой колонке этой таблицы указаны номера тем согласно разделу 4. Организация лабораторного практикума, порядок подготовки к лабораторным занятиям и методические указания к самостоятельной работе студентов, а также порядок допуска к лабораторным занятиям и отчетности по проделанным работам определены в методических указаниях по выполнению лабораторных работ.
Самостоятельная работа студентов в ходе изучения лекционного материала заключается в проработке каждой темы в соответствии с методическими указаниями , а также в выполнении домашних заданий, которые выдаются преподавателем на лекционных занятиях. Необходимым условием успешного освоения дисциплины является строгое соблюдение графика учебного процесса по учебным группам в соответствии с расписанием.
^ 8.3. Самостоятельная работа и ее содержание.
При самостоятельной работе студенты изучают методы и алгоритмы оптимального выбора, недостаточно подробно представленные в лекционном курсе. Рассматриваются теоретические аспекты методов, а также вопросы программной реализации соответствующих алгоритмов.
^ 8.4. Содержание курсовой работы
Курсовая работа посвящена углубленному изучению теоретических и алгоритмических основ принятия оптимальных решений. Она заключается в построении и типизации математических оптимизационных моделей и разработке алгоритмического и программного обеспечения для решения различных классов задач оптимального выбора. Пояснительная записка объемом 20-30 страниц должна содержать: содержательную постановку задачи, формализованную оптимизационную модель; описание используемого метода решения с обоснованием его выбора, схемы алгоритмов решения, описание разработанных программных средств и их характеристики, анализ полученного решения; сравнительный анализ реализованного алгоритма с другими методами решения данной задачи. В приложении приводятся листинги разработанных программных средств и контрольный пример.
9. Рекомендуемый перечень тем практических занятий
1. Построение моделей прикладных задач оптимального выбора. Типизация моделей.
2. Решение задач линейного и нелинейного программирования графическим методом.
3. Решение задач линейного программирования с использованием симплекс-метода и метода искусственного базиса.
4. Построение двойственных задач линейного программирования. Двойственный симплекс-метод и его использование для решения задач с возрастающим числом ограничений.
5. Решение и преобразование задач линейного программирования транспортного типа.
6. Решение полностью и частично целочисленных задач линейного программирования методами Гомори и ветвей и границ.
7. Формирование условий оптимальности для задач нелинейного программирования. Решение задач нелинейного программирования методом множителей Лагранжа.
Приложение1
^ 4. КАЛЕНДАРНЫЙ ПЛАН ЧТЕНИЯ ЛЕКЦИЙ
| Номер и краткое название темы | Дата и N недель | Примечание |
| Лекция 1. Понятие оптимизации | 1 | |
| Лекция 2.-3. Постановка задач оптимального выбора. Виды критериев оптимальности. | 2-3 | |
| Лекция 4-6. Постановка задачи линейного программирования. Формы записи задач линейного программирования и их эквивалентность. | 4-6 | |
| Лекция 7-8. Задачи линейного программирования транспортного типа. Открытые и закрытые модели транспортных задач | 7-8 | |
| ^ Лекция 9-11. Постановка задач дискретной оптимизации, основные приемы преобразования моделей. Классификация задач. Понятие о комбинаторных задачах. NP-полные задачи. | 9-11 | |
| Лекция 12.-13. Постановка задачи безусловной оптимизации. Классификация задач безусловной оптимизации и методов их решения. | 12-13 | |
| Лекция 14-15. Постановка задач нелинейного программирования. Задачи выпуклого программирования. Функция Лагранжа, принципы ее построения | 14-15 | |
| Лекция 16. Общая характеристика задач динамического программирования, их геометрическая и экономическая интерпретации. | 16 | |
| Лекция 17. Принципы построения программных комплексов принятия оптимальных решений. Основные требования к системам оптимизации. | 17 | |
Приложение 2
^ План-график самостоятельной работы
| N Недели | Вид работы | Нормотив час/задание | Объем (кол-во заданий) | Трудоемкость за неделю (час) |
| 3 | Двойственность в линейном программировании. Основные приемы построения двойственных задач. Основные теоремы двойственности. Экономическая интерпретация двойственных задач | 4 | 5 | 12 |
| 4 | Задачи дробно-линейного программирования. Основные приемы | 3 | 3 | 10 |
| 9 | Классификация основных методов решения задач дискретной оптимизации. Метод Гомори для решения полностью целочисленных и частично целочисленных задач. Метод ветвей и границ. | 4 | 2 | 8 |
| 11 | Общие сведения о решении задач условной оптимизации. Сведение задач с ограничениями к задачам безусловной оптимизации | 5 | 3 | 15 |
| 12 | Нахождение решения задач распределения ресурсов методом динамического программирования. | 4 | 3 | 12 |