Рабочая программа дисциплины М1.1.2 Методы оптимизации

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

УТВЕРЖДАЮ Декан ФВТ _______________ Л. Р. Фионова «_____» ___________________ 2015 г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

М1.1.2 Методы оптимизации

Направление подготовки 090401 «Информатика и вычислительная техника» (уровень магистратуры)

Магистерские программы

«Системы автоматизированного проектирования»;

«Вычислительные машины, комплексы, системы и сети».

Квалификация выпускника магистр

Форма обучения очная

Пенза, 2015

1. Цели освоения дисциплины

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

2. Место дисциплины в структуре ООП

2.1. Дисциплина входит в базовую часть образовательной программы. Изучение данной дисциплины базируется на следующих курсах: высшей математики, информатики, программирования, теории принятия решений, дискретной математики.. Дисциплина является предшествующей для изучения дисциплин «Планирование и организация научных исследований» «Интеллектуальные методы проектирования / Проектирование информационно-аналитических комплексов и систем» и научно-исследовательской работе по теме магистерской диссертации»

2.2. Минимальные требования к «входным» знаниям, необходимым для успешного усвоении данной дисциплины ‑ удовлетворительное усвоение программ по следующим разделам указанных выше дисциплин:

-  «Высшая математика» ‑ разделы "Математический анализ",»Алгебра», «Теория вероятностей и математическая статистика»;

-  «Информатика» в полном объеме;

-  «Программирование» ‑  практика программирование на языке высокого уровня;

-  «Дискретная математика» ‑ теория графов.

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

Коды компетенции	Наименование компетенции	Структурные элементы компетенции (в результате освоения дисциплины обучающийся должен знать, уметь, владеть)
1	2	3
ОПК-1	способностью воспринимать математические, естественнонаучные, социально-экономические и профессиональные знания, умением самостоятельно приобретать, развивать и применять их для решения нестандартных задач, в том числе в новой или незнакомой среде и в междисциплинарном контексте (ОПК-1);	Знать классификацию задач оптимизации,, методы многокритериальной оптимизации, линейной и нелинейной оптимизации, динамического программирования;
Уметь создавать математические модели практических задач, выбирать наиболее оптимальные способы их решения, использовать вычислительную технику и программные средства для их решения
Владеть методами многокритериальной свертки.
ПК-3	знанием методов оптимизации и умение применять их при решении задач профессиональной деятельности (ПК-3);

4. Структура и содержание дисциплины (модуля) __Методы оптимизации____________________________

4.1. Структура дисциплины (модуля)

Общая трудоемкость дисциплины составляет _3____ зачетных единиц, _108______ часов.

№ п/п	Наименование разделов и тем дисциплины (модуля)	Семестр	Недели семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра)
Аудиторная работа	Самостоятельная работа
Всего	Лекция	Практические занятия	Лабораторные занятия	Всего	Подготовка к аудиторным занятиям	Реферат, эссе и др.	Курсовая работа (проект)	Подготовка к экзамену	Собеседование	Коллоквиум	Проверка тестов	Проверка контрольн. работ	Проверка реферата	Проверка эссе и иных творческих работ	курсовая работа (проект)
1.	Раздел 1. Классификация задач оптимизации				6		2
1.1.	Тема 1.1. Вводная лекция				2
1.2.	Тема 1.2. Классификация задач оптимизации				2				2			2
1.3..	Тема 1.3 Математические модели				2		2		2			2
2.	Раздел 2. Многокритериальная оптимизация				4		4		8			8	2- 5
2.1	Тема 2.1 Задача многокритериальной оптимизации				4		4		8			8	11
3	Раздел 3. Линейная и нелинейная оптимизация				4		8		16			16	12
3.1	Тема 3.1 Методы линейной оптимизации				2		4		8			8	12
3.2	Тема 3.2. Методы нелинейной оптимизации				2		4		8			8	13
4	Раздел 4. Динамическое программирование				4		4		8			8	14
4.1	Тема 4.1. Динамическое программирование.				4		4		8			8	1
	Курсовая работа (проект)
	Подготовка к экзамену											36
	Общая трудоемкость, в часах				18		18		36			36	Промежуточная аттестация
