Решение матричной игры методом линейного программирования. Матричные игры: примеры решения задач

15.08.2019

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

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица .

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока - n чистых стратегий. Поскольку рассматривается игра, естественно, что в этой игре есть выигрыши и есть проигрыши.

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

Составим платёжную матрицу:

Если первый игрок выбирает i -ю чистую стратегию, а второй игрок - j -ю чистую стратегию, то выигрыш первого игрока составит a ij единиц, а проигрыш второго игрока - также a ij единиц.

Так как a ij + (- a ij ) = 0 , то описанная игра является матричной игрой с нулевой суммой.

Простейшим примером матричной игры может служить бросание монеты. Правила игры следующие. Первый и второй игроки бросают монету и в результате выпадает "орёл" или "решка". Если одновременно выпали "орёл" и "орёл" или "решка" или "решка", то первый игрок выиграет одну единицу, а в других случаях он же проиграет одну единицу (второй игрок выиграет одну единицу). Такие же две стратегии и в распоряжении второго игрока. Соответствующая платёжная матрица будет следующей:

Задача теории игр - определить выбор стратегии первого игрока, которая гарантировала бы ему максимальный средний выигрыш, а также выбор стратегии второго игрока, которая гарантировала бы ему максимальный средний проигрыш.

Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

Сначала определим величину выигрыша первого игрока, если он использует i -ю чистую стратегию. Если первый игрок использует i -ю чистую стратегию, то логично предположить, что второй игрок будет использовать такую чистую стратегию, благодаря которой выигрыш первого игрока был бы минимальным. В свою очередь первый игрок будет использовать такую чистую стратегию, которая бы обеспечила ему максимальный выигрыш. Исходя из этих условий выигрыш первого игрока, который обозначим как v 1 , называется максиминным выигрышем или нижней ценой игры .

При для этих величин у первого игрока следует поступать следующим образом. Из каждой строки выписать значение минимального элемента и уже из них выбрать максимальный. Таким образом, выигрыш первого игрока будет максимальным из минимальных. Отсюда и название - максиминный выигрыш. Номер строки этого элемента и будет номером чистой стратегии, которую выбирает первый игрок.

Теперь определим величину проигрыша второго игрока, если он использует j -ю стратегию. В этом случае первый игрок использует такую свою чистую стратегию, при которой проигрыш второго игрока был бы максимальным. Второй игрок должен выбрать такую чистую стратегию, при которой его проигрыш был бы минимальным. Проигрыш второго игрока, который обозначим как v 2 , называется минимаксным проигрышем или верхней ценой игры .

При решении задач на цену игры и определение стратегии для определения этих величин у второго игрока следует поступать следующим образом. Из каждого столбца выписать значение максимального элемента и уже из них выбрать минимальный. Таким образом, проигрыш второго игрока будет минимальным из максимальных. Отсюда и название - минимаксный выигрыш. Номер столбца этого элемента и будет номером чистой стратегии, которую выбирает второй игрок. Если второй игрок использует "минимакс", то независимо от выбора стратегии первым игроком, он проиграет не более v 2 единиц.

Пример 1.

Наибольший из наименьших элементов строк - 2, это нижняя цена игры, ей соответствует первая строка, следовательно, максиминная стратегия первого игрока первая. Наименьший из наибольших элементов столбцов - 5, это верхняя цена игры, ей соответствует второй столбец, следовательно, минимаксная стратегия второго игрока - вторая.

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

Итак, гарантированный выигрыш первого игрока:

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

Первый игрок использует такую свою чистую стратегию, чтобы проигрыш второго игрока был максимальным. Этот проигрыш обозначается так:

Второй игрок должен выбрать свою чистую стратегию так, чтобы его проигрыш был минимальным. Этот проигрыш (минимакс) обозначается так:

Ещё пример из этой же серии.

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

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:

Наибольший из наименьших элементов строк - 3, это нижняя цена игры, ей соответствует вторая строка, следовательно, максиминная стратегия первого игрока вторая. Наименьший из наибольших элементов столбцов - 5, это верхняя цена игры, ей соответствует первый столбец, следовательно, минимаксная стратегия второго игрока - первая.

