Решение матричной игры симплекс-методом

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

Игроки

B1

B2

B3

B4

B5

a = min(Ai)

A1

5

-8

7

-6

0

-8

A2

8

-5

9

-3

2

-5

A3

-2

7

-3

6

-4

-4

b = max(Bi )

8

7

9

6

2

0

Решение находим с помощью калькулятора. Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.
Предполагается, что каждый игрок может выбрать только одно из конечного множества своих действий. Выбор действия называют выбором стратегии игрока.
Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.
Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки B1 B2 B3 B4 B5 a = min(Ai)
A1 5 -8 7 6 0 -8
A2 8 -5 9 -3 2 -5
A3 -2 7 -3 6 -4 -4
b = max(Bi) 8 7 9 6 2 0

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = -4, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 2.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах -4 <= y <= 2. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij <= ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
В платежной матрице отсутствуют доминирующие строки.
В платежной матрице отсутствуют доминирующие столбцы.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.
В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (8). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

13 0 15 14 8
16 3 17 5 10
6 15 5 14 4

3. Находим решение игры в смешанных стратегиях. Для этого необходимо свести матричную игру к задаче линейного программирования. Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
13x1+16x2+6x3 ≥ 1
3x2+15x3 ≥ 1
15x1+17x2+5x3 ≥ 1
14x1+5x2+14x3 ≥ 1
8x1+10x2+4x3 ≥ 1
F(x) = x1+x2+x3 → min
найти максимум функции Ф(y) при ограничениях:
13y1+15y3+14y4+8y5 <= 1
16y1+3y2+17y3+5y4+10y5 <= 1
6y1+15y2+5y3+14y4+4y5 <= 1
Ф(y) = y1+y2+y3+y4+y5 → max
Решаем эти системы симплексным методом. Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.
Приведем систему ограничений к системе неравенств смысла <=, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
- 13x1 - 16x2 - 6x3<=-1
- 3x2 - 15x3<=-1
- 15x1 - 17x2 - 5x3<=-1
- 14x1 - 5x2 - 14x3<=-1
- 8x1 - 10x2 - 4x3<=-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x4. В 2-м неравенстве смысла (<=) вводим базисную переменную x5. В 3-м неравенстве смысла (<=) вводим базисную переменную x6. В 4-м неравенстве смысла (<=) вводим базисную переменную x7. В 5-м неравенстве смысла (<=) вводим базисную переменную x8.
-13x1-16x2-6x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = -1
0x1-3x2-15x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = -1
-15x1-17x2-5x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 = -1
-14x1-5x2-14x3 + 0x4 + 0x5 + 0x6 + 1x7 + 0x8 = -1
-8x1-10x2-4x3 + 0x4 + 0x5 + 0x6 + 0x7 + 1x8 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

-13 -16 -6 1 0 0 0 0
0 -3 -15 0 1 0 0 0
-15 -17 -5 0 0 1 0 0
-14 -5 -14 0 0 0 1 0
-8 -10 -4 0 0 0 0 1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6, x7, x8,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-1,-1,-1,-1,-1)
Базисное решение называется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 -1 -13 -16 -6 1 0 0 0 0
x5 -1 0 -3 -15 0 1 0 0 0
x6 -1 -15 -17 -5 0 0 1 0 0
x7 -1 -14 -5 -14 0 0 0 1 0
x8 -1 -8 -10 -4 0 0 0 0 1
F(X0) 0 -1 -1 -1 0 0 0 0 0

