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

Рассмотрим т х п ифу с платежной матрицей Без ограничения общности будем считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом, преобразующим заданную матрицу игры, но не изменяющим оптимальных смешанных стратегий игроков). Тем самым, искомая цена игры 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. Несколько слов в заключение Матричные игры моделируют конфликтные ситуации, в которых каждая из сторон-участниц делает свой ход одновременно со второй стороной. При этом наибольший интерес представляет случай, когда игра не заканчивается сразу же после совершения игроками одной такой пары одновременных ходов, а повторяется многократно. Причем считается, что перед каждым возобновлением игры игроки не получают никаких новых сведений ни о конфликте, ни о возможных действиях противной стороны. Иными словами, при многократном повторении матричной игры каждая из сторон всякий раз оказывается перед выбором некоторой стратегии из одного и того же множества стратегий, неизменного у каждого из игроков. Тем не менее, в таких многократно повторяющихся обстоятельствах большую роль играет анализ игры, как предварительный, так и промежуточный. В результате разумно проведенного предварительного анализа матричной игры заинтересованная в анализе сторона может определить свою линию поведения (правило выбора стратегий) на всю серию игр. Разумеется, описанный нами выше максимин-ный подход является далеко не единственным средством. Однако не следует забывать, что принципиальной особенностью этого подхода является то обстоятельство, что игрок, придерживающийся выводимого на его основе правила выбора стратегий, заранее может довольно точно оценить нетривиальные размеры своего гарантированного выигрыша. Кроме того, максиминный подход позволяет сводить задачу поиска решения игры к рассмотрению сравнительно несложных задач линейного программирования и, тем самым, получать эффективные рекомендации по тому, как лучше выбирать стратегии в конкретной игре при многократном ее повторении. Если игра повторяется много раз, то некоторые дополнительные сведения - какие именно стратегии выбирает противная сторона и какими правилами выбора стратегий она руководствуется - игрок все же получает. На основании этих сведений и результатов предварительного анализа игры он может довольно точно оценить противника и, если тот не придерживается компромиссного максиминного подхода, внести соответствующие изменения в собственную линию поведения и увеличить выигрыш.

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

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

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

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

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

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

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

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

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

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

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

Рис. 1.5.

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

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

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

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

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

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

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

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

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

Таблица 1
				2 *

к = 2 Т

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

к! = 3 Т

Таблица 2

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

Таблица 3

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

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

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

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

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

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

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

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

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

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

гозтземргим

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

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

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

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

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

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

Пусть задано матричную декабря m X n платежной матрицей (13.1).

Преобразуем систему (13.2), поделив все члены на v, v> 0 и введя обозначения

Преобразуем систему (13.6), поделив все члены на v, v> 0 и введя обозначения

Задача (13.8), (13.9) является задачей линейного программирования, решив которую получим оптимальное решение матричной игры.

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

Последовательность действий при решении матричной игры размером m X n

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

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

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

Решение одной из пары двойственных задач симплексным методом.

Выписка решение матричной игры в смешанных стратегиях.

Пример 13.1. Фирма может выпускать три вида продукции А1, А2, А3, получая при этом прибыль, зависит от спроса, который может принимать один из четырех состояний В1, В2, В3, В4. Прибыль, которую получит фирма при выпуске и го вида продукции

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

Решение. Сократить размерность платежной матрицы игры невозможно, так как она не содержит заранее невыгодных стратегий.

Определим верхнюю и нижнюю цены игры по алгоритму нахождения максимина (минимакса)

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

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

Задача линейного программирования, соответствует определению оптимальной стратегии игрока В, имеет вид:

Из анализа пары взаемнодвоистих задач линейного программирования (13.10), (13.11) и (13.12), (13.13) следует, что решать симплексным методом целесообразно задачу (13.12), 13.13), поскольку она не требует введения искусственных переменных.

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

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

Симплекс-метод основывается на свойствах ЗЛП:

1. Если есть экстремум, то он единственный.

