Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Решение матричных игр симплексным методом

Пусть игра m × n задана платежной матрицей

.

Игрок A применяет стратегии A ₁, A ₂,..., A_m, а игрок B – стратегии B ₁, B ₂,..., B_n.

Будем считать, что данная игра не имеет решения непосредственно в чистых стратегиях (нет седловой точки), и, значит, оптимальное решение необходимо искать в области смешанной стратегии.

Смешанными стратегиямиигроков A и B называют векторы P = (p₁, p₂,…, p_m) и Q = (q ₁, q ₂,..., q_n), координаты которых равны вероятностям применения игроками своих чистых стратегий A ₁, A ₂,..., A_m и B ₁, B ₂,..., B_n соответственно.

События, состоящие в том, что игроки применяют какую-либо из своих чистых стратегий, образуют для каждого игрока полную группу событий. Следовательно, сумма координат векторов P и Q равна единице:

p ₁ + p ₂+ … + p_m = 1,

q ₁ + q ₂+ … + q_n = 1.

Кроме того, по свойству вероятности, для координат смешанных стратегий выполняются неравенства:

i =1,…, m,

j =1,…, n.

Оптимальная стратегия P^* обеспечивает игроку A средний выигрыш, не меньший цены игры ν, при любой стратегии игрока B и выигрыш, равный цене игры ν, при оптимальной стратегии Q^* игрока B.

Без ограничения общности полагаем далее, что ν > 0. Применяя оптимальную стратегию P^* против любой чистой стратегии Q_j игрока B, игрок A получает средний выигрыш или математическое ожидание выигрыша

a_j = a _{1 j} p ₁ + a _{2 j} p ₂ +... + a_mj p_m ≥ ν.

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

.

Разделив каждое из неравенств на цену игры ν и вводя новые переменные

, ,…, ,

получим систему

.

Целевую функцию для игрока A найдем, учитывая, что он стремится получить максимальный выигрыш в игре. Разделив равенство

p ₁ + p ₂+ … + p_m = 1

на цену игры ν, получим

,

которое будет иметь наименьшее значение при достижении игроком A максимального выигрыша. Поэтому в качестве целевой функции можно взять функцию

F (X) = x ₁ + x ₂ +... + x_m

и задачу линейного программирования сформулировать следующим образом: определить значения переменных x_i ≥ 0, i =1,…, m, так, чтобы они удовлетворяли линейным ограничениям

(5.1)

и при этом целевая функция F (X) = x ₁ + x ₂ +... + x_m имела минимальное значение.

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

F (X^*) = min F (X).

Находим цену игры ν:

.

Вычисляем координаты смешанной оптимальной стратегии P^* игрока A:

p_i = ν x_i, i =1,…, m.

Чтобы найти оптимальную стратегию игрока B, составляем двойственную к рассмотренной задачу и решаем ее. Двойственная задача, т.е. задача игрока В имеет ограничения

(5.2)

и целевую функцию Z(Y) = y ₁ + y ₂ +…+ y_n → max.

Решая эту задачу получаем оптимальную стратегию и вычисляем координаты оптимальной смешанной стратегии Q^* игрока B:

q_i = ν y_j, j =1,…, n.

В ходе решения двойственной задачи определяется максимальное значение целевой функции Z (Y^*) = max Z (Y), и цена игры может быть определена из равенства

.

Таким образом, найдено оптимальное решение для игры.

Поскольку задачи (5.1) и (5.2) образуют пару двойственных задач, нет необходимости решать обе задачи.

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

.

Определить оптимальный план продажи товаров.

Решение. Торговая фирма может применить три стратегии продаж П₁, П₂, П₃, а конъюнктура рынка и спрос покупателей – стратегии К₁, К₂, К₃. Обозначим вероятность применения торговой фирмой стратегий П₁, П₂, П₃ как р ₁, р ₂, р ₃, вероятность использования стратегий К₁, К₂, К₃ как q ₁, q ₂, q ₃.

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

где .

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

,

y_j ≥ 0, j = 1, 2, 3,

где .

Решая задачу для второго игрока симплекс-методом, получаем:

, .

Цена игры .

Так как , то , , .

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

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

.

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