ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»
Согласовано | Утверждаю | |
Руководитель ООП доц. | Зав. кафедрой ИС и ВТ доц. |
РАБОЧАЯ ПРОГРАММА
УЧЕБНОЙ ДИСЦИПЛИНЫ
«Методы оптимизации»
Направление подготовки: 230100.68 - Информатика и вычислительная техника
Программа подготовки: Методы анализа и синтеза проектных решений
Квалификация (степень) выпускника: магистр
Форма обучения: очная
Составитель: профессор
Санкт-Петербург
2012
Составитель: профессор
Научный редактор: профессор
1. Цель и задачи дисциплины.
Цель преподавания дисциплины – приобретение студентами знаний о современных методах поиска оптимальных решений на всех этапах применения вычислительной техники в различных областях научных исследований.
Задача дисциплины – ознакомление студентов с основами построения математических моделей сложных систем и методами их анализа.
2. Место дисциплины в структуре ООП.
Курс «Методы оптимизации» является базовой дисциплиной общенаучного цикла магистратуры по направлению подготовки 230100.68 – «Информатика и вычислительная техника» и изучается студентами в 1-м семестре.
Для освоения курса обучающийся должен обладать устойчивыми знаниями по математике, информатике и программированию на языке высокого уровня.
3. Требования к результатам освоения дисциплины:
Процесс изучения дисциплины направлен на формирование следующих компетенций:
ОК-1, ОК-2, ОК-6, ПК-1, ПК-2, ПК-4.
В результате изучения дисциплины студент должен:
Знать: основы теории оптимизации скалярной функций векторного аргумента как без ограничений, так и с ограничениями на переменные; применять различные численные методы поиска экстремумом таких функций; знать постановки задач линейного программирования (ЛП).
Уметь: строить математические модели задач оптимизации; решать задачи ЛП графически и с помощью программных сред Excel и Matlab.
Владеть: методом потенциалов для решения транспортной задачи, методом ветвей и границ для решения задачи поиска гамильтонова цикла на взвешенном графе, венгерским методом решения задачи оптимального размещения заказа.
4. Объём дисциплины и виды учебной работы.
Общая трудоёмкость дисциплины составляет 3 зачётные единицы (1 зач. ед.= 36 час.).
Вид учебной работы | Всего часов |
Аудиторные занятия | 45 |
В том числе: | |
Лекции (Л) | 15 |
Практические занятия (ПЗ) | 15 |
Лабораторные работы (ЛР) | 15 |
Самостоятельная работа (СР) | 63 |
Вид итогового контроля | экзамен |
Общая трудоемкость дисциплины | 108 |
5. Содержание дисциплины.
5.1. Содержание разделов дисциплины:
№ п/п | Наименование раздела дисциплины | Содержание раздела |
1 | Предмет курса и задачи его изучения | Общие сведения о дисциплине «Методы оптимизации»: классификация задач и методов их решения. |
2 | Одномерная оптимизация | |
3 | Безусловный экстремум скалярной функции векторного аргумента | Основные обозначения и определения. Необходимые и достаточные условия безусловного экстремума. Гессиан функции и его собственные числа. Критерий собственных чисел для определения типа экстремальной точки. Критерий Сильвестра для определения типа экстремальной точки. Выпуклые функции и их свойства. Исследование квадратичной функции на экстремум. |
4 | Условный экстремум скалярной функции векторного аргумента | Различные типы ограничений на переменные и их сведение к ограничениям-равенствам. Метод множителей Лагранжа для учета ограничений-равенств на переменные в задаче поиска экстремума скалярной функции векторного аргумента. Исследование типа условного экстремума. Частный случай квадратичной функции с линейными ограничениями-равенствами на переменные. Теорема Куна-Таккера. |
5 | Численные методы оптимизации | Итерационные методы поиска экстремумов скалярной функции векторного аргумента: метод покоординатного спуска, градиентные методы, метод Ньютона-Канторовича. Сходимость численных методов. Связь градиентного метода с динамической системой. |
6 | Задача линейного программирования (ЛП) | Постановка задачи ЛП, примеры. Симплекс и его свойства, разрешимость задачи ЛП. Графический метод решения задачи ЛП. |
7 | Оптимизация на графах | Основные определения теории графов. Транспортная задача и метод потенциалов для ее решения. Задача оптимального возврата кредита, задача оптимального размещения заказа и венгерский метод ее решения. Задача “коммивояжера” (поиск гамильтонова цикла на взвешенном графе). |
5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами.
Обеспечиваемая (последующая) дисциплина – «Методы оптимизации (доп. главы)», выпускная квалификационная работа (ВКР).
5.3. Разделы дисциплин и виды занятий:
№ п/п | Наименование раздела дисциплины | Трудоёмкость (час.) | |||
Всего | Л | ПЗ | ЛР | ||
1 | Предмет курса и задачи его изучения | 1 | 1 | - | - |
2 | Одномерная оптимизация | 4 | 2 | 2 | - |
3 | Безусловный экстремум скалярной функции векторного аргумента | 10 | 4 | 6 | - |
4 | Условный экстремум скалярной функции векторного аргумента | 7 | 3 | 4 | - |
5 | Численные методы оптимизации | 6 | 2 | - | 4 |
6 | Задача линейного программирования (ЛП) | 7 | 2 | 2 | 3 |
7 | Оптимизация на графах | 10 | 1 | 1 | 8 |
Итого: | 45 | 15 | 15 | 15 |
6. Лабораторный практикум:
№ п\п | № раздела дисцип. | Наименование лабораторной работы | Количество часов |
1 | 5 | Численные методы оптимизации. Их реализация в среде Matlab. | 4 |
2 | 6 | Симплекс-метод решения задачи ЛП и его реализация в среде Excel и Matlab. | 3 |
3 | 7 | Метод потенциалов для решения транспортной задачи: использование АОС и решение контрольных задач. | 4 |
4 | 7 | Метод ветвей и границ для решения задачи “коммивояжера”: использование АОС и решение контрольных задач. | 4 |
Итого: | 15 |
7. Практические занятия:
№ п\п | № раздела дисцип. | Наименование практического занятия | Количество часов |
1 | 1,2 | Исследование скалярной функции скалярного аргумента на экстремум. Вычисление Гессиана и его собственных чисел при исследовании экстремума скалярной функции векторного аргумента. | 4 |
2 | 2 | Критерий Сильвестра для определения типа экстремальной точки скалярной функции векторного аргумента. | 2 |
3 | 2 | Исследование квадратичной функции на экстремум. | 2 |
4 | 4 | Метод множителей Лагранжа в задаче условной оптимизации. Условия Куна-Таккера. | 4 |
5 | 6 | Графический метод решения задачи ЛП. | 2 |
6 | 7 | Венгерский метод решения задачи оптимального размещения заказа. | 1 |
Итого: | 15 |
8. Семинарские занятия и примерная тематика курсовых проектов (работ).
При изучении дисциплины семинарские занятия и курсовая работа не предусмотрены.
9. Учебно-методическое и информационное обеспечение дисциплины:
а) основная литература
1. Таха Введение в исследование операций (7-е изд.). М., СПб, Киев: Издательский дом «Вильямс», 2005. – 901 с.
2. , Загоруйко операций: Учеб. для втузов/ ред. . - М.: Изд-во МГТУ, 200с. -(Математика в техническом университете, В. 20).
3. , Северцев операций: принципы принятия решений и обеспечение безопасности: Учеб. пособие/ ред. . - М.: Физматлит, 2000.-318 с.
б) дополнительная литература
4. Акулич программирование в примерах и задачах: Учебное пособие. - М.:Высш. шк.,1993.-336 с.
5. Основы исследования операций (в 3-х томах).- М.: Мир,-тс.-т– 488 с.-тс.
6. 3айченко Ю. П, Щумилова операций: Сборник задач-Киев: Выща шк., 1990.-239 с.
7. Карманов программирование.-5-е изд., испр - М.: Физматлит, 2000.-263 с.
8. Современное линейное программирование, - М.: Мир,1984.-224 с.
9. Введение в исследование операций (в 2-x кн.). М.:Мир,1985, Кн.1.-479 с., Кн. 2.-469
в) программное обеспечение: Microsoft Office (Excel), Matlab (Optimization toolbox), а также оригинальные авторские автоматизированные обучающие системы: АОС «Транспортная задача» и АОС «Задача коммивояжера».
г) ресурсы Интернет.
10. Материально-техническое обеспечение дисциплины:
а) кафедральный компьютерный класс.
_____________________________________________________________________________
Разработчик:
кафедра ИС и ВТ профессор
