Рабочая программа дисциплины Дискретные задачи принятия решений Направление подготовки
| Вид материала | Рабочая программа |
- Рабочая программа учебной дисциплины теория принятия решений Направление подготовки, 591.05kb.
- Рабочая программа дисциплины «Алгоритм принятия уголовно-процессуальных решений» Направление, 292.56kb.
- Рабочая программа дисциплины «теория принятия решений» Направление подготовки, 158.9kb.
- Рабочая программа дисциплины «математические модели принятия решений» Рекомендуется, 110.47kb.
- Рабочая программа по курсу «теория принятия решения», 87.49kb.
- Аннотация программы дисциплины «Методы принятия управленческих решений» Цели и задачи, 22.87kb.
- Рейтинг-план освоения дисциплины «Теория принятия решений» Недели, 83.54kb.
- Рабочая программа дисциплины Системный анализ и принятие решений Направление подготовки, 138.22kb.
- Рабочая программа дисциплины основы теории принятия экономических решений цели и задачи, 92.73kb.
- Программа профилирующей дисциплины "теория игр и исследование операций" Содержание, 69.55kb.
Приложение 3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Национальный исследовательский университет
Новосибирский государственный университет
Механико-математический факультет
УТВЕРЖДАЮ
_______________________
«_____»__________________201__ г.
Рабочая программа дисциплины
Дискретные задачи принятия решений
Направление подготовки
Error: Reference source not found
Профиль подготовки
Error: Reference source not found
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
Новосибирск 2010
Аннотация рабочей программы
Дисциплина «Дискретные задачи принятия решений» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found». Дисциплина реализуется на Механико-математическом факультете Национального исследовательского университета Новосибирский государственный университет кафедрой Теоретической кибернетики ММФ НИУ НГУ.
Содержание дисциплины охватывает круг вопросов, связанных с теорией принятия решений, математическими моделями целочисленного линейного программирования, вычислительной сложностью алгоритмов, а также точными и приближенными подходами к решению NP-трудных задач.
Дисциплина нацелена на формирование общекультурных компетенций ОК-6, ОК-8, ОК-11, ОК-12, профессиональных компетенций ПК-12, ПК-20, ПК-21, ПК-25, ПК-29 выпускника.
Преподавание дисциплины предусматривает следующие формы организации учебного процесса: лекции, практические занятия, контрольная работа, самостоятельная работа студента.
Программой дисциплины предусмотрены следующие виды контроля: текущий контроль успеваемости в форме контрольной работы, проверка домашних заданий промежуточный контроль в форме коллоквиума. Формы рубежного контроля определяются решениями Ученого совета, действующими в течение текущего учебного года.
Общая трудоемкость дисциплины составляет ?? зачетных единиц, 184 академических часа. Программой дисциплины предусмотрены 68 часов лекционных и 34 часа практических занятий, а также 68 часов самостоятельной работы студентов. Остальное время – контроль в форме контрольной, коллоквиума и экзамена.
1. Цели освоения дисциплины
Цель дисциплины изучить математические модели и методы принятия оптимальных решений, ознакомиться с классическими моделями исследования операций и освоить численные методы их решения. Получить базовые навыки решения оптимизационных задач с применением специализированного программного обеспечения на примере системы GAMS.
В первой части, данный курс знакомит студентов с понятиями вычислительной сложности алгоритмов, различными классическими задачами дискретной оптимизации и современными подходами к их решению. Значительное внимание уделяется обучению моделированию и построению математических постановок оптимизационных задач. В практической части курса даются навыки формулировки и решения дискретных задач с использованием разработанного программного обеспечения.
Во второй части курса студенты знакомятся с теорией NP-полноты, основными представителями NP-полных задач. Изучаются приближенные алгоритмы, аппроксимационные схемы и метаэвристики.
2. Место дисциплины в структуре ООП бакалавриата
Дисциплина «Дискретные задачи принятия решений» является частью математического цикла ООП по направлению подготовки «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. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет ?? зачетные единицы, 184 часа.
| № п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||
| Лекция | Лабор. работа | Самост. работа | Контр. работа | экзамен | |||||
| 1.1 | Алгоритмы и их сложность | 7 | 1, 2 | 4 | 0 | 4 | | | |
| 1.2 | Алгоритмы сортировки и сбалансированные деревья | 7 | 3, 4 | 4 | 0 | 4 | | | |
| 1.3 | Динамическое программирование | 7 | 5, 6 | 4 | 0 | 4 | | | |
| 1.4 | Задачи о рюкзаке | 7 | 7, 8 | 4 | 6 | 4 | | | проверка семестрового задания |
| 1.5 | Задачи раскроя и упаковки | 7 | 9, 10, 11 | 6 | 6 | 6 | | | |
| 1.6 | Метаэвристики | 7 | 12, 13, 14 | 6 | 2 | 6 | | | контрольная работа |
| 1.7 | Дискретные задачи размещения | 7 | 15, 16, 17 | 6 | 2 | 6 | | | |
| 1.8 | Задачи календарного планирования | 8 | 1, 2 | 4 | 4 | 4 | | | |
| 1.9 | Задача коммивояжера | 8 | 3, 4 | 4 | 2 | 4 | | | |
| 1.10 | Задача о назначениях | 8 | 5, 6 | 4 | 2 | 4 | | | контрольная работа |
| 1.11 | Теория NP-полных задач | 8 | 7, 8 | 4 | 6 | 4 | | | |
| 1.12 | Задачи двухуровневого программирования | 8 | 9, 10 | 4 | 0 | 4 | | | |
| 1.13 | Задачи многокритериальной оптимизации | 8 | 11, 12 | 4 | 0 | 4 | | | |
| 1.14 | Приближенные алгоритмы | 8 | 13, 14, 15 | 6 | 4 | 6 | | | |
| 1.15 | Теория игр | 8 | 16, 17 | 4 | 0 | 4 | | | проверка семестрового задания |
| | | | | | | | | 14 | |
| | ИТОГО: 184 | | | 68 | 34 | 68 | | 14 | |
5. Образовательные технологии
В учебной работе по данной дисциплине проводятся лекционные занятия, практические занятия в компьютерном классе, семинарские занятия.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины
Для контроля усвоения дисциплины в течение семестра проводится контрольная работа, а также в течение семестра студенты сдают семестровые задания. Они заключаются в решении задач с применением специализированного программного обеспечения, отражающих основное содержание дисциплины. Для самостоятельной работы предусмотрены домашние и семестровые задания по темам: дискретные задачи размещения, метаэвристики, задача коммивояжера, задачи раскроя и упаковки, календарное планирование. В конце года учебным планом предусмотрен экзамен. Образцы экзаменационных вопросов.
Предмет и метод исследования операций. Процесс решения управленческой задачи методом исследования операций. Динамическое программирование. Распределительная задача. Задача о ближайшем соседе. Модели календарного планирования. Параметры сетевой модели. Алгоритм Форда для вычисления рангов событий, ранних и поздних моментов наступления событий. Критические события, работы и пути. Правильная нумерация событий и правильное упорядочивание работ. Задачи с директивными сроками и ресурсными ограничениями. Складируемые и нескладируемые ресурсы. Алгоритм вычисления Т-поздних расписаний. Задачи маршрутизации. Сложность построения приближенных решений с гарантированной оценкой точности для задачи коммивояжера. Алгоритм перестройки остовного дерева и оценка его погрешности. Алгоритм ветвей и границ. Задача о назначениях и алгоритм ее решения. Задачи раскроя и упаковки. Приближенные алгоритмы с оценками для задачи упаковки в контейнеры. Понятие аппроксимационной схемы, полиномиальные и вполне полиномиальные аппроксимационные схемы. Примеры аппроксимационных схем. Алгоритм имитации отжига. Задачи о покрытии и метод Лагранжевых релаксаций. Дискретные задачи размещения. Генетический алгоритм для дискретных задач размещения. Теория матричных игр. Чистые и смешанные стратегии. Теорема Фон-Неймана. NP-трудные задачи. Сбалансированные деревья.
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
- Т. Кормен. Алгоритмы построение и анализ. Второе издание. – М.: Издательский дом «Вильямс», 2009.
- Э. Гимади. Математические модели и методы исследования операций. – Учебное пособие. СибГУТИ.: Новосибирск, 2009.
- А. И. Ерзин. Введение в исследование операций. – Новосибирск. НГУ, 2006.
- А. И. Ерзин, Е. Н. Гончаров, В. Залюбовский. Исследование операций: примеры и задачи. – Новосибирск. Изд-во ММФ НГУ, 2005.
- В. Л. Береснев. Дискретные задачи размещения и полиномы от булевых переменных. – Новосибирск. Изд-во ИМ СО РАН. 2005.
б) дополнительная литература:
- Ausiello G. and others. Complexity and approximation. Combinatorial optimization problems and their approximability properties – Springer, 1999.
в) программное обеспечение и Интернет-ресурсы:
- General Algebraic Modeling System. – ссылка скрыта.
- примеры задачи коммивояжера
ссылка скрыта.
8. Материально-техническое обеспечение дисциплины
- Ноутбук, медиа-проектор, экран.
- Программное обеспечение для демонстрации слайд-презентаций.
- Программное обеспечение для решения оптимизационных задач GAMS.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению «Error: Reference source not found» и профилю подготовки «Error: Reference source not found».
Авторы:
д.ф.-м.н., профессор НГУ, с.н.с. ИМ СО РАН
Кочетов Юрий Андреевич,
к.ф.-м.н., доцент НГУ, н.с. ИМ СО РАН
Алексеева Екатерина Вячеславовна
Рецензент (ы)
Программа одобрена на заседании
(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)
от ___________ года, протокол № ________