Лекция 12. Сведение матричной игры к задаче линейного программирования

Решение.

Пример 2

Найти решение матричной игры, заданной матрицей выигрышей первого игрока.

	B1	B2
A1
A2
А3
А4

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

a. Найдем нижнюю цену игры:

b. Найдем верхнюю цену игры:

c. Нижняя цена игры не равна верхнее цены игры, следовательно, седловой точки у заданной матрицы выигрышей нет и решения в чистых стратегиях отсутствует. Поэтому решение необходимо искать в области смешанных стратегий.

2. Матрица имеет размерность 4 ^x 2. В этом случае строим прямые, соответствующие стратегиям игрока 1.

3. Ломанная a₁₁Ka₄₂ соответствует верхней границе выигрыша игрока 1, а отрезок – перпендикуляр из точки K до оси x - цене игры.

Таким образом, полезными стратегиями первого игрока (Полезные стратегии – это те стратегии, который входят в состав оптимальной смешанной стратегии) являются стратегии А1 и А4, так как точка К образована пересечением именно этих стратегий.

4. Тогда можно перейти к матрице А* 2 х 2:

	B1	B2
A1
А4

5. Находим оптимальную смешанную стратегию первого игрока, применив формулу (43):

Следовательно, оптимальная смешанная стратегия первого игрока X=. Стратегии А₂ и А₃ не входят в оптимальную смешанную стратегию (это видно из рисунка), поэтому частота (вероятность) их использования равна нулю.

6. Находим цену игры, применив формулу (44):

Проверка: цена игры должна удовлетворять следующему неравенству:

Это неравенство выполнено:

7. Находим оптимальную смешанную стратегию второго игрока, используя формулу (45):

Следовательно, оптимальная смешанная стратегия второго игрока Y=.

Ответ: Оптимальное решение находится в области смешанных стратегий. Оптимальная стратегия первого игрока X=, оптимальная стратегия второго игрока Y=, цена игры.

Предположим, что цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Итак,пусть дана матричная игра с матрицей А порядка m^х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х₁,..., х_m), y = (y₁,..., y_n) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

(46)

(47)

Разделим все уравнения и неравенства в (46) и (47) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения:

,,

Тогда (46) и (47) перепишется в виде:

,,,,

,,,.

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

,. (48)

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

,. (49)

Формулы (48) и (49) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения p_i, q_j и u. Тогда смешанные стратегии, т.е. x_i и y_j получаются по формулам:

(50)

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

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим теперь пару взаимно-двойственных задач:

Решим вторую из них

Б.п.	q1	q2	q3	q4	q5	q6	Решение	å	Отношение
	-1	-1	-1					-3
q4									—
q5
q6									—

Б.п.	q1	q2	q3	q4	q5	q6	Решение	å	Отношение
		-1
q4
q3									—
q6

Б.п.	q1	q2	q3	q4	q5	q6	Решение	å	Отношение
q2
q3
q6

Из оптимальной симплекс-таблицы следует, что

(q₁, q₂, q₃) = (0;; 1),

а из соотношений двойственности следует, что

(p₁, p₂, p₃) = (; 1; 0).

Следовательно, цена игры с платёжной матрицей А₁ равна

.,

а игры с платёжной матрицей А:

.

При этом оптимальные стратегии игроков имеют вид:

Х = (х₁, х₂, х₃) = (uр₁; uр₂; uр₃) = =

Y = (y₁, y₂, y₃) = (uq₁; uq₂; uq₃) = =.

Дата добавления: 2014-01-11