§6. Второй метод решения матричной игры

с ценой произвольного знака

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

Пусть игра определена матрицей

.

В отличие от метода, изложенного в предыдущем параграфе, в данном случае цена игры может быть произвольного знака.

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

(6.1)

выполняется при .

Аналогично, если – оптимальная смешанная стратегия первого игрока и - цена игры, то система

(6.2)

справедлива при .

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

Лемма 6.1. Если , такие решения систем (6.1), (6.2), для которых , то , являются оптимальными смешанными стратегиями в игре , а число – ценой игры.

Доказательство. Поскольку , – решения систем (6.1), (6.2), то в силу второго и третьего из условий этих систем векторы , являются смешанными стратегиями в игре . А так как по условию леммы выполняется , то в силу первых из условий (6.1), (6.2)

. (6.3)

Но тогда смешанные стратегии будут оптимальными, а число – ценой игры в силу следствия теоремы 2.1.

Итак, лемма 6.1 ставит конкретную цель: найти такие решения , систем (6.1), (6.2), которые удовлетворяют условию (6.3).

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

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

З А Д А Ч А а). Минимизировать при ограничениях (6.1).

З А Д А Ч А в). Максимизировать при ограничениях (6.2).

Лемма 6.2. Задачи а) и в) являются двойственными.

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

Задача . Требуется

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

.

Задача . Требуется

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

.

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

Конечно для решения задач а) и в) равенства из условий (6.1), (6.2) не требуется заменять неравенствами. Это было сделано лишь для облегчения доказательства леммы.

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

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

А Л Г О Р И Т М 6.1.

1) Матрица А проверяется на наличие седловой точки. Если пара индексов является седловой точкой матрицы, то число является ценой игры, а индексы – оптимальными чистыми стратегиями первого и второго игроков, соответственно. Решение окончено. Иначе требуется переход к следующему пункту.

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

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

, (6.4)

в которой к новым переменным предъявляется требование . Вводятся дополнительные переменные и искусственная переменная .

Вспомогательную задачу целесообразно, как увидим позже, записывать в виде задачи максимизации.

Требуется найти

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

,

где – как угодно большое положительное число.

3) Вспомогательная задача из пункта 2 решается симплексным методом.

Пусть

ее решение. Выписываются цена , оптимальная стратегия второго игрока и оптимальная стратегия первого игрока

,

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

Поскольку решалась задача максимизации, эти оценки неотрицательны. Решение задачи окончено.

Замечание 1. Если заведомо известно, что цена игры неотрицательна, то замену (5.4) делать не следует, а если цена игры заведомо неположительная, то следует положить .

Замечание 2. Значение искусственной переменной , т.к. это значение может быть отлично от нуля только в том случае, если система ограничений задачи а) не совместна. Но согласно теореме 3.1 матричная игра всегда имеет решение в смешанных стратегиях.

Описанный алгоритм 6.1 имеет определенные преимущества по сравнению с первым методом сведения игровой задачи к задаче линейного программирования. Алгоритм 6.1 применим к игре с ценой любого знака, не требует пересчета полученных решений и цены вспомогательной задачи, что приходится делать в первом методе. Но с другой стороны число ограничений во вспомогательной задаче алгоритма 6.1, на единицу больше, чем в алгоритме 5.1. Как всегда, один алгоритм в чем-то выигрывает и в чем-то проигрывает по отношению к другому алгоритму. Если бы существовал наилучший алгоритм, то, создав его, не пришлось бы больше ничего придумывать.

Пример 6.1. Требуется определить оптимальные смешанные стратегии и цену игры с игровой матрицей

.

1) Матрица А не имеет седловых точек.

2) Для задачи а), имеющей вид

строится вспомогательная задача в соответствии с пунктом 2) алгоритма 6.1

где , а – дополнительные, – искусственная переменные.

3. Решаем вспомогательную задачу пункта 2) симплексным методом.

Таблица 6.1

