Реферат Рішення матричних ігор

>Оглавление

1. Мета роботи.. 2

2. Завдання. 3

3. Стислі теоретичні відомості. 4

4. Реалізація програмного кошти. 12

4.1 Проектування. 12

4.2Листинг програмного коду. 12

5. Приклад роботи програми.. 20

Висновки.. 21

Використовувана література. 22

Використовувані програмні кошти. 22


1. Мета роботи

Необхідно розробити програмне засіб на вирішення матричних ігор.

програма матриця граитерационний лістинг


2. Завдання

1. Поставити матрицю гри вручну, і випадково.

2. Знайти оптимальні стратегії гравців, використовуючиитерационний метод і методом чистих стратегій.

3. Зробити можливість зберігати матрицю ігри та зовсім завантажувати з файла.


3. Стислі теоретичні відомості

Постановка спільної справи теорії ігор

Теорія ігор – математична теорія конфліктним ситуаціям. Економічні змагання, спортивні зустрічі, бойові операції – приклади конфліктним ситуаціям. Найпростіші моделі конфліктним ситуаціям – це салонні і спортивні ігри.

У грі можуть зіштовхуватися інтереси двох противників (гра парна чи гра двох осіб), інтереси n (n > 2) противників (гра множинна чи гра n осіб). Існують ігри робилися із нескінченним безліччю гравців.

Стратегією гравця називається система правил, однозначно визначальних вибір поведінки гравця кожному ході залежно від цієї ситуації, яка склалася процесі гри. Залежно від кількості можливих стратегій ігри поділяються на на кінцеві й безмежні.

Процес гри полягає у виборі кожним гравцем і одній своїйстратегии.В результаті ситуації>s гравець і отримує виграш.

Ігри, у яких метою кожного учасника є отримання наскільки можна більшого індивідуального виграшу, називаютьсябескоалиционними на відміну коаліційних, щодо дії гравців спрямовані на максимізацію виграшів колективів (коаліції) без подальшого поділу виграшу між учасниками.

За визначеннямбескоалиционной грою називається система

,

у якій I і – безлічі, – функції на безлічі приймаючі речові значення.

>Бескоалиционная гра називається грою із постійною сумою, якщо є таке постійне З, що з всіх ситуацій .

Ситуація >s у грі називається прийнятною для гравця і, коли цей гравець, змінюючи у кризовій ситуації >s своєї стратегії >sі ні на яку іншу >sі', неспроможна збільшити свого виграшу.

Ситуація >s, прийнятна всіх гравців, називається ситуацією рівноваги.

Процес перебування ситуації рівноваги вбескоалиционной грі є процес розв'язування гри.

>Матричние гри

Гра називається парної, тоді як ній зіштовхуються інтереси двох противників. Гра з нульової сумою, якщо одне гравець виграє стільки, скільки другий програє у тій партії.

Кожна фіксована стратегія, яке може вибрати гравець, називається його чистої стратегією.

>Матричной називають парну гру з травня нульової сумою за умови, кожен гравець має кінцеве число чистих стратегій.

Нехай перший гравець має >m чистих стратегій, а другий – n.

>Парная гра з травня нульової сумою задається ' формально системою чисел – матрицею, елементи якої визначають виграш першого гравця (і програш другого), якщо перший гравець вибере і->ю рядок (і->ю стратегію), а другий гравець j-і стовпець (j->ю стратегію). Матриця називається платіжної матрицею чи матрицею гри.

Завдання першого гравця – максимізувати свій виграш.

Завдання другого гравця – максимізувати свій виграш – зводиться до мінімізації програшу другого, що еквівалентно завданню мінімізації виграшу першого гравця.

Чисті стратегії

Гарантований виграш першого гравця, використовує чисту і->ю стратегію,


Кількість називається нижнім значенням гри, а відповідна чиста стратегія і0, коли він досягається називається >максиминной стратегією першого гравця. Аналогічно, називається верхнім значенням гри а j0>минимаксной стратегією другого гравця.

Завжди . Коли на те гра має >седловую точку в чистих стратегіях; число називається значенням гри (чи ціною гри). Гра маєседловую крапку у чистих стратегіях тоді й тільки тоді, коли є елемент матриці , мінімальний у своїй рядку й те водночас максимальний в стовпці

