№21. Решение матричных игр с использованием графического метода

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

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Плотников А. Д. Математическое программирование: экспресс-курс. - Мн.: Новое знание, 2007. С. 147-156.
2. Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 446-465.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Опишите понятие матричной игры.
2. Опишите понятие стратегии матричной игры.
3. Опишите понятие платежной матрицы матричной игры.
4. Опишите правила выбора стратегии в матричной игре.
5. Опишите понятие нижней и верхней цены матричной игры.
6. Опишите понятие седловой точки матричной игры.
7. Дайте понятие смешанной стратегии игрока в матричной игре.
8. Приведите алгоритм решения матричной игры с использованием графического метода.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Пусть игра задана платежной матрицей . По оси абсцисс отложим единичный отрезок А₁А₂, где точка А₁ (0, 0) изображает стратегию А₁, А₂ (1, 0) – стратегию А₂, а каждая промежуточная точка S_A этого отрезка изображает смешанную стратегию первого игрока P_A = (p₁, p₂), где p₁– расстояние от точки S_A до A₂, p₂–расстояние от точки S_A до A₁. Выигрыш игрока A будем откладывать на вертикальных отрезках.

Случай 1. Если игрок B применит стратегию В₁, то выигрыш игрока A при стратегии А₁ равен а₁₁, поэтому на оси ординат отложим отрезок А₁В₁ = а₁₁. При применении игроком A стратегии А₂ выигрыш равен а₂₁, отложим этот отрезок на перпендикуляре из точки А₂, обозначим полученную точку В₁'. Ордината любой точки М₁ отрезка В₁В₁′ равна среднему выигрышу игрока A при применении смешанной стратегии S_A(действительно, этот выигрыш равен математическому ожиданию случайной величины, т.е. a₁₁p₁ + a₂₁p₂). Запишем уравнение прямой В₁В₁′:

, т.е. y=a₁₁+x(a₂₁-a₁₁),

тогда при x = p₂ получим

y = a₁₁ + p₂a₂₁ – p₂a₁₁ = a₁₁(1-p₂) + p₂a₂₁ = a₁₁p₁ + a₂₁p₂

Случай 2. Если игрок B применяет стратегию В₂, то аналогично откладываем отрезки а₁₂ и а₂₂ и получаем отрезок В₂В₂′. Ордината любой точки М₂ отрезка В₂В₂′ – выигрыш игрока A, если A применяет смешанную стратегию S_A, а B – стратегию В₂. Построим нижнюю границу выигрыша игрока А – ломаную В₁ NВ₂′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р₁, р₂).

Аналогично находится оптимальная стратегия Q = (q₁ , q₂) игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А₂NА₁′ и брать точку N с наименьшей ординатой.

Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. Q = (q₁ , q₂).

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

Пример. Дана матричная игра с платёжной матрицей

Найти ее решение графическим способом.

Решение.

Нижняя цена игры α = 1,5, верхняя цена игры β = 2. Так как α≠β, седловой точки нет. Так как a₁₁ = 1,5, a₂₁ = 2 строим точки B₁(0;1,5) и B₂(1;2), соединяем их отрезком. Так как a₁₂ = 3, a₂₂ = 1 строим точки B₂(0;3) и B₂’(1;1), соединяем их отрезком.

Уравнение прямой В₁В₁′:

т. е. y = 0,5x + 1,5;

уравнение В₂В₂′: , т. е. y = 3-2x.

Найдем точку N пересечения прямых В₁В₁′ и В₂В₂′, для чего решим систему уравнений:

т. е. N(0,6; 1,8), откуда p₂= 0,6; p₁= 0,4; γ = 1,8 – цена игры.

Аналогично строим точки А₁(0; 1,5) и А₁′(1;3), А₂(0; 2) и А₂′(1; 1) и находим точку M пересечения прямых А₁А₁′ и А₂А₂′.

Ответ: смешанная стратегия игрока А: P_A= (0,4; 0,6), игрока В: Q_B = (0,8; 0,2); цена игры 1,8.

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Опишите понятие матричной игры.
2. Опишите понятие стратегии матричной игры.
3. Опишите понятие платежной матрицы матричной игры.
4. Опишите правила выбора стратегии в матричной игре.
5. Опишите понятие нижней и верхней цены матричной игры.
6. Опишите понятие седловой точки матричной игры.
7. Дайте понятие смешанной стратегии игрока в матричной игре.
8. Приведите алгоритм решения матричной игры с использованием графического метода.

ДОМАШНЕЕ ЗАДАНИЕ:

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