Форма	Семестр
Экзамен	1

4.2. Содержание дисциплины (модуля)

4.2.1.Содержание лекционного курса

Раздел 1. Классификация задач оптимизации

Тема 1.1. Вводная лекция

Цели и задачи курса и структура курса, его место в подготовке специалиста. Оптимизация как поиск наилучшего решения. Математическое программирование.

Тема 1.2. Классификация задач оптимизации.

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

Тема 1.3 Математические модели.

Основные компоненты математической модели. Выделение искомых параметров и зависимостей между ними. Критерий оптимизации. Основные компоненты математической модели: функции цели, ограничений, граничных условий. Зависимость выбора метода решения от вида математической модели.

Раздел 2. Многокритериальная оптимизация

Тема 2.1 Задача многокритериальной оптимизации.

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

Раздел 3. Линейная и нелинейная оптимизация

Тема 3.1 Методы линейной оптимизации.

Постановка задачи линейной оптимизации. Основные утверждения теории выпуклых множеств. Стандартная, каноническая и общая постановка задачи линейной оптимизации в векторной и аналитической форме. Определения компактного, ограниченного, замкнутого и выпуклого множества, угловой и граничной точки. Основные утверждения теории выпуклых множеств

Геометрический Симплекс-метод. Аналитический Симплекс-метод.

Двойственная задача линейного программирования. Метод потенциалов..

Тема 3.2. Методы нелинейной оптимизации.

Постановка и основные утверждения нелинейной оптимизации. Теорема Куна-Таккера. Классический анализ задач нелинейной оптимизации. Задачи условной и безусловной оптимизации. Обзор методов решения задач безусловной оптимизации.

Метод множителей Лагранжа. Решение задачи условной оптимизации методом множителей Лагранжа.

Целочисленное программирование Выпуклое программирование.

Метод штрафных функций. Стохастические методы решения оптимизационных задач.

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

Раздел 4. Динамическое программирование

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

Основные понятия и утверждения. Постановка задачи динамического программирования. Приложение метода динамического программирования к решению задачи маршрутизации

4.2.2. Перечень и содержание лабораторных занятий.

№ п/п	№ темы	Наименование лабораторных работ	Кол. ч
1	1.2	Математические модели	2
2	2.1	Многокритериальная оптимизация	4
3	3.1	Методы линейной оптимизации	4
4	3.2	Методы нелинейной оптимизации	4
5	4.1	Динамическое программирование	4

5. Образовательные технологии

5.1 Чтение лекций по дисциплине проводится с использованием мультимедийного компьютерного проектора.

5.2 При изучении материалов лабораторного практикума использовать Интернет ресурсы с сайта кафедры САПР (cad. pnzgu. ru).

5.3 При самостоятельной работе используются материалы сайта «Интернет-Университет Информационных Технологий (www. intuit. ru).

5.4. В лабораторном практикуме используются офисные и программные пакеты символьной и численной математики.

5.5. Все лабораторные занятия носят проектный характер.

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

6. Учебно-методическое обеспечение самостоятельной работы студентов.

Оценочные средства для текущего контроля успеваемости,

промежуточной аттестации по итогам освоения дисциплины.

6.1. План самостоятельной работы студентов

