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

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

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

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

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

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

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

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

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

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

где X > 0, а р - любое вещественное число, имеют одинаковые равновесные ситуации (либо в чистых, либо в смешанных стратегиях), а цены игр удовлетворяют следующему условию: v B = Xv A + р.

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

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

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

Разделим все уравнения и неравенства в данных системах на и (это можно сделать, так как по предположению о > 0) и введем обозначения:

Тогда получаем

Поскольку первый игрок стремится максимизировать цену игры о выбором значений х [у то обратная величина 1/о должна минимизироваться выбором р г Таким образом, решение первой задачи сводится к нахождению таких неотрицательных значений р., 2=1,..., т у при которых

Поскольку второй игрок стремится найти такие значения у } и, следовательно, q y чтобы цена игры и была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений q jy j = 1, ..., п у при которых

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

Решив эти задачи, получим значения р®, i = 1,т у q® y j = 1,..., п.

Тогда значение цены игры о определяется из условия

Оптимальные смешанные стратегии, т.е. х® и г/?, получаются по формулам

Пример 4.7. Рассмотрим вариант игры «Борьба за рынки». Две конкурирующие компании А и Б принимают решение о финансировании трех инновационных технических проектов. Каждая из компаний может инвестировать 100 дсн. ед. Компания Б пытается занять рынок, на котором традиционно компания А лидирует. В случае разработки и развития одних и тех же проектов компания А получит прибыль, тогда как компания Б понесет убытки. Если инвестиции направляются в разные проекты, компания А понесет убытки, связанные с перераспределением рынка, а прибыль предприятия Б будет соответствовать убытку предприятия А. Необходимо найти оптимальные стратегии предприятий. Прибыль предприятия А при разных стратегических ситуациях представлена в таблице:

Решение в MS Excel

Решим задачу с помощью программы MS Excel. В таблицу MS Excel вводятся элементы платежной матрицы игры и с помощью функций МИН() и МАКС() определяются минимальные и максимальные значения по строкам и столбцам соответственно, затем с помощью этих же функций находятся максимин и ми- нимакс (табл. 4.2). Поскольку эти значения не совпадают, седловой точки в игре нет, г.е. в чистых стратегиях она не решается. Значение цены игры должно лежать в диапазоне (-5; 10).

Таблица 4.2

Проверка наличия седловой точки в игре

Для использования алгоритма решения игры путем ее сведения к задаче линейного программирования применим аффинное правило. С помощью функции МИН() находим минимальное значение элементов платежной матрицы (-20). Модуль этого числа определяется как ABS(MHH(...)). С помощью аффинного преобразования с параметрами X = 1 и р = 20 получим новую платежную матрица (табл. 4.3).

Таблица 4.3

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

Справа от платежной матрицы произвольно указываются искомые переменные р. (на этом этапе могут указываться любые значения). В ячейках под платежной матрицей с помощью функции СУММПРОИЗВ() определяются значения

которые будут использоваться в ограничениях задачи ЛИ. Эти значения для произвольно выбранных p t приведены в табл. 4.3.

В ячейке, обозначенной как «Целевая функция», вводится формула СУММ(...), соответствующая выражению для целевой функции

В ячейке, обозначенной как «Цена игры», вводится формула для определения цены игры через значение целевой функции:

В ячейках, обозначенных как x it вводятся формулы для обратного преобразования переменных и нахождения искомых элементов смешанной стратегии первого игрока x i = u Pj.

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

ни я Р" У обеспечивающие минимум функции YjPi * пип при условиях ^ a ij p i > 1,

Решение задачи линейного программирования осуществляется с помощью модуля «Поиск решения» программы MS Excel (применение этого модуля уже рассматривалось в гл. 2). В поле «Установить целевую ячейку» указывается адрес ячейки, содержащей значение целевой функции; выбирается режим «Равной: минимальному значению». В поле «Изменяя ячейки» указывается массив искомых переменных р г Нажатием кнопки «Добавить» и выбором массива, соответствующего ограничениям задачи, в поле «Ограничения» устанавливается соответствующее условие. Нажатием кнопки «Параметры» осуществляется переход в диалоговое окно «Параметры поиска решения», в котором выбираются параметры «Линейная модель» и «Неотрицательные значения»; значения остальных параметров остаются без изменений. После закрытия окна «Параметры поиска решения» (кнопкой ОК) нажатием кнопки «Выполнить» в окне «Поиск решения» осуществляется запуск итерационного процесса поиска решения задачи ЛП.

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

Аналогично решается задача ЛП для второго игрока (табл. 4.5). Обратите внимание, что в данном случае для технического удобства массив искомых переменных расположен в строку (поскольку стратегии второго игрока соответствуют столбцам платежной матрицы), а ячейки с ограничениями - в столбец. Задача решается на максимум и формулируется так: найти значения q jt

обеспечивающие максимум функции? Я) * тах П Р И условиях ^ a i} q- q } > 0.

Таблица 4.4

Результаты решения задачи ЛП для первого игрока

Результаты решения задачи ЛП для второго игрока

Таблица 4.5

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

Результаты показывают, что оптимальной стратегией компании А является распределение средств, предполагаемых к инвестированию, в пропорции 29, 60 и 11%, т.е. 29, 60 и 11 ден. ед. При этом компания А получит прибыль не менее 0,5 ден. ед. Минимальное значение прибыли (0,5 ден. ед.) компания А получит при условии, что компания Б будет придерживаться своей оптимальной стратегии инвестирования проектов, а именно 39, 25, 36%, т.е. инвестировать в проекты 39, 25 и 36 ден. ед. соответственно. Если компания Б будет отклоняться от этой стратегии (придерживаться другой схемы инвестирования), прибыль компании А будет расти.

Анализ решения показывает, что для компании Б данная игра невыгодна (ожидаемый убыток составляет приблизительно 0,5 ден. ед.). Однако если компания Б считает этот убыток сравнительно незначительным по сравнению с достижением поставленной цели - вхождением на рынок, традиционно контролируемый компанией А, то, придерживаясь своей оптимальной стратегии распределения инвестиций, компания Б потеряет не больше 0,5 ден. ед. Если компания А будет вести себя нерационально, то потери компании Б будут уменьшаться.

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

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

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

План.

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 .

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

Найдем решение игры с платежной матрицей 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 - формулу для зависимости целевой функции.

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

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

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

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