- •Государственный Университет Управления
- •Курсовая работа
- •1. Линейная производственная задача
- •2. Двойственная задача
- •Задача о «расшивке узких мест производства»
- •3. Транспортная задача линейного программирования
- •4. Анализ доходности и риска финансовых операций
- •5. Распределение капитальных вложений
- •6. Матричная игра
- •7. Принятие решений в условиях неопределенности
- •8. Формирование оптимального портфеля ценных бумаг
6. Матричная игра
Два игрока А и В играют в матричную игру. Дана платёжная матрица (А), отражающая выигрыш игрока А или проигрыш игрока В при использовании ими их стратегий.
Требуется найти решения игры для каждого игрока, а именно пару оптимальных стратегий, при которых каждому из игроков не выгодно отступать от них, поскольку это приведёт к их проигрышу.
Попытаемся упростить матрицу А, если это возможно, за счёт выявления дублирующих и доминирующих стратегий.
Стратегия Ae дублирует стратегию Ak, если элементы e-строки равны элементам k-строки.
Стратегия Bm дублирует стратегию Bn, если элементы m-столбца равны элементам n-столбца.
В нашем случае B1 дублирует B4. Исключим B4 из рассмотрения.
Стратегия AL доминирует стратегию Ak, если элементы L-строки превышают или равны элементам k-строки. Доминируемая k-стратегия из рассмотрения исключается.
1-я стратегия доминирует 2-ую стратегию, так что 2-ую стратегию из рассмотрения исключаем.
Стратегия Bm, доминирует стратегию Bn, если элементы m-столбца меньше или равны элементам n-столбца. Доминируемая n-стратегия из рассмотрения исключается. В нашем случае такого нет.
Выясним, есть ли решении игры в чистых стратегиях (проверим на оседлую точку).
A\B |
B1 |
B2 |
B3 |
B4 |
αi |
A1 |
9 |
-2 |
1 |
0 |
-2 |
A2 |
-3 |
4 |
-5 |
6 |
-5 |
A3 |
5 |
-7 |
8 |
-9 |
-9 |
βj |
9 |
4 |
8 |
6 |
|
α≠β, т.е. можно сделать вывод, что игры в чистых стратегиях нет.
Введём новые переменные: для игрока A P(p1,p2,p3) , т.е. вероятности использования игроком А 1-ой стратегии, 2-ой стратегии и т.д. соответственно, для игрока B Q(q1,q2,q3,q4) , т.е. вероятности использования игроком B 1-ой стратегии, 2-ой стратегии и т.д. соответственно. Так же введем υ – цену игры.
Добавим к каждому элементу матрицы значение +9, чтобы выигрыши были неотрицательные.
A\B |
q1 |
q2 |
q3 |
q4 | |
B1 |
B2 |
B3 |
B4 | ||
p1 |
A1 |
18 |
7 |
10 |
9 |
p2 |
A2 |
6 |
13 |
4 |
15 |
p3 |
A3 |
14 |
2 |
17 |
0 |
Пусть игрок В играет по оптимальной стратегии, а игрок А – по чистым.
A1: 18*q1+ 7*q2+ 10*q3+ 9*q4<= υ
A2: 6*q1+ 13*q2+ 4*q3+ 15*q4<= υ
A3: 14*q1+ 2*q2+ 17*q3+ 0*q4<= υ
П
(*)
18*x1+ 7*x2+ 10*x3+ 9*x4<= 1
6*x1+ 13*x2+ 4*x3+ 15*x4<= 1
14*x1+ 2*x2+ 17*x3+ 0*x4<= 1
xj=>0 j=1,2,3,4
Так как q1,q2,q3,q4 – вероятности использования стратегий игроком В, то:
q1+q2+q3+q4=1 Делим на υ>0 и получаем:
q1/υ +q2/υ +q3/υ +q4/υ =1/υ
x1+x2+x3+x4=1/υ
Так как υ – проигрыш игрока В, то он хочет минимизировать, тогда 1/υ – максимизировать. Итак, приходим к постановке задачи: найти значение вектора X=( x1; x2; x3; x4 ), которое обеспечивало бы максимальное значение функции x1+x2+x3+x4=1/υ=Z → max при следующих линейных ограничениях (*).
Решим задачу симплексным методом.
|
|
|
|
|
|
|
|
|
|
|
C |
Базис |
H |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
Примечание |
0 |
Х5 |
1 |
18 |
7 |
10 |
9 |
1 |
0 |
0 |
Min ∆j=-1 х2 – в базис min(1/7;1/13;1/2)=1/13 х6 – из базиса 2-е ур-ие разрешающее |
0 |
Х6 |
1 |
6 |
13 |
4 |
15 |
0 |
1 |
0 | |
0 |
Х7 |
1 |
14 |
2 |
17 |
0 |
0 |
0 |
1 | |
|
|
0-Z |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 | |
|
Min ∆j=-9/13 х3 – в базис min(1/17;1/4;11/213)=11/213 x7 – из базиса 3-е ур-ие разрешающее | |||||||||
0 |
X5 |
6/13 |
192/13 |
0 |
102/13 |
12/13 |
1 |
-7/13 |
0 | |
1 |
Х2 |
1/13 |
6/13 |
1 |
4/13 |
15/13 |
0 |
1/13 |
0 | |
0 |
Х7 |
11/13 |
170/13 |
0 |
213/13 |
-30/13 |
0 |
-2/13 |
1 | |
|
|
1/13-Z |
-7/13 |
0 |
-9/13 |
2/13 |
0 |
1/13 |
0 | |
|
Все ∆j=>0 => решение оптимальное
| |||||||||
0 |
Х5 |
4/71 |
604/71 |
0 |
0 |
144/71 |
1 |
-33/71 |
-34/71 | |
1 |
Х2 |
13/213 |
46/213 |
1 |
0 |
85/71 |
0 |
17/213 |
-4/213 | |
1 |
Х3 |
11/213 |
170/213 |
0 |
1 |
-10/71 |
0 |
-2/213 |
13/213 | |
|
|
8/71-Z |
1/71 |
0 |
0 |
4/71 |
0 |
5/71 |
3/71 |
X=(0; 13/213; 11/213; 0)
Zmax=1/υ=8/71
Тогда цены игры υ=71/8
qi=xi* υ i=1,2,3,4
q1=0*71/8=0
q2=13/213*71/8=13/24
q3=11/213*71/8=11/24
q4=0*71/8=0
Оптимальная стратегия игрока В (0; 13/24; 11/24; 0).
Ч
(**)
18*y1+6*y2+14*y3=>1
7*y1+13*y2+2*y3=>1
10*y1+4*2+17*y3=>1
9*y1+15*y2+0*y3=>1
yi=pi/υ =>0 i=1,2,3
Так как p1+p2+p3=1, то y1+y2+y3=1/ υ.
Так как υ – выигрыш игрока А, то он хочет максимизировать, тогда 1/υ – минимизировать. Итак, приходим к постановке задачи: найти значение вектора Y=( y1; y2; y3; y4 ), которое обеспечивало бы минимальное значение функции y1+y2+y3=1/υ=L → min при следующих линейных ограничениях (**).
Эта задача является двойственной по отношению к рассмотренной выше задачи, так что решение возьмём из последней симплексной таблицы.
Y=(0; 5/71; 3/71)
Lmin=Zmax=1/υ=8/71
υ=71/8
pi=yi* υ i=1,2,3
p1=0*71/8=0
p2=5/71*71/8=5/8
p3=3/71*71/8=3/8
Оптимальная стратегия игрока А (0; 5/8; 3/8).
Теперь возвращаемся к начальной матрице А4,5 , тогда её решение имеет вид:
A\B |
q1=0 |
q2=13/24 |
q3=11/24 |
q4=0 |
q5=0 | |
B1 |
B2 |
B3 |
B4 |
B5 | ||
p1=0 |
A1 |
9 |
-2 |
1 |
9 |
0 |
p2=0 |
A2 |
-3 |
-7 |
-5 |
-3 |
-9 |
p3=5/8 |
A3 |
-3 |
4 |
-5 |
-3 |
6 |
p4=3/8 |
A4 |
5 |
-7 |
8 |
5 |
-9 |
А цена игры υ=71/8 - 9= - 1/8.
Теперь, имея все данные, найдем риски игроков при использовании ими своих оптимальных и чистых стратегий. Нижний индекс соответствует игроку А, верхний – игроку В.
υ=M(P,Q)=∑∑aij*pi*pj= - 1/8
Найдём риск игры при использовании игроками своих оптимальных стратегий:
D00=∑∑(aij)2*pi*qj - υ2=1073/32-1/64=2145/64;
D02=∑(ai2)2*pi - υ2=1815/64;
D03=∑(ai3)2*pi - υ2=2535/64;
D30=∑(a3j)2*qj - υ2=1287/64;
D40=∑(a4j)2*qj - υ2=3575/64;
Минимальное значение риска равно: . Данные риск соответствует ситуации, когда игрок А играет по 3-ей чистой стратегии, а игрок В по оптимальной.
Так как минимальное найденное значение риска меньше чем значение риска при использовании игроками своих оптимальных стратегий, то можно сделать вывод , что играть они могут только при договорённости.