Интеллектуальная система. Разрешение конфликтных ситуаций по разработке и продаже программных продуктов между двумя фирмами. Матричная и

 

Матричные игры широко используются в системах принятия решений. Они  могут служить математическими моделями многих простейших конфликтных ситуаций в области экономики, математической статистики, военного дела, биологии.

Теория матричных игр  достаточно широко используется благодаря:

• большому количеству практических задач, которые к ней сводятся;
• сосредоточению характерных математических, алгоритмических и вычислительных сложностей.

В рамках данной работы были выполнены следующие задачи:

• исследованы методов решения матричных игр;
• изучены алгоритмы нахождения решения матричной игры методами линейного программирования; методы нахождения решений матричных игр симплекс-методом.
• разработана программа, которая находит цену и оптимальные стратегии игроков матричной игры, заданной матрицей nxm.

Выполнение данной работы помогло мне закрепить знания, полученные из курса дисциплины «Системы искусственного интеллекта».

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

1. Василевич Л.Ф. Теория игр. КИИМ, 2000
2. Гольштейн Е.Г., Юдин Д.Б. Новое направления в линейных программировании и ёё приложение. - М.: Наука, 1966. - 351
3. Давыдов Э.Г. Исследование операций. - М.: Высш. шк., 1990
4. Лапшин К.А. Методические указания для студентов экономического факультета «Игровые модели и принятие решений». - М. 2001
5. Лэдсон Л. Оптимизация больших систем. - М.: Наука, 1975
6. Лященко М.Я., Головань М.С. Численные методы: Учебник. - М.: Просвещение, 1996
7. Цукров В.И. Декомпозиционные методы решения задач большой размерности. - М.: Наука, 1981
8. Чеснокова О. В. Delphi 7. Алгоритмы и програмы. - М.: Пресс, 2008

 

ПРИЛОЖЕНИЕ 1. ЛИСТИНГ  ПРОГРАММЫ

 

//----------Реализация алгоритма----------------

procedure TForm2.Button1Click(Sender: TObject);

var flg,sid:boolean;

begin

  n:=SG.RowCount-1;

  m:=sg.ColCount-1;

  flg:=true;

  sid:=false;

  pn:=0; qm:=0;

  for i:=1 to pn do                    //

      p[i]:=0;

      xx[i]:=0;                         // Обнуляем массив

  for i:=1 to qm do

      yy[i]:=0;                        //

      q[i]:=0 ;                        //

try

  for i:=1 to n do                     //

    for j:=1 to m do                   // Считывание данных

    A[i,j]:=strtofloat(sg.cells[j,i]); //

   except

     on Exception : EConvertError do

       begin

       ShowMessage('Ошибка чтения. Проверьте правильность введённых данных');

       Exit;

       end;

   end;

  minimax;                             // Мінімакс

   if checkbox1.Checked then

    begin

    listbox1.Items.Add('Нижняя цена = '+floattostr(min));  // верхняя

    listbox1.Items.Add('Верхняя цена = '+floattostr(max)); // нижняя цены игры

    end;

    if max=min then begin              //проверка на существование седловой точки

                v:=a[mini,maxj];

                p[mini]:=1;

                q[maxj]:=1;

                listbox1.Items.Add('Решений в чистых стратегиях:');

                listbox1.Items.Add('цена игры = '+floattostr(min));

                listbox1.Items.Add('Оптимальная стратегия игрока А - A'+inttostr(mini));

                listbox1.Items.Add('Оптимальная стратегия игрока B - A'+inttostr(maxj));

                end

    else                               //нет седловой точки

begin

listbox1.Items.Add('Игра  не имеет решений в чистых  стратегиях');

if checkbox1.Checked then

listbox1.Items.Add('Найдено  решений в смешанных стратегиях.');

 for i:=1 to n do

   a[i,m+1]:=i;

  for j:=1 to m do

    a[n+1,j]:=j;

  while flg do                         //

    begin                              // Выключенние невыгодных стратегий

      optR(a,n,m,flg);                 //

      optS(a,n,m,flg);                 //

    end;

   for i:=1 to n do

      p[round(a[i,m+qm+1])]:=1;

   for i:=1 to m do

      q[round(a[n+pn+1,i])]:=1 ;

  minA:=a[1,1];

  for i:=1 to n do                      //

    for j:=1 to m do                    // Ппоиск мін. елемента матриці

      if minA>a[i,j] then minA:=a[i,j]; //

  for i:=1 to n do                      //

    for j:=1 to m do                    // a[i,j]>=0, i=1..n,j=1..m;

      a[i,j]:=a[i,j]+abs(minA);         //

  form2.simplM;

                           // симплекс метод

   j:=1;

   for i:=1 to sg.RowCount do

   if p[i]=1 then

       begin

       p[i]:=yy[j]*v;

       inc(j);

       end;

   j:=1;

   for i:=1 to sg.colCount do

   if q[i]=1 then

       begin

       q[i]:=xx[j]*v;

       inc(j);

       end;

v:=v-abs(minA);

with listbox1.Items do

begin

if checkbox1.Checked  then

  begin//---Вывод результатов----

