Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«Новосибирский государственный университет» (НГУ)

Факультет информационных технологий

Кафедра Дискретный анализ и исследование операций

ПРОГРАММА

ДИСЦИПЛИНЫ Теория принятия решений

ЦИКЛ* ЕН.Ф.01.8 Общие математические и естественнонаучные дисциплин НАПРАВЛЕНИЕ ПОДГОТОВКИ БАКАЛАВРОВ 230100.62 «ИНФОРМАТИКА И

ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»

Автор Кочетов Юрий Андреевич, к.ф.-м.н., доцент Новосибирск 2009 * Наименование цикла дисциплин в соответствии с ГОС ВПО Программа дисциплины « Теория принятия решений » составлена в соответствии с требованиями к обязательному минимуму содержания и уровню подготовки бакалавра по циклу «Общие математические и естественнонаучные дисциплин» Федеральных государственных образовательных стандартов высшего профессионального образования по направлению 230100.62 «Информатика и вычислительная техника».

1. Цели и задачи дисциплины (курса) Дисциплина (курс) «Теория принятия решений» имеет своей целью:

ознакомить студентов с классическими комбинаторными задачами дискретной оптимизации, приближенными и точными алгоритмами решения этих задач и основными результатами в этой области;

Для достижения поставленной цели выделяются задачи курса:

научить формулировать задачу в виде математической модели;

научить применять и адаптировать известные подходящие алгоритмы решения;

научить анализировать получаемые решения;

научить пользоваться разработанным программным обеспечением;

освоить алгоритм динамического программирования, имитации отжига, метод ветвей и границ, генетический алгоритм;

разобрать и знать основные формулировки и доказательства теорем курса;

освоить программное обеспечение для решения задач математического программирования.

2. Требования к уровню освоения содержания дисциплины В результате освоения дисциплины студент должен:

Иметь представление о классических дискретных оптимизационных задачах, моделях и алгоритмах их решения.

Знать основные результаты и доказательства теорем.

Уметь строить математические модели и выбирать подходящий для решения алгоритм, основываясь на свойствах задачи, применять коммерческое программное обеспечение для решения сформулированных задач.

3. Объем дисциплины и виды учебной работы Вид учебной работы Всего часов Семестры 1 Общая трудоемкость дисциплины 144 Аудиторные занятия, в том числе: 96 Лекции 32 Семинары 32 Лабораторные работы 32 Самостоятельная работа, в том числе: 48 Курсовой проект Реферат Расчетные работы 24 Другие виды самостоятельной работы 24 Текущий контроль 3 задания 3 задания 2 контрольных 2 контрольных Вид промежуточного контроля экзамен экзамен Общая трудоемкость дисциплины составляет _ зачетных единиц (если применяется на факультете/кафедре).

4. Содержание дисциплины 4.1. Новизна курса (научная, содержательная; сравнительный анализ с подобными курсами в России и за рубежом).

Курс дает основы постановки дискретных экстремальных задач и алгоритмов решения, которые являются необходимыми для студентов ФИТ.

4.2. Тематический план курса (распределение часов по видам учебной работы).

№ Наименование ВСЕГО Аудиторные занятия Самостоятел п/п тем и разделов (часов) (часов), в том числе ьная работа (часов) Лекции Семинары Лаб.

работы 1 Динамическое 15 4 6 0 программирование 2 Аппроксимационные 3 2 0 0 задачи о назначениях 4.3. Содержание разделов и тем курса.

1. Метод динамического программирования на примере распределительной задачи.

2. Модель размещения капитала.

3. Алгоритмы для задачи о рюкзаке с гарантированной точностью 0.5 и 0.75.

4. Аппроксимационные схемы. Полиномиальные и полностью полиномиальные аппроксимационные схемы.

5. Задача замены оборудования с учетом дисконтирования затрат.

6. Задача упаковки в контейнеры. Нижние оценки целевой функции.

7. Задача двумерной прямоугольной упаковки. Алгоритм имитации отжига.

8. Задача календарного планирования. Критические работы, пути и критическое время проекта. Вероятность завершения проекта к заданному сроку.

9. Постановка задачи календарного планирования с ограниченными ресурсами. Тпоздние расписания. Алгоритм вычисления Т-поздних расписаний. Доказательство оптимальности Т*-позднего расписания. Алгоритм Гимади.

10. Задачи календарного планирования с переменными длительностями работ.

Сведение к линейному программированию.

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

12. Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. Доказательство оценки и ее неулучшаемости. Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья.

Алгоритм решения задачи о назначениях.

13. Метод ветвей и границ для задачи коммивояжера.

14. Классификация задач теории расписаний. Алгоритм Лаулера для задачи 1 | prec | fmax Алгоритм решения задачи 1 | prec, pmtn, ri | fmax 15. Генетический алгоритм для задачи размещения производства. Задачи размещения в условиях конкуренции, их связь с принятием решений голосованием, «безнадежный» пример.

16. Матричные игры. Определение седловой точки. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема ФонНеймана.

4.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы.

Темы заданий для самостоятельной работы 1. Алгоритмом динамического программирования для задачи о рюкзаке, задачи о ближайшем соседе.

2. Метод ветвей и границ для задачи коммивояжера.

3. Задача сетевого планирования.

4. Алгоритм решения задачи о назначении.

