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

Пусть задана платежная матрица игры

Для оптимальной стратегии первого игрока и цены игры u выполняется неравенство или (разделив на u) обозначая получим:

Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине ¹/_u. Ñ учетом этого определение оптимальной стратегии сводится к нахождению минимума функции при условиях

(j = 1.. n); y_i ³0 (i = 1.. m).

Аналогично определение оптимальной стратегии второго игрока сводится к нахождению максимума функции при условиях

(i = 1.. m); x_j ³0 (j = 1.. n), где = z_j /u.

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

Прямая задача Двойственная задача

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

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

составляют пару двойственных задач, эквивалентных данной игре;

определяют оптимальные планы двойственных задач;

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

Пример 9.9

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

Решение.

Пара двойственных задач:

Прямая max L = x 1 + x 2 + x 3; x 1 + 2 x 2 £ 1; x 1 + x 3 £ 1; 2 x 1 + x 2 £ 1; x 1, x 2, x 3 ³ 0.   x 0 = (0; 1/2; 1).

Двойственная min L = y 1 + y 2 + y 3; y 1 + y 2 + 2 y 3 ³ 1; 2 y 1 + y 3 ³ 1; y 2 ³ 1; y 1, y 2, y 3 ³ 0.   y 0 = (1/2; 1; 0).

Из решения пары задач:

u ⁰ = (¹/₃; ²/₃; 0);

z ⁰ = (0; ¹/₃; ²/₃).

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

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

.

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

n Если каждая матричная игра имеет оптимальные стратегии, то не всякая задача линейного программирования имеет решения.

Пример 9.10

max (2 x 1 + 3 x 2); 2 x 1 + x 2 £ 10; – x 1 + 3 x 2 £ 12; x 1, x 2 ³ 0.

min (10 y 1 + 12 y 2); 2 y 1 – y 2 ³ 2; y 1 + 3 y 2 ³ 3; y 1, y 2 ³ 0.

L ⁰ = 19,71.

Решение.

Тогда матрица игры будет