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

План.

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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

План.

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

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

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

, . (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 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.

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

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

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

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

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

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

Прежде всего, проверим, имеет ли матрица седловую точку. Наименьший элемент -3 первой строки не является наибольшим в третьем столбце; наименьший элемент -1 второй строки не является наибольшим в первом столбце; наконец, наименьший элемент 2 третьей строки является одновременно наибольшим в третьем столбце. Следовательно, матрица имеет седловую точку (3, 3), в которой расположен элемент а зз = 2. Значит, игра имеет решение в чистых стратегиях, а именно:

- оптимальная стратегия первого игрока;

- оптимальная стратегия второго игрока;

v = 2 - цена игры.

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

В матрице нет седловой точки, следовательно, игра имеет решение в смешанных стратегиях.

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

Прибавив ко всем элементам матрицы А", например, число с = 3, получим матрицу

все элементы которой неотрицательны, а элементы второй строки строго положительны.

Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей А", ·а коэффициенты при неизвестных в целевой функции и свободные члeны неравенств были бы равны единице.

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем её к основной при помощи дополнительных неизвестных x 4 ≥0, x 5 ≥0. В результате получим следующую задачу.

x j ≥ 0 (j = 1,…,5),

f (X ) = x 1 + x 2 + x 3 → тах.

Задача - каноническая и, применив к ней алгоритм симплекс-метода, получим симплексные таблицы вида

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

f(X*) = g(Y*) =

Из решений двойственных задач получим цену игры и оптимальные стратегии игроков в игре с матрицей А":

v" = = ;

= v" = = ;

= v" = =

Игра с матрицей А" будет иметь те же оптимальные стратегии и , что и игра с матрицей А", причем цена игры

v" = v" - с = - 3 = .

И, наконец, исходная игра с матрицей А имеет оптимальные стратегии

Р*= и Q*=

и цену игры v = v" = .

Оптимальные стратегии Р* и Q * мы получили из оптимальных стратегий и , приписав нули на месте удаленных строк и столбцов.

Проверить правильность решения игры можно с помощью критерия оптимальности стратегий. Для этого в неравенства M(P i , Q*) ≤ v≤ М(Р*, Q j) следует подставить компоненты найденных оптимальных стратегий Р* и Q*, компоненты чистых стратегий Р i (i = 1, 2, 3) и Q j (j = 1, 2, 3, 4, 5)

и цену игры v = .

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

то в задаче 1 целевая функция будет не ограничена сверху на множестве планов, а в задаче 2 вообще не будет планов, однако, как мы убедились, выше, игра с матрицей А" имеет решение.

Оптимальная смешанная стратегия первого игрока (игрока A ) имеет вид

оптимальная смешанная стратегия второго игрока (игрока B ) имеет вид:

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

Решение игр графическим методом.

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

Пример1.

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

Нижней границей выигрыша для игрока А является ломаная В 3 КВ 4 ,. Стратегии В 3 , и В 4 являются активными стратегиями игрока В. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Второму игроку невыгодно применять стратегии В 1 и В 2 , у 1 = у 2 = 0. Решение игры сводится к решению игры с матрицей (2х2).

x 1 = 2/5, х 2 = 3/5; y 3 = 3/5, у 4 = 2/5; v = 11/5.

Ответ.

X (2/5, 3/5) и Y (0, 0,3/5, 2/5), цена игры составляет v = 11/5.

если первый игрок с вероятностью 2/5 будет применять первую стратегию и с вероятностью 3/5 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 11/5;

если второй игрок с вероятностью 3/5 будет применять третью стратегию, с вероятностью 2/5 четвертую и не будет использовать первую и вторую стратегии, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 11/5.

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

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

Верхней границей проигрыша для игрока В является ломаная А 1 КА 4 . Стратегии А 1 и А 2 являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку невыгодно применять стратегии А 3 и А 4 , поэтому вероятность их применения равна нулю, т.е. х 2 = х 3 = 0. Решение игры сводится к решению игры с матрицей (2х2)

По формулам (1)(3) находим оптимальные стратегии и цену игры:

х 1 = 7/8, х 4 = 1/8; у 1 = 3/8, у 2 = 5/8; v = 27/8.

Ответ. Оптимальные смешанные стратегии игроков

X (7/8, 0, 0, 1/8) и Y (3/8, 5/8), цена игры составляет v = 27/8.

Данный ответ означает следующее:

если первый игрок с вероятностью 7/8 будет применять первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;

если второй игрок с вероятностью 3/8 будет применять первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.

Использование компьютерных технологий при изучении темы: «Антагонистические игры».

Для графического решения матричной игры используется Microsoft Word и Microsoft Excel, а для решения матричной игры методами линейного программирования используется Microsoft Excel опция «Поиск решения». Также для расчётов возможно использование программы MATLAB, которая представляет собой высокоуровневый технический вычислительный язык и интерактивную среду для разработки алгоритмов, визуализации и анализа данных, числовых расчетов.

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

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