2. Задачи теории игр и линейное программирование

.

Сведение задач теории игр к задачам линейного программирования

Рассмотрим игру m×n, определяемую матрицей

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

Прямая задача.

.

Двойственная задача.

.

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

,

.

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

.

Решение.

Составим двойственную пару задач линейного программирования (ЗЛП).

Прямая задача.

.

В каноническом виде:

.

Двойственная задача.

.

Находим симплекс-методом оптимальные планы прямой и двойственной задач.

i	Базис	cб	Р0	1	1	1	0	0	0
				P1	P2	P3	P4	P5	P6
1	Р4	0	1	1	2	0	1	0	0
2	Р5	0	1	1	0	1	0	1	0
3	Р6	0	1	2	1	0	0	0	1
4			0	-1	-1	-1	0	0	0
1	Р4	0	1	1	2	0	1	0	0
2	Р3	1	1	1	0	1	0	1	0
3	Р6	0	1	1	2	1	0	0	1
4			1	0	-1	0	0	1	0
1	Р2	1	1/2	1/2	1	0	1/2	0	0
2	Р3	1	1	1	0	1	0	1	1
3	Р6	0	1/2	3/2	0	0	-1/2	0	0
4			3/2	1/2	0	0	1/2	1	1

; .

Сведение ЗЛП к матричной игре

Если ЗЛП имеет вид:

при ограничениях

,

то соответствующая ей матричная игра определяется квадратной блочной платёжной матрицей порядка m+n+1 вида

,

где А_m×n – матрица коэффициентов при неизвестных системы ограничений ЗЛП; В_m×1 – вектор-столбец свободных членов системы ограничений ЗЛП; С_1×n – вектор-строка коэффициентов при неизвестных целевой функции; - матрицы, транспонированные к А, В, С, (Θ₁) _n×m, (Θ₂)_m×n, (Θ₃)_1×1 – нулевые матрицы (Θ₃ = 0).

Пример. Построить матричную игру, заданную ЗЛП:

при ограничениях

.

Решение. Обозначим:

; , С = (2 3). Тогда

; = (10 12); ; ; ;

Θ₃ = 0; m+n+1 = 2 + 2 + 1 = 5.

Игру, определяемую данной ЗЛП, можно записать матрицей:

.