№ нед.	Тема	Вид самостоятельной работы )	Задание	Рекомендуемая литература	Количество
	Тема 1.2	Подготовка к аудиторным занятиям	Изучить классификацию задач оптимизации.	Учебно-методические материалы и электронные учебные пособия из раздела «Методы оптимизации» файл-сервера кафедры САПР (диски М и Т, сервер cad-filer, IP 172.16.72.254); основная и дополнительная литература.	2
	Тема 1.3	Подготовка к аудиторным занятиям	Изучить основные компоненты математической модели: функции цели, ограничений, граничных условий и построить в соответствии с заданием..	Учебно-методические материалы и электронные учебные пособия из раздела «Методы оптимизации» файл-сервера кафедры САПР (диски М и Т, сервер cad-filer, IP 172.16.72.254); основная и дополнительная литература.	2
	Тема 2.1	Подготовка к аудиторным занятиям	Изучить методы скаляризации критериев и выполнить расчеты в соответствии с заданием.	Учебно-методические материалы и электронные учебные пособия из раздела «Методы оптимизации» файл-сервера кафедры САПР (диски М и Т, сервер cad-filer, IP 172.16.72.254); основная и дополнительная литература.	8
	Тема 3.1	Подготовка к аудиторным занятиям	Изучить методы линейной оптимизации и выполнить расчеты в соответствии с заданием..	Учебно-методические материалы и электронные учебные пособия из раздела «Методы оптимизации» файл-сервера кафедры САПР (диски М и Т, сервер cad-filer, IP 172.16.72.254); основная и дополнительная литература.	8
	Тема 3.2	Подготовка к аудиторным занятиям	Изучить методы линейной оптимизации и выполнить расчеты в соответствии с заданием...	Учебно-методические материалы и электронные учебные пособия из раздела «Методы оптимизации» файл-сервера кафедры САПР (диски М и Т, сервер cad-filer, IP 172.16.72.254); основная и дополнительная литература.	8
	Тема 3.2	Подготовка к аудиторным занятиям	Изучить методы динамического программирования и выполнить расчеты в соответствии с заданием...	Учебно-методические материалы и электронные учебные пособия из раздела «Методы оптимизации» файл-сервера кафедры САПР (диски М и Т, сервер cad-filer, IP 172.16.72.254); основная и дополнительная литература.	8

6.2. Методические указания по организации самостоятельной работы студентов

Планируются следующие виды самостоятельной работы (внеаудиторной) относятся:

-  подготовка к лабораторным работам занятиям,

-  оформление отчётов по лабораторным работам,

-  подготовка к зачету,

-  работа с конспектом лекций и изучение рекомендованной литературы при подготовке к экзаменам.

6.3. Материалы для проведения текущего и промежуточного контроля знаний студентов

Контроль освоения компетенций

№ п\п	Вид контроля	Контролируемые разделы	Компетенции, компоненты которых контролируются
1	Текущий: собеседование при защите лаб. заданий	Разделы 1-4.	ОПК-1; ПК-3
2	Промежуточный: контроль, экзамен	Разделы 1-4	ОПК-1; ПК-3

Контроль освоения компетенции выполняется:

-  для компетенции (ОПК-1) ‑ путем оценки степени владения студентом способностью воспринимать математические и профессиональные знания в области математического программирования, умением самостоятельно приобретать, развивать и применять их для решения нестандартных задач, в том числе в новой или незнакомой среде и в междисциплинарном контексте

-  для компетенции (ПК-3) – путем оценки степени владения знанием методов оптимизации и умением применять их при решении задач профессиональной деятельности при выполнении лабораторного практикума.

Примерный перечень вопросов и заданий к экзамену

1.  Классификация задач оптимального проектирования. Основные этапы принятия оптимальных решений

2.  Построения математической модели Основные правила. Основные компоненты математической модели.

3.  Многокритериальная оптимизация. Оптимальность по Парето.

4.  Методы объединения критериев в задаче многокритериальной оптимизации

5.  Основные понятия линейной алгебры. Понятие базиса. Переход к новому базису.

6.  Основные понятия линейного программирования. Постановка задачи(стандартная, каноническая, общая)

7.  Основные утверждения линейного программирования. Понятия базисно допустимого и базисного решения.

8.  Экономическая интерпретация элементов отчетов Excel по решению задачи линейного программирования.

9.  Геометрическая интерпретация решения задач линейного программирования,

10.  Симплекс-метод аналитический.

