Лабораторная работа №5

№5.Симплекс метод в теории игр

Лабораторная работа № 5

Тема: Симплекс - метод в теории игр

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

Рассмотрим игру mn с m стратегиями A₁ ... A_m игрока A и n стратегиями B₁ ... B_n игрока B. Задана матрица игры

(5.1)

Требуется найти решение игры, т.е. две оптимальные смешанные стратегии игроков A и B:

,

где - вероятности применения чистых стратегий.

Оптимальная стратегия S_A должна обеспечить выигрыш, не меньший , при любом поведении противника, и выигрыш, равный , при его оптимальном поведении, т.е. при стратегии S_B . Т.е. для любой чистой стратегии игрока B имеем , при этом естественно желание игрока A максимизировать свой выигрыш. Таким образом, для игрока A имеем задачу:

Найти max

при условиях

(5.2)

Для игрока B задача приобретает вид:

Найти

при условиях

(5.3)

В силу того, что игрок B стремится минимизировать проигрыш, при использовании противником любой чистой стратегии, B проиграет меньше, чем , и , если A применит свою оптимальную стратегию. Здесь - цена игры.

Полагаем, что >0. Если это не так, то этого можно добиться прибавлением к элементам платёжной матрицы одного и того же положительного числа. Разделив каждое из соотношений задач (5.2)-(5.3) на и положив

получим для второго игрока:

,

для первого игрока:

.

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

Исходная задача (для второго игрока): найти значения , такие что

при условиях (5.4)

Двойственная задача (для первого игрока):.найти значения , такие что

при условиях (5.5)

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

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

Оптимальные стратегии матричной игры рассчитываются по формулам

(5.6).

Таким образом решение задачи симплекс-методом включает следующие этапы:

1. Если в матрице есть отрицательные элементы, то вычесть из всех число S=min .

1. Сформулировать задачи вида (5.4)-(5.5) для обоих игроков.

1. Решить обе задачи симплекс-методом, т.е. найти оптимальные значения , .

1. Найти оптимальные стратегии , по формулам (5.6) и цену игры .

1. Найти цену исходной игры добавлением к величины S.

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

Найдем оптимальную смешанную стратегию S_A^*=(p₁,p₂,p₃) игрока А. Условия (5.5) примут вид:

Минимизируемая линейная функция .

Перейдем от условий-неравенств к условиям равенствам, введя переменные x₄, x₅, x₆, каждая из которых входит в одно уравнение с коэффициентом -1, в остальные с коэффициентом равным 0. Функция L принимает вид x₁+x₂+x₃+0x₄+0x₅+0x₆. Вводим базисные переменные z₁, z₂, z₃ получаем задачу:

minZ=

при условиях:

.

Здесь M - бесконечно большое число.

Заносим данные в симплекс-таблицу и находим решение задачи.

Из таблицы видно, что функция Z принимает минимальное значение min Z=1/5 при x₁=2/21, x₂=2/21, x₃=1/7. Отсюда =1/Z=3 - цена исходной игры, p₁=x₁=2/213=2/7, p₂=x₂=2/213=2/7, p₃=x₃=1/73=3/7.

Таким образом найдена оптимальная стратегия игрока А S_A^*=(2/7,2/7,3/7). Аналогично можно найти оптимальную смешанную стратегию для игрока В. S_В^*=(3/6,2/6,1/6).

Задание к лабораторной работе № 5

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

13