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

Thin_Red_and_BlueA205.gif (1558 bytes)

А.Ю. Кочетов

Исследование операций
            

 

 

Курс лекций                      

                    

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

4 курс, ММФ НГУ, зимняя сессия,  январь, 2016 г.

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

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

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

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

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

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

7. Замена оборудования. Алгоритм динамического программирования для конечного планового периода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33. Бескоалиционные игры, равновесие по Нэшу, пример игры без равновесий.

 

Список вопросов в pdf


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

Редакция 12.01.2016