11.  Ситуации, возникающие при решении симплекс-методом. (бесконечно много решений, нет решений, зацикливание).

12.  Экономическая интерпретация элементов симплекс-таблицы.

13.  Двойственная задача (Алгоритм составления двойственной задачи).

14.  Решение двойственной задачи

15.  Анализ решения задачи линейного программирования с помощью двойственных оценок

16.  Математическая модель транспортной задачи. Усложнения в постановке транспортной задачи.

17.  Нахождение опорного плана транспортной задачи.

18.  Алгоритм решения задачи назначения.

19.  Классификация задач нелинейного программирования.

20.  Задачи условной и безусловной оптимизации.

21.  Постановка задачи безусловной оптимизации. Градиентные методы решения задач безусловной оптимизации.

22.  Метод Хука-Дживса для решения задачи безусловной оптимизации.

23.  Нелдера—Мида для решения задачи безусловной оптимизации.

24.  Метод Розенброка для решения задачи безусловной оптимизации.

25.  Постановка задачи условной оптимизации.

26.  Решение задачи условной оптимизации методом множителей Лагранжа.

27.  Понятие унимодальной функции.

28.  Методы половинного деления, золотого сечения, чисел Фибоначчи.

29.  Постановка задачи динамического программирования.

30.  Приложение метода динамического программирования к решению задачи маршрутизации при фиксированном размере шага.

31.  Приложение метода динамического программирования к решению задачи маршрутизации при произвольном размере шага.

7. Учебно-методическое и информационное обеспечение

дисциплины (модуля)

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

1. , , Старостин дискретных задач с помощью эволюционно – генетических алгоритмов: Учебное пособие. – Н. Новгород: Изд-во ННГУ, 2011.-199 с.

2. Таха в исследование операций. М.: Вильямс, 2006. Гл. 5, 6.

3. Исследование операций в экономике: Учебное пособие для вузов / , , ; под ред. проф. . М.: ЮНИТИ, 2006. Гл. 7,

4. Батищев сложность экстремальных задач переборного типа: Учебное пособие / Д. И Батищев, Д. И Коган. – Н. Новгород: ННГУ, 19994.

5. Акулич Математическое программирование в примерах и задачах: Учебное пособие. 2-е изд - Лань, СПб, 2009, 352 стр

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

1. Нелинейное программирование. Теория и алгоритмы. Пер с англ. – М.: Мир, 1992.

2. Дегтярёв оптимизации. – М: Сов. Радио,1980.

3. , Войтенко программирование в примерах и задачах: Учеб. пособие. – М.: Высш. шк., 1980

4. Курицкий оптимальных решений средствами Excel 7.0. – СПб: BHV - Питер, 1997.

5. Ашманов программирование. М.: Наука, 1981.

7.3 Программное обеспечение :

1.  Операционная система Microsoft Windows.

2.  Офисный пакет Электронные таблицы

3.  Пакеты символьной и численной математики

8. Материально-техническое обеспечение дисциплины (модуля)

Лабораторные занятия проводятся в классе, оснащенном ПЭВМ, с операционной системой Windows.

Рабочая программа дисциплины Методы оптимизации составлена в соответствии с требованиями ФГОС ВПО

Программу составили:

К. т.н., доцент каф. САПР ПГУ

Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.

Программа одобрена на заседании кафедры САПР

Протокол № ______________от «____» ______________ 2015 года

Зав. кафедрой САПР

Программа одобрена на заседании кафедры ВТ

Протокол № ______________от «____» ______________ 2015 года

Зав. кафедрой ВТ

Программа одобрена методической комиссией ФВТ

Протокол № ______от «____» ______________ 2015 года

Председатель методической комиссии ФВТ

Сведения о переутверждении программы на очередной учебный год и регистрации изменений

Учебный год	Решение кафедры (№ протокола, дата, подпись зав. кафедрой)	Внесенные изменения	Номера листов (страниц)
заменен- ных	новых	аннулиро-ванных