Add('Игра сводится  к задаче ЛП:');

    Add('MaxZ = x1 ');

    for i:=2 to m do

    Strings[Count-1]:=Strings[Count-1]+'+ x'+inttostr(i);

    Add('__');

    for i:=1 to n do

      begin

      Add('| '+floattostr(a[i,1])+'*x1');

      for j:=2 to m do

        Strings[Count-1]:=Strings[Count-1]+' + '+floattostr(a[i,j])+'*x'+inttostr(j);

      Strings[Count-1]:=Strings[Count-1]+' >= 1';

      end;

     Add('__');

  Add(':');

  Add('MaxL = y1 ');

    for i:=1 to n do

    Strings[Count-1]:=Strings[Count-1]+'+ y'+inttostr(i);

    Add('__');

    for j:=1 to m do

      begin

        Add('| '+floattostr(a[1,j])+'*y1');

        for i:=2 to n do

          Strings[Count-1]:=Strings[Count-1]+' + '+floattostr(a[i,j])+'*Y'+inttostr(i);

        Strings[Count-1]:=Strings[Count-1]+' <= 1';

      end;

     Add('__');

    Add('Решений  задачи ЛП:');

    for i := 1 to m do

      Add('x['+inttostr(i)+'] = '+floattostr(xx[i]));

    for i := 1 to n do

      Add('y['+inttostr(i)+'] = '+floattostr(yy[i]));

    Add('MaxZ = MaxL = '+floattostr(Ad[n+1, m+n+1]));

 end;///

    Add('Решений  матричной игры:');

    Add('Цена  игры = '+floattostr(v));

    Add('Оптимальная  стратегия игрока А:');

      for i := 1 to sg.RowCount-2 do

        Add('A['+inttostr(i)+'] с вероятностью '+floattostr(p[i]));

    listbox1.Items.Add('Оптимальная стратегия игрока B:');

   for i := 1 to sg.colCount-2 do

     Add('B['+inttostr(i)+'] с вероятностью '+floattostr(q[i]));

if (m>5) or (n>5) then listbox1.Width:=listbox1.Width+round(m/5)*listbox1.Width;

end;

end;//---

end;

  procedure TForm2.UpDown2Click(Sender: TObject; Button: TUDBtnType);

begin

edit2.Text:=inttostr(updown2.Position);

end;

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

procedure tform2.optR(Var a1: matrix; var n1, m1:integer; var flag:boolean);

label start;

var i1, j1,k : integer;

//del:array[1..100] of integer;

begin

flag:=false;

start:

for k:=1 to n1 do

    begin;

    for i1:=1 to n1 do

      begin

        for j1:=1 to m1 do

        begin

          if a1[k,j1]>a1[i1,j1] then break;

          if (k<>i1) and (j1=m1) then

          begin

              form2.DelR(a1,n1,m1,k); inc(pn);flag:=true; goto start;

          end;        end;      end;    end;end;

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

procedure tform2.optS(Var a1: matrix; var n1, m1:integer;var flag:boolean);

label start;

var i1, j1,k : integer;

//del:array[1..100] of integer;

begin flag:=false;

start:

for k:=1 to m1 do

    begin;    for j1:=1 to m1 do

      begin        for i1:=1 to n1 do

        begin          if a1[i1,k]<a1[i1,j1] then break;

          if (k<>j1) and (i1=n1) then

          begin              form2.DelS(a1,n1,m1,k);

              inc(qm);

              flag:=true; goto start;

          end;        end;      end;    end;end;

//----------DELETEr------------

Procedure tform2.DelR(Var X : matrix; Var nn, mm : integer; k1 : integer);

Var

  ii, jj : integer;

Begin

  for ii := k1 to nn+pn do

    for jj := 1 to mm+qm+1 do

      X[ii, jj] := X[ii+1, jj];

        //for jj := 1 to mm do

          //X[nn, jj] := 0;

  Dec(nn);End;

//----------DELETEs------------

Procedure tform2.DelS(Var X : matrix; Var nn, mm : integer; k1 : integer);

Var

  ii, jj : integer;

Begin

  for jj := k1 to mm+qm do

    for ii := 1 to nn+pn+1 do

      X[ii, jj] := X[ii, jj+1];

        //for ii := 1 to nn do

         // X[nn, jj] := 0;

  Dec(mm);

End;

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

procedure tform2.minimax();

begin

with form2 do

  begin

SG.RowCount:=SG.rowCount+1;

SG.colCount:=SG.colCount+1;

sg.Cells[SG.colCount-1,0]:='minA';

sg.Cells[0,SG.RowCount-1]:='maxB';

//_______МАКСІМІН

for i:=1 to n do

  begin

    min:=a[i,1];

    for j:=1 to m do

      begin

         if a[i,j]<min then

         min:=a[i,j];

      end;

    a[i,m+1]:=min;

    SG.Cells[SG.colcount-1,i]:=floattostr(min);

  end;

  min:=a[1,m+1];

  mini:=1;

  for i:=1 to n do

      if min<a[i,m+1] then  begin

                             min:=a[i,m+1];

                             mini:=i;

                            end;

//_______МІНІМАКС

for j:=1 to m do

  begin

    max:=a[1,j];

    for i:=1 to n do

      begin

         if a[i,j]>max then

         max:=a[i,j];

      end;

    a[n+1,j]:=max;

    SG.Cells[j,SG.rowcount-1]:=floattostr(max);

  end;

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

  maxj:=1;

  max:=a[n+1,1];

  for j:=1 to m do

      if max>a[n+1,j] then begin

                             max:=a[n+1,j];

                             maxj:=j;

                            end;

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