Тема: Решение  игры в смешанных стратегиях

        2 -1  2  1

 А =  1  3 -1  0

        4 -2  2 -1

 Найти оптимальную  стратегию и цену игры, заданной платежной матрицей А.

2.2 Постановка задачи. Математическая модель

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

 Седловой  точкой называется А_ij, которая является наименьшим элементом в своей строке и наибольшим элементом в столбце.

 Доминирующая  строка – все элементы этой строки не превосходят соответствующих  элементов другой строки.

 Доминирующий столбец – все элементы не меньше соответствующих элементов какого-либо другого столбца.

 Доминирующие  столбцы и строки можно удалить  из матрицы.

Любой задаче линейного программирования называемой исходной или прямой, можно поставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе эти задачи образуют пару двойственных (или сопряженных) задач. Каждая из задач является двойственной к другой задаче рассматриваемой пары.

 Моя задача представляет собой матрицу. Что бы ее решить сначала построим математическую модель и решим симплексным методом.

 В моей матрице есть доминирующий столбец. Это последний столбец матрицы  так как сказано из определения  все элементы не меньше соответствующих  элементов какого-либо другого столбца. Это столбец доминирует над последним столбцом.

        2 -1  2  1

 А =  1  3 -1  0

        4 -2  2 -1

Поэтому мы его вычеркиваем и составляем симметричные задачи по новой получившейся матрице А

       -1  2  0

 А^* = 3 -1  0

        -2  2 -1

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

 С = 2

 Прибавляем  это число к элементам матрицы  А^* и получаем матрицу А^**

       1  4 3

 А^** = 5  1 2

          0  4 1

 Коэффициенты  при неизвестных в целевой  функции и свободные члены  неравенств должны быть равны 1

 Составляем систему уравнений по данной матрице и целевую функцию (математическая модель).

 

 F(x) = x₁ + x₂ + x₃ → max

 

2.3 Анализ модели. Составление пары симметричных двойственных задач

 В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи) 

 

Правила составления двойственных задач:

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

2. Ограничения-неравенства  исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

3. Если знаки неравенств в ограничениях исходной задачи «≤», то целевая функция Z(X) = с₀ + с₁ · x₁ + с₂ · x₂ + … + с_n · x_n должна максимизироваться, а если «≥», то минимизироваться.

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

5. Целевая функция двойственной задачи имеет вид

где с₀ — свободный член целевой функции Z(X) исходной задачи, b₁, b₂, …, b_m,— свободные члены в ограничениях исходной задачи, при этом b_i — свободный член именно того ограничения исходной задачи, которому соответствует неизвестная y_i, a y₁, y₂, …, y_m— неизвестные в двойственной задаче.

6. Целевая функция F(Y) двойственной задачи должна оптимизироваться противоположным по сравнению с Z(X) образом, т.е. если Z(X) → max, то 
F(Y)→ min, и если Z(X) → min, то F(Y) → max.

7. Каждому неизвестному х_j, j = 1, 2, ..., п исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих п ограничений (вместе с условиями неотрицательности неизвестных y_i, соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными y_i у₂, ..., у_т — в левых. Все знаки неравенств имеют вид «≥», если F(Y) → min, и «≤», если  
F(Y) → max.

 Коэффициенты, с которыми неизвестные y_l у₂, …, у_т входят в ограничение, соответствующее неизвестному x_j, совпадают с коэффициентами при этом неизвестном х. в ограничениях исходной задачи, а именно: коэффициент при y_i совпадает с тем коэффициентом при х_j с которым х_j входит в ограничение исходной задачи, соответствующее неизвестному y_i.

 

 Двойственность

 1) Составляем матрицу из полученной математической модели

       7 6 2 1

 А =  1 3 6 1

         0 2 5 1

         1 1 1 F 

 2) Транспонируем матрицу A

       7 1 0 1

 А^-1 = 6 3 2 1

         2 6 5 1

         1 1 1 Z 

 3) Составляем двойственную задачу

 

 Z = y₁ + y₂ +y₃ → Min 

 Вот и получили пару симметричных двойственных задач. Задача на максимум и на минимум

      

 F(x) = x₁ + x₂ + x₃ → max   Z(x) = y₁ + y₂ +y₃ → min

 

2.4 Решение симплекс методом

 

   

 x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0 

 

 X0         

 X1         

 X2        

 X3         

 X4         

 X5        

 X6           

 

Вторую таблицы рассчитаем аналогичным способом. 
 

 
 

 Решив симплекс методом матрицу мы получим

 X^* = (3/19; 4/19; 0)

 Y^* = (4/19; 3/19; 0)

 F(X^*) = G(Y^*) = 7/19

 Из решения  двойственных задач получим цену игры и оптимальные стратегии  игроков для матрицы А^**  

   

   

   

 Для матрицы  А^* оптимальный план остается такой же

 V = V^” – С = 19/7 – 2 = 5/7

 Оптимальная стратегия P^* и Q^* получаются из оптимальных стратегий P^*~ и Q^*~ приписав нули на место удаленных строк и столбцов.

   

 

 V = 5/7