Системный анализ – Теория матричных игр

Федеральное агентство по образованию  РФ

Пермского Государственного технического университета

Лысьвенский филиал

Кафедра ИЭ и ЕН

Пояснительная записка к курсовой работе

по дисциплине   «Системный анализ – Теория матричных игр»

Выполнила:                        Студентка гр. БИВТ- 04-1                                                                                                                          Пилюгина К.Н.

Руководитель:                                            Аликина Е.Б.

Лысьва-2007

СОДЕРЖАНИЕ

РЕФЕРАТ

ВВЕДЕНИЕ

Глава 1: ТЕОРИЯ ИГР

1.1 Понятие игры

1.2 Основные определения

1.3 Конечная парная антагонистическая игра

1.4 Теорема фон Неймана

1.5 Игра размерностью m×n

Глава 2: РАЗРАБОТКА

2.1 О среде разработки – Turbo Pascal

2.2 Руководство пользователя

2.3 Используемые процедуры и функции

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

РЕФЕРАТ

Введение содержит главную цель разработки и её значимость на сегодняшний день.

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

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

Описан алгоритм решения задачи, используемые процедуры и переменные.

Пояснительная записка содержит так же приложение: результат работы программы над решением задачи, описанной в руководстве пользователя.

Сделан вывод о проделанной работе. Отчет содержит 24 листа.

ВВЕДЕНИЕ

Целью данного проекта является разработка программы, которая посредствам вычислений определяла оптимальные стратегии для каждого игрока и цену матричной игры в целом. Кроме того, предусматривается возможность не только получить конечный ответ, но и просмотреть промежуточные вычисления решения задачи.

Программа реализуется на языке программирования Turbo Pascal, предусматривает ввод квадратных и неквадратных платежных матриц, имеющих количество строк и столбцов не более десяти.

Глава 1: ТЕОРИЯ ИГР

1.1 Понятие игры

Теория игр представляет собой математическую теорию конфликтных ситуаций. Ее цель – выработка рекомендаций по разумному поведению участников конфликта. Впервые описана в1944 – в монографии фон Неймана и Моргенштерна.

Игра – эта ситуация, в которой эффективность решений одного игрока зависит от действий другого игрока.

Игра развивается по определенным правилам, которые определяют последовательность ходов игроков.

Конец игры наступает в том случае, когда все возможные ходы игроками сделаны.

Игра характеризуется:

1.      Множество заинтересованных сторон – лиц, участников, игроков

2.      Множеством возможных действий (ходов) для каждого игрока – стратегий

3.      Интересами игроков, задаваемых с помощью функции выигрыша – функции платежа.

Игры бывают:

1.      Игры парные (2 игрока) и множественные.

2.      По количеству возможных стратегий:

•          конечные (конечное у каждого игрока)

•          бесконечные (хотя бы у одного игрока бесконечное число стратегий)

3.      По свойствам функции платежа:

•          антагонистическая (с нулевой суммой) – выигрыш одного = проигрышу другого,

•          игра с постоянной разностью (участники выигрывают и проигрывают одновременно, следовательно выгодно действовать сообща).

4.      По наличию предварительной договоренности о совместных действиях: кооперативные (есть договоренность) и некооперативные (договоренности нет).

1.2 Основные определения

Стратегия – совокупность правил, определяющих выбор варианта действия игроком в зависимости от ситуации в игре.

Целью является отыскание оптимальной стратегии для каждого игрока.

Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный выигрыш или минимально возможный проигрыш независимо от поведения противника.

Выбор одной из возможных стратегий и ее реализация называется ходом.

Ход – может быть личным (выбор стратегии сознателен) и случайным.

Игру можно описать разными способами

1.      Позиционный – задается в виде дерева шагов.

2.      Нормальный – задаются допустимые стратегии для каждого игрока и функция выигрыша, которая определяет выигрыш или проигрыш для каждой стратегии. Чаще всего задается в виде платежной матрицы.

1.3 Конечная парная антагонистическая игра

Два игрока (I и II) обладают конечным набором стратегий:

      I   стратегии  А1…..Am        

      II  стратегии  B1….Bn

      Эта игра размерностью n×m.

Предположим, что на некотором ходе игрок I выбрал стратегию Ai , а игрок II отвечает стратегией Bj. Тогда W1 (Ai , Bj) – выигрыш, который получит игрок I при этой паре стратегий. W2 (Ai , Bj) – выигрыш, который получит игрок II при этой паре стратегий

Так как игра антагонистическая, то

W1 (Ai , Bj) + W2 (Ai , Bj) =0 или W1 (Ai , Bj) =- W2 (Ai , Bj) = W (Ai , Bj)

