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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Игра размером 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.

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

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

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

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

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

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

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

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

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

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

.

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