§ 21. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ З X 3-ИГР
З X 3-игры встречаются во многих вопросах. Поэтому умение их решать, притом без обращения к общим методикам (например, к симплекс-методу линейного программирования, о возможности использования которого см. в § 26) и, тем более, к вычислительной технике, представляется важным. Разумеется, такой подробный анализ, которому были в § 18 подвергуты 2 X 2-игры, здесь оказывается практически неосуществимым ввиду обилия и разнообразия могущих встретиться случаев. Поэто&му мы ограничимся описанием способа решения такой игры, не доводя его до расчет&ных формул, к которым он приводит в каждой из своих реализаций.
Итак, пусть нам дана игра с З X 3-матрицей выигрышей А. В основу ее решения мы положим следующие соображения.
- Прежде всего, как это уже неоднократно отмечалось, для значения vAвсякой матричной игры Г^ должно быть
vA = max min Х4./, (21.1)
X j
причем внешний максимум достигается на оптимальных стратегиях игрока 1 и только на них.
В нашем случае Xявляется вектором вида , ?2, ? 3), где
^ 0, (21.2)
+ =1. (21.3)
Обозначим множество всех таких векторов через X (см. п. 8.2). Тогда равенство
Каждое из них в условиях (21.3) является либо тождеством, либо уравнением прямой, разбивающей плоскость (21.3) на две полуплоскости, в каждой из которых одна из сравниваемых линейных форм принимает большие значения, чем другая.
Осуществив все такие разбиения плоскости (21.3) и произведя сравнения значений форм на соответствующих полуплоскостях, мы можем описать области плоскости, на которых меньшее значение оказывается у данной формы (т.е. у первой, второй или третьей) или одновременно у нескольких данйых форм. Обозначим область, в ко&торой минимальные значения будут у формы хА .f, через Ж/.
Это значит, что мы полагаем
XA.i для ІЄ «Jfp min xa.j = ха.2 для х<еж2,
/=1'2'3 [ха.3 для ІЄ
Вообще говоря, среди множеств Жх, Ж2, могут быть совпадающие, а также пустые.
Если система уравнений (21.3), (21.5), (21.6) (уравнение (21.7), очевидно, явля&ется следствием двух предыдущих) имеет единственное решение, то области , Ж2 и сЖ3 имеют вид углов (рис. 1.23). Если же эта система имеет бесконечное множество решений, то области принимают вид полос и полуплоскостей (рис. 1.24).
Применяя введенные обозначения, мы можем переписать (21.1), или, что то же самое, (21.4), в виде
v = max min xa.j = л Х(=Х /=1,2,3
Но максимум линейной формы на любом выпуклом многограннике, и в том числе на отрезке, треугольнике или выпуклом четырехугольнике, должен достигаться на его вершине (это утверждение известно из линейного программирования и широко применяется там; фактически оно равносильно опирающейся на лемму о переходе к смешанным стратегиям из п.
9.4 лемме из п. 10.2). Поэтому для нахождения мак&симума в (21.8) достаточно найти вершины многоугольников Ж] п X, вычислить в них значения соответствующей формы XA.j и сравнить эти значения между собой.
Вершины же каждого многоугольника Ж j п X суть либо вершины X, принадле&жащие Ж j, либо вершина (если она есть), принадлежащая X, либо же точки пере&сечения сторон^- со сторонами X. Все эти точки могут быть без труда перечислены.
Вершинами треугольника X являются точки 1 = (1, 0, 0), 2 = (0, 1, 0), 3 = (0,0,1). Принадлежность той или иной точки X из их числа данному множеству Ж j прове&ряется без труда путем установления того, что XA.j — наименьшее число среди XA,\, ХА.2 иХ4.3 (и во всяком случае, не большее, чем остальные).
Далее, если одно из множеств Ж у имеет вершину, то мы имеем дело со случаем, изображенным на рис. 1.23. При этом все множества Ж j должны иметь общую и притом единственную вершину. Принадлежность ее множеству X устанавливается проверкой соблюдения для ее координат уравнений (21.2) и (21.3).
Наконец, уравнение стороны Ж? і имеет вид
XA.j =XA.j2, (21.9)
а уравнение стороны X
?/ = 0. (21.10)
Комбинируя все уравнения вида (21.9) с уравнениями (21.10) и учитывая условия (21.2) и (21.3), мы можем найти все точки и этого типа.
Как видно из рис. 1.23 и 1.24, наибольшее число точек, в которых придется факти&чески вычислять и сравнивать значения линейных форм, равно семи. Общее число комбинаторно различных вариантов оказывается здесь весьма большим. Мы не будем их перечислять.
- После того как значение игры найдено, нахождение оптимальных стратегий игрока 2 не представляет большого труда. Именно, для этого нужно найти те значения вектора У - (г?!, л2 > )» которые удовлетворяют обычным соотношениям:
0, (21.11)
г?і+7?2+^З=1 (21.12)
(множество всех таких векторов составляет треугольник, который мы обозначим через Y) и для которых
шах Aj.
YT -V . (21.13)
і =1,2, З Л
С этой целью достаточно найти области и&3 плоскости (21.12), на кото&
рых из трех форм Аг-.УТ наибольшее значение принимает соответственно форма Ах. YTу А2- Ут или А^.уТ, и определить пересечение каждой из этих областей с тре&угольником.
Точки этого пересечения и составляют множество оптимальных стратегий игрока 2.
- Разумеется, при фактическом нахождении значения игры и оптимальных стратегий игроков в ней по описанному выше способу может возникать большое число возможностей сократить и упростить рассуждения и вычисления. Перечислять здесь эти возможности едва ли целесообразно.
- Пример. Пусть
1 1 2 0 2 0 2 0 0 Уравнение (21.5) в данном случае имеет вид ха3 +'2?3 +'2?2 =ха.?,
или =?3. 74
Аналогично уравнение (21.6) записывается как ХА.2=Чг +'2*а = 2|j т.е. 2?2 =
Наконец, из уравнения (21.7), которое оказывается следствием двух предыдущих, следует, что ^ -2^3.
Значит, области Жх и<2Г3 будут выглядеть так, как это изображено на рис. 1.25 (здесь точка 0 имеет координаты (1/2, 1/4, 1/4)). Вычисление значений формы ХА. j в точках 1, 2 іл 0 дает нам
(1,0, 0) (1,0, 2)г=1,
(0,1,0) (1,0, 2)г = 0,
(1/2, 1/4,1/4) (1,0, 2)г-1,
а вычисление значения формы ХА.2 в точке 3-
(0, 0,1) (1,2, 0)г=1.
Значит, именно векторы (1, 0, 0) и (1/2, 1/4, 1/4) являются оптимальными стратегия&ми игрока 1. Следовательно, на основании сказанного в предыдущем параграфе мно&жество всех оптимальных стратегий игрока 1 есть отрезок, соединяющий соответ&ствующие точки 1 и 0. Значение игры равно 1.
Обратимся к нахождению оптимальных стратегий игрока 2. Приравнивание соот&ветствующих линейных форм дает нам сначала
A1.YT = пг +17 2 +2т73 =2ГЇ2 =Л2.Уг,
откуда I + г?з = 2rj2; далее
А2.Ут = 2пг =2пж =А3.УТ;
так что rjj - г)2; наконец, из A j. У Г -А 3. следует 1 + т?3 = 277,.
Значит, области ?j, ?2 и ?3 имеют вид, изображенный на рис. 1.26. Здесь
/7= (2/3,0, 1/3), V - (0,2/3, 1/3), W = (1/3, 1/2,0).
Вычисление в точках U, V и W значений формы A j. YT дает нам
(1, 1, 2) (2/3, 0, 1 /3) т = 4/3, (1, 1, 2) (О*, 2/3, 1/3) г = 4/3,
(1, І, 2) (1/2, 1/2, 0)г= 1, (I, 1, 2) (0, 0, 1)г = 2,
а вычисляя в точках 2 и 1 соответственно значения форм А2. УТ и А 3. получаем (0, 2, 0) (0, 1, 0) т = 2, (2, 0, 0) (1, 0, 0) т = 2.
Таким образом, единственной оптимальной стратегией игрока 2 оказывается точка W= (1/2, 1/2, 0).
Еще по теме § 21. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ З X 3-ИГР: