Задачи теории игр и линейное программирование.

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

Пусть имеется два игрока, один из которых может выбрать тую стратегию из m своих возможных, а второй - тую стратегию из n своих возможных. В результате первый игрок выигрывает величину а второй ее проигрывает. Из чисел составим матрицу:

.

Строки матрицы соответствуют стратегиям первого игрока, а столбцы – стратегиям второго. Эти стратегии называются чистыми.

Определение 1. Матрица А называется платежной матрицей игры.

Определение 2. Число называется нижней ценой игры, а число называется верхней ценой игры.

Определение 3.Если , то число v называется ценой игры.

Игра, для которой , называется игрой с седловой точкой.

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

Определение 4.Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется смешанной стратегией данного игрока.

Из определения 4 следует, что сумма компонент указанного вектора равно единице, а сами компоненты не отрицательны. Обычно смешанную стратегию первого игрока обозначают как вектор , а смешанную стратегию второго – как вектор ., где , , , .

Если - оптимальная стратегия первого игрока, а - оптимальная стратегия второго игрока, то число

называется ценой игры.

Определение оптимальных стратегий и цены игры и составляет процесс нахождения решения игры.

Приведем примеры решения игр , и .

Пример 4. Найти решение игры, заданной матрицей и дать геометрическую интерпретацию этого решения.

Решение. Прежде всего проверим наличие седловой точки у данной матрицы. Для этого найдем минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5).Значит, нижняя цена игры , а нижняя цена игры . Так как , то решением игры являются смешанные оптимальные стратегии, а цена игры заключена в пределах .

Предположим, что для игрока А стратегия задается вектором . Тогда при применении игроком В чистой стратегии или игрок А получит средний выигрыш, равный цене игры, т.е.

Помимо этих двух уравнений, добавляем уравнение связи . Решая полученную систему трех уравнений с тремя неизвестными, найдем , , .

Найдем теперь оптимальную стратегию для игрока В. Пусть для него стратегия задается вектором . Тогда

(1)

Решая полученную систему, найдем , .

Следовательно, решением игры являются смешанные стратегии , , а цена игры .

Дадим геометрическую интерпретацию данной игры. Для этого на плоскости введем систему координат и на оси отложим отрезок единичной длины , каждой точке которого поставим в соответствие некоторую смешанную стратегию (РИС.3).