1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x4 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-16).

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 -1 -13 -16 -6 1 0 0 0 0
x5 -1 0 -3 -15 0 1 0 0 0
x6 -1 -15 -17 -5 0 0 1 0 0
x7 -1 -14 -5 -14 0 0 0 1 0
x8 -1 -8 -10 -4 0 0 0 0 1
F(X) 0 -1 -1 -1 0 0 0 0 0
θ 0 -1 : (-13) = 1/13 -1 : (-16) = 1/16 -1 : (-6) = 1/6 - - - - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1/16 13/16 1 3/8 -1/16 0 0 0 0
x5 -13/16 27/16 0 -137/8 -3/16 1 0 0 0
x6 1/16 -13/16 0 13/8 -11/16 0 1 0 0
x7 -11/16 -915/16 0 -121/8 -5/16 0 0 1 0
x8 -3/8 1/8 0 -1/4 -5/8 0 0 0 1
F(X0) 1/16 -3/16 0 -5/8 -1/16 0 0 0 0

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
-1 : -16 -13 : -16 -16 : -16 -6 : -16 1 : -16 0 : -16 0 : -16 0 : -16 0 : -16
-1-(-1 • -3):-16 0-(-13 • -3):-16 -3-(-16 • -3):-16 -15-(-6 • -3):-16 0-(1 • -3):-16 1-(0 • -3):-16 0-(0 • -3):-16 0-(0 • -3):-16 0-(0 • -3):-16
-1-(-1 • -17):-16 -15-(-13 • -17):-16 -17-(-16 • -17):-16 -5-(-6 • -17):-16 0-(1 • -17):-16 0-(0 • -17):-16 1-(0 • -17):-16 0-(0 • -17):-16 0-(0 • -17):-16
-1-(-1 • -5):-16 -14-(-13 • -5):-16 -5-(-16 • -5):-16 -14-(-6 • -5):-16 0-(1 • -5):-16 0-(0 • -5):-16 0-(0 • -5):-16 1-(0 • -5):-16 0-(0 • -5):-16
-1-(-1 • -10):-16 -8-(-13 • -10):-16 -10-(-16 • -10):-16 -4-(-6 • -10):-16 0-(1 • -10):-16 0-(0 • -10):-16 0-(0 • -10):-16 0-(0 • -10):-16 1-(0 • -10):-16
0-(-1 • -1):-16 -1-(-13 • -1):-16 -1-(-16 • -1):-16 -1-(-6 • -1):-16 0-(1 • -1):-16 0-(0 • -1):-16 0-(0 • -1):-16 0-(0 • -1):-16 0-(0 • -1):-16

1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 2-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-137/8).

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1/16 13/16 1 3/8 -1/16 0 0 0 0
x5 -13/16 27/16 0 -3/16 1 0 0 0
x6 1/16 -13/16 0 13/8 -11/16 0 1 0 0
x7 -11/16 -915/16 0 -121/8 -5/16 0 0 1 0
x8 -3/8 1/8 0 -1/4 -5/8 0 0 0 1
F(X) 1/16 -3/16 0 -1/16 0 0 0 0
θ 0 - - -5/8 : (-137/8) = 5/111 -1/16 : (-3/16) = 1/3 - - - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 3/74 65/74 1 0 -5/74 1/37 0 0 0
x3 13/222 -13/74 0 1 1/74 -8/111 0 0 0
x6 -2/111 -35/37 0 0 -13/37 11/111 1 0 0
x7 5/222 -125/74 0 0 -11/74 -97/111 0 1 0
x8 -40/111 3/37 0 0 -23/37 -2/111 0 0 1
F(X1) 11/111 -11/37 0 0 -2/37 -5/111 0 0 0

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
1/16-(-13/163/8):-137/8 13/16-(27/163/8):-137/8 1-(0 • 3/8):-137/8 3/8-(-137/83/8):-137/8 -1/16-(-3/163/8):-137/8 0-(1 • 3/8):-137/8 0-(0 • 3/8):-137/8 0-(0 • 3/8):-137/8 0-(0 • 3/8):-137/8
-13/16 : -137/8 27/16 : -137/8 0 : -137/8 -137/8 : -137/8 -3/16 : -137/8 1 : -137/8 0 : -137/8 0 : -137/8 0 : -137/8
1/16-(-13/16 • 13/8):-137/8 -13/16-(27/16 • 13/8):-137/8 0-(0 • 13/8):-137/8 13/8-(-137/8 • 13/8):-137/8 -11/16-(-3/16 • 13/8):-137/8 0-(1 • 13/8):-137/8 1-(0 • 13/8):-137/8 0-(0 • 13/8):-137/8 0-(0 • 13/8):-137/8
-11/16-(-13/16 • -121/8):-137/8 -915/16-(27/16 • -121/8):-137/8 0-(0 • -121/8):-137/8 -121/8-(-137/8 • -121/8):-137/8 -5/16-(-3/16 • -121/8):-137/8 0-(1 • -121/8):-137/8 0-(0 • -121/8):-137/8 1-(0 • -121/8):-137/8 0-(0 • -121/8):-137/8
-3/8-(-13/16-1/4):-137/8 1/8-(27/16-1/4):-137/8 0-(0 • -1/4):-137/8 -1/4-(-137/8-1/4):-137/8 -5/8-(-3/16-1/4):-137/8 0-(1 • -1/4):-137/8 0-(0 • -1/4):-137/8 0-(0 • -1/4):-137/8 1-(0 • -1/4):-137/8
1/16-(-13/16-5/8):-137/8 -3/16-(27/16-5/8):-137/8 0-(0 • -5/8):-137/8 -5/8-(-137/8-5/8):-137/8 -1/16-(-3/16-5/8):-137/8 0-(1 • -5/8):-137/8 0-(0 • -5/8):-137/8 0-(0 • -5/8):-137/8 0-(0 • -5/8):-137/8

