Теория прин. реш(теория игр)

Министерство образования Российской Федерации.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ

РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

( ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ.)

Курсовая работа.

Тема: ” Игры с нулевой суммой ”

по дисциплине “Теории принятия решения ”.

Москва. 2004 г.

1. Игры с чистыми стратегиями.

Игра двух лиц с нулевой суммой в матричной форме занимает центральное место в современной теории игр. Пусть имеется два игрока. В распоряжении первого игрока имеется всего n возможных ходов i=1,2,3,...,n; в распоряжении второго игрока имеется m возможных ходов j=1,2,3,...,m. Эти возможные ходы называются чистыми стратегиями игроков.

Оба игрока делают одновременно по одному ходу, после чего партия считается законченной. Если первый игрок делает ход i, а второй  ход j, то первый игрок получает выигрыш, равный a_ij. Очевидно, что выигрыш второго игрока равен -a_ij. Эти данные можно записать в виде матрицы

,

в которой строки соответствуют ходу первого игрока, а столбцы  ходу второго игрока. Эта матрица носит название матрицы выигрышей (платёжной матрицы).

Пусть первый игрок выбирает ход i. В наихудшей для него ситуации он выиграет min_ja_ij.

Стремясь сделать свой минимальный выигрыш максимальным, он выбирает свой ход из условия max_i min_j a_ij. Такая стратегия называется максиминной.

Аналогично, второй игрок, выбирая ход j, в наихудшей для себя ситуации проигрывает max_i a_ij. Стремясь сделать свой максимальный проигрыш минимальным, он должен выбирать свой ход из условия min_j max_i a_ij. Такая стратегия называется минимаксной.

Существует соотношение между max_i min_j a_ij и min_j max_i a_ij :

max_i min_j a_ij  min_j max_i a_ij

Если обе величины равны для пары i=I, j=J, говорят, что игра имеет седловую точку или решение I,J и единственную цену a_IJ. Если первый игрок знает предстоящий ход второго, и обратно, то оптимальные стратегии для такой игры не имеют смысла.

2. Игры со смешанными стратегиями.

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

Аналогично смешанная стратегия второго игрока представляет собой вектор где q_j представляет собой вероятность применения вторым игроком чистой стратегии. Цена игры должна теперь определяться математическим ожиданием выборочных значений выигрыша (проигрыша) игроков с учетом вероятностей появления различных стратегий  игроков за период игры.

В игре со смешанными стратегиями первый игрок стремится максимизировать минимум математического ожидания посредством выбора p₁,p₂,…,p_n.

Тогда как стремится минимизировать путем выбора q₁,q₂,…,q _m.

Для любой заданной матрицы выигрышей

Эта величина называется ценой V игры.

3. Связь с линейным программированием.

В соответствие с введенным понятием цены игры и записи его для случая применения произвольных стратегий со стороны одного из игроков, решение данной матричной игры не изменяется от прибавления ко всем a_ij одной и той же положительной константы a, так что не будет ограничением рассматривать игры с положительной ценой V>0. В этом случае оптимальные стратегии p₁,p₂,…,p_n; q₁,q₂,…,q_m и цена игры v конечной игры двух партнеров с нулевой суммой с заданной матрицей выигрышей есть

где z_min, w_max, X_i, Y_j определяются как решения двойственных задач линейного программирования

z=X₁+X₂+…+X_n=min

с ограничениями a_1jX₁+a_2jX₂+…+a_njX_n1 (j=1,2,…,m),

X_i0 (i=1,2,…,n),

и

w=Y₁+Y₂+…+Y_m=max

с ограничениями a_i1Y₁+a_i2Y₂+…+a_imY_m1 (i=1,2,…,n),

Y_j0 (j=1,2,…,m).

Текст программы:

#include<bios.h>

#include<iostream.h>

#include<conio.h>

#include<string.h>

#include<stdlib.h>

#include<stdio.h>

int** array;

int str,stb,f[100],f1[100];

//funkcii minmax i maxmin

int func(int n)

{array[str][n]=array[0][n];

for(int i=0;i<str;i++)

{if(array[str][n]<array[i][n])

array[str][n]=array[i][n];}

return array[str][n];}

int func1(int m)

{array[m][stb]=array[m][0];

for(int i=0;i<stb;i++)

{if(array[m][stb]>array[m][i])

array[m][stb]=array[m][i];}

return array[m][stb];}

void main()

