АННОТАЦИЯкурса “Дискретные модели и методы принятия решений ”Предлагаемая дисциплина “ Дискретные модели и методы принятия решений ”, с одной стороны, направлена на изучение математических постановок целого ряда типовых (массовых) моделей принятия целесообразных решений, имеющих дискретную структуру. С другой стороны, чтение курса ориентировано на установление пределов возможностей современных математических методов при построении алгоритмов решения дискретных оптимизационных задач. В связи с 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 Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования. Не предусмотрено.Отв. проф. д.ф.-м.н. Гимади Э.Х. Доц. Пяткин А.В. Преп. Рыков И.А.