0 0 0 –1 1 0 0 –

B	Cбаз
	0 0	0 0 1	2 4 0 –1 1 1 0 0 0 4 –1 1 0 1 0 1 1 1 0 0 0 0 1
	своб.	0	0 0 0 1 –1 0 0 0
	При	–1	–1 –1 –1 0 0 0 0 0

В симплексной таблице 1 и во всех последующих в скобки заключен ведущий при гауссовских исключениях элемент. Оценки до тех пор, пока не исключен из базиса искусственный вектор , имеют вид . Коэффициенты , со знаком которых совпадает знак оценок , записаны в последнюю, а – в предпоследнюю строку таблицы 6.1.

Итак, введем в базис вектор вместо . Тогда по схеме исключений Гаусса получим таблицу 6.2.

Таблица 6.2

0 0 0 –1 1 0 0 –

B	Cбаз
	0 0	0 0 1	0 4 –8 – 1 1 –2 0 1 0 4 –1 1 0 1 0 0 1 –3 1 –1 0 –1 1
	своб.	0	0 0 0 1 –1 0 0 0
	При	–1	0 –1 3 –1 1 0 1 0

Введем в базис вектор вместо . Новому базису соответствует

Таблица 6.3

0 0 0 –1 1 0 0 –

B	Cбаз
	–1 0	0 0 1	0 4 –8 1 – 1 1 –2 0 1 4 –4 0 0 1 –1 0 0 –3 0 0 –1 1 1
	своб.	0	0 –4 8 0 0 –1 2 0
	При	–1	0 3 – 5 0 0 1 –1 0

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

Таблица 6.4

0 0 0 –1 1 0 0

B	Cбаз
	–1 0 0	8/5 4/5 1/5	0 –4/5 0 1 – 1 –3/5 –2/5 1 8/5 0 0 0 1/5 –1/5 0 –3/5 1 0 0 –1/5 1/5
	своб.	–8/5	0 4/5 0 0 0 3/5 2/5

Итак, решением вспомогательной задачи является вектор

В соответствии с пунктом 3) алгоритма 6.1, находим цену

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

, .

Решение примера окончено. Оптимальным поведением второго игрока будет выбор случайным образом своей первой чистой стратегии в четыре раза чаще выбора третьей стратегии. Первый игрок должен своей первой чистой стратегией пользоваться чаще, чем второй в полтора раза. В этом случае первый игрок может ожидать, что он будет в среднем выигрывать 8/5 единиц.

Замечание. Поскольку все элементы матрицы в данном примере неотрицательны, то цена игры, будучи значением функции (1.2), заведомо неотрицательна. Поэтому можно было считать и не делать замену , что несколько бы облегчило счет.

А Л Г О Р И Т М 6.2.

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

Теперь алгоритм 6.2 можно сформулировать следующим образом.

1) Матрица А проверяется на наличие седловой точки. Если пара индексов является седловой точкой матрицы, то число является ценой игры, а индексы – оптимальными чистыми стратегиями первого и второго игроков, соответственно. Тогда решение окончено. Иначе следует переход к следующему пункту.

2) Из всех элементов матрицы А вычитается такое число , что и ставится задача

(6.5)

. (6.6)

3) Условие (6.5) заменяется на условие и производится замена . Вводятся дополнительных переменных и искусственная переменная .

Вспомогательная задача записывается в следующем виде.

Требуется найти

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

,

где – как угодно большое положительное число.

4) Вспомогательная задача из пункта 3) решается симплексным методом.

Пусть

–

ее решение. Выписываются цена , оптимальная стратегия второго игрока и оптимальная стратегия первого игрока

,

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

Решение задачи окончено.

Решим далее пример 6.1 с помощью алгоритма 6.2.

1) Вычитая из всех элементов матрицы примера 6.1, строим матрицу

.

2) Для решения игры с матрицей записываем задачу

(6.7)

