Решение матричной игры с помощью линейного программирования. Матричные игры: примеры решения задач
Использование линейного программирования наиболее эффективно для игр двух участников с нулевой суммой без седловых точек и большим количеством стратегий у обоих игроков. В принципе любая конечная игра двух участников с нулевой суммой может быть преобразована в соответствующую задачу линейного программирования и, наоборот, каждую задачу линейного программирования можно интерпретировать как конечную игру двух участников с нулевой суммой. Действительно, пусть - платежная матрица в игре двух участников с нулевой суммой без седловых точек. Как мы уже знаем, в этом случае оптимальная смешанная стратегия первого игрока определяется условиями:
где ν * - ожидаемая цена игры; Пij - элемент платежной матрицы, расположенный на пересечении ее i -й строки и j - гостолбца и равный выигрышу первого игрока, если он использует стратегию , а его противник использует стратегию ; - вероятность выбора первым игроком стратегии . При этом величина
представляет собой ожидаемый выигрыш первого игрока при использовании им смешанной стратегии Таким образом,
и имеют место неравенства
Поэтому задача об определении оптимальной смешанной стратегии для первого игрока может быть представлена в следующем виде:
Предположим, что ожидаемая цена игры ν* этой задачи положительна, т.е. ν* > 0. Введем новые переменные:
Так как значению max ν соответствует значение
то мы приходим к задаче линейного программирования для первого игрока
Заметим, что в этой задаче отсутствует ограничение типа равенства, связывающее вероятности выбора первым игроком своих чистых стратегий. Данное обстоятельство обусловлено наличием функциональной зависимости между координатами оптимального решения рассматриваемой задачи линейного программирования, координатами оптимальной смешанной стратегии первого игрока и ожидаемой ценой игры:
Таким образом,
тогда и только тогда, когда
Найдя оптимальное решение (
)T задачи линейного программирования для первого игрока, мы можем вычислить ожидаемую цену игры ν
* и затем оптимальную смешанную стратегию 
первого игрока.
Для второго игрока оптимальная смешанная стратегия определяется условиями:
где - вероятность выбора вторым игроком стратегии . В новых переменных
приходим к задаче линейного программирования для второго игрока
являющейся двойственной задачей по отношению к задаче линейного программирования для первого игрока.
Прежде чем переходить к рассмотрению иллюстративного примера, отметим следующее.
1. Если ν < 0, то ко всем элементам платежной матрицы (Пij ) можно прибавить настолько большое положительное число К > , что все элементы платежной матрицы станут положительными. В этом случае цена игры увеличится на К , а решение не изменится.
2. Двойственность задач линейного программирования для первого и второго игроков приводит к тому, что решение одной из них автоматически приводит к решению другой. Учитывая это, как правило, решают задачу, имеющую меньшее число ограничений. А это, в свою очередь, зависит от числа чистых стратегий, находящихся в распоряжении каждого из игроков.
Пример 3.10. Вернемся к игре «три пальца», которую мы рассматривали в примерах 3.2, 3.4. Для нее
Прибавляя ко всем элементам матрицы (Пij ) число K = 5, приходим к матрице модифицированной игры
Завершая рассмотрение игр двух участников с нулевой суммой без седловых точек, заметим, что при использовании смешанных стратегий перед каждой партией игры каждым игроком запускается некий механизм (бросание монеты, игральной кости или использование датчика случайных чисел), обеспечивающий выбор каждой чистой стратегии с заданной вероятностью. Как мы уже отмечали, смешанные стратегии представляют собой математическую модель гибкой тактики, при использовании которой противник не знает заранее, с какой обстановкой ему придется столкнуться в каждой следующей партии игры. При этом ожидаемые теоретические результаты игры, при неограниченном возрастании числа разыгрываемых партий, стремятся к их истинным значениям.
Рассмотрим т х п ифу с платежной матрицей Без ограничения общности будем считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом, преобразующим заданную матрицу игры, но не изменяющим оптимальных смешанных стратегий игроков). Тем самым, искомая цена игры v - положительное число. Интересы игрока А Из теоремы о свойствах оптимальных смешанных стратегий игроков вытекает, что при любой чистой стратегии игрока В, п, оптимальная смешанная стратегия Р = игрока А обеспечивает его средний выигрыш, не меньший v. Иными словами, выполняются соотношения которые с учетом обозначений Сведение матричной игры к задаче линейного программирования можно записать так Поскольку игрок А стремится сделать свой гарантированный выигрыш максимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче: найти неотрицательные величины удовлетворяющие неравенствам и такие, что их сумма минимальна Интересы игрока В Аналогичным образом заключаем, что оптимальная смешанная стратегия игрока В при любой чистой стратегии Ai игрока m, обеспечивает его средний проигрыш, не больший v. Иными словами, выполняются соотношения которые с учетом обозначений можно записать так Поскольку игрок В стремится сделать свой гарантированный проигрыш минимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче: найти неотрицательные величины, удовлетворяющие неравенствам и такие, что их сумма максимальна п Тем самым, мы получаем следующий важный результат. Теорема 3. Решение матричной игры с положительной платежной матрицей (а,к) равно-сильно решению двойственных задач линейного программирования При этом цена игры где 0 - величина, обратная общему значению оптимальных сумм, а оптимальные значения р и связаны с оптимальными х°{ и yj. посредством равенств Алгоритм решения матричной игры 1-й шаг. Ко всем элементам исходной матрицы игры прибавляется одно и то же положительное число 7 так, чтобы все элементы новой матрицы были строго положительны. 2-й шаг. Решаются двойственные задачи линейного программирования (А) и (В) (например, симплекс-методом, или как-нибудь иначе). Находятся наборы хJ, ук и число 6. 3-й шаг. Строятся оптимальные смешанные стратегии игроков А и Б соответственно 4-й шаг. Вычисляется цена игры Пример 9. Рассмотрим 2x2 игру с матрицей Соответствующие ей задачи линейного программирования имеют вид Решение 1-й шаг. Все элементы платежной матрицы положительны. 2-й шаг. Строим решения обеих задач линейного программирования, пользуясь графическим методом. В результате получаем, что Сведение матричной игры к задаче линейного программирования §4. Примеры задач, сводимых к матричным играм В чистом виде антагонистические конфликты встречаются редко (разве только в боевых действиях и в спортивных состязаниях). Однако довольно часто конфликты, в которых интересы сторон противоположны, при допущении, что множество способов действия сторон конечно, можно моделировать матричными играми. Рассмотрим несколько конкретных ситуаций. Пример 10. «Планирование посева». Сельскохозяйственное предприятие имеет возможность выращивать две культуры - А\ и Необходимо определить, как сеять эти культуры, если при прочих равных условиях их урожаи зависят от погоды, а план посева должен обеспечить наибольший доход (прибыль от реализации выращенной культуры определяется полученным объемом). В зоне рискованного земледелия (а таковой является большая часть России) планирование посева должно осуществляться с учетом наименее благоприятного состояния погоды. Таким образом, одной из сторон выступает сельскохозяйственное предприятие, заинтересованное в том, чтобы получить наибольший доход (игрок А), а другой стороной - природа, способная навредить сельскохозяйственному предприятию в максимальной степени (от нее зависят погодные условия) и преследующая тем самым прямо противоположные цели (игрок В). Принятие природы за противника равносильно планированию посева с учетом наиболее неблагоприятных условий; если же погодные условия окажутся благоприятными, то выбранный план даст возможность увеличить доход. Налицо антагонистический конфликт, в котором у игрока А две стратегии - А\ и Л?, а у игрока В три - //| (засушливое лето), В2 (нормальное лето) и В$ (дождливое лето). В качестве выигрыша игрока А возьмем прибыль от реализации и будем считать, что расчеты прибыли сельскохозяйственного предприятия (в млрд руб.) в зависимости от состояний погоды сведены в следующую матрицу (2 3 б)" Нетрудно заметить, что седловой точки у этой матрицы нет. Поэтому оптимальная стратегия игрока А будет смешанной. Применяя графический мотод, получаем ММ}. Замечание. Здесь мы столкнулись со сравнительно редкой ситуацией, когда оптимальная смешанная стратегия одного из игроков допускает так называемую «физическую» реализацию. Полученное решение сельскохозяйственное предприятие может использовать так: . на | всех плошадей выращивать культуру А\, на I всех плошадей выращивать культуру А2 и получать прибыль в размере, не меньшем млрд руб. Пример 11. «Переговоры о заключении контракта между профсоюзом и администрацией». Рассмотрим фирму, администрация которой ведет переговоры с профсоюзом рабочих и служащих о заключении контракта. Предположим, что платежная матрица, отражающая интересы договаривающихся сторон, имеет следующий вид Выплаты указаны в центах в час и представляют собой среднюю зарплату служащего фирмы вместе со всеми добавками. Тем самым, заданная матрица описывает прибыль профсоюза (игрок А) и затраты администрации фирмы (игрок В). Ясно, что профсоюз стремится максимизировать доходы рабочих и служащих, в то время как администрации хотелось бы минимизировать собственные потери. Нетрудно заметить, что седловой точки у платежной матрицы нот. Кроме того, для дальнейшего анализа существенными являются лишь стратегии А\ и А4 игрока А и стратегии Вi и В4 игрока В (в этом нетрудно убедиться, воспользовавшись правилом доминирования стратегий). В результате соответствующего усечения получим матрицу Элементы матрицы связаны с элементами предыдущей матрицы соотношениями. Воспользовавшись графическим методом, в итоге получим Тем самым, профсоюзу следует выбирать стратегию А\ в 20 % случаев и стратегию А4 в 80 %. Что касается администрации, то ей следует выбирать стратегию В3 с вероятностью 0,4 и стратегию В4 с вероятностью 0,6. При этом ожидаемая цена игры равна 53. Замечание. Следует отмстить, что если процесс переговоров будет повторяться много раз, то среднему должно сходиться к ожидаемому значению 53. Если же переговоры пройдут лишь единожды, то реальный результат получится при выборе каждым игроком некоторой своей чистой стратегии. Поэтому один из игроков, профсоюз или администрация, будет неудовлетворен. Пример 12. «Локальный конфликт». Рассмотрим войну между двумя небольшими государствами А и В, которая ведется в течение 30 дней. Для бомбардировки небольшого моста - важного военного объекта страны В - страна А использует оба имеющихся у нее самолета. Разрушенный мост восстанавливается в течение суток, а каждый самолет совершает один полет в день по одному из двух воздушных маршрутов, соединяющих эти страны. У страны В есть два зенитных орудия, при помощи которых можно сбивать самолеты страны А. Если самолет собьют, то некая третья страна в течение суток поставит стране А новый самолет. Страна А может послать самолеты либо по одному маршруту, либо по разным. Страна В может поместить либо обе зенитки на одном маршруте, либо по одной зенитке на каждый маршрут. Если один самолет летит по маршруту, на котором расположена одна зенитка, то этот самолет будет сбит. Если два самолета летят по маршруту, на котором расположены две зенитки, то оба самолета будут сбиты. Если два самолета летят по маршруту, на котором расположена одна зенитка, то сбит будет только один самолет. Если самолет доберется до цели, то мост будет уничтожен. У страны А есть две стратегии: послать самолеты по разным маршрутам - Л|, послать самолеты по одному маршруту - Аг- У страны В - также две стратегии: поместить зенитки на разных маршрутах - В\, поместить зенитки на одном маршруте - Внесли страна А выберет стратегию А\,ъ страна В - стратегию то страна А получит нулевой выигрыш, так как ни один из самолетов не достигнет цели. Если страна А выберет стратегию Аг. а страна В - стратегию В\, то хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1. Если страна А выберет стратегию А\, а страна В - стратегию Bj, то вновь хотя бы один самолет достигнет цели и вероятность разрушения моста будет равна 1. сли страна А выберет стратегию Аг, а страна В - стратегию Bi, то страна А с вероятностью 1/2 выберет маршрут, на котором установлены зенитки, и, следовательно, цель будет уничтожена с вероятностью 1/2. Оформим результаты проведенного анализа в стандартной игровой форме: Сведение матричной игры к задаче линейного программирования При помощи графического метода полумаем оптимальные смешанные стратегии игроков и цену игры Это означает, что если страна А будет посылать самолеты по разным маршрутам в течение десяти дней из тридцати, отпущенных на войну (и, значит, по одному маршруту в течение двадцати дней), то в среднем страна А будет иметь 66,7 % удачных случаев (мост будем находиться в нерабочем состоянии). Воспользовавшись для своих зениток предложенным выбором, страна В не позволит бомбить мост чаще, чем в 66,7% случаев. § 5. Несколько слов в заключение Матричные игры моделируют конфликтные ситуации, в которых каждая из сторон-участниц делает свой ход одновременно со второй стороной. При этом наибольший интерес представляет случай, когда игра не заканчивается сразу же после совершения игроками одной такой пары одновременных ходов, а повторяется многократно. Причем считается, что перед каждым возобновлением игры игроки не получают никаких новых сведений ни о конфликте, ни о возможных действиях противной стороны. Иными словами, при многократном повторении матричной игры каждая из сторон всякий раз оказывается перед выбором некоторой стратегии из одного и того же множества стратегий, неизменного у каждого из игроков. Тем не менее, в таких многократно повторяющихся обстоятельствах большую роль играет анализ игры, как предварительный, так и промежуточный. В результате разумно проведенного предварительного анализа матричной игры заинтересованная в анализе сторона может определить свою линию поведения (правило выбора стратегий) на всю серию игр. Разумеется, описанный нами выше максимин-ный подход является далеко не единственным средством. Однако не следует забывать, что принципиальной особенностью этого подхода является то обстоятельство, что игрок, придерживающийся выводимого на его основе правила выбора стратегий, заранее может довольно точно оценить нетривиальные размеры своего гарантированного выигрыша. Кроме того, максиминный подход позволяет сводить задачу поиска решения игры к рассмотрению сравнительно несложных задач линейного программирования и, тем самым, получать эффективные рекомендации по тому, как лучше выбирать стратегии в конкретной игре при многократном ее повторении. Если игра повторяется много раз, то некоторые дополнительные сведения - какие именно стратегии выбирает противная сторона и какими правилами выбора стратегий она руководствуется - игрок все же получает. На основании этих сведений и результатов предварительного анализа игры он может довольно точно оценить противника и, если тот не придерживается компромиссного максиминного подхода, внести соответствующие изменения в собственную линию поведения и увеличить выигрыш.
План.
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.3 Решение матричных игр в смешанных стратегиях путём сведения к задаче линейного программирования
Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.
Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.
Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x – это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям
xi >= 0 (i = 1,m), = 1.
Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел
y = (y1, ..., yn), yj >= 0, (j = 1,n), = 1.
Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями.
Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.
Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей
E (A, x, y) == x A yT
Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е (А, х, y), а второй – за счёт своих смешанных стратегий стремится сделать Е (А, х, y) минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена игры
Е (А, х, y).
Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть
Е (А, х, y).
Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы хо, уо соответственно, которые удовлетворяют равенству
Е (А, х, y) = Е (А, х, y) = Е (А, хо, уо).
Величина Е (А, хо,уо) называется при этом ценой игры и обозначается через u.
Имеется и другое определение оптимальных смешанных стратегий: хо, уо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:
Е (А, х, уо)<= Е (А, хо, уо)<= Е (А, хо, у)
Оптимальные смешанные стратегии и цена игры называются решением матричной игры.
Основная теорема матричных игр имеет вид:
Теорема (о минимаксе). Для матричной игры с любой матрицей А величины
Е (А, х, y) и Е (А, х, y) существуют и равны между собой.
Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования.
Пусть игра m × n задана платежной матрицей p = (a ij), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A 1 , A 2 , ..., A m , игрок В - стратегиями B 1 , B 2 , ..., B m . Необходимо определить оптимальные стратегии S* A = (p* 1 , p* 2 , ..., p* m) и S* B = (q* 1 , q* 2 , ..., q* n), где p* i , q* j - вероятности применения соответствующих чистых стратегий A i , B j , p* 1 + p* 2 +...+ p* m =1, q* 1 + q* 2 +...+ q* n = 1.
Оптимальная стратегия S* A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы a ij ≥ 0. Если игрок А применяет смешанную стратегию S* A = (p* 1 , p* 2 , ..., p* m) против любой чистой стратегии B j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша a j = a 1j p 1 + a 2j p 2 +...+ a m j p m , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A 1 , A 2 , ..., A m и результаты складываются).
Для оптимальной стратегии S* A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:
(2.3.1)
Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:
x 1 = p 1 /v, x 2 = p 2 /v , ..., p m /v (2.3.2)
Тогда система (2.3.1) примет вид:
(2.3.3)
Цель игрока А - максимизировать свой гарантированный выигрыш, т.е. цену игры v.
Разделив на v ≠ 0 равенство p 1 + p 2 + ...+ p m = 1 , получаем, что переменные x 1 (i = 1, 2, ..., m) удовлетворяют условию: x 1 + x 2 + ...+ x m = 1/v. Максимизация цены игры v эквивалентна минимизации величины1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных x i ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (2.3.3) и при этом линейная функция
Z = x 1 + x 2 + ...+ x m , (2.3.4)
обращалась в минимум. Это задача линейного программирования. Решая задачу (2.3.3)-(2.3.4), получаем оптимальное решение p* 1 + p* 2 + ...+ p* m и оптимальную стратегию S A .
Для определения оптимальной стратегии S* B = (q* 1 + q* 2 + ...+ q* n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти . Переменные q 1 , q 2 , ..., q n удовлетворяют неравенствам:
(2.3.5)
которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял, игрок А.
Если обозначить
y j = q j /v, j = 1, 2, ..., n, (2.3.6)
то получим систему неравенств:
(2.3.7)
Переменные y j (1, 2, ..., n) удовлетворяют условию 
.
Игра свелась к следующей задаче
Определить значения переменных y j ≥ 0, j = 1, 2, ..., n, которые удовлетворяют системе неравенств (2.3.7) и максимизируют линейную функцию
Z" = y 1 + y 2 + ...+ y n , (2.3.8)
Решение задачи линейного программирования (2.3.6), (2.3.7) определяет оптимальную стратегию S* B = (q* 1 + q* 2 + ...+ q* n) . При этом цена игры
v = 1 / max, Z" = 1 / min Z (2.3.9)
Составив расширенные матрицы для задач (2.3.3), (2.3.4) и (2.3.7), (2.3.8), убеждаемся, что одна матрица получилась из другой транспонированием:
Таким образом, задачи линейного программирования (2.3.3), (2.3.4) и (2.3.7), (2.3.8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.
Если у каждого из игроков больше двух возможных стратегий, то можно решение игры свести к решению задачи линейного программирования.
Найдем решение игры с платежной матрицей 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 - формулу для зависимости целевой функции.
В окне Параметры поиска решений устанавливаем флажок неотрицательные значения.
Результаты поиска решений:
Получили. Так как и, то находим, что - это решение для игры, заданной преобразованной матрицей.
Окончательный результат: .
