Розробка програмного забезпечення розв’язання парних матричних ігор зі змішаними стратегіями

Автор: Пользователь скрыл имя, 19 Февраля 2013 в 23:29, контрольная работа

Описание работы

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

Скачать полностью (344.91 Кб) Сколько стоит заказать работу?
Работа содержит 1 файл

РГР.docx

— 357.98 Кб (Скачать)

3 ітерація

Баз.

Сб.

План

t1

t2

t3

t4

t5

t6

t7

Ѳ

     

1

1

1

0

0

M

M

  

t2

1

4/46

-1/7

1

0

-7/46

3/46

7/46

-3/7

  

t3

1

3/23

33/46

0

1

1/46

-7/46

-1/14

1/7

  

Min

  

10/46

-14/46

0

0

-6/46

-4/46

-M+6/46

-M+4/46

  

T(0; 2/23; 3/23)

Fmin=5/23

p(0; 2/5; 3/5)

Приклад 2:

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

 

B1

B2

B3

A1

3

-3

4

A2

3

1

3





 

 Існує сідлова точка. Ціна гри 1, оптимальна стратегія для гравця А – 2.

 

 

 

 

 

4 ТЕСТУВАННЯ РОЗРОБЛЕНОГО  ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ

 

Для перевірки роботи розробленого нами ПЗ ми виконаємо два тести: матричної  гри яка має сідлову точку, та таку, яку потрібно розв’язувати симплекс методом.

 

Рисунок 4.1—Розвязання задачі, що не містить сідлової точки

 

 

Рисунок 4.2—Розвязання задачі, що містить сідлової точки

ВИСНОВОК

У розрахунково-графічній роботі, згідно технічного завдання, розроблено комплекс програм для розв’язання парних матричних ігор зі змішаною стратегією.

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

В другому розділі було розроблено USE CASE- діаграму варіантів використання, UML- діаграму класів, UML- діаграму діяльності та UML- діаграму станів.

В третьому розділі був наведений розв’язок задач даного виду різних типів.

Розроблені тести показали правильність роботи програмного забезпечення.

 

СПИСОК ЛІТЕРАТУРИ

  1. Ашманов С. А. Линейное программирование. — М.: Наука, 1981.
  2. Гасс С. Линейное программирование (методы и приложения). — М.: Физматгиз, 1961.
  3. Калихман И. Л. Сборник задач по математическому программированию. — М.: Высш. шк., 1975.
  4. Основы UML. Інтернет університету інформаційних технологій INTUIT.ru [WWW-Документ] http://www.intuit.ru/department/se/intuml/ [URL] 31.08.2009
  5. Методичні   вказівки   до  оформлення  курсових  проектів  (робіт) у  Вінницькому  національному  технічному  університеті. /Уклад. Г.Л. Лисенко, А.Г. Буда, Р.Р. Обертюх, – Вінниця: ВНТУ, 2006. – 60 с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ДОДАТОК А

Лістинг основних модулів  розробленого ПЗ

#include "stdafx.h"

 

class CSimplex   {

protected:

float **A; //     Ліва частина системи рівнянь

float *B; //      Права частина

float *Z; //      Коефіцієнти функції

int *znak; /*     1 - більше дорівнює

          0 - дорівнює

     -1 - меньше  дорівнює */

int min_max; /*   1 - прямує до максимума

                     -1 - до мінімума */

int N; //         Кількість змінних

int NN; //        Фактична кількість змінних

    int number; //    Кількість рівнянь у системі

float *X;

float MAX;

public:

CSimplex () {};

CSimplex (int n, int num, float *z, float **a, float *b, int *zn, int mnmx);

~CSimplex();

char* Simplex();

 

void sss();

};

 

CSimplex::CSimplex(int n,int num, float *z, float **a, float *b, int *zn, int mnmx)

{

N=n;

NN=N;

number = num;

min_max=mnmx;

X=(float*)malloc(N*sizeof(float));

Z=(float*)malloc((N+2*number)*sizeof(float));

B=(float*)malloc(number*sizeof(float));

znak=(int*)malloc(number*sizeof(int));

A=(float**)malloc(number*sizeof(float*));

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

A[i]=(float*)malloc((N+2*number)*sizeof(float));

 

Z=&z[0];

B=&b[0];

znak=&zn[0];

A=&a[0];

 

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

for(int j=N;j<N+2*number;j++)

      A[i][j]=0;

 

for(int j=N;j<N+2*number;j++)

      Z[j]=0;

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

X[i]=0;

}

 

 

void CSimplex::sss()

{

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

std::cout<<Z[i]<<"  ";

std::cout<<"   ->"<<min_max;

std::cout<<"\n\n";

 

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

{

for(int j=0;j<N;j++)

  std::cout<<A[i][j]<<"  ";

std::cout<<"     "<<znak[i];

        std::cout<<"     "<<B[i];

std::cout<<"\n\n";

} 

}

