Новосибирский государственный университет
Кафедра дискретного анализа и исследования операций

 Вопросы к экзамену по курсу

Теория принятия решений

3 курс, ФИТ, НГУ, Летняя сессия,  2009 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17. Классификация задач теории расписаний. Примеры.

18. Алгоритм Лаулера для задачи  1| prec| fmax

19. Алгоритм решения задачи  1| prec, pmtn, r_i | fmax

20. Алгоритм решения задачи  P | pmtn |Cmax

21. Алгоритм решения задачи  P | pmtn, r_i |Lmax

22. Алгоритм решения задачи  Q | pmtn |Cmax

23. Алгоритм решения задачи  F2 || Cmax

24. Задачи о покрытии, алгоритм Хватала, оценка его погрешности и экстремальный пример.

25. Задачи размещения. Генетический алгоритм для задачи размещения производства.

26. Задачи размещения в условиях конкуренции, их связь с принятием решений голосованием, «безнадежный» пример.

27. Матричные игры. Определение седловой точки. Примеры матричных игр с (не)нулевой суммой.
Пример игры, когда седловая точка не является оптимальным решением. Дилемма заключенных.

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

Вернуться к лекциям

Редакция 27.05.2009