План.

6.1. Связь матричных игр и линейного программирования.

6.2. Алгоритм решения матричных игр с помощью линейного программирования.

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

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

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

, . (6.1)

Эта задача может быть сформулирована в виде задачи линейного программирования. Пусть

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

(6.2)

при ограничениях

Для второго игрока задача записывается в виде

, .

Промежуточное соотношение:

Тогда задача примет вид

(6.3)

при ограничениях

.

Задача для второго игрока (6.3) является двойственной к задаче для первого игрока (6.2). Задача для второго игрока может быть решена, например, стандартным симплекс-методом, а для первого игрока – двойственным симплекс-методом. Выбор метода определяется тем, какая из задач имеет меньше ограничений, что в свою очередь зависит от числа чистых стратегий каждого из игроков.

Математическую модель задачи (6.2) можно упростить, разделив все (n + 1) ограничения на v . Это возможно при v ¹ 0. При v = 0 рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положительность значения модифицированной игры. Действительное значение игры получается вычитанием из модифицированного значения этого положительного числа. Если v < 0, то надо сменить знаки неравенств.

Полагая v > 0, систему ограничений можно записать:

Полагая X i = x i / v и если v ® max, то 1/v ® min, получим задачу линейного программирования вида

при ограничениях

.

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

при ограничениях

,

где S (Y ) max = L (X ) min = 1/v , Y j = y j /n .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Представленные выше примеры решение игры со смешенными стратегиями наглядно иллюстрируют теоретические положения матричных игр и трудоемкость ручного счета даже при матрице 2х2. Для авоматизации расчетов можно использовать программные продукты, метод расчета в которых основан на решении системы линейных уравнений http://www.uchimatchast.ru/ .

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

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

Сформулируем задачу матричной игры. Две конкурирующие компании А и B выпускают продукцию. Для увеличения продаж товар поставляется в различных упаковках. Компания А использует картон А 1 , целлофан А 2 , пластмасс А 3 . Компания B использует такие же материалы для упаковки. Однако, при этом компании использовали различные виды оформления упаковок. В компании А зафиксировали увеличение/уменьшение притока покупателей в зависимости от упаковки товара и стратегии поведения конкурента B. Эти статистические данные представлены в таблице.

	В 1	В 2	В 3	Мин строк
Макс столбцов

Решение задачи основано на получение наилучшего результата из наихудших для каждого игрока, который может быть получен определенной стратегии поведения. Из представленной таблицы следует, что данную задачу нельзя решить на основе чистых стратегий (седловой точки нет). Решение задачи находится между -2 и 2. В данном случае присутствуют смешенные стратегии, а так как количество стратегий у игрока А равно трем эту задачу можно решить с помощью линейного программирования (ЛП) алгебраическим методом. Следует заметить, что эту задачу нельзя решить графическим методом, так как количество стратегий у каждого игрока больше двух.

В соответствии с данными, представленными в таблице, задача ЛП для игрока А записывается следующим образом

максимизировать:
(максимальное количество клиентов) при выполнении следующих ограничений:

5.3.3.1 Решение задачи лп симплекс-методом

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

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

Из данных задачи составляем исходную симплекс таблицу.

									Свободный член

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -1 Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R 1 , а ведущий элемент: 1.

								Свободный член

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -3, он задает ведущую строку - X 11 . В этой строке так же находим максимальный по модулю отрицательный элемент: -5 он находится в столбце X 5 , который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

								Свободный член

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -4,4, он задает ведущую строку - X 10 . В этой строке так же находим максимальный по модулю отрицательный элемент: -7,6 он находится в столбце X 4 , который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

								Свободный член

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -2,11, он задает ведущую строку - X 9 . В этой строке так же находим максимальный по модулю отрицательный элемент: - 2,82 он находится в столбце X 2 , который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

								Свободный член

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение F=-0,75 при значениях переменных равных: X 2 =0,75, X 4 =0,4, X 5 =0,29, X 3 =0,3.

В соответствии с данными, представленными в таблице, задача ЛП для игрока B записывается следующим образом:

максимизировать:
(минимальное количество клиентов) при выполнении следующих ограничений:

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

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

Тогда система запишется в виде:

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции.

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

Из данных задачи составляем исходную симплекс таблицу.

									Свободный член

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке M имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -1. Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R 1 , а ведущий элемент: 1.

								Свободный член

В составленной нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю - это элемент: -3, он задает ведущую строку - X 9 . В этой строке так же находим максимальный по модулю отрицательный элемент: -6 он находится в столбце X 5 , который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответствующая ведущему столбцу включается в базис. Пересчитаем симплекс-таблицу:

								Свободный член

В строке M отрицательные элементы отсутствуют. Рассмотрим строку F в которой имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1. Ведущей строкой будет та, для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X 11 , а ведущий элемент: 1,83.

								Свободный член

В строке M отрицательные элементы отсутствуют. Рассмотрим строку F в которой имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -3,92. Ведущей строкой будет та для которой положительное отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X 10 , а ведущий элемент: 9,75.

								Свободный член

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение F=-0.75 при значениях переменных равных: X 5 =0,53, X 4 =0,12, X 2 =0,75, X 3 =0,35.

