Методы оптимальных решений (стр. 15 )

A =

Прежде всего, проверим, имеет ли матрица (80) седловую точку. Наименьший элемент -3 первой строки не является наибольшим в третьем столбце; наименьший элемент -1 второй строки не является наибольшим в первом столбце; наконец, наименьший элемент 2 третьей строки является одновременно наибольшим в третьем столбце. Следовательно, матрица (80) имеет седловую точку (3, 3), в которой расположен элемент а33= 2. Значит, игра имеет решение в чистых стратегиях, а именно;

Р*3 = (0, 0, 1) — оптимальная стратегия первого игрока;

Q*3 = (0, 0, 1, 0) - оптимальная стратегия второго игрока;

n = 2 — цена игры. -

Пример 9. Найти решение игры, заданной платежной матрицей

A = 2

В матрице (81) нет седловой точки, следовательно, игра имеет решение в смешанных стратегиях.

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

А’ = 2

Прибавив ко всем элементам матрицы А’, например, число с = 3, получим матриц

А” = 5 0 7

2 4 1

Составим пару симметричных двойственных задач (84), так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей А’, а коэффициенты при неизвестных в целевой функции и

свободные члены неравенств были бы равны единице.

Задача 1 Задача 2

Max ¦(X) = x1 + x2 + x3 Min g(Y) = y1 + y2

при условиях: х1 ³ 0, х2 ³ 0, х3 ³ 0, при условиях: y1 ³ 0, y2 ³ 0,

5х1 +7х3 £ 1, 5y1 + 2y2 ³ 1,

2х1 + 4х2 + х3 £ 1. 4y2 ³ 1, (84)

7y1 + y2 ³ 1.

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем ее к основной при помощи дополнительных неизвестных х4 ³ 0, х5 ³ 0. В результате получим следующую задачу.

5х1 + 7х3 + х4 = 1,

2х1 + 4х2 + х3 + + х5 = 1, (85)

xj ³ 0 ( j = 1 ¸ 5) , (86)

¦ (X) = x1 + x2 + x3 ¾ max. (87)

Задача (85)—(87) — каноническая и, применив к ней алгоритм симплекс-метода, получим симплексные таблицы вида

			0	1	1	1	0	0
		Баз.	х0	х1	х2	х3	х4	х5
	0	х4	1	5	0	7	1	0	Табл.1 q= 1/4
	0	х5	1	2	4	1	0	1
		¦	0	-1	-1	-1	0	0
	0	х4	1	5	0	7	1	0	Табл.2 q =1/7
®	1	х2	¼	1/2	1	1/4	0	1/4
		¦	¼	-1/2	0	-3/4	0	1/4
®	1	х3	1/7	5/7	0	1	1/7	0	Табл.3
	1	х2	3/14	9/28	1	0	-1/28	1/4
		¦	5/14	1/28	0	0	3/28	1/4
			g	y3	y4	y5	y1	y2

Из столбца х0 индексной строки табл.3 выпишем оптимальные планы пары двойственных задач (84), а именно:

Х*=(0, 3/14, 1/7); Y*=(3/28,1/4), причем ¦(Х*)=g(Y*)= 5/14.

Из решений двойственных задач (84) получим цену игры и оптимальные стратегии игроков в игре с матрицей A²:

n²= 1/¦(X*) = 1/g(Y*) = 14/5; P*= n² × Y* = 14/5(3/28, 1/4) = (3/10, 7/10);

Q*= n² × X*= 14/5(0, 3/14, 1/7) = (0, 3/5, 2/5)

Игра с матрицей А’ будет иметь те же оптимальные стратегии P* и Q*, что и игра с матрицей А”, причем цена игры n¢ = n² - c = 14/5 - 3 = - 1/5

И, наконец, исходная игра с матрицей А имеет оптимальные стратегии

P*=(0,3/10,7/10) и Q*= (0, 3/5, 0, 2/5,0) и цену игры n = n¢ = -1/5.

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

Проверить правильность решения игры можно с помощью критерия оптимальности стратегий. Для этого в неравенства (79) следует подставить компоненты найденных оптимальных стратегий Р* и Q* компоненты чистых стратегий Рi (i = 1, 2, 3) и Qj (j = 1, 2, 3, 4, 5) и цену игры n = -1/5

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

A’ = 2 -3 4

То в задаче 1 целевая функция будет не ограничена сверху на множестве планов, а в задаче 2 вообще не будет планов, однако, как мы убедились выше, игра с матрицей А’ имеет решение.