1. Проверка критерия оптимальности.
План 2 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 5-ая строка, а переменную x8 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-23/37).

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 3/74 65/74 1 0 -5/74 1/37 0 0 0
x3 13/222 -13/74 0 1 1/74 -8/111 0 0 0
x6 -2/111 -35/37 0 0 -13/37 11/111 1 0 0
x7 5/222 -125/74 0 0 -11/74 -97/111 0 1 0
x8 -40/111 3/37 0 0 -2/111 0 0 1
F(X) 11/111 -11/37 0 0 -5/111 0 0 0
θ 0 - - - -2/37 : (-23/37) = 2/23 -5/111 : (-2/111) = 21/2 - - -

4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 11/138 20/23 1 0 0 2/69 0 0 -5/46
x3 7/138 -4/23 0 1 0 -5/69 0 0 1/46
x6 14/23 -12/23 0 0 0 3/23 1 0 -117/23
x7 5/46 -122/23 0 0 0 -20/23 0 1 -11/46
x4 40/69 -3/23 0 0 1 2/69 0 0 -114/23
F(X2) 3/23 -7/23 0 0 0 -1/23 0 0 -2/23

Представим расчет каждого элемента в виде таблицы:

B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
3/74-(-40/111-5/74):-23/37 65/74-(3/37-5/74):-23/37 1-(0 • -5/74):-23/37 0-(0 • -5/74):-23/37 -5/74-(-23/37-5/74):-23/37 1/37-(-2/111-5/74):-23/37 0-(0 • -5/74):-23/37 0-(0 • -5/74):-23/37 0-(1 • -5/74):-23/37
13/222-(-40/1111/74):-23/37 -13/74-(3/371/74):-23/37 0-(0 • 1/74):-23/37 1-(0 • 1/74):-23/37 1/74-(-23/371/74):-23/37 -8/111-(-2/1111/74):-23/37 0-(0 • 1/74):-23/37 0-(0 • 1/74):-23/37 0-(1 • 1/74):-23/37
-2/111-(-40/111 • -13/37):-23/37 -35/37-(3/37 • -13/37):-23/37 0-(0 • -13/37):-23/37 0-(0 • -13/37):-23/37 -13/37-(-23/37 • -13/37):-23/37 11/111-(-2/111 • -13/37):-23/37 1-(0 • -13/37):-23/37 0-(0 • -13/37):-23/37 0-(1 • -13/37):-23/37
5/222-(-40/111-11/74):-23/37 -125/74-(3/37-11/74):-23/37 0-(0 • -11/74):-23/37 0-(0 • -11/74):-23/37 -11/74-(-23/37-11/74):-23/37 -97/111-(-2/111-11/74):-23/37 0-(0 • -11/74):-23/37 1-(0 • -11/74):-23/37 0-(1 • -11/74):-23/37
-40/111 : -23/37 3/37 : -23/37 0 : -23/37 0 : -23/37 -23/37 : -23/37 -2/111 : -23/37 0 : -23/37 0 : -23/37 1 : -23/37
11/111-(-40/111-2/37):-23/37 -11/37-(3/37-2/37):-23/37 0-(0 • -2/37):-23/37 0-(0 • -2/37):-23/37 -2/37-(-23/37-2/37):-23/37 -5/111-(-2/111-2/37):-23/37 0-(0 • -2/37):-23/37 0-(0 • -2/37):-23/37 0-(1 • -2/37):-23/37

