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

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

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

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

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

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

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

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

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

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

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

План.

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 .

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

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

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

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

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

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

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

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

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

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

.

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