Будь-яка пара (і0, j0), що має властивістю (10.1), називається >седловой точкою.

Змішані стратегії

Якщо позначити через x1, x2, …, x>m ймовірності (частоти), із якими перший гравець вибирає відповідно першу, другу, . . ., >m->ю чисту стратегію, отже через ; через y1, y2, …, yn ймовірності, із якими другий гравець вибирає першу, другу, ,.., n->ю свою чисту стратегію, причому , то набори чисел x=( x1, x2, …, x>m) і y=(y1, y2, …, yn) називаються змішаними стратегіями першого і другого гравців відповідно. Кожен гравець має незліченну кількість змішаних стратегій. Безліч змішаних стратегій першого гравця позначимо через >s1 і безліч змішаних стратегій другого гравця – через >s2.

Завдання першого гравця полягає у виборі такий стратеги щоб за відсутності інформації про вибір іншого максимізувати свій виграш. Завдання другого гравця полягає у виборі такий стратегії , щоб за відсутності інформації щодо поведінки першого гравця мінімізувати виграш першого.

Якщо Сталін перший гравець застосовує стратегію, а другий – стратегію то середній виграш M(x, y) першого гравця дорівнює

Виграш M(x, y) називають функцією гри.

Наприклад, в завданню з матрицею

перший гравець має дві чисті стратегії , й незліченну безліч змішаних стратегій, як-от , тощо. буд.; всі є елементами безлічі другий гравець має чотири чисті стратегії й незліченну безліч змішаних стратегій, як-от , є елементами безлічі


Якщо Сталін перший гравець застосовує змішану стратегію , а другий застосовує стратегію, то середній виграш першого гравця, визначається функцією гри, виявиться рівним

Якщо самий перший гравець застосовує стратегію, а другий — стратегію , то . Оптимальна стратегія першого гравця другого гравця; —ціна гри.

>Седловая точка в змішаних стратегіях

Кілька змішаних стратегій (x*, у*) називається >седловой точкою функції М(x, у), якщо

Кожна матрична гра з травня нульової сумою має рішення, у змішаних стратегіях, т. е. є такі змішані стратегії x* і y* першого і другого гравців відповідно, що виконується умова (10.2). Гарантований виграш першого гравця, використовує змішану стратегію

Стратегія x*, коли він гарантований виграш першого гравця сягає максимального значення, називається оптимальної стратегією першого гравця:

Гарантований програш другого гравця

y* – оптимальна стратегія другого гравця, якщо

Гарантований виграш першого гравця, використовує свою оптимальну стратегію, дорівнює гарантованого програшу другого гравцю, використовує свою оптимальну стратегію: – ціна гри.

Зведення завдання теорія ігор до завданню лінійного програмування

Завдання максимізації гарантованого виграшу першого гравця і завдання мінімізації гарантованого програшу другого гравця зводяться до парі взаємно двоїстих завдань лінійного програмування:

Завдання першого гравця Завдання другого гравця


Процес вирішення завдань спрощується, якщо можливість перейти доПеременним . Це можна, якщо.

Маємо:

Завдання першого гравця Завдання другого гравця

Оптимальні стратегії гравців не зміняться, якщо матрицюигризаменить на . Ціна гри у своїй поповнюється з.

Методи вирішення завдань теорії ігор великою мірою залежить та умовами завдання й від матриці А виграшів першого гравця.

Якщо матриця А маєседловую точку, те решіння гри зводиться до пошукуседловой точки матриці А. Оптимальні стратегії гравців визначаються у своїй координатами (і,j)седловой точки матриці А, а ціна гри елементом вседловой точці.

Якщо завдання теорії ігор немає рішення на чистих стратегіях, вона може стати вирішеноюитерационним методом.

>Итерационний метод.

Розігрується уявний експеримент, у якому гравці Проте й У застосовують проти друг

друга свої стратегії. Експеримент складається з послідовності партій. А вибирає стратегію

