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

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

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

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

  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. Алгоритм решения задачи  P | pmtn |Cmax

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

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

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

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

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

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

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

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

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


Редакция 30.04.2008