В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 11/138 20/23 1 0 0 2/69 0 0 -5/46
x3 7/138 -4/23 0 1 0 -5/69 0 0 1/46
x6 14/23 -12/23 0 0 0 3/23 1 0 -117/23
x7 5/46 -122/23 0 0 0 -20/23 0 1 -11/46
x4 40/69 -3/23 0 0 1 2/69 0 0 -114/23
F(X1) 3/23 -7/23 0 0 0 -1/23 0 0 -2/23

Оптимальный план можно записать так:
x2 = 11/138
x3 = 7/138
x6 = 14/23
x7 = 5/46
x4 = 40/69
F(X) = 1•11/138 + 1•7/138 = 3/23
Составим двойственную задачу к прямой задаче.
13y1 + 15y3 + 14y4 + 8y5<=1
16y1 + 3y2 + 17y3 + 5y4 + 10y5<=1
6y1 + 15y2 + 5y3 + 14y4 + 4y5<=1
y1 + y2 + y3 + y4 + y5 → max
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
y4 ≥ 0
y5 ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
A = (A2, A3, A6, A7, A4, ) =

16 6 0 0 1
3 15 0 0 0
17 5 1 0 0
5 14 0 1 0
10 4 0 0 0

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
А-1 =

0 -2/69 0 0 5/46
0 5/69 0 0 -1/46
0 3/23 1 0 -117/23
0 -20/23 0 1 -11/46
1 2/69 0 0 -114/23

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
(1, 1, 0, 0, 0) x

0 -2/69 0 0 5/46
0 5/69 0 0 -1/46
0 3/23 1 0 -117/23
0 -20/23 0 1 -11/46
1 2/69 0 0 -114/23

= (0;1/23;0;0;2/23)
Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 1/23
y3 = 0
y4 = 0
y5 = 2/23
Z(Y) = 1*0+1*1/23+1*0+1*0+1*2/23 = 3/23
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 3/23 = 72/3
p1 = 72/3 • 0 = 0
p2 = 72/311/138 = 11/18
p3 = 72/37/138 = 7/18
Оптимальная смешанная стратегия игрока I:
P = (0; 11/18; 7/18)
q1 = 72/3 • 0 = 0
q2 = 72/31/23 = 1/3
q3 = 72/3 • 0 = 0
q4 = 72/3 • 0 = 0
q5 = 72/32/23 = 2/3
Оптимальная смешанная стратегия игрока II:
Q = (0; 1/3; 0; 0; 2/3)
Поскольку ранее к элементам матрицы было прибавлено число (8), то вычтем это число из цены игры.
72/3 - 8 = -1/3
Цена игры: v=-1/3
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑aijpi ≥ v
∑aijqj <= v
M(P1;Q) = (5•0) + (-8•1/3) + (7•0) + (6•0) + (0•2/3) = -2.67 ≥ v
M(P2;Q) = (8•0) + (-5•1/3) + (9•0) + (-3•0) + (2•2/3) = -0.33 ≥ v
M(P3;Q) = (-2•0) + (7•1/3) + (-3•0) + (6•0) + (-4•2/3) = -0.33 ≥ v
M(P;Q1) = (5•0) + (8•11/18) + (-2•7/18) = 4.11 > v
M(P;Q2) = (-8•0) + (-5•11/18) + (7•7/18) = -0.33 < v
M(P;Q3) = (7•0) + (9•11/18) + (-3•7/18) = 4.33 > v
M(P;Q4) = (6•0) + (-3•11/18) + (6•7/18) = 0.5 > v
M(P;Q5) = (0•0) + (2•11/18) + (-4•7/18) = -0.33 < v
загрузка...