>Аi, гравець У вже це й відповідає своєї стратегієюВj, найвигіднішою йому у ситуації. Далі, перший гравець вибирає подальші стратегії виходячи з попередньої грі. Отже, кожному кроціитерационного процесу гравець відповідає на крок іншого тієї своєї стратегією, що є оптимальної щодо всіх попередніх ходів. Якщо партії продовжувати тривалий час, то середній виграш прагне ціні гри, а частоти – до можливостям оптимальних стратегій. Основною перевагою Сендеги цього є незалежність його складності від розмірності гри.

 


4. Реалізація програмного кошти

Середовище розробки: З++BuilderXE

Мова програмування: З++

4.1 Проектування

Список модулів з коротким описом:

1)Mainform.cpp – це головний модуль у якому, реалізовані функції: розрахунку в чистих стратегіях,сохранение/загрузка і введення вихідних даних .

2)Iter.cpp – це допоміжний модуль у якому реалізованийитерационний метод рішення матричної гри.

4.2Листинг програмного коду

 

Модуль >Mainform.>cpp:

//---------------------------------------------------------------------------

#>include <>vcl.h>

#>pragmahdrstop

#>include ">Series.hpp"

#>include ">Iter.h"

#>include ">pic.h"

#>include ">mainform.h"

#>include <>fstream.h>

#>include <>iostream>

//---------------------------------------------------------------------------

#>pragmapackage(smart_init)

#>pragmaresource "*.>dfm"

>TForm1 *>Form1;

//---------------------------------------------------------------------------

__>fastcallTForm1::TForm1(TComponent*Owner)

:TForm(Owner)

{

}

//---------------------------------------------------------------------------

>void __>fastcallTForm1::RaschetClick(TObject *>Sender) // розрахунок

{

>doubleMaxMin=0,MinMax=0;

>doubleMinRow[100];

>doubleMaxCol[100];

>int і, j, n,m;

>doubleA0[100][100];

n =StrToInt(Edit4->Text);

>m =StrToInt(Edit5->Text);

>for (і = 0; і <m; і++) {

>for (j = 0; j < n; j++) {

//переклад значень з таблиці в масивdouble матриціA0:

>A0[j][i]=StrToFloat(StringGrid1->Cells[i+1][j+1]);

}

}

//--------------------- розрахунок в чистих стратегіях -----------------------------

>for (і = 0; і < n; і++) {

>MinRow[i]=A0[i][0];

}

>for (і = 0; і <m; і++) {

>MaxCol[i]=A0[0][i];

}

//очистимострингриди 2 і трьох:

>for (>registerint і = 0; і <StringGrid2->RowCount; і++)

{

>StringGrid2->Rows[i]->Clear();

}

>for (>registerint і = 0; і <StringGrid3->RowCount; і++)

{

>StringGrid3->Rows[i]->Clear();

}

>StringGrid2->Cells[0][0]="Min";

>StringGrid3->Cells[0][0]="Max";

// розрахунок мінімумів і максимумів

>for (і = 0; і < n; і++) {

>for (j = 0; j <m; j++) {

//пошук мінімального значення рядках :

>if (>A0[i][j] <=MinRow[i]) {

>MinRow[i] =A0[i][j];

}

}

//висновок мінімумів рядківСтрингГрид2 :

>StringGrid2->Cells[0][i+1] =MinRow[i];

}

>for (j = 0; j <m; j++) {

>for (і = 0; і < n; і++) {

//пошук максимального значення шпальтах :

>if (>A0[i][j] >=MaxCol[j]){

>MaxCol[j] =A0[i][j];

}

}

//висновок максимумів шпальт вСтрингГрид3 :

>StringGrid3->Cells[j+1][0] =MaxCol[j];

}

//знайдемомаксимин

>MaxMin =MinRow[0];

>for (і = 0; і < n; і++) {

>if (>MinRow[i] >=MaxMin ){>MaxMin =MinRow[i];}

}

>Edit2->Text=MaxMin;

//знайдемоминимакс

>MinMax =MaxCol[0];

>for (і = 0; і <m; і++) {

>if (>MaxCol[i] <=MinMax ){>MinMax =MaxCol[i];}

}

>Edit3->Text=MinMax;

>if (>MinMax ==MaxMin) {

>ShowMessage("Игра розв'язано нелегку для чистих стратегіях");

>Edit1->Text =MinMax;

}else {>ShowMessage("Игра не вирішується в чистих стратегіях, спробуєте вирішити їїитерационним методом");}

//------------------------------------------------------------------------------

}

