Составить задачу линейного программирования для нахождения оптимальной стратегии игрока A

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

Дана матричная игра с матрицей выигрышей игрока A:

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

Нужно составить задачу линейного программирования для нахождения оптимальной стратегии игрока A.

Теория

Игрок A выбирает стратегию x = (x_1, x_2), где x_1, x_2 \geq 0 и x_1 + x_2 = 1 (вероятности выбора каждой стратегии).

Оптимальная стратегия игрока A решается через задачу линейного программирования:

 \begin{cases} \text{max } z = v \ 4x_1 + 3x_2 \geq v \ 2x_1 + 8x_2 \geq v \ x_1 + x_2 = 1 \ x_1, x_2 \geq 0 \end{cases} 

Здесь v — минимальный гарантированный выигрыш игрока A.

Преобразуем задачу

Вместо равенства x_1 + x_2 = 1 можно использовать нормировку, а в условии задачи линейного программирования обычно ставят:

• Оптимизировать z = x_1 + x_2 \to \min или \max в зависимости от формулировки
• Условия:

 \begin{cases} 4x_1 + 3x_2 \geq 1 \ 2x_1 + 8x_2 \geq 1 \ x_1, x_2 \geq 0 \end{cases} 

где x_1, x_2 — "взвешенные" вероятности, сумма которых не обязательно равна 1, а оптимальное значение z = x_1 + x_2 будет минимальным.

Анализ вариантов

1. z = x_1 + x_2 \to \max,
   условия:
    \begin{cases} 4x_1 + 3x_2 \leq 1 \ 2x_1 + 8x_2 \leq 1 \ x_1, x_2 \geq 0 \end{cases} 
   — неверно, так как знаки не соответствуют условию игры (условия должны быть с >=).

2. z = x_1 + x_2 \to \min,
   условия:
    \begin{cases} 4x_1 + 3x_2 \geq 1 \ 2x_1 + 8x_2 \geq 1 \ x_1, x_2 \geq 0 \end{cases} 
   — соответствует классической постановке задачи для игрока A.

3. z = x_1 + x_2 \to \min,
   условия:
    \begin{cases} 4x_1 + 2x_2 \geq 1 \ 3x_1 + 8x_2 \geq 1 \ x_1, x_2 \geq 0 \end{cases} 
   — неверно, так как коэффициенты не соответствуют матрице.

4. z = x_1 + x_2 \to \max,
   условия:
    \begin{cases} 4x_1 + 2x_2 \leq 1 \ 3x_1 + 8x_2 \leq 1 \ x_1, x_2 \geq 0 \end{cases} 
   — неверно.

Вывод

Правильная задача линейного программирования для нахождения оптимальной стратегии игрока A — вариант 2.

Правильный ответ: a. 2