2. Множество всех планов ЗЛП выпуклая.

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

4. Каждой вершине многоугольника решений соответствует опорный план ЗЛП.

Если нужно максимизировать целевую функцию, то можно перейти к минимуму max Ly = min (-Ly).

Сведем задачу (13.12), (13.13) к каноническому виду путем введения дополнительных переменных - y5, y6, y7.

Если неравенство в системе ограничений ЗЛП имеет знак "≤", то дополнительную переменную вводят со знаком "+"; если неравенство имеет знак "≥", то дополнительную переменную вводят со знаком "-".

ЗЛП (13.12), (13.13) в канонической форме имеет следующий вид

Переменные x1, x2, х3, х4, являются основными, х5, х6, х7 - дополнительными. Векторы р5, р, р7 образуют единичный базис и называются базисными, причем р5 - первый базисный вектор.

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

если дополнительная переменная имеет знак минус, то в это уравнение вводят искусственную переменную со знаком плюс;

если дополнительная переменная имеет знак плюс, то в это уравнение искусственную переменную вводить не нужно.

Искусственные переменные одновременно вводят в целевую функцию с неизвестным положительным коэффициентом М.

В нашем случае искусственные переменные вводить не следует.

Заполним первую симплекс-таблицу. Начальная симплекс-таблица заполняется следующим образом. В первой строке записывают коэффициенты целевой функции. В столбец "Базис" записывают базовые векторы. В столбце "С" записывают коэффициенты целевой функции при базисных векторах. В столбцах "р0", "р1", "Р2", "р3", "р4", "р5", "р6", "р7" записывают компоненты соответствующих векторов.

Для заполнения клеток таблицы, которые находятся в двух последних строках нужно элементы столбца "С" умножить на соответствующие элементы столбца, рассчитываемого и вычесть число, стоит в первой строке (за исключением столбца "р0»). Например, для заполнения клеток столбца "р2" умножим элементы столбца "С" на соответствующие элементы столбца "р2" и вычтем число - 1: 0 * 3 + 0 * 4 + 0 * 5 - (- 1) = 1.

Таблица 13.1. Первая симплексная таблица

Последняя строка симплекс-таблицы называется индексным. В нем, начиная с столбца "р1", содержатся оценки оптимальности, с помощью которых проверяют оптимальность опорного плана, соответствующего данной таблицы. Значение составляющих опорного плана расположены в столбце "р0", причем небазисные переменным присваивают нулевые значения.

Оптимальность опорного плана проверяют по индексным строкой с помощью критерия оптимальности. Критерий оптимальности опорного плана:

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

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

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

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

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

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

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

В нашем случае вектор "р3" следует ввести в базис.

Найдем симплексная отношение оптимальности вQo: элементы столбца "р0" поделим на положительные элементы решающих столбца. Строка, соответствует наименьшему отношению оптимальности вQo, называется решающих. Он показывает вектор следует вывести из базиса.

Генеральный элемент - это элемент, который расположен на пересечении решающих столбца и решающих строки. В нашем случае это число 6.

Правила перехода к следующей симплекс-таблицы: Все элементы решающих строки разделить на генеральный элемент.

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

Таким образом, вторая симплекс-таблица имеет вид:

Таблица 13.2. Вторая симплексная таблица

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

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

Таблица 13.3. Третья симплексная таблица

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

Перейдем к четвертой симплексной таблице:

Таблица 13.4. Четвертая симплексная таблица

Симплекс-таблицы 13.4 соответствует опорный план:

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

Таким образом, фирме (игроку А) следует выпускать 50% продукции А, 50% продукции А3, продукцию А1 не выпускать. Это позволит фирме получить гарантированную среднюю величину прибыли,

По состояний спроса можно сделать вывод, что оптимальный спрос в 75% находится в состоянии В1 и в 25% - в состоянии В4.

План.

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

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

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

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

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

, . (14.1)

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

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

(14.2)

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

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

, .

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

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

(14.3)

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

.

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

Математическую модель задачи (14.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 .