CSimplex::~CSimplex()

{

free(B);

free(Z);

free(znak);

free(A); 

free(X);

}

char* CSimplex::Simplex()

{

if (min_max==-1)    // Перевірка напрямку функції

{

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

Z[i]=Z[i]*(-1);

min_max=1;

}

for(int i=0;i<number;i++) // Перевірка знаку чисел правої сторони

{

if (B[i]<0)

{

for(int j=0;j<N;j++)

A[i][j]=A[i][j]*(-1);

if (znak[i]==-1)

znak[i]=1;

else if( znak[i]==1)

znak[i]=-1;

B[i]=B[i]*(-1);

}

}

    for(int i=0;i<number;i++) // Компенсуючі змінні

{

if(znak[i]==1)

{

N++;

Z[N-1]=0;

A[i][N-1]=-1;

znak[i]=0;

}

else if (znak[i]==-1)

{

N++;

Z[N-1]=0;

A[i][N-1]=1;

znak[i]=0;

}

}

float *Bazes=(float*)malloc(number*sizeof(float));

int *Bazes_number=(int*)malloc(N*sizeof(int));

for(int i=0;i<number;i++)  //Унікальні змінні

{

N++;

Z[N-1]=-M;

A[i][N-1]=1;

Bazes[i]=Z[N-1];

Bazes_number[i]=N-1; 

}

 

// Формування першої  симплекс таблиці

 

// Ініціалізація  додаткових змінних

float *Teta=(float*)malloc(number*sizeof(float));

float *Plan=(float*)malloc((number+1)*sizeof(float));

float *Tabl=(float*)malloc(N*sizeof(float));

float Minimum=999;

float Tiger;

int END=0;

int Tiger_i,Tiger_j; // Номер строки та стовбця змінної "тигра"

/////////////////////////////////////////////////////////////////

 

    Plan[number]=0;  // План

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

{

Plan[i]=B[i];

Plan[number]+=Plan[i]*Bazes[i];

}

 

for(int i=0;i<N;i++)   ////

{

Tabl[i]=0;

for(int j=0;j<number;j++)

Tabl[i]+=A[j][i]*Bazes[j];

Tabl[i]=Tabl[i]-Z[i];

}

 

for (int i=0;i<N;i++) // Пошук мінімального значення

if (Tabl[i]<Minimum)

{

Minimum=Tabl[i];

Tiger_j=i;

}

 

for (int i=0;i<number;i++)  // Розрахунок значень тета

Teta[i]=Plan[i]/A[i][Tiger_j];

 

Minimum=999;

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

if ((Teta[i]>=0)&(Teta[i]<Minimum))

{

Minimum=Teta[i];

Tiger_i=i;

}

Bazes[Tiger_i]=Z[Tiger_j];

Tiger=A[Tiger_i][Tiger_j];

Bazes_number[Tiger_i]=Tiger_j;

 

float **AA=(float**)malloc(number*sizeof(float*));

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

AA[i]=(float*)malloc((N+2*number)*sizeof(float));

// Формування послідуючих  симплекс таблиць

 

 

   

while(1)

{

 

 

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

AA[Tiger_i][i]=A[Tiger_i][i]/Tiger;

   

 

for(int i=0;i<number;i++) // Метод прямокутників

{

if (i==Tiger_i)

continue;

 

for(int j=0;j<N;j++)

AA[i][j]=(A[i][j]*Tiger-A[Tiger_i][j]*A[i][Tiger_j])/Tiger;

 

Plan[i]=(Plan[i]*Tiger-A[i][Tiger_j]*Plan[Tiger_i])/Tiger;

}

 

Plan[Tiger_i]=Plan[Tiger_i]/Tiger;

Plan[number]=0;

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

Plan[number]+=Plan[i]*Bazes[i];

 

for(int i=0;i<N;i++)  ////

{

Tabl[i]=0;

for(int j=0;j<number;j++)

Tabl[i]+=AA[j][i]*Bazes[j];

Tabl[i]=Tabl[i]-Z[i];

}

 

for (int i=0;i<number;i++)  // Переприсвоювання

for (int j=0;j<N;j++)

      A[i][j]=AA[i][j];

 

Minimum=9999;

for (int i=0;i<N;i++) // Пошук мінімального значення

if (Tabl[i]<Minimum)

{

Minimum=Tabl[i];

Tiger_j=i;

}

 

if (Minimum>=0)

END=1;

 

for (int i=0;i<number;i++)  // Розрахунок значень тета

Teta[i]=Plan[i]/A[i][Tiger_j];

 

Minimum=9999;

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

 if ((Teta[i]>=0)&(Teta[i]<Minimum))

{

Minimum=Teta[i];

Tiger_i=i;

}

 

Bazes[Tiger_i]=Z[Tiger_j];

Tiger=A[Tiger_i][Tiger_j];

Bazes_number[Tiger_i]=Tiger_j;

 

    if(END==1)

break;

}

////////// Завершення  ітерацій

    int j;

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

{

        j=Bazes_number[i];

X[j]=Plan[i];

}

MAX=Plan[number];

//

char *Output=new char[80];

sprintf(Output,"T( ");

char *buf=new char[80];

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

{

sprintf(buf,"%2.2f  ",X[i]);

        strcat(Output,buf);

//std::cout<<X[i]<<"  ";

}

strcat(Output,")\n");

sprintf(buf,"MIN->%2.2f",-MAX);

strcat(Output,buf);

   

    free(Teta);

free(Plan);

free(Tabl);

free(AA);

free(Bazes_number);

free(Bazes);

return Output;

}

 

 

 

