09 - Лекция

Стратегия

Мы должны помочь принять правильную стратегию. Чтобы их интересы соединились.
Интерес первого игрока - заработать больше денег
Интерес второго игрока - потерять меньше денег
То есть должна быть нулевая сумма

Игра парная
Ходы личные
Игра с нулевой суммой

Способ решения смежной стратегии методов ЗЛП

Двойственные задачи

Если нет седловой точки, то используем метод Смешанной стратегии

Под смешанной стратегией понимается вектор. Решив игру, мы найдем вектор. В этом векторе каждый элемент означает вероятность выбора стратегии. Если у первого игрока 4 стратегии, то в векторе 4 элемента. Каждый элемент это число от 0 до 1, то бишь процент успеха стратегии.

Любую игру можно решить с помощью смешанной стратегией.

Пример:
$f = 3 x_{1} + 4 x_{2} + 1 x_{3} \to m a x$ , $3 x_{1}$ - вектор С
$5 x_{1} + 12 x_{2} + 8 x_{3} \leq 100$
$10 x_{1} + 4 x_{2} + 7 x_{3} \leq 80$
$x_{j} \geq 0$

$Z = 100 y_{1} + 80 y_{2} \to m i n$
$5 y_{1} + 10 y_{2} \geq 3$
$12 y_{1} + 4_{y} 2 \geq 4$
$8 y_{1} + 7 y_{2} \geq 1$
$y_{i} \geq 0$

Правила

В задаче в первой ищется максимум, в другой минимум
Коэффициенты при переменных целевой функции одной задачи являются свободными членами в ограничениях второй задачи
В ограничениях задачи на минимум знак $\geq$ , а в задаче на максимум знак $\leq$ .
Коэффициенты в системе ограничений описываются матрицами транспонированными относительно друг-друга.
Число неравенств одной задачи совпадает с числом переменных другой задачи.
Условие неотрицательности сохраняется.

Задача:
Задана матрица

[\begin{matrix} 2 & 1 & 0 \\ 3 & 0 & 1 \\ 1 & 2 & 4 \end{matrix}]

Ищем по столбцам максимум, а по строкам минимум

[\begin{matrix} 2 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 \\ 1 & 2 & 4 & 1 \\ 3 & 2 & 4 \end{matrix}]

В оставшейся ячейке инвертируем принцип. По новой строке ищем минимум, а по столбцу максимум

[\begin{matrix} 2 & 1 & 0 & 0 \\ 3 & 0 & 1 & 0 \\ 1 & 2 & 4 & 1 \\ 3 & 2 & 4 & 2 / 1 \end{matrix}]

Симплекс метод

$f = x_{1} + x_{2} + x_{3} \to m i n$
$2 x_{1} + 3 x_{2} + 1 x_{3} \geq 1$
$x_{1} + 2 x_{3} \geq 1$
$x_{2} + 4 x_{3} \geq 1$
$x_{j} \geq 0$

$f = y_{1} + y_{2} + y_{3} \to m a x$
$2 y_{1} + y_{2} \leq 1$
$3 y_{1} + y_{3} \leq 1$
$y_{1} + 2 y_{2} + 4 y_{3} \leq 1$
$y_{j} \geq 0$

[\begin{matrix} Б а з и с & B & y_{1} & y_{2} & y_{3} & y_{4} & y_{5} & y_{6} \\ y_{4} & 0 & 0 & 0 & - \frac{5}{2} & 1 & - \frac{1}{2} & - \frac{1}{2} \\ y_{1} & \frac{1}{3} & 1 & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\ y_{2} & \frac{1}{3} & 0 & 1 & \frac{11}{6} & 0 & - \frac{1}{6} & \frac{1}{2} \\ Z (y_{3}) & \frac{2}{3} & 0 & 0 & \frac{7}{6} & 0 \end{matrix}]

$y_{1} = \frac{1}{7}$
$y_{2} = 0$

Каждый из игроков a и b записывает одно из чисел: 1, 4, 6, 9
Затем они показывают одновременно написанные.
Если оба числа четные - то игрок a выигрывает столько очков какова сумма этих чисел.
Если разной четности, то выигрывает игрок b.
Составьте платежную матрицу. Найдите верхнюю и нижнюю матрицу частицу цепи игры.

1 4 6 9
Положительное число - победа первого игрока
Отрицательное число - победа второго игрока

[\begin{matrix} B_{1} (1) & B_{2} (4) & B_{3} (6) & B_{4} (9) \\ A_{1} (1) & 2 & - 5 & - 7 & 10 \\ A_{2} (4) & - 5 & 8 & 10 & - 13 \\ A_{3} (6) & - 7 & 10 & 12 & - 15 \\ A_{4} (9) & 10 & - 13 & - 15 & 18 \end{matrix}]

[\begin{matrix} B_{1} (1) & B_{2} (4) & B_{3} (6) & B_{4} (9) & M I N \\ A_{1} (1) & 2 & - 5 & - 7 & 10 & - 7 \\ A_{2} (4) & - 5 & 8 & 10 & - 13 & - 13 \\ A_{3} (6) & - 7 & 10 & 12 & - 15 & - 15 \\ A_{4} (9) & 10 & - 13 & - 15 & 18 & - 15 \\ M A X & 10 & 10 & 12 & 18 & 10 / - 7 \end{matrix}]

Строка $A_{1} (1)$ является максиминной, ибо в ней минимальный элемент совпадает с элементом на пересечении $M A X$ и $M I N$

Столбец $B_{1} (1)$ или $B_{2} (4)$ являются максиминными, ибо в них максимальный элемент совпадает с элементом на пересечении $M A X$ и $M I N$

Найдите седловую точку для:

[\begin{matrix} 4 & 2 & 3 & 2 \\ 6 & 1 & - 1 & - 3 \\ 9 & - 2 & - 5 & 1 \end{matrix}]

[\begin{matrix} 4 & 2 & 3 & 2 & 2 \\ 6 & 1 & - 1 & - 3 & - 3 \\ 9 & - 2 & - 5 & 1 & - 2 \\ 9 & 2 & 3 & 2 \end{matrix}]

[\begin{matrix} 4 & 2 & 3 & 2 & 2 \\ 6 & 1 & - 1 & - 3 & - 3 \\ 9 & - 2 & - 5 & 1 & - 2 \\ 9 & 2 & 3 & 2 & 2 / 2 \end{matrix}]

!Pasted image 20241030131839.png

Седловые точки: ( $A_{1}$ ; $B_{2}$ )( $A_{1}$ ; $B_{4}$ )