Реферат: Метод Гурвица
.
2.2.Экономико – математическая модель
Основная теорема теории игр, состоит в следующем: любая конечная игра имеет, по крайне мере, одно решение, возможно в области смешанных стратегий. Применение оптимальной стратегии позволяет получить выигрыш равный цене игры: , – цена игры.
Применение игроком А оптимальной стратегии должно обеспечивать ему выигрыш при любых действиях игрока В, не меньше цены . Выполняется соотношение:
, - вероятность использования стратегии игрока А.
Аналогично, для игрока В оптимальная стратегия должна обеспечить при любых стратегиях игрока А проигрыш, не более :
, - вероятность использования стратегии игрока В.
Задача имеет решение игры, если её матрицы не содержит седловой точки ().
Расчет выигрышей производится по целевой функции:
Система ограничения:
2.3.Описания метода Гурвица
2.3.1. Выбираем по строкам наименьший выигрыш и заполняем колонку а.
2.3.2. Выбираем по строкам наибольший выигрыши и заполняем колонку
2.3.3. Производим расчёт выигрыша по формуле: ; результаты заносим в таблицу и получаем матрицу .
2.3.4. По методу максимина определяется наибольший из всех расчётных выигрышей; по наибольшему значению определяется стратегия данного игрока.
2.3.5. Для разрешения конфликтной ситуации составляется таблица Гурвица относительно игрока В. В таблице меняем платёжную матрицу.
2.3.6. Далее также применяем принцип Гурвица и метод максимина относительно игрока В.
2.3.7. Игрок, разрешающий конфликтную ситуацию определяется по наибольшему расчётному выигрышу из соответствующих оптимальных стратегий игроков.
2.4.Алгоритм задачи
2.4.1. Алгоритм основной программы
2.4.2. Алгоритм процедуры W_rezultat
2.5. Описание алгоритма
2.5.1. Описание алгоритма основной программы
Блок 1 - Начало программы
Блок 2 - Процедура ввод статистических коэффициентов оптимизации
Блок 3 - Основная процедура расчета по методу Гурвица
Блок 4 - Оператор вывода расчетных таблиц
Блок 5 - Процедура вывода расчетной таблицы и платежной матрицы игрока А
Блок 6 - Процедура вывода расчетной таблицы и платежной матрицы игрока В
Блок 7 - Конец программы
2.5.2. Описания основной процедуры W_rezultat расчета по методу Гурвица
Блок 1 - Вход в процедуру
Блок 2 - Начало цикла i от 1 до m
Блок 3 - Начало цикла j от 1 до n
Блок 4 - Преобразования символа строки из ячейки таблицы C_S в целое число матрицы C_a
Блок 5 - Конец цикла по j
Блок 6 - Конец цикла по I
Блок 7 - Начало цикла i от 1 до n
Блок 8 - Начало цикла j от 1 до m
Блок 9 - Преобразования символа строки из ячейки таблицы C_S в целое число матрицы С_b
Блок 10 - Конец цикла по j
Блок 11 - Конец цикла по I
Блок 12 - Начало цикла i от 1 до m
Блок 13 - Массиву a_m (наименьшие выигрыши)присваивается первый элемент i строки матрицы С_a (игрока А)
Блок 14 - Массиву a_b (наибольшие выигрыши)присваивается первый элемент i строки матрицы С_a (игрока А)
Блок 15 - Начало цикла j от 2 до n
Блок 16 - Проверка условия на нахождения минимального элемента
Блок 17 - Нахождения минимального элемента
Блок 18 - Проверка условия на нахождения максимально элемента
Блок 19 - Нахождения максимально элемента
Блок 20 - Конец цикла по j
Блок 21 - Начало цикла j от 1 до k
Блок 22 - Расчет условно расчетных выигрышей (игрока А)
Блок 23 - Конец цикла по j
Блок 24 - Конец цикла по i
Блок 25 - Максимальному выигрышу max_a присваивается первый элемент первой строки матрицы условно расчетных выигрышей (игрока А)
Блок 26 - Оптимальной стратегии H_a присваивается первая стратегия (игрока А)
Блок 27 - Начало цикла i от 1 до m
Блок 28 - Начало цикла j от 1 до k
Блок 29 - Проверка условия на нахождения максимально выигрыша
Блок 30 - Нахождения максимально выигрыша
Блок 31 - Нахождения оптимальной стратегии
Блок 32 - Конец цикла по j (игрока А)
Блок 33 - Конец цикла по I (игрока А)
Блок 34 - Начало цикла i от 1 до n
Блок 35 - Массиву b_m (наименьшие выигрыши)присваивается первый элемент i строки матрицы С_b (игрока В)
Блок 36 - Массиву b_b (наибольшие выигрыши)присваивается первый элемент i строки матрицы С_b (игрока В)
Блок 38 - Проверка условия на нахождения минимального элемента
Блок 39 - Нахождения минимального элемента
Блок 40 - Проверка условия на нахождения максимально элемента
Блок 41 - Нахождения максимально элемента
Блок 44 - Расчет условно расчетных выигрышей (игрока В)
Блок 47 - Максимальному выигрышу max_b присваивается первый элемент первой строки матрицы условно расчетных выигрышей (игрока B)
Блок 48 - Оптимальной стратегии H_b присваивается первая стратегия (игрока B)
Блок 51 - Проверка условия на нахождения максимально выигрыша
Блок 52 - Нахождения максимально выигрыша
Блок 53 - Нахождения оптимальной стратегии
Блок 56 - Проверка условия на наличие седловых точек
Блок 58 - Проверка условия на нахождения игрока, разрешающего конфликтную ситуацию
Блок 59 - Вывод игрока А разрешивший конфликтную ситуацию
Блок 60 - Вывод игрока В разрешивший конфликтную ситуацию
Блок 61 - Вывод оптимальной стратегии и набольшего выигрыша игрока А
Блок 62 - Вывод оптимальной стратегии и набольшего выигрыша игрока В
Блок 63 - Выход из процедуры
2.6.Характеристика программы
Программа написана на языке Object Pascal. Она занимает 44,8 Кб оперативной памяти, место на жестком диске 498 Кб. Программа была реализована на компьютере Intel Celeron 366 с помощью OC Windows’ 98, в среде программирования Delphi версия 5.0.
Выходными данными является платёжная матрица, состоящая из вещественных чисел и коэффициенты оптимизма – целые числа. Эти данные будут вводиться пользователем с клавиатуры и идентифицироваться в окне на экране монитора.
Выходными данными будет расчетные таблицы для игроков А и В, максимальный выигрыш, оптимальная стратегия каждого из игроков, а также будет выведен игрок, разрешающий конфликтную ситуацию.
2.7.Описание процесса отладки
Под отладкой понимается процесс поиска и устранения ошибок в программе. Ошибки, которые могут быть в программе, принято делить на три группы: синтаксические ошибки; ошибки времени выполнения; алгоритмические ошибки.
В среде Delphi мощный встроенный отладчик, значительно упрощающий отладку программ.
Основными инструментами отладки является точки контрольного останова и окно наблюдения за переменными. Если программа запущена из среды Delphi, ее работу можно прервать в любой момент или установив точку контрольного останова в той части программы, которая выполняется в данный момент или будет выполнена.
После контрольного останова в окне наблюдения отображаются текущие значения наблюдаемых объектов. Кроме того, можно увидеть текущее значение любой переменной, если в окне редактора укажете на нее мышью.
Для написания моей программы использовался метод тестирования. Метод тестирования основан на обдумываний и заключается в использования тестов. Существую два типа тестов: тесты для тестирования целью которых является обнаруживания заранее не определенной ошибки и тесты для отладки, цель которых обеспечить информации полезной для выявления место нахождения подозреваемой ошибки.
2.8.Результаты решения задачи
Разрешить конфликтную ситуацию двух игроков А и В заданную в неопределенных условиях с статистические коэффициентами оптимизации =0,1; =0,2; =0,3.
Исходные данные и решения задачи сводится в таблицу 2.8.1.
Таблица 2.8.1
В1 | В2 | В3 |
Наименьший выигрыш |
Наибольший выигрыш |
Коэффициенты оптимизма | |||
0,1 | 0,2 | 0,3 | ||||||
А1 | 1 | 1 | 3 | 1 | 3 | 2,8 | 2,6 | 2,4 |
А2 | 5 | 6 | 8 | 5 | 8 | 7,7 | 7,4 | 7,1 |
А3 | 4 | 3 | 5 | 3 | 5 | 4,8 | 4,6 | 4,4 |
Найти игрока, разрешающего конфликтную ситуацию.
Найдём условно расчётные выигрыши игрока А по формуле:
V11=0,1*1+(1 – 0,1)*3=2,8
V12=0,2*1+(1 – 0,2)*3=2,6
V13=0,3*1+(1 – 0,3)*3=2,4
V21=0,1*5+(1 – 0,1)*8=7,7
V22=0,2*5+(1 – 0,2)*8=7,4
V23=0,3*5+(1 – 0,3)*8=7,1
V31=0,1*3+(1 – 0,1)*5=4,8
V32=0,2*3+(1 – 0,2)*5=4,6
V33=0,3*3+(1 – 0,3)*5=4,4
Среди найденных условных расчётных выигрышей найдём максимальный. Он равен 7.7, значит оптимальная стратегия игрока А будет А2.
Далее найдём оптимальная стратегия игрока В, для этого транспонируем матрицу. Результаты заносим в таблицу 2.8.2.
Таблица 2.8.2
А1 | А2 | А3 |
Наименьший выигрыш |
Наибольший выигрыш |
Коэффициенты оптимизма | |||
0,1 | 0,2 | 0,3 | ||||||
В1 | 1 | 5 | 4 | 1 | 5 | 4,6 | 4,2 | 3,8 |
В2 | 1 | 6 | 3 | 1 | 6 | 5,5 | 5 | 4,5 |
В3 | 3 | 8 | 5 | 3 | 8 | 7,5 | 7 | 6,5 |
Найдём условно расчётные выигрыши игрока В
V11=0,1*1+(1 – 0,1)*5=4,6
V12=0,2*1+(1 – 0,2)*5=4,2
V13=0,3*1+(1 – 0,3)*5=3,8
V21=0,1*1+(1 – 0,1)*6=5,5
V22=0,2*1+(1 – 0,2)*6=5
V23=0,3*1+(1 – 0,3)*6=4,5
V31=0,1*3+(1 – 0,1)*8=7,5
V32=0,2*3+(1 – 0,2)*8=7
V33=0,3*3+(1 – 0,3)*8=6,5
Среди найденных условных расчётных выигрышей найдём максимальный. Он равен 7.5, значит оптимальная стратегия игрока В будет В3.
Из 2-х оптимальных стратегий, находим наибольший выигрыш, а именно 7,7>7,5; следовательно игрок А разрешит конфликтную ситуацию с максимальным выигрышем равным 7,7, стратегия которого равна 2.
2.9.Оценки результатов решения задачи
Результат решения задачи полностью соответствует заданию курсового проекта. В сравнении результатов решения задачи ручным с результатами автоматизированным методом, получил одинаковые результаты. Что означает что программа работает верно. Преимущество автоматизированного метода над ручным состоит в том, что автоматизированное время выполнения программы меньше, чем ручным.
ЗАКЛЮЧЕНИЕДанная курсовая работа включает в себя два предмета: «Программирование» и «Компьютерное модулирование»
В курсовой работе были рассмотрены следующие вопросы:
· Рассмотрена характеристика «Теории игр» и следующие методы ее решения: метод Гурвица, метод Сэвиджа, метод максимина.
· Рассмотрен и дан алгоритм решения теории игры в условии неопределенности методом Гурвица.
· Дана краткая характеристика ПК, включая анализ средств программирования, описания ОС MS-DOS и MS Windows’
· Рассмотрен выбор языка программирования.
· Написана программа для решения данной задачи.
СПИСОК ЛИТЕРАТУРЫ1. Г. С. Малик «Основы экономики и математические методы в планировании».
2. Кузнецов «Математическое программирование».
3. В. В. Фаронов «Delphi 5. Учебный курс».
4. Ю. П. Зайченко «Исследование операций в задачах, алгоритмах, программах».
Приложение 1 Текст программыMedot_Gurwiwiza.dpr
program Medot_Gurwiza;
{Курсовой проект по предмету "Компьютерное модулирование" по теме "Теория игр"
Принцип Гурвица Выполнил студент гр. П-00-1 Юшков Андрей 10.06.02}
uses
Forms,
osnowa in 'osnowa.pas' {form1},
Unit2 in 'Unit2.pas' {Form2};
{$R *.RES}
begin
Application.Initialize;
Application.CreateForm(Tform1, form1);
Application.CreateForm(TForm2, Form2);
Application.Run;
end.
unit osnowa;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
Grids, StdCtrls, ToolWin, ComCtrls, Buttons, ActnList, StdActns, Menus,
Mask, ExtCtrls, jpeg;
type
Tform1 = class(TForm)
tabliza: TStringGrid;
Panel1: TPanel;
Button1: TButton;
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
C_S: TStringGrid;
Panel2: TPanel;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
Label8: TLabel;
Label9: TLabel;
Label10: TLabel;
Label11: TLabel;
Label12: TLabel;
Label13: TLabel;
Label14: TLabel;
Panel3: TPanel;
Panel4: TPanel;
Label17: TLabel;
Label18: TLabel;
Panel5: TPanel;
Label19: TLabel;
Label20: TLabel;
Label21: TLabel;
Label22: TLabel;
Label23: TLabel;
RadioButton7: TRadioButton;
RadioButton8: TRadioButton;
Button3: TButton;
Panel6: TPanel;
Label1: TLabel;
BitBtn1: TBitBtn;
Label15: TLabel;
procedure WWod_koef(Sender: TObject);
procedure W_Rezultat(Sender: TObject);
procedure W_tabliza_A(Sender: TObject);
procedure W_tabliza_B(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
form1: Tform1;
C_B,C_A:array [1..10,1..10] of integer; { платёжная матрица игрока А,В}
a_b,a_m,b_b,b_m:array[1..10] of integer; {наибольший наименьший выигрыш иг. А,В}
al:array[1..10] of real; {массив альфа}
V_A,V_B:array[1..10,1..10]of real; {Расчётные выигрыши иг. А,В }
max_a:real; { Наибольший выигрыш игрока А}
max_b:real; { Наибольший выигрыш игрока В}
H_a:integer; { Оптимальная стратегия игрока А}
h_b:integer; { Оптимальная стратегия игрока В}
m:Integer; { Количество стратегий игрока А}
n:Integer; { Количество стратегий игрока В}
k:Integer; { Количество статистических коэффициентов}
I,J:Integer;
implementation
uses Unit2;
{$R *.DFM}
{ вывод коэф., матрицы С_А}
procedure WW_A;
begin
form1.c_s.Colcount:=n+1;
form1.c_s.Rowcount:=m+1;
form1.tabliza.Rowcount:=m+1;
for i :=1 to m do
begin
form1.tabliza.Cells[0,i]:='A'+intToStr(i);
form1.C_S.Cells[0,i]:='A'+intToStr(i);
for j :=1 to n do
begin
form1.C_S.Cells[j,0]:='B'+intToStr(j);
form1.C_S.Cells[j,i]:=intToStr(C_A[i,j]);
end;
end;
with form1 do
begin
label23.caption:='A';
tabliza.cells[1,0]:='a_малая';tabliza.cells[2,0]:='a_большая';
end;
end;
{ Вывод наибольший, наименьший, расчётный выигрыш матрицы V_А}
procedure WW_A1;
begin
WW_A;
With form1.tabliza Do
begin
for j:=1 to n do
begin
cells[1,j]:=intToStr(a_m[j]);
cells[2,j]:=intToStr(a_b[j]);
end;
for i:=1 to m do
for j:=1 to k do
cells[j+2,i]:=floatToStr(V_a[i,j]);
end;
end;
{событие на нажатие кнопки 'Ввод коэф..'}
procedure TForm1.WWod_koef(Sender: TObject);
begin
try
m:=strToint(edit1.text);
n:=strToint(edit2.text);
k:=strToint(edit3.text);
except
showMessage('Ошибочная запись числа ');
end;
try
Form2 := TForm2.Create(self);
tabliza.Colcount:=3+k;
Form2.ShowModal;
finally
Form2.Close;
WW_a;
end;
end;
{событие на нажатие кнопки 'вывод результата'}
procedure Tform1.W_Rezultat(Sender: TObject);
begin
Panel6.Visible:=false;
panel3.Visible:=true;
{Вводим из таблицы C_A в матрицу игрока А - C_A} { C_S[столбец,строка] }
for i :=1 to m do {по столбцам m таблицы C_S}
for j :=1 to n do {по строкам n таблицы C_S}
C_a[i,j]:=StrToInt(C_S.Cells[j,i]);
{Создаём матрицу C_B путём транспонирования матрицы игрока А}
for i :=1 to n do
for j :=1 to m do
C_b[i,j] :=StrToInt(C_S.Cells[i,j]);
{расчет наименьших и наибольших выигрышей игрока A}
for i:=1 to m do
begin
a_m[i]:=C_a[i,1]; {массив наименьшии выигрыш}
a_b[i]:=C_a[i,1]; {массив наибольшии выигрыш}
for j :=2 to n do
begin
if C_a[i,j]<a_m[i] then a_m[i]:=C_a[i,j];
if C_a[i,j]>a_b[i] then a_b[i]:=C_a[i,j];
end;
{вычисления расчетных выигрышей игрока A}
for j :=1 to k do
V_a[i,j]:=al[j]*a_m[i]+(1-al[j])*a_b[i];
end;
{нахождения оптимальной стратегии и максимального выигрыша игрока A}
max_a:=V_a[1,1];
H_A:=1;
for i :=1 to m do
for j :=1 to k do
if V_a[i,j]>max_A then
begin
max_a:=V_a[i,j]; { максимальный выигрыш игрока А}
H_a:=i { оптимальная стратегия игрока А}
end;
{расчет наименьших и наибольших выигрышей игрока В}
for i:=1 to n do
begin
b_m[i]:=C_b[i,1]; {массив наименьшии выигрыш}
b_b[i]:=C_b[i,1]; {массив наибольшии выигрыш}
for j:=2 to m do
begin
if C_b[i,j]<b_m[i] then b_m[i]:=C_b[i,j];
if C_b[i,j]>b_b[i] then b_b[i]:=C_b[i,j];
end;
{вычисления расчетных выигрышей игрока В}
for j:=1 to k do
V_b[i,j]:=al[j]*b_m[i]+(1-al[j])*b_b[i];
end;
{нахождения оптимальной стратегии и максимального выигрыша игрока В}
max_b:=V_b[1,1];
H_b:=1;
for i:=1 to n do
for j:=1 to k do
if V_b[i,j]>max_b then
begin
max_b:=V_b[i,j]; { максимальный выигрыш игрока B}
H_b:=i { оптимальная стратегия игрока B}
end;
{ нахождения наибольшего расчетного выигрыша одного из игроков }
if max_a=max_b then Panel6.Visible:=true
else
if max_a>max_b then
begin
Panel4.Visible:=true;
panel5.Visible:=false
end
else
begin
panel5.Visible:=true;
Panel4.Visible:=false
end;
label11.Caption:=FloatToStr(max_a);
label12.Caption:=FloatToStr(H_a);
label14.Caption:=FloatToStr(max_b);
label13.Caption:=FloatToStr(H_b);
WW_A1;
end;
{просмотр для игрока А}
procedure Tform1.W_tabliza_A(Sender: TObject);
begin
WW_A1;
end;
{просмотр для игрока B}
procedure Tform1.W_tabliza_B(Sender: TObject);
begin
with form1 do
Begin
c_s.Colcount:=m+1;
c_s.Rowcount:=n+1;
tabliza.Rowcount:=n+1;
for i:=1 to n do
begin
form1.tabliza.Cells[0,i]:='B'+intToStr(i);
form1.C_S.Cells[0,i]:='B'+intToStr(i);
for j:=1 to m do
begin
form1.C_S.Cells[j,0]:='A'+intToStr(j);
form1.C_S.Cells[j,i]:=intToStr(C_B[i,j]);
end;
end;
label23.caption:='B';
tabliza.cells[1,0]:='b_малая';tabliza.cells[2,0]:='b_большая';
for j:=1 to n do
begin
tabliza.cells[1,j]:=intToStr(b_m[j]);
tabliza.cells[2,j]:=intToStr(b_b[j]);
end;
for i:=1 to n do
for j:=1 to k do
tabliza.cells[j+2,i]:=floatToStr(V_b[i,j]);
end;
end;
end.
unit Unit2;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
Grids, StdCtrls, ExtCtrls, Buttons, Menus;
type
TForm2 = class(TForm)
alpfa: TStringGrid;
Panel1: TPanel;
BitBtn1: TBitBtn;
BitBtn2: TBitBtn;
procedure FormShow(Sender: TObject);
procedure BitBtn2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form2: TForm2;
i,j:integer;
implementation
uses osnowa;
{$R *.DFM}
{ Ввод козффициентов оптимизмов}
procedure TForm2.FormShow(Sender: TObject);
begin
j:=0;
form1.tabliza.Visible:=true;
alpfa.Colcount:=strToInt(form1.edit3.text);
for i:=0 to alpfa.Colcount do
begin
j:=j+1;
alpfa.Cells[i,0]:='Alpha'+intToStr(i+1);
alpfa.Cells[i,1]:=FloatToStr(al[j]);
end;
end;
procedure TForm2.BitBtn2Click(Sender: TObject);
begin
j:=0;
for i:=0 to alpfa.Colcount do
begin
j:=j+1;
try
al[j]:=strToFloat(trim(alpfa.Cells[i,1]));
form1.tabliza.Cells[3+i,0]:=alpfa.Cells[i,1];
except
showMessage('Ошибочная запись числа : '+alpfa.Cells[i,1]);
end; end;
end;
end.