Проведенный расчет показал. Значение игры, как со стороны игрока А, так и со стороны игрока B одинакова и равняется -0,75.

Пусть дана т х п- игра, заданная своей т х п- матрицей А для первого игрока, А = [а^], г Е I = {1,..., ?n}, j € J = = {1,..., ?г}. Будем предполагать, что ау ^ О . В этом случае цена игры v > 0. Предположим также, что в матрице А нс имеется идентичных строк и столбцов (если они имеются, то надо исключить лишнее). Наконец, предполагаем, что в матрице нет лишних стратегий, т.е. уже исключены столбцы (строки), элементы которых ^ (^) соответствующих элементов других столбцов (строк) для первого игрока, который играет на максимум (соответственно для второго игрока, который играет на минимум).

Учитывая эти обозначения, перепишем ограничения:

Чтобы найти максимум v для v 9 надо найти минимум для

Если ввести функцию z = - = Х4, то оказывается, что

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

Аналогичным образом, чтобы найти оптимальные стратегии для второго игрока (М(Р. Q ) ^ ?;), надо решить задачу линейного программирования:

Замечаем, что элементы а! п ^ a" i2 , г = 1,3. Следовательно, можно исключить первый столбец.(стратегию В так как командир (В) играет на минимум. Замечаем также, что элементы а" 3 ^ а[ 4 , г = 1,3. Поэтому можно исключить четвертый столбец (стратегию В 4 ). Матрица игры становится

Наконец, замечаем, что элементы a”j ^ а 2 р j = 1,2. Поэтому можно исключить вторую строку (стратегию Л 2), так как командир (Л) играет на максимум. Матрица игры становится

Чтобы решить эту последнюю игру, применим линейное программирование. Имеются двойственные задачи (1.30) и

Решим эти задачи с помощью геометрического метода (рис. 1.5).

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

Рис. 1.5.

Программа {х = х 2 = 1/2} даст минимум экономической функции z, z - Z m i n = 1.

Координаты точки С дают также оптимальную программу для двойственной задачи. Программа {у = у 2 = 1/2} даст максимум экономической функции w, w = = 1.

Так как z = 1 = -, то Т/ = - = 1 => Цена v = v"-l = 0.

Получаем оптимальные стратегии для командира (Л):

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

Оптимальные стратегии для командира (В):

т.с. надо охранять один вход двумя солдатами, а другой - одним. ?

Замечание 6. Если нс уменьшить размеры матрицы А! до второго порядка, то для решения игры надо применить симплекс-метод к двойственной задаче (1.31), которую надо представить в стандартной форме:

Заполним три симплекс-таблицы.

Таблица 1
				2 *

к = 2 Т

Разрешающий элемент - 2*.

к! = 3 Т

Таблица 2

Разрешающий элемент - 2*.

Таблица 3

Значения всех критериев Aj ^ 0, (У в ^ 0). Следовательно, программа {у 2 = 1/2; ?у 3 = 1/2; щ = 1; ?yi = 1М = 2У5 = 2У7 =

• 0} дает максимум экономической функции ги, zD = w max =

Так как тй = - = 1, то Т/ = 1 v = Т/ - 1 = 0 (потому

что у" = v+1). Получаем оптимальные стратегии командира (В ), который охраняет объект:

Чтобы найти оптимальную программу первичной задачи (1.30), применим теорему Неймана (с. 34), согласно которой

Min = Wmax- СлСДОВаТСЛЬНО, МИНИМуМ ЭКОНОМИЧССКОЙ фуНК- ции 2 первоначальной задачи равен z - z m n = 1.

Соответствие между переменными Х{ и yj определяется соотношением (1.24) (с. 34). Следовательно,

Из таблицы 3 находим оптимальную программу первоначальной задачи:

откуда получаем оптимальные стратегии командира (Л):

Этот результат ранее был получен при решении задачи геометрическим методом. ?

гозтземргим

Это пособие набрано с помощью пакета Scientific Workplace, состоящего из трех частей. Часть Scientific Word служит для набора и форматирования текстов. Вторая часть Maple V или MuPAD позволяет производить математические вычисления в символьном виде или с применением численных методов и строить графики в R 2 или R 3 . Третья часть Exam Builder служит для организации проверки уровня знаний.

В качестве примера решим с помощью Scientific Work- Place задачу линейного программирования:

Р е ш с н и е. С помощью клавиатуры, главного меню и панелей инструментов заполним 8 х 1 -матрицу:

и в главном меню применим команду Compute + Simplex + Maximize. Вместо заполнения пяти симплекс-таблиц получаем ответ: Maximum is at: {23 = 0, ?’1 = О.Х 2 = 40}.

• Если существуют atj

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

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

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

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

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

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

Прежде всего, проверим, имеет ли матрица седловую точку. Наименьший элемент -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, которая представляет собой высокоуровневый технический вычислительный язык и интерактивную среду для разработки алгоритмов, визуализации и анализа данных, числовых расчетов.

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

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

---