Теория игр и исследование операций
Source: https://asvk.cs.msu.ru/uchebnyj-process/chitaemye-kursy/teoriya-igr-i-issledovanie-operacij/ Parent: https://asvk.cs.msu.ru/
Теория игр и исследование операций
Лектор: доцент М.Г. Фуругян
Целью является развитие прикладного математического мышления. В частности, ставятся следующие задачи обучения студентов:
- методам принятия решений в ситуациях неопределенности на основе принципа наилучшего гарантированного результата, способам и примерам построения различных игровых моделей (антагонистические и бескоалиционные игры), а также математическому аппарату анализа таких моделей (методы поиска седловых точек, оптимальных смешанных стратегий, ситуаций равновесия);
- методам построения и анализа потоковых моделей, сведению большого числа задач исследования операций к потоковым задачам, основным алгоритмам решения задачи о максимальном потоке в сети и потоке минимальной стоимости;
- методам анализа и решения дискретных задач оптимизации, точным и приближенным алгоритмам решения большого числа оптимизационных задач, возникающих при разработке сложных технических систем (задачи теории расписаний, упаковки, различные задачи на сетях и др.), а также способам анализа сложности таких алгоритмов.
Содержание дисциплины:
-
- Основные понятия антагонистических игр.
- Смешанные стратегии в матричных антагонистических играх. Методы поиска оптимальных смешанных стратегий.
- Бесконечные антагонистические игры. Аппроксимация бесконечных игр конечными.
- Модели антагонистических игр и методы их решения.
- Бескоалиционные игры. Ситуация равновесия и условия ее существования.
- Потоки в сетях. Алгоритмы нахождения максимального потока в сети.
- Задача о потоке минимальной стоимости в сети.
- Приложения потоковых задач в исследовании операций.
- Классификация дискретных оптимизационных задач. Полиномиально разрешимые и NP-трудные задачи.
- Методы решения NP-трудных задач.
Литература:
-
- Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
-
- Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990.
-
- Морозов В.В. Основы теории игр. М.: МГУ, 2002.
-
- Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: Макс Пресс, 2005.
-
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
-
- Кормен Т., Лейзерсон Ч., Ривест Р, Штайн К. Алгоритмы. Построение и анализ.\ М.: МЦНМО, 2005.