Новосибирский государственный университет
Кафедра дискретного анализа и исследования операций
Thin_Red_and_BlueA205.gif (1558 bytes)

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

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

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

Устные вопросы "до билета" на экзамене
 

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

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

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

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

5. Задача упаковки в контейнеры. Алгоритмы NF, FF, BF, FFD и их свойства,
отрицательный результат об аппроксимируемости.

6. Нижние оценки Martello и Toth.

7. Метод генерации столбцов для задачи упаковки в контейнеры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Устные вопросы "до билета" на экзамене

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


Редакция 18.05.2010