3) Вводим дополнительные переменные и искусственную переменную и строим исходную симплексную таблицу 6.5.

Таблица 6.5

0 0 0 1 0 0 –

B	Cбаз
	0 0	0 0 1	– 2 0 –4 1 1 0 0 –3 –4 0 1 0 1 0 1 1 0 0 0 1
	своб.	0	0 0 0 –1 0 0 0
	При	–1	–1 –1 –1 0 0 0 0

Согласно симплексному правилу вводим в базис вектор и выводим из базиса вектор . Проводя процесс исключений по схеме Гаусса при ведущем элементе , получим таблицу 6.6, при этом столбец, соответствующий искусственному вектору , из таблицы вычеркивается.

Таблица 6.6

0 0 0 1 0 0

B	Cбаз
	0 0 0	2 3 1	0 2 –2 1 0 0 –1 3 1 0 1 1 1 1 0 0 0
	своб.	0	0 0 0 –1 0 0

Теперь заменяется в базисе на .

Таблица 6.7

0 0 0 1 0 0

B	Cбаз
	0 0 0	2 1 1	0 2 –2 1 1 0 0 –3 0 –1 1 1 1 1 0 0 0
	своб.	2	0 2 –2 0 1 0

Вводим, наконец, в базис вектор вместо . Получим таблицу 6.8.

Таблица 6.8

0 0 0 1 0 0

B	Cбаз
	1 0 0	12/5 1/5 4/5	0 4/5 0 1 3/5 2/5 0 – 3/5 1 0 –1/5 1/5 1 8/5 0 0 1/5 –1/5
	своб.	12/5	0 4/5 0 0 3/5 2/5

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

.

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

Вычислительное замечание. Систему (6.7) пункта 2) алгоритма прежде, чем составлять симплексную таблицу, можно преобразовать следующим образом. К первому неравенству прибавить удвоенное третье ограничение-равенство, а ко второму неравенству прибавить утроенное третье ограничение. Тогда искусственную переменную не потребуется вводить вообще, а исходной симплексной таблицей станет таблица 6.6.

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

У П Р А Ж Н Е Н И Я.

Приведем несколько задач для самостоятельной работы.

1. Определить цену игры и оптимальные смешанные стратегии игроков в игре, заданной матрицей

.

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

Ответ. .

2. Для игры с матрицей

требования те же, что и в задаче 1.

Указание. Цена игры заведомо положительна (см. определение функции выигрыша ). Задачу можно решать по алгоритму 4.1 без предварительной подготовки. Сравнить с решением по алгоритму 5.2, вычитая предварительно из всех элементов матрицы число 2.

3. Решить каждую из игровых задач с матрицами

,

двумя методами, с помощью алгоритмов 4.1 и 5.1.

ВСПОМОГАТЕЛЬНАЯ ЛИТЕРАТУРА

(основная литература указана в пособии )

1. Я.И.Заботин. Теория игр (Теоретические основы и игры с седловыми точками). Набережные Челны, с. 31, 2004г.

2. Я.И.Заботин. Симплексный метод (метод последовательного улучшения плана) в линейном программировании. Набережные Челны, с. 32, 2003г.

3. Я.И.Заботин. Лекции по линейному программированию. Казань, КГУ, с. 96, 1985г.

О Г Л А В Л Е Н И Е

Введение …………………………………………..……… ...... 3

§1. Смешанные стратегии ………………………………………….4

§2. Теоремы об оптимальных смешанных стратегиях……………8

§3. Теорема существования решений в смешанных стратегиях ..12

§4 Метод одновременного решения двойственных задач

линейного программирования ………………………………………. 16

§5. Метод решения матричных игр с положительной ценой

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

§6. Второй метод решения матричной игры с ценой

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

Алгоритм 5.1. ……………………………………………….. 24

Алгоритм 5.2. ………………………………………………... 28

Упражнения ………………………………………………………. 31

Вспомогательная литература ……………………………………... 32