Седловая точка в матричных играх

Если верхняя и нижняя цена игры одинаковая, то считается, что матричная игра имеет седловую точку. Верно и обратное утверждение: если матричная игра имеет седловую точку, то верхняя и нижняя цены матричной игры одинаковы. Соответствующий элемент одновременно является наименьшим в строке и наибольшим в столбце и равен цене игры.

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

В этом случае матричная игра имеет решение в чистых стратегиях .

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

Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 5. То есть . Цена игры равна значению седловой точки . Максиминная стратегия первого игрока - вторая чистая стратегия, а минимаксная стратегия второго игрока - третья чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.

Решить задачу на матричную игру самостоятельно, а затем посмотреть решение

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

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Матричные игры с оптимальной смешанной стратегией

В большинстве случаев матричная игра не имеет седловой точки, поэтому соответствующая матричная игра не имеет решений в чистых стратегиях.

Но она имеет решение в оптимальных смешанных стратегиях. Для их нахождения нужно принять, что игра повторяется достаточное число раз, чтобы на основании опыта можно было предположить, какая стратегия является более предпочтительной. Поэтому решение связывается с понятием вероятности и среднего (математического ожидания). В окончательном же решении есть и аналог седловой точки (то есть равенства нижней и верхней цены игры), и аналог соответствующих им стратегий.

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

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

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

Если первый игрок использует смешанную стратегию p , а второй игрок - смешанную стратегию q , то имеет смысл математическое ожидание выигрыша первого игрока (проигрыша второго игрока). Чтобы его найти, нужно перемножить вектор смешанной стратении первого игрока (который будет матрицей из одной строки), платёжную матрицу и вектор смешанной стратегии второго игрока (который будет матрицей из одного столбца):

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

Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока , а смешанная стратегия второго игрока .

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

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

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

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

В таком случае для функции E существует седловая точка , что означает равенство .

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

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

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

Функция цели в прямой задаче линейного программирования:

Система ограничений в прямой задаче линейного программирования:

Функция цели в двойственной задаче:

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

В соответствии определениям предыдущего параграфа и координатами оптимальных планов, в силе следующие смешанные стратегии первого и второго игроков:

Математики-теоретики доказали, что цена игры следующим образом выражается через линейные формы оптимальных планов:

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

Нам, практикам, остаётся лишь использовать эту формулу для решения матричных игр в смешанных стратегиях. Как и формулы для нахождения оптимальных смешанных стратегий соответственно первого и второго игроков:

в которых вторые сомножители - векторы. Оптимальные смешанные стратегии также, как мы уже определили в предыдущем параграфе, являются векторами. Поэтому, умножив число (цену игры) на вектор (с координатами оптимальных планов) получим также вектор.

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

Найти цену игры V и оптимальные смешанные стратегии и .

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

Находим линейную форму оптимальных планов как сумму найденных координат.

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

Удаляем, если они есть, доминируемые строки и доминирующие столбцы. На их месте в оптимальных стратегиях игроков соответствующие компоненты будут равны нулю.

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

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

Пример индивидуального решения.

Пример. Найти решение игры, заданной платежной матрицей

Прежде всего, проверим, имеет ли матрица седловую точку. Наименьший элемент -3 первой строки не является наибольшим в третьем столбце; наименьший элемент -1 второй строки не является наибольшим в первом столбце; наконец, наименьший элемент 2 третьей строки является одновременно наибольшим в третьем столбце. Следовательно, матрица имеет седловую точку (3, 3), в которой расположен элемент а зз = 2. Значит, игра имеет решение в чистых стратегиях, а именно:

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

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

v = 2 - цена игры.

Пример. Найти решение игры, заданной платежной матрицей

В матрице нет седловой точки, следовательно, игра имеет решение в смешанных стратегиях.

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

Прибавив ко всем элементам матрицы А", например, число с = 3, получим матрицу

все элементы которой неотрицательны, а элементы второй строки строго положительны.

Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей А", ·а коэффициенты при неизвестных в целевой функции и свободные члeны неравенств были бы равны единице.

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем её к основной при помощи дополнительных неизвестных x 4 ≥0, x 5 ≥0. В результате получим следующую задачу.

