Рабочая программа дисциплины «Методы оптимизации» по направлению подготовки дипломированного специалиста 654600 «Информатика и вычислительная техника»
| Вид материала | Рабочая программа |
- Рабочая программа дисциплины «Компьютерная графика» по направлению подготовки дипломированного, 108.6kb.
- Рабочая программа дисциплины «Теория систем» по направлению подготовки дипломированного, 142.63kb.
- Рабочая программа дисциплины «Параллельные вычислительные процессы» по направлению, 108.72kb.
- Рабочая программа дисциплины «Теория принятия решений» по направлению подготовки дипломированного, 176.95kb.
- Рабочая программа дисциплины «Инструментальные средства 3D графики» по направлению, 112.55kb.
- Рабочая программа дисциплины «Проектирование интеллектуальных автоматизированных систем», 126.15kb.
- Рабочая программа дисциплины «Системный анализ и исследование операций» по направлению, 161.5kb.
- Рабочая программа дисциплины «Современные технологии разработки интеллектуальных автоматизированных, 121.51kb.
- Рабочая программа дисциплины «Системы искусственного интеллекта» по направлению подготовки, 132.28kb.
- Рабочая программа дисциплины «Теоретические основы автоматизированного управления», 141.49kb.
Министерство образования Российской Федерации
Московский государственный горный университет
УТВЕРЖДАЮ
Председатель УМК по направлению
«Информатика и вычислительная техника»
проф., д.т.н. Федунец Н.И.
«_____» ____________2002 г.
Рабочая программа
дисциплины «Методы оптимизации»
по направлению подготовки дипломированного специалиста
654600 - «Информатика и вычислительная техника»
специальности 220200 – «Автоматизированные системы обработки информации и управления»
Москва 2002
^ 1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Цель изучения дисциплины – формирование у студентов знаний математических моделей нелинейного программирования, методы и алгоритмы их решения.
Основными задачами изучения дисциплины являются:
- обучение практическим навыкам построения математических моделей нелинейного программирования;
- детальное изучение каждого метода и алгоритмов в области нелинейного программирования;
- приобретение практических навыков решения широкого круга задач нелинейного программирования на персональных компьютерах с использованием современных пакетов программ нелинейной оптимизации.
^ 2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ
В результате изучения дисциплины студент должен:
- знать основные классы и методы решения нелинейных задач математического программирования, возможности реализации нелинейных моделей с помощью ЭВМ;
- уметь осуществить математическую постановку конкретной задачи в различных сферах человеческой деятельности, выбрать метод и алгоритм ее решения, решить ее на основе современного программного обеспечения современных персональных компьютеров.
^ 3. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ
| Вид учебной работы | Всего часов | Семестр |
| Общая трудоемкость дисциплины Аудиторные занятия | 170(136) 68 | 6 |
| Лекции Практические занятия (ПЗ) Лабораторные занятия (ЛЗ) | 34 17 17 | 34 17 17 |
| Самостоятельная работа (СР) | 68 | 68 |
| Курсовая работа (КР) | | |
| Расчетно-графические работы (РГР) | | |
| Вид итогового контроля | | экзамен |
^ 4. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
4.1. Разделы дисциплины и виды занятий
| № п/п | Раздел дисциплины | Лекции | ПЗ | ЛР |
| 1 | 2 | 3 | 4 | 5 |
| 1 | Введение | | | |
| 2 | Часть 1. Методы нелинейного программирования без ограничений Методы минимизации без ограничений, использующие производные | * | * | * |
| 3 | Методы минимизации без ограничений, не использующие производные | * | * | * |
| 4 | ^ Часть2.Методы нелинейного программирования при наличии ограничений Методы линейной аппроксимации | * | * | * |
| 5 | Методы штрафных функций | * | * | * |
| 6 | ^ Часть 3. Специальные вопросы Геометрическое программирование | * | * | |
| 7 | Двойственность в задачах нелинейной оптимизации | * | * | |
| 8 | Программное обеспечение задач оптимизации | * | * | |
^ 4.2. Содержание разделов дисциплины
Раздел 1. Введение. (1 час.)
Предмет дисциплины, ее цели и задачи. Связь данной дисциплины с другими математическими дисциплинами.
Основные понятия и определение нелинейного программирования.
Общая математическая постановка задачи нелинейного программирования.
^ Часть 1. Методы нелинейного программирования без ограничений
Раздел 2. Методы минимизации без ограничений, использующие производные. (8 час.)
Классификация и краткая характеристика методов. Градиентные методы. Метод наискорейшего спуска. Метод вторых производных. Метод Ньютона-Рафсона. Сравнение методов, основанных на использовании производных первого и второго порядка.
Сопряженность и сопряженные направления. Метод сопряженного градиента (Флетчера-Ривса). Партан методы. Метод проекций (Заутендейка). Многопараметрический поиск. Метод Дэвидона–Флетчера-Пауэлла. Класс методов переменной метрики (градиентный метод с большим шагом). Сравнение алгоритмов программирования без ограничений.
^ Раздел 3. Методы минимизации без ограничений, не использующие производные (методы поиска). (8 час.)
Классификация методов поиска. Прямой поиск для функций n переменных. Метод Хука и Дживса. Поиск по деформируемому многограннику (метод Нелдера и Мида). Метод Розенброка. Метод Пауэлла. Методы случайного поиска. Сравнение алгоритмов нелинейного программирования при отсутствии ограничений.
^ Часть 2. Методы нелинейного программирования при наличии ограничений.
Раздел 4. Методы линейной аппроксимации. (4 час.)
Краткая характеристика методов. Метод аппроксимирующего программирования (МАП). Характерные черты семейства проективных методов: метод проекции градиента (метод Розена), обобщенный градиентный метод оптимизации поиска, обобщенный метод Дэвидона. Метод допустимых направлений (метод Заутендейка). Метод обобщенного приведенного градиента (МОПГ).
^ Раздел 5. Методы штрафных функций. (6 час.)
Методы штрафных функций специальной структуры. Метод, использующий множители Лагранжа, метод Розенброка, метод внутренней точки, метод Вейсмана. Метод последовательной безусловной минимизации.
Метод скользящего допуска. Стратегия алгоритма скользящего допуска.
Сравнения алгоритмов нелинейного программирования при наличии ограничений.
^ Часть 3. Специальные вопросы.
Раздел 6. Геометрическое программирование. (4 час.)
Краткая характеристика геометрического программирования. Задачи и методы геометрического программирования.
Раздел 7. Двойственность в задачах оптимизации. (2 час.)
Двойственность в задачах квадратичного, нелинейного и геометрического программирования.
^ Раздел 8. Программное обеспечение задач оптимизации. (3 час.)
Библиотеки и пакеты программ для решения задач оптимизации. Назначение, состав и характеристика. Практические приемы работы с программами из библиотек и пакетов программ. Интерфейс. Перспективы развития программного обеспечения задач оптимизации.
^ 5. ЛАБОРАТОРНЫЙ ПРАКТИКУМ
| № п/п | № раздела дисциплины | Наименование лабораторных работ |
| 1 2 3 4 5 6 7 | 1(1) 1(2) 2(4) 3(5) 3(6) 3(7) 3(7) | Решение задач минимизации без ограничений, не использующие производные Решение задач минимизации без ограничений, не использующие производные Решение задач оптимизации методом штрафных функций Решение задач геометрического программирования Решение двойственных задач нелинейного программирования Решение задач оптимизации на базе табличного процессора EXCEL Решение задач оптимизации с помощью пакета MATLAB |
Практические занятия
| № п/п | № раздела дисциплины | Наименование практического занятия |
| 1 2 3 4 5 6 7 | 2,8 3,8 3,8 4,8 5,8 6,8 7,8 | Нахождение минимума нелинейных функций методами, использующими производные первого и второго порядка. Решение задач оптимизации методами прямого поиска. Минимизация нелинейных функций методами случайного поиска. Решение задач нелинейного программирования проективными методами. Решение задач оптимизации методами штрафных функций. Решение задач геометрического программирования. Решение двойственных нелинейных задач оптимизации. |
^ 6. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
6.1. Рекомендуемая литература
а) основная литература
- Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы решения задач оптимизации. Киев, Высшая школа, 1983; с.512, библ. стр.482-505.
- Химмельблау Д. Прикладное нелинейное программирование. Пер. с англ. М., “Мир”, 1975, с.534, библ. к каждой главе.
- Банди Б. Методы оптимизации. Вводный курс. Пер. с англ. М., “Радио и связь”, 1988 г., с. 127, библ. к каждой главе.
- Базара М., Шетти К. Нелинейное программирование. Пер. с англ. М., “Мир”, 1982, с. 583, библ. с. 531-569 и с. 573-576.
- Зарубежные библиотеки и пакеты программ по вычислительной математике. Пер. с англ. М., “Наука”, 1993, с. 344, библ. к каждой главе..
б) дополнительная литература
- Хедли Дж. Нелинейное и динамическое программирование. Пер. с англ. М., “Мир”, 1967 г., с.506, библ. к каждой главе.
- М. Аоки. Введение в методы оптимизации. Основы и приложения нелинейного программирования. Пер. с англ. М., “Наука”, 1977 г., с. 343, библ. с. 332-340.
- Таха Х. Введение в исследование операций. В 2-х ч. Том2. М., “Мир”, с. 496.
- Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. Пер. с англ. М., “Мир”, 1972, с. 240, библ. с. 119 назв.
^ 6.2. Средства обеспечения освоения дисциплины
В качестве программного обеспечения практических занятий используются библиотеки программ по вычислительной математики NAG, IMSL, MATLAB, MATHCAD.
- ^ МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
Практические занятия по дисциплине «Методы оптимизации» проводятся в специализированной учебной лаборатории кафедры АСУ, оснащенный 10 современными персональными компьютерами на базе микропроцессоров PENTIUM II и PENTIUM III под управлением операционной системы WINDOWS 2000, UNIX, LINUX. Объем оперативной памяти составляет 128-256 Мб, накопителей на жестких дисках – несколько Гб.
- ^ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ
8.1. Методические рекомендации преподавателю
Лекции должны читаться в полном соответствии с нормами и правилами высшей школы Российской Федерации и данной рабочей программой. Преподавателю рекомендуется учесть как опыт чтения данной и подобных математических дисциплин в МГГУ и других ведущих университетах и вузах РФ, а также опыт чтения лекций в ведущих университетах передовых стран мира: США, Канада, Япония и др. Для этого преподавателю рекомендуется просматривать, причем регулярно, сайты и Web-страницы ведущих университетов в глобальной сети InterNet, посвященные как программам и отдельным разделам дисциплины «Методы оптимизации», так программному обеспечению решения задач оптимизации.
Практические занятия рекомендуется проводить в соответствии с темами практических занятий, утвержденных данной программой. Для полного освоения методов и алгоритмов задачи оптимизации решаются преподавателем совместно со студентами вручную в аудитории, а также в учебной лаборатории на современных персональных компьютерах на базе Pentium II, Pentium III с использованием операционной системы Windows 2000 и библиотек и пакетов программ IMSL, NAG и других на алгоритмических языках C/C++ и Java.
Как конкретные примеры, так и программы и алгоритмические языки преподаватель выбирает по собственному усмотрению. По каждой решенной задаче студент обязан выполнить отчет и защитить его. В результате выполнения и оформления всех задач оптимизации преподавателю рекомендуется провести зачетное занятие, в результате которого студент должен получить зачет.
Преподавателю, проводящему практические занятия, по согласованию с лектором, рекомендуется обратить внимание на вопросы, которые лектор рассмотрел на лекциях в сокращенном объеме.
При проведении со студентами вида учебной работы «Самостоятельная работа студента» преподавателю рекомендуется заранее разработать и в начале семестра выдать каждому студенту «Индивидуальное задание» по дисциплине «Методы оптимизации». Все «Индивидуальные задания» должны быть различными. Преподавателю, проводящему этот вид учебной работы, рекомендуется в одних заданиях предусмотреть несколько различных задач оптимизации, подлежащих решению студентом вручную различными методами с последующей проверкой полученных решений по рабочим программам, реализующим эти методы; в других заданиях возможно предложить решить одну и ту же задачу различными методами или с использованием различных алгоритмов, реализующих один и тот же метод; в третьих заданиях студентам может быть предложено либо полностью запрограммировать данный метод оптимизации, либо составить вызывающие программы на алгоритмических языках высокого уровня C, C++, Java.
^ 8.2. Рекомендуемые темы рефератов
- Характеристика методов прямого потока функции n переменных при отсутствии ограничений.
- Сравнительный анализ градиентных методов оптимизации при отсутствии ограничений.
- Краткая характеристика методов выбранной точки для безусловной минимизации.
- Вычислительные аспекты алгоритмов безусловной минимизации без производных.
- Вычислительные аспекты алгоритмов безусловной минимизации с использованием первых производных.
- Краткая характеристика методов одномерной оптимизации.
- Вычислительные аспекты алгоритмов безусловной оптимизации с использованием вторых производных.
- Сравнение проективных методов решения задач оптимизации.
- Оценки эффективности методов нелинейного программирования.
- Обзор библиотек и пакетов прикладных программ для решения задач оптимизации.
- Организация данных оптимизационных программ.
- Разработка программ решения задач оптимизации.
^ 8.3. Тематика самостоятельных работ студентов
- Краткая характеристика методов решения задач нелинейного программирования без ограничений.
- Краткая характеристика методов решения задач безусловной оптимизации при наличии ограничений.
- Математическая постановка и методы решения задач геометрического программирования.
- Форматы входных и выходных данных при решении задач оптимизации.
- Сравнение методов штрафных функций.
- Структура и краткое описание библиотек программ для решения задач оптимизации.
- Описание пакетов программ решения задач оптимизации на основе методов минимизации без ограничений, использующих производные.
- Описание пакетов программ решения задач оптимизации на основе методов минимизации без ограничений, не использующие производные.
- Краткая характеристика методов решения задач нелинейного программирования при наличии ограничений.
- Программирование одного из алгоритмов методов минимизации без ограничений, использующие производные.
- Программирование одного из алгоритмов методов минимизации без ограничений, не использующие производные.
- Программирование одного из методов нелинейного программирования при наличии ограничений.
^ 8.3. Методические рекомендации студентам
Студентам рекомендуется регулярно посещать лекции, тщательно конспектировать и прорабатывать их с одним из рекомендованных литературных источников.
На практических занятиях студенты совместно с преподавателем решают в аудитории отдельные оптимизационные задачи вручную у доски, в том числе с известной долей самостоятельности. Кроме того, некоторые задачи, решенные вручную, далее решаются на современных персональных компьютерах с предварительным объяснением преподавателем методики решения данной задачи. Некоторые задачи могут быть решены прямо на компьютере в качестве демонстрационных. Каждую задачу студент обязан оформить в виде отчета и защитить его. Выполнив и защитив все оптимизационные задачи, студент должен получить зачет по практическим занятиям.
При изучении данной дисциплины каждый студент должен получить у преподавателя, читающего лекции или проводящего только практические занятия, «Индивидуальное задание» по дисциплине «Методы оптимизации», которое он должен выполнить в установленный срок в виде отчета по «Индивидуальному заданию» и защитить у преподавателя, получив зачет.
В «Индивидуальном задании» студент решает несколько задач вручную с последующей проверкой полученных результатов решением их на компьютере. Студенту может быть предложено решить одну задачу различными методами или с использованием различных алгоритмов, реализующих данный метод. Студенту также может быть предложено запрограммировать конкретный метод, либо составить вызывающую программу на каком-либо языке высокого уровня.
Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по направлению 654600 – «Информатика и вычислительная техника» и специальности 220200 – «Автоматизированные системы обработки информации и управления».
Программу составил:
доц., к.т.н. Черников Ю.Г.
Рецензент
проф., д.т.н. Бахвалов Л.А.
Программа одобрена на заседании кафедры АСУ
«___» ___________2002 г. протокол №
Зав. кафедрой АСУ