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

 

Если игра т х п не имеет оптимального решения непосредственно в чистых стратегиях, то оптимальное решение необходимо искать в области смешанных стратегий. Игрок А обладает стратегиями А₁, А₂,…, А_m, а игрок В – стратегиями B₁, B₂,…, B_n. Необходимо определить оптимальные стратегии и , где - вероятности применения соответствующих чистых стратегий А_i, B_j. При этом и .

Если игрок А применяет смешанную стратегию против любой чистой стратегии В_j игрока В, то он получает средний выигрыш (математическое ожидание выигрыша):

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

a₁₁p₁ + a₂₁p₂ +…+ a_m1p_m ≥ v

a₁₂p₁ + a₂₂p₂ +…+ a_m2p_m ≥ v

………………………………

a_1np₁ + a_2np₂ +…+ a_mnp_m ≥ v

Если каждое неравенство разделить на число v> 0 (v> 0 можно добиться, сделав все элементы a_ij ≥ 0) и введя новые переменные:

x₁=p₁/v, x₂=p₂/v, …., x_m=p_m/v

предыдущая система примет вид:

a₁₁x₁ + a₂₁x₂ +…+ a_m1x_m ≥ 1

a₁₂x₁ + a₂₂x₂ +…+ a_m2x_m ≥ 1

………………………………

a_1nx₁ + a_2nx₂ +…+ a_mnx_m ≥ 1

Если нормировочное условие, выраженное равенством p₁ + p₂ +…+ p_m =1 разделить также на v, тополучим, что переменные x₁ + x₂ +…+ x_m=1/v. В силу того, что цель игрока А максимизировать свой выигрыш, т.е. максимизировать цену игры v, максимизация цены игры v эквивалентна минимизации величины 1/ v. Поэтому задача в терминах линейного программирования может быть сформулирована следующим образом:

 

Найти минимум целевой функции Z = x₁ + x₂ +…+ x_m при ограничениях. Тем самым получаем задачу линейного программирования, решая которую получим оптимальную стратегию и цену игры v= 1/Z.

Для определения оптимальной стратегии игрока В следует учесть, что игрок стремится минимизировать гарантированный выигрыш, т.е. найти max 1/ v. Переменные q₁, q₂,…, q_n удовлетворяют неравенствам

 

a₁₁q₁ + a₁₂q₂ +…+ a_1nq_n ≤ v

a₂₁q₁ + a₂₂q₂ +…+ a_2nq_n ≤ v

………………………………

a_m1q₁ + a_m2q₂ +…+ a_mnq_n ≤ v

Если также как и в предыдущем случае ввести новые переменные:

y₁=q₁/v, y₂=q₂/v, …., y_n=q_n/v,

то предыдущая система примет вид:

a₁₁y₁ + a₁₂y₂ +…+ a_1ny_n ≤ 1

a₂₁y₁ + a₂₂y₂ +…+ a_2ny_n ≤ 1

……………………………

a_m1y₁ + a_m2y₂ +…+ a_mny_n ≤ 1,

а задача сводится к задаче линейного программирования, в которой надо найти максимум целевой функции Z’ = y₁ + y₂ +…+ y_n при заданных системой ограничениях.

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

v = 1/max Z' = 1/min Z.

 

Пример. Найти решение игры со следующей платежной матрицей:

С=

Так как матрица не имеет седловой точки, то ее решение будем искать в смешанных стратегиях. Математические модели будут состоять из пары двойственных задач линейного программирования. Первая задача на нахождение минимума функции F(x) = x ₁+ x ₂+ x ₃

При следующих ограничениях:

2 x ₁+4 x ₂+ x ₃ ≥ 1

3 x ₁+2 x ₂+3 x ₃ ≥ 1

x ₁+2 x ₂+4 x ₃ ≥ 1

x _i ≥ 0, i=1,3

где , i=1,3

Вторая задача будет на нахождение максимума функции Z(y)=y₁+y₂+y₃

При следующих ограничениях:

2y₁+3y₂+ y₃ ≤ 1

4y₁+2y₂+ 2y₃ ≤ 1

y₁+3y₂+ 4y₃ ≤ 1

y_i ≥ 0, i=1,3

где , i=1,3

Решение задач может быть выполнено симплекс-методом.

 

 

Задачи для самостоятельного решения.

Составив прямую и двойственную задачи линейного программирования решить задачи:

1. 2. 3.

4. 5. 6.

7. 8. 9.

10. 11. 12.