Курс «Теория игр и исследование операций» читается студентам четвертого курса факультета вычислительной математики и кибернетики в 8 семестре.

Целями освоения дисциплины «Теория игр и исследование операций» является знакомство с основными понятиями теории оптимизации и теории игр, развитие навыков построения оптимизационных и теоретикоигровых моделей, овладение основными алгоритмами оптимизации.

В результате освоения дисциплины студент должен:

•             знать основные понятия теории оптимизации и теории игр;

•             уметь строить и анализировать математические модели практических оптимизационных и теоретикоигровых задач;

•             иметь навыки применения основных алгоритмов оптимизации.

Список всех тем лекций

Лекция 1. Седловые точки и антагонистические игры.
Задачи на принятие решений Неантагонистические игры Теория принятия решений в условиях особой неопределенности Седловые точки и решение антагонистических игр Седловые точки Антагонистическая игра Лемма I (о значении в разных седловых точках) Матричные игры Условия существования антагонистической игры Максиминная стратегия Минимаксная стратегия Лемма II (о связи нижнего и верхнего значения игры) Седловая точка на произведении множеств

Лекция 2. Максиминные и минимаксные стратегии.
Условия существования максиминных и минимаксных стратегий при отсутствии седловых точек Теорема о существовании максиминной стратегии и ее доказательство Определение непрерывных игр Следствия теоремы Пример разрыва функции минимума Выпуклое множество Выпуклая (вогнутая) и строго выпуклая (вогнутая) функция Теорема о достаточных условиях существования седловой точки и ее доказательство Доказательство теоремы о седловой точки вогнуто-выпуклой функции Прием: возмущенная функция о существовании седловой точке функции через максиминную стратегию седловая точка как решение минимаксной стратегии

Лекция 3. Непрерывные игры.
Пример матрицы игры, не имеющей решения Смешанная стратегия Смешанная игра на отрезке Смешанная игра на выпуклом компакте Математическое ожидание Смешанное расширение антагонистических игр Основная теорема матричных игр Смешанные стратегии и случаи их применения Теория ожидаемой полезности Физические смеси Непрерывная игра на прямоугольнике Слабая сходимость Терема Хелли Лемма о существовании максиминной и минимаксной стратегии в смешанной игре на прямоугольнике Лемма о нижних и верхних значениях в двух антагонистических играх Основная теорема непрерывных игр Аппроксимация непрерывной функции

Лекция 4. Свойства смешанных стратегий.
Доказательство) для матричных игр) (о верхней и нижней грани смешанных стратегий в непрерывной игре) для значений игры на прямоугольнике для матричной игры Следствие 1.8* максиминных чистых стратегий Спектр смешанной стратегии (Свойство дополняющей нежелательности) Следствие из Теоремы 1.9 (свойство дополняющей нежелательности для матричных игр)

Лекция 5. Методы решения матричных игр.
Доминирование строк и столбцов (о доминировании строк) (о доминировании столбцов) Аналитический метод решения матричной игры Графический метод решения матричной игры строки- n столбцов столбца - m строк Ввод вспомогательной переменной (от минимума к максимума)

Лекция 6. Игры с выпуклой (вогнутой) функцией выигрыша.
Максимализация линейной функции Свойство дополняющей нежесткости для оптимальных решений Игры с выпуклой (вогнутой) функцией выигрыша Крайняя точка выпуклого множества Утверждение о крайней точке выпуклого компакта (Каратеодори) (о крайней точке-максимуме) Игры с выпуклой (вогнутой) функцией выигрыша для игры с выпуклой функцией выигрыша для игры с вогнутой функцией выигрыша

Лекция 7. Антагонистические игры с полной информацией.
Антагонистические игры с полной информацией Стратегия и ее определение Функция Бемена Теорема Цермело Игра "шахматы" Применение теоремы Цермело на матричной игре

Лекция 8. Исследование игровых моделей.
Модель "нападение - защита" Функция выигрыша Исследование игры "нападение-зашита" Минимаксная и максиминная стратегия в игре "нападение-защита" Решение в смешанных стратегиях Модель "Дуэль" Шумная дуэль Бесшумная дуэль

Лекция 9. Биматричные игры.
Биматричная игра Ситуация равновесия Свойство дополняющей нежесткости Биматричная игра "Семейный спор" Смешанная стратегия в биматричной игре с санкциями Метод поиска равновесий Теорема доминирования в биматричных играх

Лекция 10. Неантагонистические игры.
Общая игра двух лиц Равновесие по Нэшу Биматричная игра Оптимальная по Парето ситуация Равновесие по Нэшу о существовании равновесия в игре многих лиц Теорема Брауэра о неподвижной точке Состояние равновесия в биматричной игре Модель дуополии Курно

Лекция 11. Теория принятия решений.
Теорема Геймеера Теория принятия решений Оптимальная по Парето стратегия Оптимальная стратегия по Слейтеру Теорема о множествах стратегий оптимальных по Парето и Слейтеру Теорема о представлении стратегий оптимальных по Слейтеру

Лекция 12. Иерархические игры.
Первая иерархическая игра Эпсилон оптимальная стратегия Равновесие по Штакельберу Вторая иерархическая игра "Стратегия наказаний" Минимизирующая стратегия 2 Теорема Гермейера

Лекция 13. Критерии и математическая модель операций.
Бинарное отношение Векторные оценки  Бинарное отношение по Парето Сужение векторных стратегий Лемма о векторной оценке, связанной отношением Парето Утверждение о бинарном отношении при равноценных критериях Основные определения: операции и оперирующая сторона Контролируемые и неконтролируемые факторы Критерий эффективности

Лекция 14. Многокритериальная оптимизация.
Сравнение стратегий по Парето и Слейтеру  Допустимое или возможное направление вектора о неоптимальной стратегии Общая задача принятия решений и бинарное отношение  Ядро бинарного отношения

Лекция 15. Необходимое условие для оптимальной максиминных стратегий.
Необходимое условие для оптимальной максиминных стратегий о существовании производной по направлению максиминная стратегия максиминная стратегия на отрезке ( на параллелепипеде) Алгоритм поиска максиминных стратегий

Лекция 16. Оптимальные стратегии в операции.
Определения (информационная гипотеза, стратегия) Подход Гермейра, принцип гарантированного результата Оптимальная стратегия Оценка эффективности стратегий Оценка эффективности смешанной стратегии Абсолютно оптимальные стратегии о существовании абсолютно оптимальной стратегии о наилучшем результате при достижении максимума

Лекция 17. Задача поиска объекта.
Задача поиска объекта Лемма о максимизации суммарной эффективности (Критерий Гросса) Алгоритм нахождения оптимального распределения ресурсов

Лекция 18. Некоторые задачи оптимального распределения ресурсов.
Общая постановка задачи оптимального распределения ресурсов (§15) Принцип уравнивания Достаточное условие оптимальности распределения Алгоритм для нахождения оптимального распределения ресурсов (о значении эффекта) Лемма Гиббса