Теория игр и исследование операций

Лектор: доцент М.Г. Фуругян

Целью является развитие прикладного математического мышления. В частности, ставятся следующие задачи обучения студентов:

  1. методам принятия решений в ситуациях неопределенности на основе принципа наилучшего гарантированного результата, способам и примерам построения различных игровых моделей (антагонистические и бескоалиционные игры), а также математическому аппарату анализа таких моделей (методы поиска седловых точек, оптимальных смешанных стратегий, ситуаций равновесия);
  2. методам построения и анализа потоковых моделей, сведению большого числа задач исследования операций к потоковым задачам, основным алгоритмам решения задачи о максимальном потоке в сети и потоке минимальной стоимости;
  3. методам анализа и решения дискретных задач оптимизации, точным и приближенным алгоритмам решения большого числа оптимизационных задач, возникающих при разработке сложных технических систем (задачи теории расписаний, упаковки, различные задачи на сетях и др.), а также способам анализа сложности таких алгоритмов.

Содержание дисциплины:

  1. Основные понятия антагонистических игр.
  2. Смешанные стратегии в матричных антагонистических играх. Методы поиска оптимальных смешанных стратегий.
  3. Бесконечные антагонистические игры. Аппроксимация бесконечных игр конечными.
  4. Модели антагонистических игр и методы их решения.
  5. Бескоалиционные игры. Ситуация равновесия и условия ее существования.
  6. Потоки в сетях. Алгоритмы нахождения максимального потока в сети.
  7. Задача о потоке минимальной стоимости в сети.
  8. Приложения потоковых задач в исследовании операций.
  9. 9. Классификация дискретных оптимизационных задач. Полиномиально разрешимые и NP-трудные задачи.

    10. Методы решения NP-трудных задач.

Литература:

  1. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
  2. Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990.
  3. Морозов В.В. Основы теории игр. М.: МГУ, 2002.
  4. Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: Макс Пресс, 2005.
  5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  6. Кормен Т., Лейзерсон Ч., Ривест Р, Штайн К. Алгоритмы. Построение и анализ.
    М.: МЦНМО, 2005.

© 2011-2018 Лаборатория Вычислительных комплексов факультета ВМК МГУ