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

Предмет: Математика
Раздел: Линейное программирование, теория игр

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

 P = \begin{pmatrix} 4 & 2 \ 3 & 8 \end{pmatrix} 

Теория

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

Обозначим вероятности выбора стратегий игроком А как x_1 и x_2, при этом x_1 \geq 0, x_2 \geq 0 и x_1 + x_2 = 1 (сумма вероятностей равна 1).

Оптимальная стратегия игрока А определяется из условия максимизации минимального выигрыша, то есть:

 \max_{x_1, x_2} \min_{j} \sum_{i} x_i p_{ij} 

где p_{ij} — элемент матрицы выигрышей.

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

Введем переменную z — минимальный гарантированный выигрыш игрока А, тогда задача:

 \max z 

при условиях:

 4x_1 + 3x_2 \geq z \ 2x_1 + 8x_2 \geq z \ x_1 + x_2 = 1 \ x_1 \geq 0, x_2 \geq 0 

Преобразуем задачу для стандартного вида линейного программирования

Перенесем z в левую часть, чтобы получить неравенства:

 4x_1 + 3x_2 - z \geq 0 \ 2x_1 + 8x_2 - z \geq 0 

И при этом максимизируем z.

Анализ вариантов из условия

В вариантах задачи переменная z задается как z = x_1 + x_2, что совпадает с условием x_1 + x_2 = 1 (сумма вероятностей).

Сравним условия из вариантов:

• Вариант 2)
   z = x_1 + x_2 \to \min \ 4x_1 + 3x_2 \geq 1 \ 2x_1 + 8x_2 \geq 1 \ x_1 \geq 0, x_2 \geq 0 

• Вариант 3)
   z = x_1 + x_2 \to \min \ 4x_1 + 2x_2 \geq 1 \ 3x_1 + 8x_2 \geq 1 \ x_1 \geq 0, x_2 \geq 0 

Обратите внимание, что в матрице P в условии:

 P = \begin{pmatrix} 4 & 2 \ 3 & 8 \end{pmatrix} 

Коэффициенты в варианте 3 совпадают с элементами матрицы: первая строка (4, 2), вторая (3, 8).

Вывод

Правильная задача линейного программирования для нахождения оптимальной стратегии игрока А — это задача, где:

• максимизируется минимальный выигрыш (минимизация z = x_1 + x_2 в данном случае — это форма, которую используют для преобразования),
• коэффициенты соответствуют строкам матрицы,
• неравенства имеют знак "больше или равно" (для гарантирования минимального выигрыша).

Таким образом, правильный вариант — 2.

Ответ: a. 2