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

Рассмотрим игру mxn, определенную матрицей А =

По теореме 3 для оптимальной стратегии первого игрока U^*(u₁^*, u₂^*, …, u_m^*) и цены игрока ν выполняется неравенство

Пусть ν > 0. Разделим обе части неравенства на ν.

(*)

Из обозначения выразим u_i^*: u_i^* = ν * y_i^*. Т.к. или .

Т.к. первый игрок стремится получить максимальный выигрыш, то величина должна быть минимальной, следовательно надо найти минимальной значение f^* = при условии (*), т.е. если .

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

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

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

Найти максимум функции F = при условиях .

Двойственная задача: Найти минимум функции f^* = , если , у_i ≥ 0 (i = 1, 2,.., m).

Итак, процесс нахождения решения игры включает следующие этапы:

1. Составить пару двойственных задач линейного программирования, эквивалентных данной матричной игре.

2. Определить оптимальные решения пары двойственных задач.

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

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

Решение.

1. Составим двойственную пару задач линейного программирования. Прямая задача:

х₁ + 2х₂ ≤ 1

х₁ + х₃ ≤ 1

2х₁ + х₂ ≤ 1

х₁, х₂, х₃ ≥ 0

f = x₁ + x₂ + x₃ → max

Обратная задача:

у₁ + у₂ + 2у₃ ≥ 1

2у₁ + у₃ ≥ 1

у₂ ≥ 1

у₁, у₂, у₃ ≥ 0

f = y₁ + y₂ + y₃ → min

2. С помощью симплекс-метода определяются решения двойственных задач.

u_i^* = y_i * ν, z_i^* = x_i * ν => u^*(1/2*2/3, 2/3,0) z^* (0, 1/3, 2/3)

Задачи для самостоятельного решения.

1. Для следующих платежных матриц определить верхнюю и нижнюю цену игры, минимаксные стратегии и оптимальные решения игры, если существует седловая точка.

;

1. Решить графическим методом игру, заданную матрицей
2. Предприятие может выпускать три вида продукции (А1, А2, А3), получая при этом прибыль зависящую от спроса, который может быть в одном из следующих состояний (В1, В2, В3). Дана матрица (таблица), элементы которой a_ij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса. Определить оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределенным.

Поиск по сайту: