<<
>>

  § 21. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ З X 3-ИГР

  З X 3-игры встречаются во многих вопросах. Поэтому умение их решать, притом без обращения к общим методикам (например, к симплекс-методу линейного программирования, о возможности использования которого см.
в § 26) и, тем более, к вычислительной технике, представляется важным. Разумеется, такой подробный анализ, которому были в § 18 подвергуты 2 X 2-игры, здесь оказывается практически неосуществимым ввиду обилия и разнообразия могущих встретиться случаев. Поэто&му мы ограничимся описанием способа решения такой игры, не доводя его до расчет&ных формул, к которым он приводит в каждой из своих реализаций.

Итак, пусть нам дана игра с З X 3-матрицей выигрышей А. В основу ее решения мы положим следующие соображения.

  1. Прежде всего, как это уже неоднократно отмечалось, для значения vAвсякой матричной игры Г^ должно быть

vA = max min Х4./,              (21.1)

X j

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

В нашем случае Xявляется вектором вида , ?2, ? 3), где

^ 0, (21.2)

+              =1.              (21.3)

Обозначим множество всех таких векторов через X (см. п. 8.2). Тогда равенство

(21.4)

(21.1) можно переписать в виде хал

= max mm хєх

v. - шах mm А АГ ЄЕ X

ха.2

xa.3f

  1. (21.7)

Рассмотрим теперь равенства ХА.! = ХА.2, ха.2 =ха.3,

ха.3=ха.1.

Mli + +'Мзі

$га12 ±ї2а22 + Ц3а3

Каждое из них в условиях (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

(21.8)

= max{ max X4.i, max ХА.2, max XA.3} . ІЄ^ПХ              хєж2г)х              хєж3 ПХ

21.3. Нам остается найти в (21.8) внутренние максимумы и сравнить их между собой. Заметим, что каждое из множеств n X есть пересечение треугольника с углом, полосой или полуплоскостью. Поэтому оно либо пусто, либо состоит из един&ственной точки, либо является отрезком, либо треугольником, либо, наконец, вы&пуклым четырехугольником.

ХА хА.*

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

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

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

<< | >>
Источник: Воробьев Н.Н.. Теория игр для экономистов-кибернетиков. — М.: Наука, Главная редакция физико-математической литературы,1985. -272 с.. 1985

Еще по теме   § 21. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ З X 3-ИГР:

  1.   § 19. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ 2Х/2-ИГР
  2.   § 20. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ т X 2-ИГР
  3.   § 21. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ З X 3-ИГР
- Антимонопольное право - Бюджетна система України - Бюджетная система РФ - ВЭД РФ - Господарче право України - Государственное регулирование экономики России - Державне регулювання економіки в Україні - ЗЕД України - Инвестиции - Инновации - Инфляция - Информатика для экономистов - История экономики - История экономических учений - Коммерческая деятельность предприятия - Контроль и ревизия в России - Контроль і ревізія в Україні - Логистика - Макроэкономика - Математические методы в экономике - Международная экономика - Микроэкономика - Мировая экономика - Муніципальне та державне управління в Україні - Налоги и налогообложение - Организация производства - Основы экономики - Отраслевая экономика - Политическая экономия - Региональная экономика России - Стандартизация и управление качеством продукции - Страховая деятельность - Теория управления экономическими системами - Товароведение - Управление инновациями - Философия экономики - Ценообразование - Эконометрика - Экономика и управление народным хозяйством - Экономика отрасли - Экономика предприятий - Экономика природопользования - Экономика регионов - Экономика труда - Экономическая география - Экономическая история - Экономическая статистика - Экономическая теория - Экономический анализ -
- Аудиторская деятельность - Банки - Бизнес - Бухгалтерский учет - Кредит - Маркетинг - Менеджмент - Философия - Финансы - Экономика -