x j ≥ 0 (j = 1,…,5),

f (X ) = x 1 + x 2 + x 3 → тах.

Задача - каноническая и, применив к ней алгоритм симплекс-метода, получим симплексные таблицы вида

Из столбца базисных переменных, и индексной строки выпишем оптимальные планы пары двойственных задач, а именно:

f(X*) = g(Y*) =

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

v" = = ;

= v" = = ;

= v" = =

Игра с матрицей А" будет иметь те же оптимальные стратегии и , что и игра с матрицей А", причем цена игры

v" = v" - с = - 3 = .

И, наконец, исходная игра с матрицей А имеет оптимальные стратегии

Р*= и Q*=

и цену игры v = v" = .

Оптимальные стратегии Р* и Q * мы получили из оптимальных стратегий и , приписав нули на месте удаленных строк и столбцов.

Проверить правильность решения игры можно с помощью критерия оптимальности стратегий. Для этого в неравенства M(P i , Q*) ≤ v≤ М(Р*, Q j) следует подставить компоненты найденных оптимальных стратегий Р* и Q*, компоненты чистых стратегий Р i (i = 1, 2, 3) и Q j (j = 1, 2, 3, 4, 5)

и цену игры v = .

Заметим, что сводить задачу теории игр к паре двойственных задач ЛП следует только тогда, когда все элементы хотя бы одной строки платежной матрицы строго положительны . В этом случае обе задачи будут иметь оптимальные планы, из которых можно получить оптимальные стратегии игроков. В противном случае в исходной задаче целевая функция может оказаться неограниченной, а в двойственной задаче не будет ни одного плана. Так, в после примере, если составить пару двойственных задач в игре с матрицей

то в задаче 1 целевая функция будет не ограничена сверху на множестве планов, а в задаче 2 вообще не будет планов, однако, как мы убедились, выше, игра с матрицей А" имеет решение.

Оптимальная смешанная стратегия первого игрока (игрока A ) имеет вид

оптимальная смешанная стратегия второго игрока (игрока B ) имеет вид:

Поскольку данная матричная игра была упрощена путём удаления заведомо невыгодных стратегий и её окончательное решение имеет вид:

Решение игр графическим методом.

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Пример1.

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

Нижней границей выигрыша для игрока А является ломаная В 3 КВ 4 ,. Стратегии В 3 , и В 4 являются активными стратегиями игрока В. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Второму игроку невыгодно применять стратегии В 1 и В 2 , у 1 = у 2 = 0. Решение игры сводится к решению игры с матрицей (2х2).

x 1 = 2/5, х 2 = 3/5; y 3 = 3/5, у 4 = 2/5; v = 11/5.

Ответ.

X (2/5, 3/5) и Y (0, 0,3/5, 2/5), цена игры составляет v = 11/5.

если первый игрок с вероятностью 2/5 будет применять первую стратегию и с вероятностью 3/5 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 11/5;

если второй игрок с вероятностью 3/5 будет применять третью стратегию, с вероятностью 2/5 четвертую и не будет использовать первую и вторую стратегии, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 11/5.

Пример2. Найти решение игры, заданной матрицей

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

Верхней границей проигрыша для игрока В является ломаная А 1 КА 4 . Стратегии А 1 и А 2 являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку невыгодно применять стратегии А 3 и А 4 , поэтому вероятность их применения равна нулю, т.е. х 2 = х 3 = 0. Решение игры сводится к решению игры с матрицей (2х2)

По формулам (1)(3) находим оптимальные стратегии и цену игры:

х 1 = 7/8, х 4 = 1/8; у 1 = 3/8, у 2 = 5/8; v = 27/8.

Ответ. Оптимальные смешанные стратегии игроков

X (7/8, 0, 0, 1/8) и Y (3/8, 5/8), цена игры составляет v = 27/8.

Данный ответ означает следующее:

если первый игрок с вероятностью 7/8 будет применять первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;

если второй игрок с вероятностью 3/8 будет применять первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.

