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

Thin_Red_and_BlueA205.gif (1558 bytes)

Ю.А. Кочетов

Теория принятия решений
Вопросы к экзамену

НГУ, Факультет информационных технологий
3 курс летняя сессия 2012 год
             

 

 

            

                      

                    

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

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

  3. Классическая задача о рюкзаке, теорема об алгоритмах с гарантированной
    абсолютной точностью.

  4. Жадные алгоритмы для классической задачи о рюкзаке, свойства
    LP-релаксации

  5. Приближенные алгоритмы с гарантированной относительной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и алгоритм с точностью ¾.

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

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

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

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

  10. Задача двумерной упаковки, кодировки решений. Алгоритм имитации отжига.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Вопросы к экзамену ФИТ 2012.pdf

 

Лектор: д.ф.-м.н., профессор Кочетов Юрий Андреевич
e-mail:  jkochet@math.nsc.ru  

Редакция 06.06.2012