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

Посмотреть архив целиком

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


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

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

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

Рассмотрим игру mn с m стратегиями A1 ... Am игрока A и n стратегиями B1 ... Bn игрока B. Задана матрица игры

(5.1)

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

,

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

Оптимальная стратегия SA должна обеспечить выигрыш, не меньший , при любом поведении противника, и выигрыш, равный , при его оптимальном поведении, т.е. при стратегии SB . Т.е. для любой чистой стратегии игрока 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.

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

Найдем оптимальную смешанную стратегию SA*=(p1,p2,p3) игрока А. Условия (5.5) примут вид:

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

Перейдем от условий-неравенств к условиям равенствам, введя переменные x4, x5, x6, каждая из которых входит в одно уравнение с коэффициентом -1, в остальные с коэффициентом равным 0. Функция L принимает вид x1+x2+x3+0x4+0x5+0x6. Вводим базисные переменные z1, z2, z3 получаем задачу:

minZ=

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


.

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

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

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

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







Коэффициенты


базисные

свобод-

1

1

1

0

0

0

M

M

M

базисные

перемен-

ные

Переменные


ные

члены

x1

x2

x3

x4

x5

x6

z1

z2

z3

M

z1

1

2

1

5

-1

0

0

1

0

0

M

z2

1

3

6

1

0

-1

0

0

1

0

M

z3

1

6

3

1

0

0

-1

0

0

1

Z=3M

1-11M

1-10M

1-7M

M

M

M

0

0

0

M

z1

2/3

0

0

14/3

-1

0

1/3

1

0

M

z2

1/2

0

9/2

1/2

0

-1

1/2

0

1

1

x1

1/6

1

1/2

1/6

0

0

-1/6

0

0

Z=7/6M+1/6

0

1/2-9/2M

5/6-31/6M

M

M

1/6-5/6M

0

0

1

x3

1/7

0

0

1

-3/14

0

1/14

-

0

M

z2

3/7

0

9/2

0

3/28

-1

13/28

-

1

1

x1

1/7

1

1/2

0

1/28

0

-15/84

-

0

Z=3/7M+2/7

0

1/2-9/2M

0

5/28-3/28M

M

9/84-13/28M

-

0

1

x3

1/7

0

0

1

-3/14

0

1/14

1

x2

2/21

0

1

0

1/42

-2/9

13/126

1

x1

2/21

1

0

0

1/42

1/9

-29/126

Z=1/3

0

0

0

5/28

1/9

7/126



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

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16

17.

18.

19.

20.

21.

22.

23.

24.

25.





13