Аннотация курса “Дискретные модели и методы принятия решений ”
| Вид материала | Документы |
- Методические указания к изучению курса «модели и методы принятия решений в анализе, 683.86kb.
- Аннотация программы дисциплины «Методы принятия управленческих решений» Цели и задачи, 22.87kb.
- К. А. Фисун модели и методы принятия решений в анализе и аудите конспект, 2366.25kb.
- Аннотация рабочей программы дисциплины методы принятия управленческих решений для направления, 31.71kb.
- Аннотация рабочей программы дисциплины методы принятия управленческих решений По направлению, 115.63kb.
- Анализ принятия управленческих решений, 54.28kb.
- Программа «Методы принятия решений». Гу-вшэ, 2010 г. Министерство экономического развития, 750.51kb.
- Примерная программа наименование дисциплины Линейная алгебра Рекомендуется для направления, 206.03kb.
- Рабочая программа дисциплины «математические модели принятия решений» Рекомендуется, 110.47kb.
- Математические методы принятия управленческих решений в туризме Мордовченков, 94.86kb.
АННОТАЦИЯ
курса “Дискретные модели и методы принятия решений ”
Предлагаемая дисциплина “ Дискретные модели и методы принятия решений ”, с одной стороны, направлена на изучение математических постановок целого ряда типовых (массовых) моделей принятия целесообразных решений, имеющих дискретную структуру. С другой стороны, чтение курса ориентировано на установление пределов возможностей современных математических методов при построении алгоритмов решения дискретных оптимизационных задач.
В связи с NP-трудностью многих задач дискретной оптимизации, большое внимание в курсе уделено применению эффективных (полиномиально ограниченных) приближенных алгоритмов с оценками их качества, и, в частности, асимптотически точному подходу к их решению.
Несомненно, что сочетание прикладной направленности изучаемого спецкурса с глубоким изучением теоретических аспектов, возникающих при построении реализуемых алгоритмов решения задач принятия решений, окажется неоценимым для предприятий, фирм, учреждений, в которых будут работать выпускники, проходящие данную специализацию, после окончания ими Новосибирского университета.
Организационно-методический раздел.
1.1Название курса.
«Дискретные модели и методы принятия решений»
Направление - математика
Раздел - общие математические и естественно-научные дисциплины
Семестры – 2 семестра, 72 часа
1.2Цели и задачи курса.
Дисциплина предназначена для студентов старших курсов и магистрантов
механико-математического факультета Новосибирского государственного
университета, проходящих специализацию в области дискретной оптимизации и исследования операций.
Для достижения поставленной цели выделяются задачи курса:
1) изучение теоретической части курса в соответствии с программой
2) сдача экзамена в соответствии с учебным планом.
1.3 Требования к уровню освоения содержания курса.
По окончании изучения указанной дисциплины студент должен
- иметь представление о месте и роли изучаемой дисциплины среди других наук;
- знать содержание программы курса, формулировки задач, условия применимости и характеристики методов решения дискретных задач принятия решений;
- уметь определять применимость конкретных методов для решения различных классов задач дискретной оптимизации и исследования операций.
1.4Формы контроля
Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен.
Текущий контроль. Фиксация посещаемости спецкурса.
2 Содержание дисциплины.
2.1Новизна.
Дисциплина “ Дискретные модели и методы принятия решений ” построена с учетом современных достижений и тенденций в области методов решения дискретных оптимизационных задач и в исследовании операций.
2.2Тематический план курса.
| Наименование разделов и тем | | ||||
| Лекции | | | | Кол-во часов | |
| Введение в дисциплину и основные понятия | 3 | | | | 6 |
| Модели динамического программирования | 5 | | | | 10 |
| Сетевые модели планирования и управления | 3 | | | | 6 |
| Календарное планирования с ограниченными ресурсами | 3 | | | | 6 |
| Задачи упаковки в контейнеры и в полосу | 3 | | | | 8 |
| Задачи о потоке | 2 | | | | 4 |
| Задачи маршрутизации на графах | 6 | | | | 12 |
| Многоиндексные задачи о назначениях. | 3 | | | | 6 |
| Выбор экстремальных подграфов и подмножеств векторов. | 4 | | | | 8 |
| Задачи размещения и стандартизации. | 4 | | | | 8 |
| Итого по курсу: | 36 | | | | 72 |
| | | | | | |
| | | | | | |
2.3 Содержание отдельных разделов и тем.
1. Ведение в дисциплину и основные понятия. Типовые модели принятия решений. Понятие о сложности задач дискретной оптимизации. Классы NP, P, NPC. Алгоритмы и оценки их качества. Приближенные алгоритмы для труднорешаемых задач.
2. Динамическое программирование (ДП). Вывод основных рекуррентных соотношений ДП. Принцип оптимальности Беллмана. Алгоритм ДП с одним прямым и одним обратным ходом. Релаксационный алгоритм. Сравнение с полным перебором. Задача о ранце. Связь прямой и обратной задач о ранце. Задача альтернативного выбора. Задачи о «ближайшем соседе». Задача Вентцель о распределении ресурсов между отраслями. Вычислительные трудности для многомерной задачи.
3. Сетевое планирование и управление. Представление проекта в виде сетевой модели (СМ). Параметры и алгоритмы анализа СМ. Алгоритм обнаружения контуров и вычисления рангов вершин СМ. Стохастическая СМ.
4. Задача календарного планирования с ограничениями на ресурсы и директивные сроки. Полиномиальный точный алгоритм в случае складируемости ограниченных ресурсов.
5. Задачи упаковки в контейнеры и в полосу. Асимптотически точный подход к ее решению.
6. Задачи о потоке максимальной мощности в сети и о потоке минимальной стоимости.
7. Задачи маршрутизации. Задача коммивояжера (ЗК). Метод ветвей и границ. Применение метода ветвей и границ к ЗК. Условия асимптотической точности алгоритма «Иди в ближайший непройденный город» для ЗК на случайных входах. Приближенные алгоритмы.
8. Многоиндексные задачи о назначениях (аксиальная и планарная).
9. Задачи выбора экстремальных подграфов и подмножеств векторов.
10. Задачи размещения и стандартизации. Полиномиально разрешимые случаи. Приближенные полиномиальные алгоритмы. Применение метода ветвей и границ. Асимптотически точный подход.
2.4 Перечень примерных контрольных вопросов и заданий для самостоятельной работы.
Смотри п.2.6
Учебно-методическое обеспечение дисциплины
Образцы вопросов для подготовки к экзамену.
1. Алгоритмы и оценки их качества. Определение асимптотически точного алгоритма. Примеры таких алгоритмов.
2. Основные рекуррентные соотношения динамического программирования (ДП)
для планирования деятельности предприятия на n хозяйственных лет. Трудоемкость алгоритма ДП с одним прямым и одним обратным ходом.
3. Трудоемкость релаксационного алгоритма ДП. Сравнение ДП с полным перебором. Трудности в случае многомерной задачи ДП.
4. Задача о ранце (ЗР). Алгоритмы в случае нелинейной и линейной ЗР.
5. Связь прямой и обратной ЗР. Рекуррентные соотношения и алгоритм решения задачи альтернативного выбора проблем.
6. Задача о "ближайшем соседе" (ЗБС). Алгоритмы в случае фиксированного числа интервалов обслуживания.
7. Алгоритмы решения ЗБС с оптимизируемым числом интервалов обслуживания.
8. Задача Вентцель динамического планирования многих отраслей и сведение ее к задаче двумерного ДП.
9. Сетевое планирование и управление. Представление проекта в виде сетевой модели (СМ). Ранг вершины, наиболее ранний и наиболее поздний моменты свершения события, критическое время и критический путь, полный резерв работы. Необходимый и достаточный признак критичности работы.
10. Алгоритмы вычисления рангов вершин и обнаружения контуров СМ.
11. Задача календарного планирования с ограничениями на ресурсы и директивные сроки. Построение асимптотически точного алгоритма в случае складируемости ограниченных ресурсов.
12. Метод ветвей и границ (МВГ). Утверждение о конечности и точности МВГ.
13. Задача коммивояжера (ЗК). Применение МВГ к ЗК.
14. Доказательство условий асимптотической точности алгоритма "Иди в ближайший непройденный город" для ЗК на случайных входных данных.
15. Задачи отыскания нескольких реберно непересекающихся маршрутов коммивояжера.
16. Задача отыскания регулярного подграфа в полном взвешенном графе.
17. Задача отыскания подмножества векторов с максимальной нормой суммы.
18. Постановки задач размещения и стандартизации.
19. Полиномиально разрешимые случаи для задачи размещения.
20. Приближенные методы решения задач размещения (стандартизации).
-
Учебно-методическое обеспечение дисциплины
3.1 Темы рефератов (курсовых работ).
Не предусмотрено.
3.2. Список основной и дополнительной литературы.
- Гимади Э.Х., Глебов Н.И. Математические модели и методы принятия решений. Новосибирск: НГУ, 2008. 144с.
- Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333с.
- Вентцель Е.С. Исследование операций. М: Сов. радио, 1972.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М: Мир, 416c.
Дополнительная литература
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985.
- Гимади Э.Х., Глебов Н.И. Экстремальные задачи принятия решений. Новосибирск: НГУ, 1982. 80с.
- Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. Новосибирск: НГУ, 1991. 76с.
- Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. пособие, Новосибирск: Изд-во НГУ, 2005.
3.3 Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.
Не предусмотрено.
Отв. проф. д.ф.-м.н. Гимади Э.Х.
Доц. Пяткин А.В.
Преп. Рыков И.А.