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

АННОТАЦИЯ

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

В связи с 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

6. Учебно-методическое обеспечение дисциплины

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

1. Алгоритмы и оценки их качества. Определение асимптотически точного алгоритма. Примеры таких алгоритмов.

2. Основные рекуррентные соотношения динамического программирования (ДП)

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

3. Трудоемкость релаксационного алгоритма ДП. Сравнение ДП с полным перебором. Трудности в случае многомерной задачи ДП.

4. Задача о ранце (ЗР). Алгоритмы в случае нелинейной и линейной ЗР.

5. Связь прямой и обратной ЗР. Рекуррентные соотношения и алгоритм решения задачи альтернативного выбора проблем.

6. Задача о "ближайшем соседе" (ЗБС). Алгоритмы в случае фиксированного числа интервалов обслуживания.

7. Алгоритмы решения ЗБС с оптимизируемым числом интервалов обслуживания.

8. Задача Вентцель динамического планирования многих отраслей и сведение ее к задаче двумерного ДП.

9. Сетевое планирование и управление. Представление проекта в виде сетевой модели (СМ). Ранг вершины, наиболее ранний и наиболее поздний моменты свершения события, критическое время и критический путь, полный резерв работы. Необходимый и достаточный признак критичности работы.

10. Алгоритмы вычисления рангов вершин и обнаружения контуров СМ.

11. Задача календарного планирования с ограничениями на ресурсы и директивные сроки. Построение асимптотически точного алгоритма в случае складируемости ограниченных ресурсов.

12. Метод ветвей и границ (МВГ). Утверждение о конечности и точности МВГ.

13. Задача коммивояжера (ЗК). Применение МВГ к ЗК.

14. Доказательство условий асимптотической точности алгоритма "Иди в ближайший непройденный город" для ЗК на случайных входных данных.

15. Задачи отыскания нескольких реберно непересекающихся маршрутов коммивояжера.

16. Задача отыскания регулярного подграфа в полном взвешенном графе.

17. Задача отыскания подмножества векторов с максимальной нормой суммы.

18. Постановки задач размещения и стандартизации.

19. Полиномиально разрешимые случаи для задачи размещения.

20. Приближенные методы решения задач размещения (стандартизации).

2. Учебно-методическое обеспечение дисциплины

3.1 Темы рефератов (курсовых работ).

Не предусмотрено.

3.2. Список основной и дополнительной литературы.

1. 
   Гимади Э.Х., Глебов Н.И. Математические модели и методы принятия решений. Новосибирск: НГУ, 2008. 144с.
   
2. 
   Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333с.
   
3. 
   Вентцель Е.С. Исследование операций. М: Сов. радио, 1972.
   
4. 
   Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М: Мир, 416c.
   

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

1. 
   Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985.
   
2. 
   Гимади Э.Х., Глебов Н.И. Экстремальные задачи принятия решений. Новосибирск: НГУ, 1982. 80с.
   
3. 
   Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. Новосибирск: НГУ, 1991. 76с.
   
4. 
   Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: Учеб. пособие, Новосибирск: Изд-во НГУ, 2005.
   

3.3 Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.

Не предусмотрено.

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

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

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