Пример индивидуального решения

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

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

– оптимальная стратегия первого игрока;

– оптимальная стратегия второго игрока;

v = 2 – цена игры.

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

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

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

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

все элементы которой неотрицательны, а элементы второй строки строго положительны.

Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей А", ·а коэффициенты при неизвестных в целевой функции и свободные члeны неравенств были бы равны единице.

Задача 1 Мах f(X} = x₁+ x₂+ x₃ при условиях: x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, 5 x₁+ 7 x₃≤1, 2 x₁+ 4 x₂+ x₃≤1.

Задача 2 Min g(Y) = у₁ + у₂ при условиях: 5y₁ + 2y₂ ≥1, 4y₂ ≥1, 7 у₁ + у₂ ≥ 1, у₁ ≥ 0, у₂ ≥0.

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

x_j ≥ 0 (j = 1,…,5),

f(X) = x₁+ x₂+ x₃ → тах.

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

Баз.пер	Св.чл.	x₁	x₂	x₃	x₄	x₅
x₄
x₅
F		-1	-1	-1
x₄
x₂	1/4	1/2		1/4		1/4
F	1/4	-1/2		-3/4		1/4
x₃	1/7	5/7			1/7
x₂	3/14	9/28			-1/28	1/4
F	5/14	1/28			3/28	1/4
		y₃	y₄	y₅	y₁	y₂

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

Х* =

У* =

причем

f(X*) = g(Y*) =

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

v" = = ;

= v" = = ;

= v" = =

Игра с матрицей А' будет иметь те же оптимальные стратегии и , что и игра с матрицей А", причем цена игры

v' = v" – с = - 3 = .

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

Р*= и Q*=

и цену игры v = v' = .

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

Проверить правильность решения игры можно с помощью критерия оптимальности стратегий. Для этого в неравенства M(P_i, Q*) ≤ v≤ М(Р*, Q_j) следует подставить компоненты найденных оптимальных стратегий Р* и Q*, компоненты чистых стратегий Р _i(i = 1, 2, 3) и Q_j (j = 1, 2, 3, 4, 5) и цену игры v = .

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

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

Оптимальная смешанная стратегия первого игрока (игрока A) имеет вид