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

.   (10) 

Если  , имеем .              (11)

Таким образом, u является минимумом n линейных функций одной переменной; можно начертить графики этих функций и затем максимизировать их минимум g () графическими методами [7].

Пример 1. Пусть игра задана матрицей

 

.

 

Строим прямые, соответствующие  стратегиям игрока В. (Рисунки 2 и 3)

Ломаная соответствует нижней границе выигрыша, точка D0 на ней дает решение игры:

, , .             (12)

В этом случае оптимальная  стратегия противника получается применением смеси двух полезных стратегий й , пересекающихся в точке К. Стратегия является заведомо выгодной при оптимальных стратегиях.

 

,     (13)

.     (14)

 

 

Рисунок 2. Решение игры           Рисунок 3. Решение игры    

 

1) Строим прямые, соответствующие  стратегиям второго (первого) игрока.

2) Определяем нижнюю (верхнюю) огибающую  графиков, соответствующие столбцам (строкам).

3) Находим две стратегии второго  (первого) игрока, которым соответствуют  две прямые, пересекающиеся в  точке с максимальной (минимальной)  ординатой.

4) Определяем цену игры и оптимальные  стратегии игроков.   

                 

3.3. Решение игры m ×  n

 

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

Пусть дана m × n - игра А. Говорят, что i-я  стратегия игрока A доминирует над  его k-й стратегией, если a_ij ≥ a_kj для  всех j = 1,2, ..., n ... Говорят, что j-и стратегия  игрока B доминирует над его l-ю стратегией, если a_ij ≤ a_il для всех i = 1,2, ..., m ....      

Из определения видно, что доминирующая стратегия дает игроку выигрыш не меньше, чем не доминирующих. Отсюда следует, что игрок всегда может обойтись без доминирующих стратегий, в частности, если одинаковы стратегии, то он может применять только одну из них. Поэтому в матрице А доминирующие стратегии (строки или столбцы) могут быть отброшены, а это приводит к матрице малых размеров. В результате выполнения доминирование получается игра, эквивалентная первичной [7].

Теорема. Пусть (x, y) - седловая точка m × n - игры А, а (x ^ ', y ^') - седловая точка m ^ '× n ^' - игры A '(m ^' <m 〖, n〗 ^ '<n), полученной из А в результате исключения доминирующих стратегий. Тогда x_i ^ '= x_i, y_i ^' = y_i для всех недоминирующих i, j: x_i = 0, y_i = 0, для всех доминирующих i: V (A ^ ') = V (А).

Пример 2. Рассмотрим упрощение игры А:

Стрелками показаны доминирующие стратегии. Получили 2х2-игру, в которой  все стратегии недоминирующих. Игра A' эквивалентна первоначальной игре А, т.е. оптимальные стратегии в игре А имеют вид x = (0, x_2, x_3), у = (y_1, y_2, 0,0).

В результате вместо игры А мы можем решить более простую игру.

Теперь мы можем указать  общий порядок решения матричной  игры:

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

 

 

 

 

3.4. Решение матричных игр методами линейного программирования

 

 

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

 

	1	2	.	n
A1	A11	A12	...	A1n
A2	A21	A22	...	A2n
…	...	...	...	...
Am	Аm1	Аm2	...	Аmn

 

Рисунок 4. Общий вид платежной матрицы матричной игры

 

Для матричной игры, платежная  матрица которой показана на рисуноке 4, V_н¹V_в,, определим следующие значения вероятности выбора стратегий для игрока А (p₁, p₂, ..., p_m) и для игрока В (q₁, q₂, ..., q_n), при которых игроки достигали бы своего максимально гарантированного выигрыша.

Если один из игроков  придерживается своей оптимальной  стратегии, то, по условию задачи, его  выигрыш не может быть меньше цены игры V. Поэтому данная задача может  быть представлена ​​для игроков в виде следующих систем линейных неравенств:

Для первого игрока:

 

Для другого игрока:

 

Чтобы определить значение V, разделим обе части каждого  из уравнений на V. Величину pi / V обозначим  через xi, а qj / V - через yj.

Для игрока А получим следующую систему неравенств, из которой найдем значение 1 / v.

Для игрока А необходимо найти максимальную цену игры (V). Следовательно, значение 1 / V должно стремиться к минимуму.

Целевая функция задачи будет иметь следующий вид:

min Z = min 1 / V = ​​min (x1 + x2 + ... + xm)

Для игрока В получим следующую  систему неравенств, из которой найдем значение 1 / v:

