Реферат: Аннотация курса “Дискретные модели и методы принятия решений ”

АННОТАЦИЯ

курса “Дискретные модели и методы принятия решений ”


Предлагаемая дисциплина “ Дискретные модели и методы принятия решений ”, с одной стороны, направлена на изучение математических постановок целого ряда типовых (массовых) моделей принятия целесообразных решений, имеющих дискретную структуру. С другой стороны, чтение курса ориентировано на установление пределов возможностей современных математических методов при построении алгоритмов решения дискретных оптимизационных задач.

В связи с 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 Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.
Не предусмотрено.

Отв. проф. д.ф.-м.н. Гимади Э.Х.

Доц. Пяткин А.В.

Преп. Рыков И.А.