Приложение 3 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Национальный исследовательский университет
Новосибирский государственный университет
Механико-математический факультет
УТВЕРЖДАЮ
_______________________ «_____»__________________201__ г.
Рабочая программа дисциплины
Принятие решений
Направление подготовки
Error: Reference source not found
Профиль подготовки
Error: Reference source not found
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
Новосибирск 2010 Аннотация рабочей программы Дисциплина «Принятие решений» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found». Дисциплина реализуется на Механико-математическом факультете Национального исследовательского университета Новосибирский государственный университет кафедрой Теоретической. кибернетики ММФ НИУ НГУ.
Содержание дисциплины охватывает круг вопросов, связанных с изучением математических моделей и методов принятия оптимальных решений, составляющих основу направления, известного под названием «Исследования операций».
Дисциплина нацелена на формирование общекультурных компетенций ОК-6, ОК-8, ОК-11, ОК-12, профессиональных компетенций ПК-12, ПК-20, ПК-21, ПК-25, ПК-29 выпускника.
Преподавание дисциплины предусматривает следующие формы организации учебного процесса: лекции и самостоятельная работа студента.
Общая трудоемкость дисциплины составляет 68 лекционных часов. 1. Цели освоения дисциплины
(Указываются цели освоения дисциплины (или модуля), соотнесенные с общими целями ООП ВПО).
Курс ставит своей целью усвоение студентами понятий, связанных с разработкой математических моделей и методов принятия оптимальных решений.
В спецкурсе, с одной стороны, изучаются математические постановки целого ряда типовых (массовых) моделей принятия целесообразных решений. С другой стороны, в спецкурсе устанавливаются пределы возможностей современных математических методов при построении алгоритмов решения задач принятии решений. В связи с NP-трудностью многих задач принятия решений, большое внимание в спецкурсе уделено применению эффективных (полиномиально ограниченных) приближенных алгоритмов с оценками их качества, и, в частности, асимптотически точному подходу к их решению.
Несомненно, что сочетание прикладной направленности изучаемого спецкурса с глубоким изучением теоретических аспектов, возникающих при построении реализуемых алгоритмов решения задач принятия решений, окажется неоценимым для предприятий, фирм, учреждений, в которых будут работать выпускники кафедры теоретической кибернетики после окончания ими Новосибирского Университета. 2. Место дисциплины в структуре ООП бакалавриата
(Дается описание логической и содержательно-методической взаимосвязи с другими частями ООП (дисциплинами, модулями, практиками). Указываются требования к «входным» знаниям, умениям и готовностям обучающегося, необходимым при освоении данной дисциплины и приобретенным в результате освоения предшествующих дисциплин (модулей).)
Дисциплина «Принятие решений» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found».
Дисциплина «Принятие решений» опирается на следующие дисциплины данной ООП:
Математический анализ;
Теория вероятностей и математическая статистика;
Теория алгоритмов;
Основы работы на ЭВМ;
Методы оптимизации (математическое программирование).
Результаты освоения дисциплины «Error: Reference source not found» используются в следующих дисциплинах данной ООП:
Математическое программирование;
Базы данных и экспертные системы;
Вычислительная практика;
Системное и прикладное ПО;
Информационные системы.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Error: Reference source not found»:
общекультурные компетенции: ОК-6, ОК-8, ОК-11, ОК-12;
профессиональные компетенции: ПК-12, ПК-20, ПК-21, ПК-25, ПК-29.
В результате освоения дисциплины обучающийся должен:
иметь представление о месте и роли изучаемой дисциплины среди других наук;
освоить содержание программы курса, формулировки задач, уметь анализировать входные данные задачи;
иметь представление об условиях применимости и о характеристиках методов решения задач принятия решений;
уметь определять применимость конкретных методов для решения различных классов задач принятия решений.
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 2,5 зачетные единицы, 72 часа.
№ п/п
| Раздел дисциплины
| Семестр
| Неделя семестра
| Виды учебной работы, включая самостоятельную работу студентов и трудоемкость
(в часах)
| Формы текущего контроля успеваемости (по неделям семестра)
Форма промежуточной аттестации (по семестрам)
| Лекция
| Лабор. работа
| Самост. работа
| Контр. работа
| Зачет
| 1
| Введение в дисциплину и основные понятия. Стадии операционного исследования. Математическое моделирование. Роль исследователя операций. Типовые модели ИО. Алгоритмы и оценки их качества. Понятие о сложности задач дискретной оптимизации.
| 1
| 1
| 4
|
|
|
|
|
| 2
| Многошаговые модели динамического программирования. Вывод основных рекуррентных соотношений ДП. Принцип оптимальности Беллмана. Алгоритм ДП с одним прямым и одним обратным ходом. Релаксационный алгоритм. Сравнение с полным перебором. Задача о ранце. Связь прямой и обратной задач о ранце. Задача альтернативного выбора. Задачи о «ближайшем соседе». Задача Вентцель о распределении ресурсов между отраслями. Вычислительные трудности для многомерной задачи.
| 1
| 3
| 12
|
|
|
|
|
| 3
| Линейные производственные модели. Задача об оптимальном рационе. Стандартная задача линейного программирования (ЗЛП). Двойственность в ЛП: прямая и двойственная задачи ЛП, теоремы двойственности, экономическая интерпретация. Задачи транспортного типа. Задача об оптимальном назначении. Многоиндексная задача о назначениях (аксиальная и планарная). Блочные задачи. Двухэтапная задача линейного стохастического программирования.
| 1
| 9
| 4
|
|
|
|
|
| 4
| Элементы теории матричных игр. Основные понятия теории игр. Матричная игра. Принцип минимакса. Седловая точка. Смешанные стратегии. Основная теорема матричных игр. Методы решения матричных игр. Доминирование. Игра 2х2, игры 2хn и mх2. Игры mхn. Итеративный метод Брауна-Робинсон и сведение к задаче ЛП.
| 1
| 11
| 6
|
|
|
|
|
| 5
| Сетевые модели планирования и управления. Графы. Представление комплекса операций (проекта) в виде сетевой модели (СМ). Параметры и алгоритмы анализа СМ. Алгоритмы сортировки чисел. Алгоритм обнаружения контуров и вычисления рангов вершин СМ. Задача календарного планирования с ограничениями на ресурсы и директивные сроки. Полиномиальный точный алгоритм в случае складируемости ограниченных ресурсов. Задача упаковки в контейнеры и в полосу. Асимптотически точный подход к ее решению. Стохастическая СМ.
| 1
| 14
| 8
|
|
|
|
|
| 6
| Задачи замены оборудования. Аналитические модели при неслучайном спросе. Приведение затрат к текущему моменту. Теорема об оптимальном периоде замены. Применение ДП к задаче замены оборудования.
| 1
| 18
| 2
|
|
|
|
|
| 7
| Задачи управления запасами. Задача об оптимальном объеме партии и периоде поставок в случае детерминированного стационарного спроса. Нестационарный спрос. Вероятностный спрос. Управление многономенклатурными запасами.
| 2
| 19
| 2
|
|
|
|
|
| 8
| Задачи маршрутизации на графах. Задача о кратчайших путях. Задача о кратчайшей связывающей сети. Задача коммивояжера. Применение метода ветвей и границ. Условия асимптотической точности алгоритма «Иди в ближайший непройденный город». Приближенный алгоритм с использованием решения задачи о назначении.
| 2
| 20
| 10
|
|
|
|
|
| 9
| Задачи теории расписаний. Задачи с одним рабочим местом. Задача Джонсона 2хn и 3хn. Применение метода компактного суммирования векторов к задаче Джонсона. Задача Акерса-Фридмена.
| 2
| 25
| 6
|
|
|
|
|
| 10
| Задачи размещения и стандартизации. Полиномиально разрешимые случаи для задачи размещения. Приближенные полиномиальные алгоритмы для задач коммивояжера и размещения.
| 2
| 28
| 4
|
|
|
|
|
| 11
| Модели динамики средних. Уравнения Колмогорова. Метод динамики средних.
| 2
| 30
| 2
|
|
|
|
|
| 12
| Управление ресурсными и финансовыми потоками. Задачи о потоке максимальной мощности в сети и о потоке минимальной стоимости. Задача о погашении взаимных долгов между предприятиями. Задача о проведении целесообразных финансовых и товарообменных операциях с учетом фактора кредитования. Задача о проведении расчетов между банками.
| 2
| 32
| 4
|
|
|
|
|
|
|
|
|
| 72
|
|
|
|
| Экзамен
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| (Наиболее распространенные виды/формы организации учебного процесса: лекция/мастер-класс, лабораторная работа, практическая занятие, семинар/коллоквиум, самостоятельная работа студента, консультации/тьюторство, курсовое проектирование, производственная практика, научно-исследовательская работа, выпускная квалификационная работа). 5. Образовательные технологии
(Указываются образовательные технологии, используемые при реализации различных видов учебной работы. Наиболее распространенные виды/формы образовательных технологий: традиционные лекционно-семинарские системы обучения, информационные технологии (обучение в электронной образовательной среде), работа в команде, case-study (анализ реальных проблемных ситуаций и поиск решений), ролевая игра, проблемное изучение, контекстное изучение, обучение на основе опыта, индивидуальное обучение, междисциплинарное обучение, опережающая самостоятельная работа.
В соответствии с требованиями ФГОС ВПО по направлению подготовки реализация компетентностного подхода должна предусматривать широкое использование в учебном процессе активных и интерактивных форм проведения занятий (компьютерных симуляций, деловых и ролевых игр, разбор конкретных ситуаций, психологические и иные тренинги) в сочетании с внеаудиторной работой с целью формирования и развития профессиональных навыков обучающихся. В рамках учебных курсов должны быть предусмотрены встречи с представителями российских и зарубежных компаний, государственных и общественных организаций, мастер-классы экспертов и специалистов.
Удельный вес занятий, проводимых в интерактивных формах, определяется главной целью (миссией) программы, особенностью контингента обучающихся и содержанием конкретных дисциплин, и в целом в учебном процессе они должны составлять не менее 30% аудиторных занятий (определяется требованиями ФГОС с учетом специфики ООП). Занятия лекционного типа для соответствующих групп студентов не могут составлять более 50% аудиторных занятий (определяется соответствующим ФГОС)).
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины
(Приводятся виды самостоятельной работы обучающегося, порядок их выполнения и контроля, дается учебно-методическое обеспечение (возможно в виде ссылок) самостоятельной работы по отдельным разделам дисциплины.
Указываются темы эссе, рефератов, курсовых работ и др. Приводятся контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины.) 7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
Гимади Э.Х., Глебов Н.И. Математические модели и методы принятия решений. Уч. пос. НГУ. Новосибирск 2008, 163 с.
Гэри М., Джонсон Д. Вычислительные машины и трудно-решаемые задачи: Пер. с англ. – М: Мир, 1982, 416c.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. – М.: Мир, 1985. 512 с.
б) дополнительная литература:
Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации // Уч. пособие. Новосибирск: НГУ, 2000. 105 с.
Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи. Уч. пособие. Новосибирск: НГУ, 2005. 78 с.
Ерзин А.И. Введение в исследование операций. Уч. пособие. Новосибирск: НГУ, 2006. 100 с.
Севастьянов С.В. Введение в теорию расписаний. Электронное пособие. НГУ. Версия 2003 г.
Alexander Schrijver. A Course in Combinatorial Optimization // Department of Mathematics. University of Amsterdam. Netherland, 2008. 223 p.
Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency // Springer. 2002. 1433 p.
R.E. Burkard, M. Dell’Amico and S. Martello. Assignment Problems // SIAM, Philadelphia, 2009, 382 p.
The Traveling Salesman Problem and its variations (ed. by A. Punnen and G. Gutin). Kluwer Academic Publishers.Dortrecht/Boston/London. 2002. 808 p..
в) программное обеспечение и Интернет-ресурсы: 8. Материально-техническое обеспечение дисциплины
Ноутбук, медиа-проектор, экран.
Программное обеспечение для демонстрации слайд-презентаций.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению «Error: Reference source not found» и профилю подготовки «Error: Reference source not found».
Автор: Гимади Эдуард Хайрутдинович
д.ф.-м.н., профессор ММФ НГУ,
зав. лаб. ИМ СО РАН
Рецензент (ы)
Программа одобрена на заседании
(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)
от ___________ года, протокол № ________
|