Для игрока В необходимо найти минимальную цену игры (V). Следовательно, значение 1 / V должно стремиться к максимуму.

Целевая функция задачи будет иметь следующий вид:

max Z = max 1 / V = ​​max (y1 + y2 + ... + yn)                               (18)

Все переменные в данных системах линейных неравенств должны быть неотъемлемыми: xi = pi / V, а yi = qj / V. Значение pi и qj не могут быть отрицательными, поскольку являются значениями вероятности выбора стратегий игроков. Поэтому необходимо, чтобы значение цены игры V не было отрицательным. Цена игры вычисляется на основе коэффициентов выигрышей платежной матрицы. Поэтому, для того, чтобы гарантировать условие додатности для всех переменных, необходимо, чтобы все коэффициенты матрицы были неотъемлемыми. Этого можно добиться, добавив перед началом решения задачи к каждому коэффициента матрицы число K, соответствующее модулю наименьшего отрицательного коэффициента матрицы. Тогда в ходе решения задачи будет определена не цена игры, а величина V * = V + K.

Для решения задач  линейного программирования используется симплекс-метод. В результате решения  определяются значения целевых функций (для обоих игроков эти значения совпадают), а также значения переменных xi и yj.

Величина V * определяется по формуле: V * = 1 / z.                (19)

Значение вероятности  выбора стратегий определяются: для  игрока А:

Pi = xiV * и для игрока В: qi = yiV *.                                        (20)

Для определения цены игры V от величины V * необходимо вычесть  число K [6].

 

4. РЕШЕНИЕ ЗАДАЧИ

4.1. Постановка задачи

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

Фирма А и Фирма  Б имеют равные степени популярности программных продуктов среди потребителей. Увеличить свою популярность, обе фирмы собираются, развернув рекламные кампании. При этом привлечение новых клиентов одной фирмой сопровождается потерей этих клиентов другой фирмой. Исследование показало, что потенциальные клиенты получают информацию через интернет, телевидение.

Задача каждой фирмы – выбрать стратегию привлечения клиентов. 
В данной игре у каждого из игроков по 4 стратегии:

А1, В1 – рекламировать свой программный продукт через телевидение;

А2, В2 – через газеты;

А3, В3 – через радиовещание;

А4, В4 – через Интернет;

Поскольку это игра с  нулевой суммой, то матрицу выигрышей Фирмы А (игрок А) можно представить в виде платёжной матрицы:

Рисунок 5. Матрица игры

где aij – количество привлечённых клиентов Фирмы А в процентах, на которое оно увеличивается, если Фирма А применяет стратегию Аi , а В – стратегию Вj.

4.2. Описание разработанной  программы

 

В рамках данной курсовой работы была реализована программа, которая находит цену игры и оптимальные стратегии игроков матричной игры, заданной платежной матрицей m х n.

Входные данные:

• m - количество строк матрицы,
• n - количество столбцов матрицы,
• платежная матрица размерностью m х n.

Есть возможность автозаполнения случайными числами от -10 до 10.

Рисунок 6. Ввод данных в  программу

 

Выходные данные (рисунок 7):

• верхняя и нижняя цена игры,
• общая цена игры v,
• вероятности применения каждой стратегии игрока А, для получения им максимального выигрыша,
• вероятности применения каждой стратегии игрока В, для получения им минимального проигрыша.

 

 

Рисунок 7. Результат работы программы

4.3. Алгоритм работы программы

 

Программа написана на объектно-ориентированном  языке Delphi в среде Delphi 7.0.

1. Находим верхнюю  и нижнюю цены игры (минимакс и максимин)

 

 

//_______МАКСІМІН

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;

 

 

2. Если верхняя и нижняя цена игры равны, то существует седловая точка Aij, тогда стратегии Аи и Bj будут чистыми оптимальными стратегиями игры, переходим к пункту 7;

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                               //нет седловой точки

 

3. Если седловой точки  не существует, то выполняем исключения невыгодных стратегий, в результате чего уменьшается размерность матрицы.

  while flg do                         //

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

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

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

    end;

 

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

  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]; //

 

5. Рассматриваем полученную  матрицу, как матрицу коэффициентов  системы ограничений задачи линейного  программирования и находим решение  этой задачи и двойственной к ней за помощью симплекс-метода.

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

   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);

 

6. Находим цену матричной  игры и вероятности применения  каждой стратегии.

7. Выводим результат.

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:');

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