Обозначим W (Ai , Bj)=aij  тогда получим платежную матрицу

Каждый положительный элемент это выигрыш I игрока, каждый отрицательный – проигрыш II.

1.4 Теорема фон Неймана

Любая антагонистическая парная конечная игра имеет по крайней мере одно решение, возможное в смешанных стратегиях.

Следовательно игра имеет цену γ, α≤ γ ≤ β

Игрок I стремится добиться выигрыша = γ, а игрок II стремится минимизировать проигрыш до γ.

Смешанные стратегии также обладают свойством равновесия, обоим игрокам выгодно их применять.

Теорема:

Применение оптимальных смешанных стратегий гарантирует игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш) равный цене игры γ, независимо от поведения противника, если игрок не выходит за пределы своих активных стратегий. 

1.5 Игра размерностью m×n

В ТИ доказано, что в играх размерностью m×n число активных стратегий = min{m,n}. Таким образом,  решение игр m×2 и 2×n сводится к решению игр 2×2.

Способы понижения размерности платежной матрицы

1.      Размерность матрицы можно понизить путем удаления дублирующих и заведомо не выгодных стратегий .

2.      Если в матрице все элементы некоторой строки (столбца) равны, то соответствующие стратегии называются дублирующими.

3.      Если в матрице все элементы некоторой строки , соответствующие стратегии Ai I игрока не больше соответствующих элементов другой строки, то стратегии Ai  называется заведомо невыгодной для I игрока.

4.      Если в матрице все элементы некоторого столбца, соответствующие стратегии Bj II игрока не меньше соответствующих элементов другого столбца, то стратегию Bj   называется заведомо невыгодной для II игрока

Рассмотрим игру, которая будет описана следующей платежной матрицей.

Находим решение в смешанных стратегиях:

I игрок   чистые стратегии  А1…..Am;  II  игрок  чистые стратегии  B1….Bn;

Оптимальные смешанные стратегии  p*A ,p*B

Предположим, что все элементы платежной матрицы ≥0, иначе добавляем к каждому элементу положительное число, при этом оптимальные стратегии не меняются, а цена игры увеличивается на это число. 

Согласно теореме ТИ если I игрок будет придерживаться оптимальной смешанной стратегии, то он получит выигрыш ≥γ (цены игры). При этом II игрок применяет свои чистые стратегии

Введем обозначения xi=pi/γ   i=1..m

Разделим неравенства на γ

Цель I игрока увеличить выигрыш γ

Так как p1+…+pm=1, то x1+…xm=1/γ

             F=x1+…..+xm→min

Получаем задачу линейного программирования.

Составим аналогичную задачу для II игрока.

Если II игрок  придерживается оптимальной смешанной стратегии, то он получит проигрыш ≤γ. При этом I игрок применяет свои чистые стратегии.

Введем обозначения yi=qj/γ   j=1..n

Разделим неравенства на γ

II игрок стремится уменьшить γ и следовательно F1 надо максимизировать. Таким образом, решение матричных игр m×n сводится к решению пары двойственных симметричных задач.

Решая эти задачи найдем оптимальное решение x*=(x1*.....xm*)    y*=(y*1…y*n)

Отсюда найдем цену игры:

Глава 2: РАЗРАБОТКА

2.1 О среде разработки – Turbo Pascal

 2.1.1 Системные требования

В официальной документации написано, что для минимальной работоспособности потребуется процессор не ниже Intel 80386 и 4МБ памяти – это действительно минимальная конфигурация для запуска компилятора, для нормальной работы лучше иметь железо не хуже, чем Pentium-75/16МБ. Требуемое место на диске зависит от того, что вы будете устанавливать – можно работать с 8МБ, можно поставить и на 90МБ – и пользоваться всеми возможностями этого замечательного продукта. 

2.1.2 Ожидаемые технико-экономические показатели

Данная программа довольно проста и легко компилируется.

Благодаря реализованному алгоритму она будет исправно работать на любом ПК в любой операционной системе Windows NT.

2.2 Руководство пользователя

Поскольку программа реализована в среде Turbo Pascal, то пользователю достаточно выполнять инструкции, следующие друг за другом. Переход от одного действия к другому выполняется клавишей Enter.

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

Найти решение игры, определяемой матрицей:

А=

Решение:

1.      На первом этапе пользователю необходимо ввести размерность платежной матрицы: количество строк и количество столбцов (Рис.1)

Рис.1 – Ввод размерности матрицы

2.      Затем, нужно ответить какое решение нужно:

      целочисленное, то есть во время вычисления программа будет округлять все промежуточные и конечное решения до целого;