//------------------------------------------------------------------------------

>void __>fastcallTForm1::Button1Click(TObject *>Sender)

{

>Form2->Show();

}

//---------------------------------------------------------------------------

>void __>fastcallTForm1::Button2Click(TObject *>Sender)

{

>int і, j, n,m;

>doubleA0[100][100];

n =StrToInt(Edit4->Text);

>m =StrToInt(Edit5->Text);

//очищаємоСтрингГрид1:

>for (>registerint і = 0; і <StringGrid1->RowCount; і++){

>StringGrid1->Rows[i]->Clear();

}

>for (і = 0; і < n; і++) {

>StringGrid1->Cells[0][i+1]="A"+String(i+1);

}

>for (і = 0; і <m; і++) {

>StringGrid1->Cells[i+1][0]="B"+String(i+1);

}

}

//---------------------------------------------------------------------------

>void __>fastcallTForm1::SaveClick(TObject *>Sender)

{

>intn,m;

n =StrToInt(Edit4->Text);

>m =StrToInt(Edit5->Text);

// збереження в файл

>SaveTextFileDialog1->Execute();

>SaveTextFileDialog1->FileName;

>ofstreammyfile(SaveTextFileDialog1->FileName.t_str());

>for (>int і = 0; і < n; і++) {

>for (>int j = 0; j <m; j++) {

 >myfile <<StrToFloat(StringGrid1->Cells[j+1][i+1]);

 >myfile << " ";

}

>myfile << "n";

}

>myfile.close();

}

//---------------------------------------------------------------------------

>void __>fastcallTForm1::Button4Click(TObject *>Sender)

{

>intn,m;

n =StrToInt(Edit4->Text);

>m =StrToInt(Edit5->Text);

//Завантаження файла

>int a;

>if (>OpenDialog1->Execute()){

>OpenDialog1->FileName;

>ifstreamloadfile(OpenDialog1->FileName.c_str());

>for(inti=0;i<n; і++){

>for(intj=0;j<m; j++){

>loadfile >> a;

>StringGrid1->Cells[j+1][i+1] =IntToStr(a);

}

//>StringGrid1[i+1][j+1]=ch;

}

>loadfile.close();

}

}

//---------------------------------------------------------------------------

>void __>fastcallTForm1::Button5Click(TObject *>Sender)

{

>int і, j, n,m;

>doubleA0[100][100];

n =StrToInt(Edit4->Text);

>m =StrToInt(Edit5->Text);

//>Создаемрандомную матрицю

>for (і = 0; і < n; і++) {

>for (j = 0; j <m; j++) {

>A0[i][j] =RandomRange(1, 10);

}

}

//Матрицю вСтрингГрид1:

>for (і = 0; і < n; і++) {

>for (j = 0; j <m; j++) {

>StringGrid1->Cells[j+1][i+1]=String(A0[i][j]);

}

}

}


5. Приклад роботи програми

1) Приклад випадково заданої матрицірешенной в чистих стратегіях:

2) Прикладплатежной матриці нерозв'язною в чистих стратегіях:

3) Приклад матриці гри розв'язуваноїитерационним методом:


Висновки

Через війну зробленого було розроблено програмне засіб на вирішення матричних завдань методом чистих стратегій іитерационним методом.


Використовувана література

>1)Гейл Д. Теорія лінійних економічних моделей. М.:Изд–во іноземної літератури, 1968.

>2)ПетросянЛ.А.Зенкевич Н.А. СьомінаЕ.А. Теорія ігор :Учеб. посібник – М.:ВЫСШ.ШК.; : УНІВЕРСИТЕТ, 1998. – 300 з.

3) Орлов, А.І. Теорія прийняття рішень. Навчальний посібник /А.И.Орлов.- М.:

Видавництво Березень, 2004. - 656 з

Використовувані програмні кошти

 

З++BuilderXE


Схожі реферати:

Нові надходження

Замовлення реферату

Реклама

Навігація