{clrscr();

int i,j;

//Vvod

cout<<"\nVvedite razmer matrici [Nstolb*Mstrok]:\n";

cin>>stb>>str;

array=new int*[str+2];

for (i=0;i<str+2;i++)

{array[i]=new int [stb+2];}

cout<<"\n\nViberite vid vvoda(1_Manual. Other_Random.):";

for (i=0;i<str;i++)for(j=0;j<stb;j++)

{array[i][j]=0;}

cin>>i;

if(i==1)

{for (i=0;i<str;i++)

for(j=0;j<stb;j++)

{printf("Vvedite element[%d][%d]: ",i+1,j+1);

scanf("%d", &array[i][j]);}

}

else {randomize();

cout <<"\n\t Sluchaino!\n";

for (i=0;i<str;i++)

for(j=0;j<stb;j++)

{array[i][j]=(rand()%8+1);}}

//vivod

cout<<"\n";

printf("\n\t\tMatrica:\n");

for (i=0;i<str;i++)

{for (j=0;j<stb;j++)

{printf(" %d",array[i][j]);}

printf(" \n");}

for(i=0;i<str;i++){f[i]=0;} //massivi 0

for(j=0;j<stb;j++){f1[j]=0;}

while(1)

{int g=0; //flag

for(i=0;i<str;i++) //cikl po vsem strokam

{if(f[i]!=1) //cikl po strokam s prediduchei

for(int k=0;k<str;k++)

if(k!=i)

{if(f[k]!=1){

f[k]=1;g++;

for(int zz=0;zz<stb;zz++)if(f1[zz]!=1)

if(array[i][zz]<array[k][zz]){f[k]=0;g--;break;}}

}}

for(i=0;i<stb;i++)

{if(f1[i]!=1)

for(int k=0;k<stb;k++)

if(k!=i)

{if(f1[k]!=1)

{f1[k]=1;g++;

for(int zz=0;zz<str;zz++)if(f[zz]!=1)

if(array[zz][i]>array[zz][k]){f1[k]=0;g--;break;}}

}}

if(g==0){break;}

}

cout<<"Posle mazhorirovanija:\t\t\n";

for (i=0;i<str;i++)

if(f[i]!=1)

{for (j=0;j<stb;j++)

if(f1[j]!=1)

{printf(" %d",array[i][j]);}

printf(" \n");}

int maxmin=0,minmax=0;

cout<<"\nai ";

for (i=0;i<str;i++)

if(f[i]!=1)

{func1(i);cout<<"\n"<<func1(i);}

int n=func1(0);

for (i=1;i<str;i++)

if(f[i]!=1)

{if(n<func1(i))

{n=func1(i);maxmin=i;}}

cout<<"\n\nbi ";

for (j=0;j<stb;j++)

if(f1[j]!=1)

{func(j);cout<<func(j)<<" ";}

n=func(0);

for (j=1;j<stb;j++)

if(f1[j]!=1)

{if(n>func(j))

{n=func(j);minmax=j;}}

cout<<"\n"<<"Verhnaja cena igri: minmax= "<<array[str][minmax];

cout<<"\nNiznaja cena igri: maxmin= "<<array[maxmin][stb];

if(array[maxmin][stb]==array[str][minmax])

{cout<<"\n"<<"Sedlo!!!";}

int min=array[0][0];

for(i=0;i<str;i++)

for(j=0;j<stb;j++)

if(array[i][j]<min){min=array[i][j];}

if(min<0)

{for(i=0;i<str;i++)

for(j=0;j<stb;j++)

array[i][j]+=((-1)*min+1);}

else {min=0;}

int cs=0; //skol'ko strok ostalos'

for(i=0;i<str;i++)

if(f[i]!=1)cs++;

int cs1=0; //skol'ko stb ostalos'

for(i=0;i<stb;i++)

if(f1[i]!=1)cs1++;

double ox=0,oy=0,oc=0;

if(cs==2)

{int y1,y2;

for(i=0;i<str;i++)

if(f[i]!=1){y1=i;break;}

for(i=i+1;i<str;i++)

if(f[i]!=1){y2=i;break;}

for(i=0;i<stb;i++)

if(f1[i]!=1)

for(int k=i+1;k<stb;k++)

if(f1[k]!=1)

{double opred=array[y1][i]*array[y2][k]-array[y2][i]*array[y1][k];

if(opred==0) continue;

double lx=(array[y2][k]-array[y2][i])/opred;

double ly=(array[y1][i]-array[y1][k])/opred;

if((lx+ly)>oc)

{ox=lx;oy=ly;oc=lx+ly;}}

if(min==0)

{cout<<"\nPa1="<<ox/oc<<" \nPa2="<<oy/oc<<"\nCena igri V="<<1/oc;}

else cout<<"\nPa1="<<ox/oc<<" \nPa2="<<oy/oc<<"\nCena igri V="<<1/oc+min-1;}

cout<<"\n";ox=0,oy=0,oc=0;

if(cs1==2)

{int y1,y2;

for(i=0;i<stb;i++)

if(f1[i]!=1){y1=i;break;}

for(i=i+1;i<stb;i++)

if(f1[i]!=1){y2=i;break;}

for(i=0;i<str;i++)

if(f[i]!=1)

for(int k=i+1;k<str;k++)

if(f[k]!=1)

{double opred=array[i][y1]*array[k][y2]-array[k][y1]*array[i][y2];

if(opred==0) continue;

double lx=(array[k][y2]-array[i][y2])/opred;

double ly=(array[i][y1]-array[k][y1])/opred;

if((lx+ly)>oc)

{ox=lx;oy=ly;oc=lx+ly;}}

if(min==0)

{cout<<"\nPb1="<<ox/oc<<" Pb2="<<oy/oc<<"\nCena igri W="<<1/oc;}

else cout<<"\nPb1="<<ox/oc<<" Pb2="<<oy/oc<<"\nCena igri V="<<1/oc+min-1;}

for(i=0;i<str+1; i++)

{delete[] array[i];}

delete[] array;

while(1)

{switch(bioskey(0))

{case 0x11b :goto swq;}}

swq:}

Запишем матрицу выигрышей, найдем минимальный элемент (a=-5), прибавим его ко всем элементам матрицы.

Матрица симметрична, m=n=3.

Выигрыш первого игрока будет составлять:

7P₁+2P₂+9P₃V

2P₁+9P₂+0P₃V

9P₁+0P₂+11P₃V

Поскольку V>0, то можно поделить на V с сохранением знаков неравенств. Обозначим P_i/V=X_i, тогда нас интересует min X₁+X₂+X₃ при X_i0 (i=1,2,3) и

7X₁+2X₂+9X₃1

2X₁+9X₂1

9X₁+11X₃1

Приводим задачу к каноническому виду.

7X₁+2X₂+9X₃-Y₁1

2X₁+9X_2­-Y₂1