Использование компьютерных технологий при изучении темы: «Антагонистические игры».

Для графического решения матричной игры используется Microsoft Word и Microsoft Excel, а для решения матричной игры методами линейного программирования используется Microsoft Excel опция «Поиск решения». Также для расчётов возможно использование программы MATLAB, которая представляет собой высокоуровневый технический вычислительный язык и интерактивную среду для разработки алгоритмов, визуализации и анализа данных, числовых расчетов.

Варианты заданий для самостоятельной работы.

Найти оптимальные стратегии и цену игры, заданной платежной матрицей А.

Рассмотрим т х п ифу с платежной матрицей Без ограничения общности будем считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом, преобразующим заданную матрицу игры, но не изменяющим оптимальных смешанных стратегий игроков). Тем самым, искомая цена игры v - положительное число. Интересы игрока А Из теоремы о свойствах оптимальных смешанных стратегий игроков вытекает, что при любой чистой стратегии игрока В, п, оптимальная смешанная стратегия Р = игрока А обеспечивает его средний выигрыш, не меньший v. Иными словами, выполняются соотношения которые с учетом обозначений Сведение матричной игры к задаче линейного программирования можно записать так Поскольку игрок А стремится сделать свой гарантированный выигрыш максимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче: найти неотрицательные величины удовлетворяющие неравенствам и такие, что их сумма минимальна Интересы игрока В Аналогичным образом заключаем, что оптимальная смешанная стратегия игрока В при любой чистой стратегии Ai игрока m, обеспечивает его средний проигрыш, не больший v. Иными словами, выполняются соотношения которые с учетом обозначений можно записать так Поскольку игрок В стремится сделать свой гарантированный проигрыш минимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче: найти неотрицательные величины, удовлетворяющие неравенствам и такие, что их сумма максимальна п Тем самым, мы получаем следующий важный результат. Теорема 3. Решение матричной игры с положительной платежной матрицей (а,к) равно-сильно решению двойственных задач линейного программирования При этом цена игры где 0 - величина, обратная общему значению оптимальных сумм, а оптимальные значения р и связаны с оптимальными х°{ и yj. посредством равенств Алгоритм решения матричной игры 1-й шаг. Ко всем элементам исходной матрицы игры прибавляется одно и то же положительное число 7 так, чтобы все элементы новой матрицы были строго положительны. 2-й шаг. Решаются двойственные задачи линейного программирования (А) и (В) (например, симплекс-методом, или как-нибудь иначе). Находятся наборы хJ, ук и число 6. 3-й шаг. Строятся оптимальные смешанные стратегии игроков А и Б соответственно 4-й шаг. Вычисляется цена игры Пример 9. Рассмотрим 2x2 игру с матрицей Соответствующие ей задачи линейного программирования имеют вид Решение 1-й шаг. Все элементы платежной матрицы положительны. 2-й шаг. Строим решения обеих задач линейного программирования, пользуясь графическим методом. В результате получаем, что Сведение матричной игры к задаче линейного программирования §4. Примеры задач, сводимых к матричным играм В чистом виде антагонистические конфликты встречаются редко (разве только в боевых действиях и в спортивных состязаниях). Однако довольно часто конфликты, в которых интересы сторон противоположны, при допущении, что множество способов действия сторон конечно, можно моделировать матричными играми. Рассмотрим несколько конкретных ситуаций. Пример 10. «Планирование посева». Сельскохозяйственное предприятие имеет возможность выращивать две культуры - А\ и Необходимо определить, как сеять эти культуры, если при прочих равных условиях их урожаи зависят от погоды, а план посева должен обеспечить наибольший доход (прибыль от реализации выращенной культуры определяется полученным объемом). В зоне рискованного земледелия (а таковой является большая часть России) планирование посева должно осуществляться с учетом наименее благоприятного состояния погоды. Таким образом, одной из сторон выступает сельскохозяйственное предприятие, заинтересованное в том, чтобы получить наибольший доход (игрок А), а другой стороной - природа, способная навредить сельскохозяйственному предприятию в максимальной степени (от нее зависят погодные условия) и преследующая тем самым прямо противоположные цели (игрок В). Принятие природы за противника равносильно планированию посева с учетом наиболее неблагоприятных условий; если же погодные условия окажутся благоприятными, то выбранный план даст возможность увеличить доход. Налицо антагонистический конфликт, в котором у игрока А две стратегии - А\ и Л?, а у игрока В три - //| (засушливое лето), В2 (нормальное лето) и В$ (дождливое лето). В качестве выигрыша игрока А возьмем прибыль от реализации и будем считать, что расчеты прибыли сельскохозяйственного предприятия (в млрд руб.) в зависимости от состояний погоды сведены в следующую матрицу (2 3 б)" Нетрудно заметить, что седловой точки у этой матрицы нет. Поэтому оптимальная стратегия игрока А будет смешанной. Применяя графический мотод, получаем ММ}. Замечание. Здесь мы столкнулись со сравнительно редкой ситуацией, когда оптимальная смешанная стратегия одного из игроков допускает так называемую «физическую» реализацию. Полученное решение сельскохозяйственное предприятие может использовать так: . на | всех плошадей выращивать культуру А\, на I всех плошадей выращивать культуру А2 и получать прибыль в размере, не меньшем млрд руб. Пример 11. «Переговоры о заключении контракта между профсоюзом и администрацией». Рассмотрим фирму, администрация которой ведет переговоры с профсоюзом рабочих и служащих о заключении контракта. Предположим, что платежная матрица, отражающая интересы договаривающихся сторон, имеет следующий вид Выплаты указаны в центах в час и представляют собой среднюю зарплату служащего фирмы вместе со всеми добавками. Тем самым, заданная матрица описывает прибыль профсоюза (игрок А) и затраты администрации фирмы (игрок В). Ясно, что профсоюз стремится максимизировать доходы рабочих и служащих, в то время как администрации хотелось бы минимизировать собственные потери. Нетрудно заметить, что седловой точки у платежной матрицы нот. Кроме того, для дальнейшего анализа существенными являются лишь стратегии А\ и А4 игрока А и стратегии Вi и В4 игрока В (в этом нетрудно убедиться, воспользовавшись правилом доминирования стратегий). В результате соответствующего усечения получим матрицу Элементы матрицы связаны с элементами предыдущей матрицы соотношениями. Воспользовавшись графическим методом, в итоге получим Тем самым, профсоюзу следует выбирать стратегию А\ в 20 % случаев и стратегию А4 в 80 %. Что касается администрации, то ей следует выбирать стратегию В3 с вероятностью 0,4 и стратегию В4 с вероятностью 0,6. При этом ожидаемая цена игры равна 53. Замечание. Следует отмстить, что если процесс переговоров будет повторяться много раз, то среднему должно сходиться к ожидаемому значению 53. Если же переговоры пройдут лишь единожды, то реальный результат получится при выборе каждым игроком некоторой своей чистой стратегии. Поэтому один из игроков, профсоюз или администрация, будет неудовлетворен. Пример 12. «Локальный конфликт». Рассмотрим войну между двумя небольшими государствами А и В, которая ведется в течение 30 дней. Для бомбардировки небольшого моста - важного военного объекта страны В - страна А использует оба имеющихся у нее самолета. Разрушенный мост восстанавливается в течение суток, а каждый самолет совершает один полет в день по одному из двух воздушных маршрутов, соединяющих эти страны. У страны В есть два зенитных орудия, при помощи которых можно сбивать самолеты страны А. Если самолет собьют, то некая третья страна в течение суток поставит стране А новый самолет. Страна А может послать самолеты либо по одному маршруту, либо по разным. Страна В может поместить либо обе зенитки на одном маршруте, либо по одной зенитке на каждый маршрут. Если один самолет летит по маршруту, на котором расположена одна зенитка, то этот самолет будет сбит. Если два самолета летят по маршруту, на котором расположены две зенитки, то оба самолета будут сбиты. Если два самолета летят по маршруту, на котором расположена одна зенитка, то сбит будет только один самолет. Если самолет доберется до цели, то мост будет уничтожен. У страны А есть две стратегии: послать самолеты по разным маршрутам - Л|, послать самолеты по одному маршруту - Аг- У страны В - также две стратегии: поместить зенитки на разных маршрутах - В\, поместить зенитки на одном маршруте - Внесли страна А выберет стратегию А\,ъ страна В - стратегию то страна А получит нулевой выигрыш, так как ни один из самолетов не достигнет цели. Если страна А выберет стратегию Аг. а страна В - стратегию В\, то хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1. Если страна А выберет стратегию А\, а страна В - стратегию Bj, то вновь хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1. сли страна А выберет стратегию Аг, а страна В - стратегию Bi, то страна А с вероятностью 1/2 выберет маршрут, на котором установлены зенитки, и, следовательно, цель будет уничтожена с вероятностью 1/2. Оформим результаты проведенного анализа в стандартной игровой форме: Сведение матричной игры к задаче линейного программирования При помощи графического метода полумаем оптимальные смешанные стратегии игроков и цену игры Это означает, что если страна А будет посылать самолеты по разным маршрутам в течение десяти дней из тридцати, отпущенных на войну (и, значит, по одному маршруту в течение двадцати дней), то в среднем страна А будет иметь 66,7 % удачных случаев (мост будем находиться в нерабочем состоянии). Воспользовавшись для своих зениток предложенным выбором, страна В не позволит бомбить мост чаще, чем в 66,7% случаев. § 5. Несколько слов в заключение Матричные игры моделируют конфликтные ситуации, в которых каждая из сторон-участниц делает свой ход одновременно со второй стороной. При этом наибольший интерес представляет случай, когда игра не заканчивается сразу же после совершения игроками одной такой пары одновременных ходов, а повторяется многократно. Причем считается, что перед каждым возобновлением игры игроки не получают никаких новых сведений ни о конфликте, ни о возможных действиях противной стороны. Иными словами, при многократном повторении матричной игры каждая из сторон всякий раз оказывается перед выбором некоторой стратегии из одного и того же множества стратегий, неизменного у каждого из игроков. Тем не менее, в таких многократно повторяющихся обстоятельствах большую роль играет анализ игры, как предварительный, так и промежуточный. В результате разумно проведенного предварительного анализа матричной игры заинтересованная в анализе сторона может определить свою линию поведения (правило выбора стратегий) на всю серию игр. Разумеется, описанный нами выше максимин-ный подход является далеко не единственным средством. Однако не следует забывать, что принципиальной особенностью этого подхода является то обстоятельство, что игрок, придерживающийся выводимого на его основе правила выбора стратегий, заранее может довольно точно оценить нетривиальные размеры своего гарантированного выигрыша. Кроме того, максиминный подход позволяет сводить задачу поиска решения игры к рассмотрению сравнительно несложных задач линейного программирования и, тем самым, получать эффективные рекомендации по тому, как лучше выбирать стратегии в конкретной игре при многократном ее повторении. Если игра повторяется много раз, то некоторые дополнительные сведения - какие именно стратегии выбирает противная сторона и какими правилами выбора стратегий она руководствуется - игрок все же получает. На основании этих сведений и результатов предварительного анализа игры он может довольно точно оценить противника и, если тот не придерживается компромиссного максиминного подхода, внести соответствующие изменения в собственную линию поведения и увеличить выигрыш.

Использование линейного программирования наиболее эффективно для игр двух участников с нулевой суммой без седловых точек и большим количеством стратегий у обоих игроков. В принципе любая конечная игра двух участников с нулевой суммой может быть преобразована в соответствующую задачу линейного программирования и, наоборот, каждую задачу линейного программирования можно интерпретировать как конечную игру двух участников с нулевой суммой. Действительно, пусть - платежная матрица в игре двух участников с нулевой суммой без седловых точек. Как мы уже знаем, в этом случае оптимальная смешанная стратегия первого игрока определяется условиями:

где ν * - ожидаемая цена игры; Пij - элемент платежной матрицы, расположенный на пересечении ее i -й строки и j - гостолбца и равный выигрышу первого игрока, если он использует стратегию , а его противник использует стратегию ; - вероятность выбора первым игроком стратегии . При этом величина

представляет собой ожидаемый выигрыш первого игрока при использовании им смешанной стратегии Таким образом,

и имеют место неравенства

Поэтому задача об определении оптимальной смешанной стратегии для первого игрока может быть представлена в следующем виде:

Предположим, что ожидаемая цена игры ν* этой задачи положительна, т.е. ν* > 0. Введем новые переменные:

Так как значению max ν соответствует значение

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

Заметим, что в этой задаче отсутствует ограничение типа равенства, связывающее вероятности выбора первым игроком своих чистых стратегий. Данное обстоятельство обусловлено наличием функциональной зависимости между координатами оптимального решения рассматриваемой задачи линейного программирования, координатами оптимальной смешанной стратегии первого игрока и ожидаемой ценой игры:

Таким образом,

тогда и только тогда, когда

Найдя оптимальное решение ( )T задачи линейного программирования для первого игрока, мы можем вычислить ожидаемую цену игры ν * и затем оптимальную смешанную стратегию первого игрока.

Для второго игрока оптимальная смешанная стратегия определяется условиями:

где - вероятность выбора вторым игроком стратегии . В новых переменных

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

являющейся двойственной задачей по отношению к задаче линейного программирования для первого игрока.

Прежде чем переходить к рассмотрению иллюстративного примера, отметим следующее.

1. Если ν < 0, то ко всем элементам платежной матрицы (Пij ) можно прибавить настолько большое положительное число К > , что все элементы платежной матрицы станут положительными. В этом случае цена игры увеличится на К , а решение не изменится.

2. Двойственность задач линейного программирования для первого и второго игроков приводит к тому, что решение одной из них автоматически приводит к решению другой. Учитывая это, как правило, решают задачу, имеющую меньшее число ограничений. А это, в свою очередь, зависит от числа чистых стратегий, находящихся в распоряжении каждого из игроков.

Пример 3.10. Вернемся к игре «три пальца», которую мы рассматривали в примерах 3.2, 3.4. Для нее

Прибавляя ко всем элементам матрицы (Пij ) число K = 5, приходим к матрице модифицированной игры

Завершая рассмотрение игр двух участников с нулевой суммой без седловых точек, заметим, что при использовании смешанных стратегий перед каждой партией игры каждым игроком запускается некий механизм (бросание монеты, игральной кости или использование датчика случайных чисел), обеспечивающий выбор каждой чистой стратегии с заданной вероятностью. Как мы уже отмечали, смешанные стратегии представляют собой математическую модель гибкой тактики, при использовании которой противник не знает заранее, с какой обстановкой ему придется столкнуться в каждой следующей партии игры. При этом ожидаемые теоретические результаты игры, при неограниченном возрастании числа разыгрываемых партий, стремятся к их истинным значениям.

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

Найдем решение игры с платежной матрицей m n:

Пусть матрица игры не содержит седловой точки. Тогда решение игры будем искать в смешанных стратегиях p= (p 1 , p 2 , …, p m) и q = (q 1 , q 2 , …, q m), где p 1 + p 2 +… + p m = 1 и q 1 + q 2 +… + q n = 1

Стратегия является оптимальной, то есть при любой стратегии игрока B средний выигрыш игрока A будет больше или равен цены игры, таким образом, получаем систему ограничений

Будем считать, что цена игры больше нуля. Действительно, если 0, то это означает, что некоторые элементы матрицы игры не положительные. Тогда найдём число M>0, которое прибавим ко всем элементам матрицы игры и получим новую матрицу с положительными элементами. Это сложение сделает цену новой игры, равную +M, положительной, но не изменит решения игры.

Разделим обе части всех неравенств на положительное число и обозначим

тогда система ограничений примет вид

Игрок A стремится максимизировать свой средний выигрыш, то есть минимизировать отношение

Таким образом, получаем задачу линейного программирования:

Заметим, что эта задача всегда имеет оптимальное решение. Его можно найти симплекс-методом или с использованием средств Excel. Тогда цена игры. Оптимальная смешанная стратегия первого игрока, где.

Аналогичные рассуждения дают оптимальную стратегию игрока B. При любой стратегии игрока А проигрыш игрока В не должен превышать цену игры. Получаем систему ограничений:

Обозначим.

Тогда для нахождения оптимальной смешанной стратегии игрока B необходимо решить следующую задачу линейного программирования:

Это двойственная задача к ранее составленной. Задача всегда имеет оптимальное решение, которое можно найти симплекс-методом или по теореме равновесия, зная решение ранее составленной задачи. Тогда цена новой игры. Оптимальная смешанная стратегия второго игрока, где.

Найти решение игры, заданной платежной матрицей:

Найдем верхнюю и нижнюю цены игры.

Следовательно, игра не имеет седловой точки, решение будет в смешанных стратегиях.

Чтобы свести матричную игру для игрока А к задаче линейного программирования преобразуем платежную матрицу так, чтобы все ее элементы были больше нуля - прибавим ко всем элементам матрицы число 4. Получаем преобразованную платежную матрицу:

Средний выигрыш А должен быть не меньше цены игры при любом поведении игрока В. Так, если игрок В использует свою первую стратегию, то средний выигрыш игрока А составит: , . Аналогично, записав неравенства для стратегий В 2 и В 3 , получаем систему линейных ограничений:

Из условия p 1 + p 2 + p 3 = 1, разделив обе части уравнения на >0 (цена игры больше нуля, т.к. все элементы преобразованной матрицы больше нуля), получаем целевую функцию. Цель игрока А - получить максимальный средний выигрыш, т.е. max, а значит. Если обозначить (i =1, 2, 3), то целевая функция.

Перейдем в системе ограничений к переменным x i , разделив каждое неравенство на >0:

Поиск решения.

1. Для решения нашей задачи создадим в Excel книгу с именем «Решение игры». Подготовим данные на листе.

Сначала определим ячейки, в которые будет помещен результат решения. Пусть это будут ячейки В2, С2, D2, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Далее заполним коэффициенты при неизвестных и правые части системы ограничений (строки 5-7). Заведем строку 10 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения.

Для ячеек B2:D2 и D10 установим числовой формат с 4 знаками после запятой. Для этого выделим эти ячейки, в контекстном меню по правой кнопке мыши выберем команду Формат ячеек… и в появившемся окне Формат ячеек на вкладке Число установим нужный формат.

2. Далее необходимо воспользоваться надстройкой Поиск решения. На вкладке Данные в группе Анализ выберите команду Поиск решения. Появится диалоговое окно Поиск решения, которое необходимо заполнить следующим образом (для добавления ограничений пользуемся кнопкой Добавить):

В окне Поиск решения после нажатия кнопки Выполнить появляется окно Результаты поиска решения , в котором выбираем сохранение найденных значений и нажимаем кнопку ОК .

Результаты поиска решений:

Получили. Так как и, то находим, что - это решение для игры, заданной преобразованной матрицей. Для исходной матрицы компоненты смешанной стратегии не меняются, а цена игры меньше на число, которое прибавляли ко всем элементам матрицы, т.е. на 4.

Окончательный результат: .

Аналогично можно составить и решить задачу линейного программирования для игрока В. Средний проигрыш игрока В должен быть не больше цены игры при любом поведении игрока А. Получаем систему линейных ограничений:

Из условия q 1 + q 2 + q 3 = 1, разделив обе части уравнения на >0, получаем целевую функцию. Цель игрока В - получить минимальный средний проигрыщ, т.е. min, а значит. Если обозначить, (j=1, 2, 3), то целевая функция.

Перейдем в системе ограничений к переменным y j , разделив каждое неравенство на >0:

Таким образом, для нахождения оптимальной стратегии игрока А необходимо решить задачу линейного программирования:

Решим задачу средствами табличного редактора MS Excel.использованием настройки Поиск решения.

1. Подготовим данные на листе.

В ячейки F5, F6, F7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку D10 - формулу для зависимости целевой функции.

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

Результаты поиска решений:

Получили. Так как и, то находим, что - это решение для игры, заданной преобразованной матрицей.

Окончательный результат: .