Приведение матричной игры к задаче

Линейного программирования

Пусть имеем игру размерности m* n с матрицей:

.

Обозначим через р^*=(р₁, …, р_m) g^*=(g₁, …, g_n) – оптимальные смешанные стратегии игроков А и В. Стратегия р^* игрока А гарантирует ему вы­игрыш ≥ υ независимо от выбора стратегии игроком В. Это можно запи­сать так:

                  (9)

где р₁ + р₂ + … + р_m = 1, .

Аналогично стратегия g^* игрока В гарантирует ему проигрыш ≤ υ, не­зависимо от выбора стратегии игроком А, т. е.

                 (10)

где g₁ + g₂ + … + g_n = 1, g_j ≥ 0 (j = ).

Поскольку элементы платежной матрицы можно сделать положи­тельными, то и цена игры υ ≥ 0.

Разделим системы (9) и (10) на υ ≥ 0, получим (11) и (12).

     (11)

где

                 (12)

где  

Обозначим , тогда имеем:

                 (13)

где х₁ + х₂ + … + х_m=

                (14)

где у₁ + у₂ + … + у_n =

Так как игрок А стремится получить max от игры (υ = max), то функция  будет минимизироваться, т. е. оптимальная стратегия игрока А определится из задачи линейного программирования вида: найти min  при ограничениях (13).

Оптимальная смешанная стратегия игрока В определяется решением задачи: найти max φ(y) =  = y₁ + y₂ + … + у_n при ограничениях (14).

Получим двойственную задачу линейного программирования, решив ее графически (для случая двух переменных) или симплексным методом, определим

.

Пример 23. Два сельскохозяйственных предприятия А и В выделяют денежные средства на строительство 3-х объектов. С учетом особенностей вкладов и местных условий прибыль предприятия А в зависимости от объ­ема финансирования выражается элементами матрицы .

Будем предполагать, что убыток предприятия В при этом равен прибыли предприятия А. Требуется найти оптимальные стратегии предприятий А и В.

Решение.

1) Доминирующих строк и столбцов у матрицы нет, поэтому упростить ее нельзя. Обозначим чистые стратегии предприятия:

А: А₁, А₂, А₃;

В: В₁, В₂, В₃.

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

2) Проверим игру на наличие седловой точки:

	В1	В2	В3	а i	. Седловой точки нет,
А1 А2 А3	50 25 10	15 40 30	20 30 60	15 25 10
	50	40	60

 

поэтому решение игры определим в смешанных стратегиях. Цена игры а ≤ υ ≤ β => 25 ≤ υ ≤ 40.

3) Составим задачу линейного программирования:

а) найти для игрока А: min f =  при ограничениях

1 1 1, xi ≥ 0.

б) найти для игрока В: max φ= y₁ + y₂ +y₃ при ограничениях 

1 1 1, yi ≥ 0.

Проще решить задачу для игрока В (двойственная задача): найти max φ = y₁ + y₂ + y₃ + 0y₄ + 0y₅ + 0y₆. Сведем ее к каноническому виду при ограничениях

Строим симплекс-таблицу и решаем ее. Последняя итерация представлена в табл. 28.

Таблица 28

			У1	У2	У3	У4	У5	У6
Б П	Сб	В	1	1	1	0	0	0
У1 У2 У3	1 1 1	0,0133 0,0094 0,0098	1 0 0	0 1 0	0 0 1	0,0234 – 0,0188 0,0056	– 0,0047 0,0438 – 0,0211	– 0,0055 – 0,0156 0,0254
Tj – Cj		0,0325	0	0	0	0,0102	0,0180	0,0043

Оптимальный план У^* = (0,0133; 0,0094; 0,0098; 0; 0;), max φ(у^*) = 0,0325.

Найдем решение прямой задачи:

                                   СП      БП

                                         Y₁ Y₂ Y₃ Y₄ Y₅ Y₆

                                           ↕  ↕ ↕ ↕ ↕   ↕

                                         Х₄ Х₅ Х₆ Х₁ X₂ Х₃

                                   

                                      БП      СП

 

Х^*= (0,0102; 0,0180; 0,0043; 0; 0; 0), f(х^*) = 0,0325,

 цена игры.

Найдем верно

 

        верно.

Итак, оптимальными смешанными стратегиями предприятий А и В являются стратегии р^* = (0,314; 0,554; 0,132) и g^* = (0,409; 0,289; 0,302). Это означает, что из общей суммы а тыс. руб., выделяемых предприятием А на строительство 3-х объектов, на долю   1-го объекта должно выделяться 31,4 %, 2-го – 55,4 %, 3-го –      13,2 % этой суммы. Аналогично распределяются средства b тыс. руб., предприятием В: так на долю 1-го объекта расходуется      40,9 %, 2-го – 28,9 %, 3-го – 30,2 % общей суммы. Такое распределение денежных средств предприятиями А и В по трем строящимся объектам позволит им получить max прибыль 30,77 тыс. руб.

Пример 24. Найти решение игры, заданной матрицей.

А= .

Решение.

Попробуем упростить матрицу:

1) Элементы 1-го столбца не больше элементов 2 столбца (т. е. 1 столбец доминирует над 2-м);

2) Элементы 3-го столбца не больше элементов 4-го и 5-го столбцов (т. е. 3-й столбец доминирует над 4-м и 5-м столбцом)

  1 стр доминирует над 3 стр

 

3) Проверим игру на наличие седловой точки.

	В1	В2	а i	а = max а ij = 2 β = mini аij = 4 2 ≠ 4 => седловой точки нет, 2 ≤ υ ≤ 4
А1 А2	4 3	2 6	2 1
Βj	4	6

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

а) для игрока А: min f_(х) = x₁ + x₂ при ограничениях

 

б) для игрока В: max φ_(y) = У₁ + У₂ при ограничениях

5) Решим графически прямую задачу (рис. 15):

а) Строим область  допустимых решений	Рис. 15
l1: 4х1 + 3х2 = 1,
(0; ), (; 0),
l2: 2х1 + 6х2 = 1
(0; ), (; 0),
б) f0 = 0, х1 + х2 = 0, х1 = – х2,
в)

г) оптимальное решение получим в точке В.

Решим систему

Тогда

min f = .

 

Решаем двойственную задачу (рис. 16): строим область решений l1: 4у1 + 2у2 = 1 (0; ), (; 0) l2: 3у1 + 6у2 = 1 (0; ), (; 0).

Рис. 16

Точка В₁ – оптимальное решение – 9у₁ = =  max φ = υ =  ден. ед. – цена игры,

Следовательно, игрок А применяет стратегию А₁ с вероятностью , а стратегию А₂ с вероятностью , его выигрыш при этом в среднем составит  ден. ед.

 Аналогично делаем вывод и для игрока В.

 

Задание для самостоятельной работы

Решить матричную игру m×n с помощью линейного программирования.

 

1.        2.

 

 

3.         4.

 

5.        6.

 

7.        8.

 

9.              10.

 

11.       12.

13.                         14.

 

15.        16.

 

17.        18.

 

19.          20.

 

21.        22.

 

23.       24.

 

 

25.       26.

 

 

27.       28.

 

 

29.       30.