Компьютерное моделирование графического решения матричных игр
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
¶естве чистых стратегий). В этом случае игроки оперируют уже с математическими ожиданиями выигрышей.
Основная теорема теории Матричные игры (теорема Неймана о минимаксе) утверждает, что в любой Матричные игры существуют оптимальные смешанные стратегии х*, у*, на которых достигаемые минимаксы равны (общее их значение есть значение игры). Например, игра с матрицей имеет седловую точку при i0 = 2, j0 = 1, а значение игры равно 2; игра с матрицей не имеет седловой точки. Для неё оптимальные смешанные стратегии суть х* = (3/4, 1/4), y* = (1/2, 1/2); значение игры равно 1/2.
Для фактического нахождения оптимальных смешанных стратегий чаще всего используют возможность сведения Матричные игры к задачам линейного программирования Можно использовать так называемый итеративный метод Брауна - Робинсон, состоящий в последовательном фиктивном разыгрывании данной игры с выбором игроками в каждой данной партии своих чистых стратегий, наилучших против накопленных к этому моменту стратегий оппонента. Игры, в которых один из игроков имеет только две стратегии, просто решить графически.
Матричные игры могут служить математическими моделями многих простейших конфликтных ситуаций из области экономики, математической статистики, военного дела, биологии. Нередко в качестве одного из игроков рассматривают природу, под которой понимается вся совокупность внешних обстоятельств, неизвестных принимающему решения лицу (другому игроку).
4.2 Графоаналитический метод решения матричных игр 2n и m 2
Для некоторых классов матричных игр практический интерес представляет графоаналитический метод. Этот метод состоит из двух частей. Вначале в матричной игре графически выявляются качественные особенности решения, затем полная характеристика решения находится аналитически. В основе метода лежит утверждение, которое остаётся верным и в смешанном расширении игры. Седловая точка в матричной игре существует тогда и только тогда, когда выполняется равенство
max min f (x,y) min max f (x,y)= *
причём седловую точку составляют стратегии, доставляющие внешние экстремумы в последнем равенстве.
4.2.1 Пример решения игры вида 2хN:
Рассмотрим следующую игру 2х4.
В А223-14326Таблица 1
Эта игра не имеет седловой точки. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям В, представлены в таблице 2.
Чистые стратегии игрока ВОжидаемый выигрыш игрока А1-2х1+42-х1+33х1+24-7х1+6Таблица 2
На рисунке 1 изображены четыре прямые, являющиеся графиками этих функций от х1. Максимин достигается при х1*=1/2. В этой точке пересекаются любые две из прямых 2,3 и 4. Следовательно, оптимальной стратегией игрока А является (х1*=1/2, х2*=1/2) и значение игры находится подстановкой х1 в уравнение любой из прямых, проходящих через максиминную точку. Это дает
Рис. 1
4.2.2 Пример решения игры вида Mх2:
Рассмотрим следующую игру вида 4х2.
ВА242332-26Таблица 3
Эта игра не имеет седловой точки. Пусть у1 и у2=(1-у1) - смешанные стратегии игрока В. Тогда
Чистые стратегии игрока АОжидаемый выигрыш игрока В1-2у1+42-у1+33У1+24-8у1+6Таблица 4
Эти четыре прямые изображены на рисунке 2. В данном случае минимаксная точка определяется как самая нижняя точка на огибающей сверху. Значение у1* получается как точка пересечения прямых 1 и 3. Это дает у1*=2/3 и *=8/3.
Рис. 2
. ЛИСТИНГ ПРОГРАММЫ
uses crt,Graph;
var, Gm : Integer;:array [1..10,1..10] of integer;,y,k1,k2,z0,z1:array [1..10] of integer;,q0,a,yy,wx,wy:integer;,j,n,m,c,minZ0,minZ1,zj0,zj1:integer;,yyy,aa:real;:string[15];[1]:=9;st[2]:=8;st[3]:=7;st[4]:=6;[5]:=5;st[6]:=4;st[7]:=3;st[8]:=2;[9]:=1;st[10]:= ;st[11]:=1;st[12]:=2;[13]:=3;st[14]:=4;;(‚›Ѓ€ђ€… ђЂ‡Њ…ђЌЋњ ‡Ђ„Ђ-€: 1 - 2xN, 2 - Mx2);(1 -> 2 x N);(2 -> M x 2);(c);;c=1 then(‚‚€„€… N :);read(n); clrscr;(‚‚€„€… Џ‹Ђ…†„ћ ЊЂђ€- :);i:=1 to 2 doj:=1 to n do(a[,i,,,j,]=); readln(Mat[i,j]);;;j:=1 to n do[j]:=mat[1,j]-mat[2,j];[j]:=mat[2,j];;( €ѓђЋЉ B | €ѓђЋЉ A );(-----------------------------------);j:=1 to n do( ,j, | ,k1[j], X1 +(,k2[j],) );;j:=1 to n do[j]:=k2[j];[j]:=k1[j]+k2[j];;:=z0[1];zj0:=1;j:=2 to n dominZ0>z0[j] then begin minZ0:=z0[j] ; zj0:=j;end;;:=z1[1];zj1:=1;j:=2 to n dominZ1>z1[j] then begin minZ1:=z1[j] ; zj1:=j;end;;(k2[zj0]=7 then begin setcolor(11); OutTextXY(10,160, line - 7); end;(3); OutTextXY(10,30, Exit-[Esc] );(255,50, 2 x N); readkey;;;c=2 then;(‚‚…„€… M :);read(n); clrscr;(‚‚€„€… Џ‹Ђ…†Ќћ ЊЂђ