class CMatrix : public CSimplex {

float alfa;

float beta;

int n_A;

int n_B;

float **Data;

float *P;

public:

CMatrix() {}

CMatrix(int n, int m, float **A);

~CMatrix();

int Analiz();

float get_Alfa();

char *Get_P();

};

 

CMatrix::~CMatrix()

{

}

 

CMatrix::CMatrix(int n, int m, float **a)

{

n_A=n;

n_B=m;

Data=(float**)malloc(n_A*sizeof(float*));

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

Data[i]=(float*)malloc(n_B*sizeof(float));

Data=&a[0];

    // Ініціалізація

N=n_A;

number=n_B;

NN=N;

 

X=(float*)malloc(N*sizeof(float));

P=(float*)malloc(N*sizeof(float));

Z=(float*)malloc((N+2*number)*sizeof(float));

B=(float*)malloc(number*sizeof(float));

znak=(int*)malloc(number*sizeof(int));

A=(float**)malloc(number*sizeof(float*));

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

A[i]=(float*)malloc((N+2*number)*sizeof(float));

 

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

for(int j=N;j<N+2*number;j++)

      A[i][j]=0;

 

for(int j=N;j<N+2*number;j++)

      Z[j]=0;

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

X[i]=0;

 

 

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

Z[i]=1;

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

{

B[i]=1;

znak[i]=1;

}

min_max=-1;

}

 

float CMatrix::get_Alfa()

{

return alfa;

}

 

char *CMatrix::Get_P()

{

char *Out=new char[20];

char *buf=new char[20];

sprintf(Out,"P( ");

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

{

P[i]=X[i]/(-MAX);

sprintf(buf,"%2.2f ",P[i]);

strcat(Out,buf);

}

strcat(Out,")");

return Out;

}

 

 

int CMatrix::Analiz()

{

for (int i=0;i<n_A;i++) // Транспонування матриці

for (int j=0;j<n_B;j++)

A[j][i]=Data[i][j];

 

float *min_A, *max_B;

alfa=-999; beta=999;

min_A=(float*)malloc(n_A*sizeof(float));

max_B=(float*)malloc(n_B*sizeof(float));

 

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

{

min_A[i]=999;

for (int j=0;j<n_B;j++)

if (Data[i][j]<min_A[i])

min_A[i]=Data[i][j];

}

 

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

{

max_B[i]=-999;

for (int j=0;j<n_A;j++)

if (A[i][j]>max_B[i])

max_B[i]=A[i][j];

}

 

alfa=-999;

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

if (min_A[i]>alfa)

alfa=min_A[i];

beta=999;

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

if (max_B[i]<beta)

beta=max_B[i];

   

free(min_A);

free(max_B);

if(alfa==beta)

  return 1;

else return 0;

}

 

 

int _tmain(int argc, _TCHAR* argv[])

{

int n,nm;

std::cout<<"Enter a number of A\n";

std::cin>>n;

std::cout<<"Enter a number of B\n";

std::cin>>nm;

std::cout<<"Enter a matrix data ("<<n<<"x"<<nm<<") of games\n";

 

float **aa;

aa=(float**)malloc(n*sizeof(float*));

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

aa[i]=(float*)malloc(nm*sizeof(float));

 

 

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

for (int j=0;j<nm;j++)

std::cin>>aa[i][j];

 

CMatrix obj(n,nm,aa);

if (obj.Analiz()!=1)

{

std::cout<<obj.Simplex();

std::cout<<"\n"<<obj.Get_P();

}

else

std::cout<<"Alfa=Beta="<<obj.get_Alfa();

std::cout<<"\n";

system("PAUSE");

free(aa);

return 0;

 

}

 


Информация о работе Розробка програмного забезпечення розв’язання парних матричних ігор зі змішаними стратегіями