Методы приближённого решения матричных игр (стр. 4 из 4)
Итерация 1. Так как e1 не равно 0, то процесс продолжается дальше. Теперь за начальные условия примем найденные значения векторов x1, c1. С их помощью вычисляем
, которые с большей точностью будут близки к истинным оптимальным стратегиям игрока 1.1. Итак, пусть x1=(1/2, 1/2, 0), c1=(2, 3/2, 3/2).
Найдём множество индексов
, на которых игрок 1 может получить наименьший выигрыш: 
, значит, J1={2,3}. Для этих индексов выигрыш равен 3/2. Это есть значение нижней оценки цены игры, т. е. 
. Заметим, что 
.2. Далее найдём компоненты векторов
. Для этого рассмотрим подыгру 
. В силу симметричности матрицы ее решением будет вектор (1/2, 1/2), т. е. 
1/2a1+1/2a2+0a3==(4/2, 3/2, 3/2).
3. Вычислим коэффициент e2. Для этого решим подыгру (2´3):
. Стратегии игроков совпадают, поэтому e2=0. В этом случае цена игры совпадает со своим нижним значением, т. е. 
. Возвращаемся к предыдущему шагу.Итак, оптимальной стратегией игрока 1 является x*=x1=(1/2,1/2, 0) и
.Задача решена.На первый взгляд алгоритм практически трудно реализовать, так как не известно, какого размера будет получена матрица для подыгры ГN. Но на самом деле с вероятностью 1 на каждом шаге придётся решать подыгру размера не больше чем m´2.[9]
Инженерами-программистами алгоритм был реализован на языке программирования Фортран-IV. Вычислительные эксперименты, проведённые на ЭЦВМ ЕС-1030, показали, что для игр размерности от 25´25 до 100´100, элементы, матрицы выигрышей которых были заполнены случайными числами, алгоритм позволяет найти искомое приближение за 100-1000 итераций, причём их число слабо зависит от размера матрицы. Для решения одной задачи машина затрачивает не дольше 8 минут. Ими же были разработаны различные модификации алгоритма. [9]
Приложение
В приложении приведена реализация итеративного метода Брауна-Робинсона решения матричных игр на языке программирования TurboPascal 7.0.
Пользователь вводит матрицу выигрышей размера m×n, где m≥3, n≥3.
Далее машина запрашивает информацию о том, кто из игроков начинает игру, какую стратегию он выбирает и количество итераций.
На дисплее выводится таблица разыгрываний игры за определённое число итераций.
program br;
uses crt;
const matr1:array[1..3,1..3] of byte=((0,4,2),
(3,1,0),
(1,2,3)); {Начальнаяматрица}
var
matr:array [1..10,1..10] ofinteger; {Матрица, введенная пользователем}
win_one:array[0..150,1..10] of word; {Массивдлявыигрышейигр.1}
win_two:array[0..150,1..10] of word; {Массивдлявыигрышейигр.2}
max,min:integer;
a,i,j,m,n,pl,st,st1,st2,kl:byte;
nol,otr:boolean;
functionigr_one:byte; {Функция определения следующего}
var a1,a2,max:integer; {ходадляигрока 1}
begin
max:=win_one[a,1];
igr_one:=1;
if pl=1 then a2:=m else a2:=n;
for a1:=1 to a2 do if win_one[a,a1]>max then begin
max:=win_one[a,a1];
igr_one:=a1;
end;
end;
function igr_two:byte; {Функция определения следующего}
var a1,a2,min:integer; {ходадляигрока 2}
begin
min:=win_two[a,1];
igr_two:=1;
if pl=1 then a2:=n else a2:=m;
for a1:=1 to a2 do if win_two[a,a1]<min then begin
min:=win_two[a,a1];
igr_two:=a1;
end;
end;
begin
clrscr;
writeln ('Итеративный метод Брауна-Робинсона.');
writeln('Матрица пользователя? (y/n)');
if (readkey='y')or(readkey='Y') then begin {Матрица из памяти или вводит пользователь}
write ('Введите размеры матрицы:');
readln(n,m); {Ввод количества строк и столбцов}
writeln('Введите ',n,' строки по ',m,' элементов:');
nol:=true;
otr:=false;
min:=0;
for j:=1 to n do for i:=1 to m do begin {Вводэлементовматрицы}
read(matr[i,j]);
ifmatr[i,j]<>0 thennol:=false; {Установка флага, что не все элементы равны 0}
ifmatr[i,j]<0 thenotr:=true; {Установка флага наличия отрицательных элементов}
ifmatr[i,j]<minthenmin:=matr[i,j];{Определение минимального элемента}
end
end else begin {Иначе берем матрицу из константы}
n:=3;m:=3;
for i:=1 to m do for j:=1 to n do matr[i,j]:=matr1[i,j];
end;
clrscr;
writeln ('Итеративный метод Брауна-Робинсона.');
if nol then writeln('Все элементы матрицы равны 0!') else begin {если установлен флаг нуля, то алгоритм не работает}
if otr then for j:=1 to n do for i:=1 to m do matr[i,j]:=matr[i,j]-min;{еслиестьотрицательныеэлементы,}
writeln('Начальная матрица:'); {Вывод окончательной матрицы}
for j:=1 to n do begin
for i:=1 to m do write(matr[i,j]:4);
writeln;
end;
write('Какой игрок начнет игру? '); {Вод стартовых значений}
readln(pl);
write('Какую стратегию выберет ',pl,' игрок? ');
readln(st);
write('Количество итераций? ');
readln(kl);
a:=1; {заглавие таблицы}
writeln(' № стр. выигрыш 1-го игр. стр. выигрыш 2-го игр. V W Y');
repeat
write(a:2,st:6,' '); {формирование таблицы: номер итерации, стратегия 1игр.}
if pl=2 then begin
for i:=1 to n do begin
win_one[a,i]:=matr[st,i]+win_one[a-1,i];{формированиематрицывыигрышей 1 игр.}
write(win_one[a,i]:4); {выводнаэкран}
end;
st1:=igr_one; {определение ответной стратегии 2 игр.}
gotoxy(32,wherey);
write(st1:10,' '); {вывод на экран}
for i:=1 to m do begin
win_two[a,i]:=matr[i,st1]+win_two[a-1,i]; {формированиематрицывыигрышей 2 игр.}
write(win_two[a,i]:4); {выводнаэкран}
end;
gotoxy(64,wherey);
write(win_one[a,st1]:4); {вывод наибольшего суммарного выигрыша 1 игр.}
st:=igr_two; {определение ответной стратегии 1 игр.}
write(win_two[a,st]:4); {вывод наибольшего суммарного выигрыша 2 игр.}
write((win_one[a,st1]+win_two[a,st])/(a*2):6:2);{приближенноезначениеценыигры}
end
else
begin
for i:=1 to m do begin
win_one[a,i]:=matr[i,st]+win_one[a-1,i];{формированиематрицывыигрышей 1 игр.}
write(win_one[a,i]:4);
end;
st1:=igr_one; {определение ответной стратегии 2 игр.}
gotoxy(32,wherey);
write(st1:10,' ');
for i:=1 to n do begin
win_two[a,i]:=matr[st1,i]+win_two[a-1,i];{формированиематрицывыигрышей 2 игр.}
write(win_two[a,i]:4);
end;
gotoxy(64,wherey);
write(win_one[a,st1]:4); {вывод наибольшего суммарного выигрыша 1 игр.}
st:=igr_two; {определение ответной стратегии 1 игр.}
write(win_two[a,st]:4); {вывод наибольшего суммарного выигрыша 2 игр.}
write((win_one[a,st1]+win_two[a,st])/(a*2):6:2);{приближенноезначениеценыигры}
end;
a:=a+1; {увеличение счетчика итераций}
writeln;
until a=kl+1;
end;
readln;
readln;
end.
Списоклитературы
1. Беленький В.З. Итеративные методы в теории игр и программировании. М.: «Наука», 1977
2. Блекуэлл Д.А. Теория игр и статистических решений. М., Изд. иностранной литературы, 1958
3. Вентцель Е.С. Элементы теории игр. М., Физматгиз, 1961
4. Вилкас Э.И. Оптимальность в играх и решениях. М.: «Наука», 1986
5. Воробьёв И.Н. Математическая теория игр. М.: «Знание», 1976
6. Давыдов Э.Г. Методы и модели теории антагонистических игр. М.: «Высшая школа», 1990
7. Дрешер М. Стратегические игры. Теория и приложения. М., 1964
8. Исследование операций в экономике / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман. М.: «Банки и биржи», Юнити, 1997
9. Итеративный алгоритм решения матричных игр// Доклады Академии наук СССР, том 238, №3, 1978
10. Карлин С. Математические методы в теории игр, программировании и экономике. М.: «Мир», 1964
11. Крапивин В.Ф. Теоретико-игровые методы синтеза сложных систем в конфликтных ситуациях. М.: «Советское радио», 1972
12. Крушевский А.В. Теория игр: [Учебное пособие для вузов]. Киев: «Вища школа», 1977
13. Льюис Р., Райфа Х. Игры и решения. М.,1961
14. Морозов В.В., Старёв А.Г., Фёдоров В.В. Исследование операций в задачах и упражнениях. М.: «Высшая школа», 1996
15. Матричные игры. [Сборник переводов]. Под ред. Воробьёва И.Н. М., Физматгиз, 1961
16. Оуэн Г. Теория игр. [Учебное пособие]. М.: «Мир», 1973
17. Петросян Л.А., Зенкевич Н.А., Семен Е.А. Теория игр. М., 1989
18. Школьная энциклопедия математика. Ред. С. М. Никольский, М.: 1996, с. 380