4.5. Примерная тематика рефератов, курсовых работ.

Рефераты и курсовые работы не предполагаются 5. Учебно-методическое и информационное обеспечение дисциплины (курса) 5.1. Примерный перечень вопросов к зачету (экзамену) по всему курсу.

1. Метод динамического программирования на примере распределительной задачи.

2. Модель размещения капитала. Свойство дробных решений. Процедура округления.

3. Алгоритмы для задачи о рюкзаке с гарантированной точностью 0.5 и 0.75.

4. Аппроксимационные схемы. Полиномиальные и полностью полиномиальные аппроксимационные схемы. Примеры таких схем для задачи о рюкзаке.

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

6. Задача упаковки в контейнеры. Нижние оценки целевой функции.

7. Задача двумерной прямоугольной упаковки. Алгоритм имитации отжига.

8. Задача календарного планирования. Критические работы, пути и критическое время проекта. Вероятность завершения проекта к заданному сроку.

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

10. Т-поздние расписания. Алгоритм вычисления Т-поздних расписаний.

11. Доказательство оптимальности Т*-позднего расписания. Алгоритм Гимади.

12. Задачи календарного планирования с переменными длительностями работ.

Сведение к линейному программированию.

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

14. Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2. Доказательство оценки и ее неулучшаемости.

15. Нижние оценки в задаче коммивояжера: примитивная оценка, оценка линейного программирования, оценка задачи о назначениях и минимальные 1-деревья.

16. Алгоритм решения задачи о назначениях.

17. Метод ветвей и границ для задачи коммивояжера.

18. Классификация задач теории расписаний 19. Алгоритм Лаулера для задачи 1 | prec | fmax 20. Алгоритм решения задачи 1 | prec, pmtn, ri | fmax 21. Генетический алгоритм для задачи размещения производства 22. Задачи размещения в условиях конкуренции, их связь с принятием решений голосованием, «безнадежный» пример.

23. Матричные игры. Определение седловой точки.

24. Необходимые и достаточные условия равенства верхней и нижней цен игры в чистых стратегиях. Теорема Фон-Неймана.

Основная литература*.

5.2.

1. Э.Х. Гимади. Н. И. Глебов. Дискретные экстремальные задачи. Учебное пособие.

Новосибирск, 1991.

2. Э.Х. Гимади. Н. И. Глебов. Экстремальные задачи принятия решений. Учебное пособие. НГУ, 1982.

3. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи.

4. Т. Кормен, Ч. Лейзерсон и др. Алгоритмы: построение и анализ. Москва. 2005.

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

1. S. Martello, P. Toth. Knapsack Problem. Algorithms and Computer Implementations.

University of Bologna. John Wiley & Sons. 1990.

5.4. Программное и коммуникационное обеспечение (если используется).

Коммерческий пакет GAMS 6. Методические рекомендации по организации изучения дисциплины Текущая успеваемость студента оценивается по результатам контрольных работ, домашних и лабораторных заданий. К сдаче экзамена допускаются студенты, выполнившие учебный план: три задачи лабораторного практикума, две контрольные работы, все домашние задания.

6.1 Структура лабораторного практикума В ходе освоения курса студенты решают практические задачи лабораторного практикума.

Преподаватель выдает персональные задания каждому студенту и проверяет выполнение каждого задания. При выполнении задания студент должен:

– построить математическую модель в терминах частично-целочисленного линейного или нелинейного программирования, – разработать алгоритм решения соответствующей оптимизационной задачи или воспользоваться коммерческим программным обеспечением, например, системой GAMS, – провести расчеты и получить оптимальное решение задачи, – выполнить пост-оптимизационный анализ, т.е. ответить на вопросы типа: а что если в модели изменится целевая функция или какая-то группа ограничений?

Задание считается принятым, если студент выполнит все четыре этапа исследований.

Примерный перечень задач лабораторного практикума:

Задачи календарного планирования, задачи раскроя и упаковки, задачи теории расписаний, задачи маршрутизации, дискретные задачи размещения производства.

Не более 10 источников.

6.2 Порядок работы с учебно-методическим комплексом При изучении теоретического материала рекомендуется строго придерживаться календарного плана. В ходе лекций студенту рекомендуется самостоятельно воспроизводить ее содержание в виде конспекта. После каждой лекции рекомендуется самостоятельно изучить дополнительную литературу по теме лекции.

Лабораторные занятия проводятся в учебном компьютерном классе один раз в неделю. Всего 16 занятий. Перед каждым занятием студенту рекомендуется освежить в памяти содержание соответствующей лекции, вспомнить перечень рассматриваемых на ней математических моделей и их свойства.

Семинарские занятия проводятся в аудиториях без компьютеров, один раз в неделю, всего 16 семинарских занятий. На занятиях студенты получают навыки построения математических моделей, применения методов динамического программирования, метода ветвей и границ, осваивают методы расчетов параметров сетевых моделей. После каждого занятия студентам выдается домашнее задание.

Рекомендуется перед выполнением домашнего задания тщательно изучить соответствующий лекционный материал.

Самостоятельная работа студента связана в первую очередь с решением задач лабораторного практикума. Все задачи предполагают самостоятельное построение математических моделей. В этом творческом процессе рекомендуется тщательно проработать лекционный материал и всю дополнительную литературу по курсу.