Вариант 2 - Теория игр

Найти все максиминные и минимаксные стратегии игроков, нижнюю и верхнюю цены игры. Указать все ситуации равновесия и решение игры.

Принцип построения стратегии x, основанный на максимизации минимального выигрыша,-- принципом максимина, а выбираемая в соответствии с этим принципом стратегия x -- максиминной стратегией игрока 1.

Принцип построения стратегии у, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия у-- минимаксной стратегией игрока 2.

При заданных условиях

Верхняя цена игры равна нижней цене игры и равна -2.

В антагонистической игре Г = (X, Y, K) ситуация (x? , y?) называется ситуацией равновесия или седловой точкой, если K(x, y?) ? K(x? , y?), K(x?, y) ? K(x ? , y?) для всех x ? X и y ? Y. Т. е. в седловой точке элемент матрицы ai ?j ? является одновременно минимумом в своей строке и максимумом в своем столбце.

В заданной задаче ситуация (x2 , y2) является ситуацией равновесия. Решение игры Г=(2,2,-2). Найти ситуацию равновесия и решение игры в смешанных стратегиях графоаналитическим методом.

Игра решается графически, поскольку игрок имеет только две стратегии. При этом игра рассматривается с позиции игрока.

решение матричной игры графическим методом

Рис. 1 - Решение матричной игры графическим методом

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

Например, если игрок придерживается своей 1-й стратегии, то выигрыш, который получит игрок, может быть равен -1, если он будет придерживаться своей 1-й стратегии, или может быть равен 2, если игрок В будет придерживаться своей 2-й стратегии. Откладываем эти значения по осям и, соответственно, и соединяем их отрезком прямой, который подписываем. Аналогично строим отрезки прямых, соответствующих остальным двум стратегиям игрока В. Ломаная линия является нижней границей возможного выигрыша игрока. На этой границе находим точку с максимальной ординатой. Видно, что это точка образованная пересечением линий и, которые отвечают стратегиям и игрока. Это означает, что стратегии и являются активными стратегиями игрока, других стратегий он не применяет. Ординатой точки является цена игры, а отрезки и, на которые проекция точки разделяет единичный отрезок оси абсцисс, определяют вероятности и, с которыми игрок будет применять стратегии и, соответственно. Целью графического решения является определение активных стратегий каждого из игроков, далее задача решается аналитически.

В активных стратегиях матрица имеет вид:

.

По этой матрице оптимальную стратегию игрока определяет вектор, а игрока - вектор. Для вычисления компонентов вектора рассмотрим игру с позиции игрока, то есть, составим систему уравнений, в которых неизвестными являются вероятности и, с которыми игрок придерживается своих активных стратегий, а также цена игры. Первые два уравнения этой системы в качестве коэффициентов при неизвестных и содержат элементы платежной матрицы активных стратегий, которые записаны в ее столбцах. Поскольку игрок придерживается либо стратегии, или стратегии, то выбор или одной, или другой из этих стратегий - полная группа событий, соответственно, сумма вероятностей этих событий равна единице. Это и описывает третье уравнение системы. Получаем математическую модель задачи линейного программирования:

Решая полученную систему уравнений, находим оптимальный план относительно вероятностей, с которыми игрок использует свои стратегии, и цену игры, соответствующие этому плану:

Решая методом Крамера получаем

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

Решая эту систему уравнений, находим компоненты оптимального плана двойственной задачи, соответствующие вероятностям активных стратегий игрока, и значение функции цели, которое отвечает этому плану:

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

Привести матричную игру к задаче линейного программирования и решить ее, используя симплекс-метод

ТЕОРИЯ.

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

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

.

Оптимальная стратегия X* обеспечивает первому игроку средний выигрыш, не меньший, чем цена игры V, при любой стратегии второго игрока и выигрыш, равный цене игры V, при оптимальной стратегии второго игрока.

Если первый игрок применяет смешанную стратегию X* против любой чистой стратегии второго игрока, то он получает средний выигрыш, или математическое ожидание выигрыша V(j)=a1jx1+...amjxm, j= 1, 2,..., п (т. е. элементы j-гo столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий первого игрока и результаты складываются).

Для оптимальной стратегии X* все средние выигрыши не меньше цены игры V, поэтому получаем систему неравенств:

