zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Теория игр и исследование операций

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

Общий курс

Составитель: к.ф.-м.н., доцент Тарашнина С.И.

Введение.
Основные этапы исследования операций. Типичные классы задач исследования операций.
Тема 1. Линейное программирование.
Постановка задач линейного программирования (ЗЛП) и исследование их структуры. Стандартная и общая задачи ЛП. Различные формы представления ЗЛП. Геометрическая интерпретация. Допустимые и оптимальные решения ЗЛП. Понятие базисного решения. Основные теоремы линейного программирования. Допустимое базисное решение. Графический метод решения задач линейного программирования. Симплекс-метод: алгоритм и обоснование. Нахождение допустимых базисных решений: метод искусственных переменных. Двухэтапный симплекс-метод. Прямая и двойственная задачи линейного программирования. Структура и свойства двойственной задачи. Двойственный симплекс-метод. Теорема двойственности.
Тема 2. Целочисленное программирование.
Постановка транспортной задачи (Т-задача). Способы задания Т-задачи. Разрешимость. Условие баланса. Нахождение начального опорного плана: метод северо-западного угла, метод минимального элемента, приближённый метод Фогеля. Метод потенциалов. Решение транспортной задачи при вырожденном опорном плане. Простая задача о назначениях. Потоки в сетях. Теорема о максимальном потоке. Алгоритм нахождения максимального потока и минимального сечения в сети. Задача о коммивояжёре.
Тема 3. Матричные игры.
Задание матричной игры. Решение игры в чистых стратегиях. Понятие ситуации равновесия. Значение (цена) игры. Смешанное расширение матричной игры. Существование ситуации равновесия в матричной игре. Свойства ситуаций равновесия и значения игры. Доминирование стратегий. Принцип исключения доминируемых стратегий. Графоаналитический метод решения матричных игр. Свойства оптимальных смешанных стратегий. Нахождение оптимальных смешанных стратегий в играх с матрицей выигрышей 3x3. Метод приближенного решения матричных игр Брауна-Робинсон. Решение матричных игр методами ЛП.
Тема 4. Неантагонистические игры.
Неантагонистическая игра n лиц в нормальной форме: определение и примеры. Равновесие по Нэшу, оптимальность по Парето. Смешанное расширение игры. Существование ситуации равновесия по Нэшу в смешанных стратегиях для биматричной игры. Понятие кооперативной игры с побочными платежами (ТП-игра). Характеристическая функция кооперативной игры. Различные классы ТП-игр. Понятие дележа. Отношение доминирования на множестве дележей. С-ядро. Вектор Шепли: аксиоматизация. Игры в развёрнутой форме. Полная и неполная информация. Существование абсолютного равновесия по Нэшу в игре с полной информацией. Метод нахождения абсолютного равновесия в игре. Нормализация игры в развернутой форме.
Тема 5. Динамическое программирование.
Основная идея и особенности. Примеры решения задач динамического программирования. Уравнение Беллмана для детерминированного многошагового процесса принятия решений. Динамическое программирование и принцип максимума Понтрягина. Задачи динамического программирования на сетях.

Рекомендуемая литература

  1. Гейл Д. Теория линейных экономических моделей.- М.: Мир, 1969. 342 с.
  2. Петросян Л.А., Зенкевич Н.А. Теория игр. - М.: изд-ва ВШ и "Книжный дом "Университет", 1998.- 300 с.
  3. Таха Х. Введение в исследование операций. Т.1,2. - М.: Мир, 1985. 560 с.
  4. Форд Л., Фалкерсон Д. Потоки в сетях.- М.: Мир, 1966. 230 с.
  5. Ху Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1972. 410 с.
  6. Харшаньи Дж., Зельтен Р. Общая теория выбора равновесия в играх (Перевод с англ. под ред. Зенкевича Н.А.) - СПб: изд-во "Экономическая школа", 2001. 415 с.
  7. Martin J. Osborne, Ariel Rubinstein.A Course in Game Theory. MIT, 1994. 352 p.