A11x1+a21x2+...+am1xmV,

A12x1+a22x2+...+am2xmV,

.......................... (1)

A1n x1+a2n x2+...+amn xmV.

Каждое из неравенств можно разделить на число V > 0. Введем новые переменные

Zi=. (2)

Тогда система (1) примет вид:

(3)

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

Максимизация цены игры V эквивалентна минимизации величины , поэтому задача может быть сформулирована следующим образом: определить значения переменных так, чтобы они удовлетворяли линейным ограничениям (1.4.3) и при этом линейная функция

(4)

Обращалась в минимум. Это задача линейного программирования. Решая задачу (3) ? (4), получаем оптимальные стратегии .

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

(5)

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

Если обозначить

(6)

То получим систему неравенств:

(7)

Переменные , удовлетворяют условию .

Игра свелась к следующей задаче: определить значения переменных , которые удовлетворяют системе неравенств (1.4.7) и максимизируют линейную функцию

(8)

Решение задачи линейного программирования (7) ? (8) определяет оптимальную стратегию . При этом цена игры

. (9)

Задачи линейного программирования (3) ? (4) и (7) ? (8) являются взаимно двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.

Решение.

Любая игра сводится к задаче линейного программирования. Для первого игрока ограничения и целевая функция выглядят следующим образом:

Где

Для второго игрока задача линейного программирования является двойственной к предыдущей и имеет вид:

Где

Решим симплекс-методом систему, составленную для второго игрока.

Добавим новые переменные и приведем систему к каноническому виду:

Базис составляют переменные 5 6 7

Находим начальное опорное решение. Для этого свободные переменные приравниваем к нулю 1= 2=3=4= 0.

Получили опорное решение N1 = (0,0,0,0,1,1,1) с единичным базисом Б1 =(А5,А6,А7).

F(N1)=0

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Стратегия игрок игра программирование

Дk = CбNk -- ck

Где:

Cб = (с1, с2, ... , сm) -- вектор коэффициентов целевой функции при базисных переменных

Nk = (1k, 2k, ... , mk) -- вектор разложения соответствующего вектора Ак по базису опорного решения

Ск -- коэффициент целевой функции при переменной к.

Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения запишем в симплексной таблице:

1

1

1

1

0

0

0

Б

Сб

А0

А1

А2

А3

А4

А5

А6

А7

5

0

1

3

4

6

4

1

0

0

1/3

6

0

1

4

4

4

5

0

1

0

1/4

7

0

1

2

3

6

8

0

0

1

1/2

Дk

0

-1

-1

-1

-1

0

0

0

Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Во втором столбце таблицы "Сб" записываются коэффициенты целевой функции при базисных переменных в том же порядке.

В последней строке таблицы с оценками Дk в столбце "А0" записываются значения целевой функции на опорном решении Z (N1).

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

Так как имеется три одинаковых отрицательных оценки, выберем вектор А1. Наименьшее значение - во второй строке. Значит вводим в базис Х2 переменную 1 вместо 6.

Выполняем преобразования Жордана с элементом х21= 4, получаем второе опорное решение N2 = (0.25; 0; 0; 0;0,25;0;0,5) з базисом Б2 = (А5, А1, А7) (таблица 2)

Стратегия игрок программирование

1

1

1

1

0

0

0

Б

Сб

А0

А1

А2

А3

А4

А5

А6

А7

5

0

1/4

0

1

3

1/4

1

- 3/4

0

1

1

1/4

1

1

1

1 1/4

0

1/4

0

7

0

1/2

0

1

4

5 1/2

0

- 1/2

1

Дk

1/4

0

0

0

1/4

0

1/4

0

Все оценки положительные, то есть решение оптимальное.

Полученное оптимальное решение имеет вид:

Перейдем к исходным переменным:

Из полученных результатов следует, что минимальный гарантированный проигрыш второго игрока составит 4 в случае если он будет использовать только свою первую стратегию.

Решение задачи для первого игрока найдем с помощью теорем двойственности.

Первая теорема двойственности

Для взаимодвойственных ЗЛП имеет место один из взаимоисключающих случаев.

Похожие статьи




Вариант 2 - Теория игр

Предыдущая | Следующая