Теория игр

Министерство образования и науки Российской Федерации Амурский государственный университет УДК 519.832 ББК 22.18 М17 Рекомендовано учебно-методическим советом университета Рецензент: Н.Н. Максимова ТЕОРИЯ ИГР Бризицкий Р.В., старший научный сотрудник Института прикладной математики ДВО РАН, канд.физ.-мат. наук. Максимова Н.Н. М17 Теория игр: учебно-методическое пособие / Н.Н. Максимова. – Благовещенск: Изд-во АмГУ, 2015. – 94 с. Учебно-методическое пособие Учебно-методическое пособие содержит краткие теоретические сведения по курсу «Теория игр». Подробно рассмотрены методы решения матричных игровых задач, теории принятия решений и представлены образцы решения задач. Предлагаются варианты заданий для контрольной работы студентов заочного отделения. Учебный материал позволяет выработать практические навыки решения задач теории игр. Учебно-методическое пособие предназначено для студентов направлений подготовки 38.03.01 «Экономика», 38.03.02 «Менеджмент», 38.03.06 «Торговое дело», 01.03.02 «Прикладная математика и информатика (в рамках изучения дисциплины «Теория игр и исследование операций»). Благовещенск 2015 1 © Максимова, Н.Н., 2015 © Амурский государственный университет, 2015 2 ВВЕДЕНИЕ Другими словами, теория игр дает математический прогноз конфликта. Реальные конфликтные ситуации приводят к различным видам игр. В зависи- Теория игр – раздел прикладной математики, в котором рассматриваются мости от вида игры разрабатывается и метод ее решения. методы изучения оптимальных стратегий в играх. Под игрой понимается про- Если описание игры предполагает рассмотрение всех возможных страте- цесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию гий каждого игрока и определение платежей, соответствующих любым воз- своих интересов. Каждая из сторон имеет свою цель и использует некоторую можным комбинациям стратегий всех игроков, то такую игру называют игрой в стратегию, которая может вести к выигрышу или проигрышу – в зависимости нормальной форме. от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с Классификацию игр проводят по различным признакам [7]. учётом представлений о других участниках, их ресурсах и их возможных по- По числу игроков определяются игры одного игрока, двух игроков, n иг- ступках. Чаще всего методы теории игр находят применение в экономике, чуть роков. Игры одного игрока (типа пасьянсов) не представляют интереса и не реже в других общественных науках. Очень важное значение она имеет для ис- рассматриваются в теории игр. Игры двух игроков – наиболее распространен- кусственного интеллекта и кибернетики, особенно с проявлением интереса к ные, их исследованию посвящено много работ. Игры трех и более игроков ме- интеллектуальным агентам. нее исследованы из-за возникающих принципиальных трудностей и техниче- Простейшие модели принятия решений рассматриваются в курсах мате- ских возможностей получения решения. матического анализа и оптимизации. В этих моделях лицо, принимающее ре- По количеству стратегий игры делятся на конечные и бесконечные. Ес- шения (ЛПР), выбирает свое действие из некоторого множества стратегий. За- ли в игре каждый из игроков имеет конечное число возможных стратегий, то дана целевая функция, которая отражает интересы ЛПР и зависит от выбранной она называется конечной. Если хотя бы один из игроков имеет бесконечное ко- им стратегии. Задача принятия решения в этой постановке состоит, как прави- личество возможных стратегий, то такая игра называется бесконечной. ло, в том, чтобы найти стратегию, доставляющую экстремум целевой функции. По характеру взаимоотношений игры делятся на бескоалиционные, коо- Отличие конфликтной ситуации в том, что решение принимается не одним ин- перативные и коалиционные. Бескоалиционными называются игры, в которых дивидуумом, а несколькими участниками, и функция выигрыша каждого инди- игроки не имеют права вступать в соглашения, образовывать коалиции. Коали- видуума зависит не только от его стратегии, но также и от решений других уча- ционной игрой называется игра, в которой игроки могут вступать в соглашения, стников. Математическая модель такого рода конфликта называется игрой, а образовывать коалиции. В кооперативной игре коалиции наперед определены. участники конфликта – игроками [3]. По характеру выигрышей делятся на игры с нулевой суммой и игры с не- Теория игр занимается исследованием математических моделей конфликтов и их формальным решением, что позволяет: – смоделировать процесс и возможные результаты будущей игры еще до ее фактического начала; нулевой суммой. Игра с нулевой суммой будет тогда, когда сумма выигрышей всех игроков в каждой ее партии равна нулю, т.е. в игре с нулевой суммой общий капитал всех игроков не меняется, а перераспределяется между игроками в зависимости от получающихся исходов. Примером игры с ненулевой суммой – по результатам моделирования будущей игры принять решение о целесообразности участия и оптимальном поведении в реальном конфликте. 3 могут быть торговые взаимоотношения между странами. В таких случаях все стороны могут быть в выигрыше или оказаться в проигрыше. 4 По виду функций выигрышей игры делятся на матричные, биматричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др. В данном пособии ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ АНТАГОНИСТИЧЕСКИХ МАТРИЧНЫХ ИГРОВЫХ ЗАДАЧ рассмотрены матричные и биматричные игры. По количеству шагов игры делятся на одношаговые и многошаговые. В одношаговых играх совершается ровно один ход. Примером многошаговых игр могут служить шашки, шахматы и карточные игры, то есть когда совершается много шагов, и каждый последующий шаг зависит от предыдущих. 1.1. Матричные игровые задачи Наибольшее практическое значение имеют парные игры, поэтому основное внимание уделим рассмотрению этого класса игр [7]. Развитие игры во времени представляется состоящим из ряда последова- Наиболее изученными являются игры двух участников, преследующих тельных «ходов». Ходом в теории игр называется выбор одного из предусмот- противоположные цели (или игры с нулевой суммой). Такие игры называются ренных правилами игры действий и его осуществление. Ходы бывают личные и антагонистическими. случайные. Личным ходом называется сознательный выбор игроком одного из Учебно-методическое пособие состоит из введения, четырех глав, указа- возможных вариантов действий и его осуществление. Случайным ходом назы- ний по выполнению контрольной работы, заключения, библиографического вается выбор из ряда возможных альтернатив, осуществляемый некоторой не- списка. В первой главе рассматривается основные понятия антагонистических заинтересованной средой – назовем ее природой. Для каждого случайного хода конфликтов, приводятся примеры построения матричных игр, исследуется воз- правила игры определяют распределение вероятностей возможных исходов. можность сокращения размерности матричных игр. Во второй главе приведены методы решения антагонистических конфликтов в зависимости от размерности Задача теории игр – рекомендовать игрокам определенные «стратегии» при выборе их личных ходов. игровой задачи (графические и аналитические методы). В третьей главе рас- Стратегией игрока называется совокупность правил, определяющих вы- сматриваются вопросы принятия решения в условиях неопределенности на ос- бор варианта действий при каждом личном ходе этого игрока, в зависимости от новании критериев Вальда, Сэвиджа, Гурвица, Лапласа. В четвертой главе из- ситуации, сложившейся в ходе игры. ложен графический метод решения простейшей биматричной задачи. В конце пособия представлены варианты задания контрольной работы и указания по ее выполнению. Библиографический список содержит перечень литературы по данной дисциплине. Целью теории игр является определение «оптимальной стратегии» для каждого игрока. Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально Данное пособие может быть использован для организации и проведения лекционных, практических и лабораторных занятий, а также для самостоятельного изучения дисциплины студентами заочной формы обучения по направлениям подготовки 38.03.01 – «Экономика», 38.03.02 – «Менеджмент», 38.03.06 – возможный средний выигрыш. При выборе этой стратегии делается расчет на противника, который делает все, чтобы помешать нам, добиться своей цели. При постановке игровых задач должны быть определены следующие условия: «Торговое дело», 01.03.02 – «Прикладная математика и информатика» (в рам- – стороны, принимающие решения (игроки); ках изучения дисциплины «Теория игр и исследование операций»). – множество всех возможных действий (стратегий); – выигрыши сторон для каждой ситуации (платежная функция). 5 6 В том случае, когда цели двух конкурирующих сторон являются прямо противоположными, для них можно определить единый критерий: одна из сто- теж (в у.е.), равный этой сумме, если сумма пальцев нечетная, то А платит В. Определить оптимальные стратегии поведения сторон. рон будет заинтересована в увеличении значения этого критерия, а другая – в его уменьшении. Решение. Очевидно, что у каждого игрока по три стратегии: показывать один, два или три пальца. Элементы платежной матрицы в данной задаче могут Рассмотрим игру двух игроков, скажем А и В, каждый из которых имеет быть рассчитаны по формуле конечное число стратегий. Предположим, игрок А имеет m стратегий: А1, А2,..., Аm, а игрок В – n стратегий: B1, B2,..., Bn. Каждой паре стратегий (Аi , Bj) ставится в aij  (i  j )(1) i  j , и матрица размерности 3  3 примет вид соответствие число aij, выражающее выигрыш игрока А за счет игрока В (если  2 3 4    A    3 4  5 . 4 5 6    aij>0) или проигрыш игрока А игроку В (если aij<0), когда А применяет свою стратегию Аi , а В – стратегию Bj. Возможен вариант «ничьи» в случае, если aij=0. В случае единого критерия данная игра полностью может быть описана Пример 1.2 (игра «Орлянка»). Первый игрок закладывает монету орлом матрицей размерности m  n , которая называется матрицей игры или платеж- или решкой, а второй пытается отгадать. Если второй игрок отгадает, то первый ной матрицей (отсюда следует и название данного класса игр – матричные иг- платит ему 10 рублей, если не отгадает, то он платит первому 10 рублей. Требу- ры). ется определить оптимальные стратегии каждого из игроков. B1 B2 ... Bn A1  a11 a12 ... a1n    A2  a 21 a 22 ... a 2 n  . ...  ... ... ... ...    Am  a m1 a m 2 ... a mn  Решение. У первого игрока две стратегии: A1 и A2 – заложить монету орлом или решкой. У второго игрока две стратегии: B1 и B2 – предположить, что заложен орел или решка. Получаем платежную матрицу B1 B2 вает другой, т. е. сумма выигрышей игроков равна нулю. Поэтому игры данного A1   10 10   . A2  10  10  класса называют играми с нулевой суммой. Пример 1.3 (выбор ассортимента товаров). На базе торговой организа- В данной игре один игрок выигрывает ровно столько, сколько проигры- Ценой игры называется средний выигрыш игрока А. ции имеется п типов одного из товаров ассортиментного минимума (к примеру, п сортов яблок). В магазин должны быть завезены один или несколько типов 1.2. Примеры матричных игр. Составление модели игры данного товара. Если товар j-го типа (j = 1, ..., n), будет пользоваться спросом, Рассмотрим несколько примеров построения платежных матриц. то магазин от его реализации получит прибыль p j у.е. Если же этот товар не бу- Пример 1.1 (игра «Три пальца»). Пусть А и В одновременно показыва- дет пользоваться спросом, то магазин понесет убытки от его хранения, порчи и ют от одного до трех пальцев. Выигрыш или проигрыш определяется числом т.д., которые составят lj у.е. (табл. 1.1). Требуется выбрать типы товара, которые целесообразно завести в мага- показанных пальцев. Если сумма числа пальцев четная, то А получает от В плазин. 7 8 Таблица 1.1 В распоряжении стороны В (бомбардировщики) также 2 стратегии: Расчетные данные к примеру 1.3 Типы товара Доход от реализации pj у.е. Убыток от хранения lj у.е. 1 32 16 2 32 8 A2 – обстреливать второй бомбардировщик. 3 32 4 4 32 4 5 32 2 B1 – поместить бомбу на первый бомбардировщик; B2 – поместить бомбу на второй бомбардировщик. Элементы платежной матрицы – вероятности сбития бомбардировщика с Решение. В данной задаче в качестве одной из конфликтующих сторон выступает магазин (игрок А), а в качестве другой – покупательский спрос (игрок В). Каждый из игроков имеет n стратегий. Завоз i-го товара – Ai стратегия игрока А, спрос на j-й товар – Bj стратегия игрока В. В данном случае платежная матрица игры будет квадратной матрицей размерности n  n .  32  16  16  16  8 8   8 32 A    4  4 32  4    4  4  4 32  2  2  2  2   16   8  4   4  32  бомбой. Очевидно, что если истребитель будет стрелять по бомбардировщику без бомбы, соответствующий элемент платежной матрицы будет равен нулю. В результате платежная матрица примет вид:  (1  P2 ) P1 A    0.32 0 .  0.128  (1  P2 ) 2 P1   0 Пример 1.5. Мистер N часто ездит между двумя городами. При этом есть возможность один из двух маршрутов: скоростное шоссе или длинную обдуваемую ветром дорогу. Патрулирование дорог осуществляется ограниченным количеством полицейских. Если полицейские расположены на одном маршру- Пример 1.4. Истребитель (И) атакует один из бомбардировщиков Б1 или Б2, летящих один за другим. Вооружение истребителя позволяет ему обстрелять один из бомбардировщиков. Вероятность сбития бомбардировщика при этом составляет P1 = 0.8. На одном из бомбардировщиков находится бомба, однако, на каком – не известно. Цель истребителя – сбить бомбардировщик с бомбой. Подлетая к бомбардировщику, истребитель подвергается обстрелу и может быть сбит с вероятностью Р2 = 0.6. После этого он обстреливает первый бомбардировщик или летит ко второму, подвергается обстрелу бомбардировщиком те, то мистер N с его страстным желанием ездить быстро, получит штраф в 1500 рублей за превышение скорости. Если полицейские патрулируют на двух маршрутах в соотношении 50 на50, то есть 50%-я вероятность получить штраф на первом маршруте и 30%-я – на втором. Кроме того, второй маршрут длиннее, поэтому бензина расходуется на 400 рублей больше, чем на первом маршруте. Построить матрицу игры, определить нижнюю и верхнюю цены игры и найти решение графическим методом. Решение. Пусть элементы платежной матрицы – затраты мистера N на Б2 и обстреливает его. Требуется определить оптимальные стратегии поведения сторон, если ис- дорогу (с отрицательными знаками). У мистера N две стратегии: A1 и A2 – по- требитель (сторона А) стремится максимизировать вероятность сбития бомбар- ехать по скоростному шоссе или по дороге. У полицейских три стратегии: B1 – дировщика с бомбой, а бомбардировщики (сторона В) стремятся эту вероят- расположиться на шоссе, B2 – расположиться на дороге, B3 – расположиться на ность минимизировать. шоссе и дороге в соотношении 50 на 50. Решение. В распоряжении стороны А (истребитель) – 2 стратегии: Рассчитаем элементы платежной матрицы: А1 – обстреливать первый бомбардировщик; 9 10 p ( A1 , B1 )  1500 , p ( A1 , B2 )  0 , A3 – послать к поставщику представителя и транспорт; p( A1 , B3 )  1500  0,5  750 , p( A2 , B1 )  (0  400)  400 , A4 – заказать поставку у плодоовощной базы. p( A2 , B2 )  (400  1500)  1900 , p( A2 , B3 )  (400  1500  0,3)  850 . В итоге получаем платежную матрицу B1 B2 У поставщика имеются две стратегии: B1 – поставка своевременная, B2 – поставки нет. B3 Всего возможны восемь ситуаций. В зависимости от каждой из них, мага- A1   1500  750   . A2   400  1900  850  зин понесет различные затраты. Для наглядности расчеты представим в Пример 1.6. Коммерческое предприятие заключило договор на централи- табл. 1.2. Таблица 1.1 зованную поставку овощей из теплиц на сумму 10 000 руб. ежедневно. Если в Затраты магазина, руб. течение дня овощи не поступают, магазин имеет убытки в размере 20 000 руб. от невыполнения плана товарооборота. Ситуации Магазин может осуществить самовывоз овощей фермера. Для этого он может сделать заказ в транспортном предприятии, что вызовет дополнительные расходы в размере 500 руб. Однако опыт показывает, что в половине случаев посланные машины возвращаются без овощей. Можно увеличить вероятность получения овощей от фермера до 80%, если предварительно посылать туда своего представителя, что требует дополнительных расходов в размере 400 руб. ( A1, B1 ) ( A1, B2 ) ( A2 , B1 ) ( A2 , B2 ) ( A3 , B1 ) ( A3 , B2 ) ( A4 , B1 ) ( A4 , B2 ) 10000 Транспортные издержки 20000 20000 10000 500 10500 5000 10000 500 15500 10000 500 400 10900 8000 4000 500 400 12900 25000 500 300 25800 15000 500 15500 Стоимость овощей Убытки от непоставки Командировочные издержки Издержки от реализации Всего за день 10000 Существует возможность заказать дневную норму овощей у другого надежного поставщика – плодоовощной базы по повышенной на 50% цене. Однако в этом случае, кроме расходов на транспорт (500 руб.), возможны дополнительные издержки в размере 300 руб., связанные с трудностями реализации товара, если в тот же день поступит и централизованная поставка от фермера. Какой стратегии надлежит придерживаться магазину, если заранее неизвестно, поступит или не поступит централизованная поставка. В итоге получаем платежную матрицу: B1 A1   10000  A2   10500 A3   10900  A4   25800 B2  20000    15500  .  12900    15500  Решение. Построим игровую модель этой задачи. Игроками являются представители магазина и поставщика. Перечислим стратегии первого игрока – 1.3. Сокращение размерности игровой задачи Прежде чем приступить к решению игровой задачи, надо проанализиро- магазина: A1 – ожидать поставку, не принимая дополнительных мер; вать платежную матрицу на предмет сокращения ее размерности. При анализе A2 – послать к поставщику свой транспорт; 11 12 игровой матрицы сразу можно выделить стратегии, являющиеся дублирующими или заведомо невыгодными для сторон [7]. В игре i-я стратегия дублирует j-ю стратегию, если ail = a jl, для l  [1, m] или ali = alj для l  [1, n] . Если в матрицу игры входят дублирующие стратегии, то из них оставляется любая одна, а остальные – удаляются. Определение заведомо невыгодных стратегий производится с помощью отношений доминирования, которые заключаются в следующем. Если каждой из стратегий стороны А поставить в соответствие вектор-строку матрицы А, то стратегия Ai будет доминировать стратегию Aj B1 B2 7 4   6 10 A 9 5  2 7 B3 6  A1  11 A2 8  A3  5  A4 Элементы i-й строки матрицы А являются выигрышами стороны А при применении ею своей i-й стратегии. Если сравнить стратегию А1 со стратегией А3, можно заметить, что независимо от того, какую стратегию применяет сторона В, выигрыш стороны А при применении ею своей третьей стратегии всегда будет больше, чем при использовании первой стратегии. Следовательно, стратегия А1 является невыгодной по сравнению со стратегией А3, и соответст- при выполнении следующего условия: ail  a jl для l  1, n . В этом случае вующая строка может быть удалена из платежной матрицы. Аналогично, если стратегия Aj не будет использоваться, и соответствующая строка из пла- сравнить стратегию А2 со стратегией А4, можно заметить, что А4 невыгодна по тежной матрицы удаляется. сравнению с А2, и соответствующая строка может быть удалена. Следовательно, Если каждой из стратегий стороны В поставить в соответствие вектор-столбец матрицы А, то стратегия Вj будет доминировать над стратегией Вi при выполнении следующего условия ali  alj для l  1, m . В этом случае стратегия Вj не будет использоваться, и соответствующий столбец из пла- B1 B2 B3  6 10 11 A2  A    9 5 8  A3 Рассмотрим данную игру с позиции стороны В. Для стороны В элементы тежной матрицы удаляется. Таким образом, из платежной матрицы удаляются дублирующие стратегии (кроме одной), доминируемые строки и доминирующие столбцы. Порядок удаления строк и столбцов значения не имеет. Пример 1.7. Рассмотрим игру со следующей платежной матрицей: B1 B2 7 4   6 10 A  9 5  3 7 9 5  мы имеем: j-го столбца платежной матрицы являются проигрышами при применении ею своей стратегии Bj. Естественно, выгодной для В является та стратегия, которая дает ей меньший проигрыш, независимо от образа действий стороны А. Если сравнить стратегии B2 и B3, то видно, что независимо от того, какую стратегию применит сторона А, проигрыш стороны В будет больше при стратегии B3, и, B3 6  A1  11 A2 8  A3  5  A4 8  A5 следовательно, соответствующий столбец может быть удален из платежной матрицы: B1 B2  6 10  A2 A     9 5  A3 Решение. Как видно из матрицы, стратегии А3 , A5 являются дублирующими, и одна из них, скажем А5, из матрицы А может быть удалена: 13 Пример 1.8. Рассмотрим применение отношений доминирования к матрице вида: 14 B1 4 6 A  1 3 B2 5 1 4 2 B3 9 10 2 8 ношения доминирования в платежной матрице остается единственный элемент. B4 B5 3 6  A1 0 2  A2  3 10  A3 1 4  A4 Номера строки и столбца, где этот элемент находится, и определяют равновесную ситуацию или решение игры в «чистых» стратегиях, т.е. четко указывают, какие стратегии должны принять стороны. Решение. Столбец 3 – доминирующий по отношению к столбцу 1, а столбцы 2 и 5 – доминирующие по отношению к столбцу 4. Другой случай наличия решения в «чистых» стратегий связан с существованием седловой точки. Преобразованная матрица: Определение седловых точек производится по следующей схеме: B1 4  A  6 1 3   a11 a12   a21 a 22 A   ... ...  a  m1 a m 2 B4 3 0 3 1  A1 A2 A3 A4 a1max Строки 3 и 4 – доминируемые по отношению к строке 1. ... ... ... ... a 2 max ... a1n   a2n  ...   amn  a m max a1min a 2 min ...    max min aij am min i j  Преобразованная матрица:   min max aij B1 B4 A A   4 3  1 6 A   2 j i Поставим задачу: определить наилучшую из стратегий игрока А при ус- Столбец В1 – доминирующий по отношению к В4: ловии, что игрок В будет действовать наихудшим для нее способом. Элементы i-й строки матрицы А являются выигрышами стороны А при B4 A A  3 1 0 A2 выборе ею своей стратегии Ai . Сторона А считает, что в ответ на любую ее Строка А2 – доминируемая по отношению к А1 т.е. дает А наименьший выигрыш. Поэтому в каждой строке находим мини- B4 A  3 A1 мальный элемент: стратегию сторона В ответит той стратегией, которая наименее выгодна для А, ai 1.4. Решение игровых задач в «чистых» стратегиях. Принцип минимакса min  min aij . j Далее сторона А должна выбрать ту стратегию, которая обеспечит ей наибольший выигрыш из имеющихся гарантированных минимумов: В некоторых ситуациях равновесная ситуация может быть определена непосредственно. В матричных играх ситуация (k, l) является равновесной, если для i  1, m и для j  1, n выполняется неравенство   max a i min  max min aij . i i j Величина α называется нижней ценой игры или максиминным выигрышем, или максимином. Стратегия игрока А, соответствующая максимину α, на- ail  a kl  akj . зывается максиминной стратегией. Если игрок А будет придерживаться Прежде всего, это касается ситуаций, когда в результате применения от15 своей максиминной стратегии, то при любом действии противника, ему 16 Эти игры называются играми с седловой точкой. В матрице такой игры гарантирован выигрыш, не меньший α. Рассмотрим теперь игру с позиции игрока В и выберем для него оптимальную стратегию. Элементы j-го столбца платежной матрицы являются про- существует элемент, являющийся одновременно минимальным в своей строке и максимальным в своем столбце. Такой элемент называется седловой точкой. игрышами стороны В при применении им стратегии Bj. Сторона В считает, что Общее обозначение нижней и верхней цены игры в ответ на любую ее стратегию Bj игрок А ответит той стратегий, которая наи-     менее выгодна для В, т.е. дает В наибольший проигрыш. Поэтому в каждом называется чистой ценой игры. Соответствующие седловой точке стратегии Ai столбце находим максимальный элемент: и Bj называются оптимальными, они образуют равновесную ситуацию или ре- a j max  max aij . шение игры. i Решение игры с седловой точкой обладает свойством: если один из игро- Выбирая стратегию Bj, сторона В рассчитывает на то, что в результате любых действий противника он проиграет не больше, чем a j max . Далее в интересах В выбрать ту стратегию, при которой он получит наименьший проигрыш из набора ожидаемых максимумов: j быть выгодным отклонение от своей оптимальной стратегии. Замечание. В платежной матрице может быть несколько седловых точек, и все они имеют одно и то же значение; в этом случае имеется несколько опти-   min a j max  min max aij . j ков отклоняется от своей оптимальной стратегии, то для другого не может мальных стратегий. i Пример Величина β называется верхней ценой игры, или минимаксным выигрышем, или минимаксом. Стратегия игрока В, соответствующая минимаксу, называется минимаксной стратегией. Если игрок В будет придерживаться своей 1.9. Определить решение и Решение. Нижняя цена игры равна рован проигрыш, не превышающий величину β. 7   10 6  6    max min   9  6 16   max   9   6 . j  14 i i   3 5  3     венством: с матрицей Верхняя цена игры равна  . Игры, в которых нижняя цена игры строго меньше верхней ее цены, называются играми без седловых точек. В этом случае каждый из игроков может ухучшить свое положение, отступив от своей максиминной (минимаксной) стратегии. Особое место в теории игр занимают игры, в которых нижняя цена равна 7   10 6   min max  9  6 16   min 14 6 16   6 . j j i  14 5  3   Получили, что верхняя цена игры равна нижней, следовательно, это игра с седловой точкой. Оптимальное решение имеет вид (A1, B2), чистая цена игры  *  6 . Вернемся к рассмотренным ранее примерам, и определим верхнюю и верхней   игры 7   10 6 A    9  6 16  .  14 5  3    минимаксной стратегии, то при любом поведении стороны А, ему гаранти- Очевидно, что нижняя цена α и верхняя цена β игры всегда связаны нера- цену или max min a ij  min max aij . i j j 17 i нижнюю цены игры, а также наличие или отсутствие седловой точки в платежных матрицах. 18 Пример 1.1. Нижняя цена игры равна   3  2 3 4      3 4  5   max min   max   5   3 .  j  i i    5 4  5 6      10000    10500   min max  j i  10900    25800 Верхняя цена игры равна Получили, что верхняя цена игры равна нижней, следовательно, это игра  2 3 4      min max  3 4  5   min4 4 6  4 . j i  j  4  5 6   20000    15500   min  10000  12900  12900 . j  12900    15500  с седловой точкой. Оптимальное решение имеет вид (A3 , B2). Это означает, что магазину следует послать к поставщику представителя и транспорт. При этом затраты магазина составят 12900 руб. Получили, что верхняя    , следовательно, это игра без седловой точки. Стратегия A1 – это максиминная стратегия первого игрока (показывать один 1.5. Понятие смешанных стратегий палец), стратегии B1 и B2 – минимаксные стратегии второго игрока (показывать В тех случаях, когда равновесная ситуация не может быть найдена при помощи исключения доминируемых строк и доминирующих столбцов и не вы- один или два пальца). Пример 1.5. Нижняя цена игры равна полняются условия существования седловой точки, ситуация равновесия в чис-  750    1500   1500    max    1500 .   max min  j   400 i i   1900   1900  850  тых стратегиях отсутствует. В этом случае каждая из сторон может использо- Верхняя цена игры равна определяемая платежной матрицей A, повторяется достаточное количество раз  750    1500   min max   min 400 0  750  750 . j j i   400  1900  850  [1, 7, 12]. Получили, что верхняя    , следовательно, это игра без седловой точ- чтобы они обеспечивали максимально гарантированный выигрыш при учете ки. Стратегия A1 – это максиминная стратегия первого игрока (мистеру N выбрать проезд по скоростному шоссе), стратегия B3 – минимаксная стратегия второго игрока (полицейским разделиться в соотношении 50/50 на шоссе и трассе). Пример 1.6. Нижняя цена игры равна   10000    10500   max min j i  10900    25800  20000    20000      15500    15500   max  12900 . i  12900   12900      15500    25800  ваться свои стратегии с некоторой вероятностью в предположении, что игра, Задача состоит в том, чтобы определить эти вероятности таким образом, действий противоположной стороны. Обозначим через x вектор-столбец размерности m, где m – число стратегий стороны A:  x1     x2  x  x[ m1]    . ...    xm  Элемент этого вектора xi определяет вероятность применения стороной A своей i-й стратегии. Через y обозначим n-мерный вектор-столбец, где n – число стратегий сто- Верхняя цена игры равна роны B: 19 20 ненты вектора смешанной стратегии первого игрока, снизу – компоненты век-  y1    y  y  y[ n 1]   2  . ...    yn  тора смешанной стратегии второго игрока: 6 3  x1  1   A  9 5 4  x2  4  5  1 x   3 y1 y 2 y3 Элемент этого вектора y j определяет вероятность применения стороной B своей j-й стратегии. Запишем функцию выигрыша: Элементы этих векторов должны удовлетворять условиям:  a ( x, y )  m  xi  1, xi  0, i  1,..., m; y j  0, j  1,..., n. 9  x2 y1  5  x2 y2  4  x2 y3  i1 n  y j  1, 4  x3 y1  5  x3 y 2  1  x3 y3 . При различных допустимых векторах смешанных стратегий игроков j 1 Очевидно, что каждая чистая стратегия является частным случаем сме- можно получить конкретные значения для функции выигрыша. Например, шанной стратегии: когда все стратегии, кроме данной, имеют нулевые вероят- пусть ности, а данная – единичную вероятность. 1 xT   2 В условиях смешанных стратегий каждая обычная ситуация (в чистых  1  x1 y1  6  x1 y2  3  x1 y3   стратегиях) Ai , B j является случайным событием и ввиду независимости на-   реализуется с вероятностью боров вероятностей xi  , y j Ai , B j  игрок A получает выигрыш xi y j . В ситуации смешанная 1 4 первого игрока 1 1 T  , второго игрока – вектором y   4 7 определяется 2 7 вектором 4  , тогда значение 7 функции выигрыша будет следующим  a ( x, y )  aij . Таким образом, математическое ожи- дание выигрыша (функция выигрыша первого игрока или, что то же самое, функция проигрыша второго игрока) игрока A в условиях смешанных стратегий будет определяться следующим образом: m n  a ( x, y )    aij xi y j . стратегия 1 1 1 2 1 4 1   6    3    2 7 2 7 2 7 1 1 1 2 1 4 9    5    4    4 7 4 7 4 7 1 1 1 2 1 4 4    5    1    4 7 4 7 4 7 2  24  24  9  10  16  4  10  4 57   . 28 28 Следует отметить, что и чистые стратегии также можно представить в ви- i 1 j 1 Это число принимается за средний выигрыш игрока A при смешанных де векторов. Так, например, чистая стратегия A2 первого игрока определяется вектором x T  0 1 0 , чистая стратегия B1 второго игрока – вектором стратегиях. Пример 1.10. Составим функцию выигрыша в игре с платежной матри- 6 3  1   цей A    9 5 4 .  4  5  1   y T  1 0 0  , и т.п. Нетрудно посчитать соответствующий выигрыш:  a ( x, y )  1 0 1  6  0  0  3  0  0  9  1  1  5  1  0  4  1  0  4  0  1  5  0  0  1  0  0  9. Решение1 Для удобства припишем к платежной матрице справа компо21 22 Отметим, что это значение совпадает (и должно совпадать) с элементом (– 9), стоящим на пересечении второй строки и первого столбца платежной Основная теорема теории игр. Каждая конечная игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий. Активными стратегиями игрока называются те стратегии, которые вхо- матрицы.  T Стратегии x *  x1*  T  x2* ... xm* , y *  y1* y 2* ... yn *  называют оптимальными смешанными стратегиями игроков A и B соответственно, если m n * * * m n ся своей оптимальной стратегии, то выигрыш первого игрока (проигрыш второ*   aij xi y j    aij xi y j    aij xi y j . i 1 j 1 i 1 j 1 тивном случае стратегия называется пассивной. Теорема об активных стратегиях. Если один из игроков придерживает- выполняется двустороннее неравенство: m n дят в его оптимальную стратегию с отличными от нуля вероятностями. В про- (1.1) i 1 j 1 Решением игры называется пара x* , y * , в общем случае смешанных, об- го игрока) остается неизменным и равным цене игры  * , независимо от того, что делает другой игрок, если только тот не выходит за пределы своих активных стратегий. ладающих свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей оптимальной. Смысл этой теоремы состоит в том, что если один из игроков начнет последовательно придерживаться своей оптимальной смешанной стратегии, то противостоящий ему игрок уже не сможет изменить исход игры. Левое неравенство в (1.1) означает, что если второй игрок придерживается своей оптимальной стратегии, а первый будет отклоняться от своей опти- Эта теорема имеет большое практическое значение: она дает конкретные методы нахождения оптимальных стратегий при отсутствии седловой точки. мальной стратегии, то это повлечет уменьшение выигрыша для второго игрока. Аналогично для правого неравенства. Задания для самостоятельной работы Выигрыш, соответствующий решению, называется ценой игры; обозначим ее через  * (как чистую цену): стить матрицу игры, удалив заведомо невыгодные стратегии: m n  *    aij xi * y j * . i 1 j 1 В векторно-матричной форме последнее неравенство будет выглядеть следующим образом: * *T 1. Определить нижнюю и верхнюю цены игры, заданной матрицей; упро- 7 6 а) A    2 4 2 9 4 6 5 1 3 7 4 2 ; 1 9 3 1  9 2 б) A   10 1 1 5 2 4 8 1 9 3 6 6 6 . 4 3 4 9  2. Определить наличие седловых точек в следующих матрицах, найти ре- *   x Ay . шение в играх с седловой точкой. Цена игры всегда лежит между нижней и верхней ценами игры: *     . Если  *  0 , то игра выгодна первому игроку; если  *  0 – второму иг- 3 4 1 а) A   6 0 7  ; 9 2 1    8 2 4 б) A   9 0 7  ; 8 1 5   року; при  *  0 игра «честная» или «справедливая», т.е. одинаково выгодная для обоих участников. 23 24 4  3 в) A   7  8 5 6 7 9  4 6 7 6 . 6 10 8 11  5 4 7 3  ГЛАВА 2. МЕТОДЫ РЕШЕНИЯ АНТАГОНИСТИЧЕСКИХ ИГРОВЫХ КОНФЛИКТОВ a11x1*  a 21x2*   * . B2 a a A A   11 12  1 a a A  21 22  2 Аналогично составляется уравнение для стратегии B2. Следовательно, получаем систему уравнений 2.1.1. Аналитический метод Предположим, что у платежной матрицы A нет седловой точки, следовательно, решение должно быть в смешанных стратегиях. Определим это решеT  ние, т.е. найдем пару оптимальных смешанных стратегий x *  x1* y   y2 *  и цену игры  Сначала T  x *  x1* определим вероятность соответствующего выигрыша и складывая полученные произведения: каждого игрока по две стратегии: y1*  x2* . С вероятностью x1* выигрыш первого игрока соста- игрыш, соответствующий решению) получим, умножая значение выигрыша на Наиболее простым случаем конечной игры является игра 2  2 , когда у *T  вит a11 , с вероятностью x2* – выигрыш будет a 21 . Цену игры (или средний вы- 2.1. Методы решения матричных игр размерности 2  2 B1 T стратегию x *  x1* *  x2 * , . смешанную стратегию первого игрока  x2 * . Согласно теореме об активных стратегиях, если один из игроков придерживается своей оптимальной стратегии, то его выигрыш остается неизменным и равным цене игры ν, независимо от образа действий противника, если только тот не выходит за пределы своих активных стратегий. В игре 2  2 обе стратегии противника являются активными (в противном случае игра имела бы седловую точку). Значит, если первый игрок придерживается своей оптимальной стратегии x* , его противник может, не меняя выигрыша, применять любую из своих чистых стратегий. Чтобы составить систему уравнений, вспомним, что цена игры – это математическое ожидание выигрыша при оптимальных стратегиях. Будем искать ее как математическое ожидание дискретной случайной величины – выигрыша игрока A. Пусть игрок B применяет свою стратегию B1, а игрок A – смешанную 25 a11 x1*  a21 x2*   * ,  a12 x1*  a 22 x2*   * , из которой с учетом условия нормировки x1*  x2*  1 получим формулы для расчета оптимальной стратегии первого игрока и цены игры:  * a 22  a 21 ,  x1  a11  a 22  a12  a 21   * a11  a12 ,  x2  a  a 11 22  a12  a 21   a11a 22  a 21a12 .   a11  a 22  a12  a 21  Аналогично получаются формулы для расчета оптимальной стратегии второго игрока и цены игры:  * a 22  a12 ,  y1  a  a 11 22  a12  a 21   * a11  a 21 ,  y2  a11  a 22  a12  a 21   a11a 22  a 21a12 .   a11  a 22  a12  a 21  Следует отметить, что можно и не запоминать формулы, по которым находятся оптимальные смешанные стратегии каждого из игроков. Можно поступать проще: составлять соответствующие системы линейных уравнений и на26 ходить их решение.  4 7  . Пример 2.1. Найти решение игры, определяемой матрицей A    5 2 Решение. Данная игра седловой точки не имеет:   4,   5 . Поэтому решение игры ищем в смешанных стратегиях. Для удобства запишем платежную матрицу в виде: B1 A1 A2 B2 T 1 Окончательно получаем решение задачи: x *   2 T 5 стратегия первого игрока, y *   6 ка,  *  1  – оптимальная 2 1  – оптимальная стратегия второго игро6 9 – цена игры. 2 2.2.2. Метод, основанный на понятии равновесия по Нэшу  4 7  x1    5 2  x2 y1 y 2  m ... для всех i  1, ..., n достигается оптимум h m   max h m . Равновесие по Нэшу есть точка m H  m1H H 2 mn H  такая, что H i Составим следующие системы линейных уравнений (с помощью теоремы об активных стратегиях и условия нормировки). Пусть второй игрок поочередно принимает свои чистые стратегии, а первый игрок – свою смешанную стратегию. Получим систему i mi Точка m H определяется из решения системы уравнений hi m  0, i  1, ..., n . mi Рассмотрим игру 2  2 , не имеющую седловой точки 4 x1  5 x 2   * ,  * 7 x1  2 x2   ,  x  x  1. 2  1 B1 B2 a a A A   11 12  1  a21 a22  A2 Найдем решение системы любым известным способом и получим: Пусть игрок A использует свою стратегию A1 с вероятностью x, а стратегию A2 – с вероятностью 1–x. Пусть игрок B использует свою стратегию B1 с 1 1 9 x1  , x 2  ,  *  . 2 2 2 вероятностью y, а стратегию B2 – с вероятностью 1–y. Аналогично составим систему для определения оптимальной стратегии второго игрока: первый игрок поочередно принимает свои чистые стратегии, а второй игрок – свою смешанную стратегию. Имеем 4 y1  7 y 2   * ,  * 5 y1  2 y 2   ,  y  y  1. 2  1 a  x a A   11 12   a21 a22 1  x y 1 y Тогда математическое ожидание выигрыша игрока A будет определяться функцией  a ( x, y )  a11xy  a12 x(1  y )  a21 (1  x) y  a22 (1  x)(1  y ) . 5 1 9 Откуда находим y1  , y 2  ,  *  . 6 6 2 27 Очевидно  b ( x, y )   a ( x, y ) . Точка Нэша уравнений 28 x Н , yН  определяется из  a ( x, y )  0, x  a ( x, y )  0. y  1 5 Тем самым,  ,  – точка равновесия Нэша. Тогда оптимальные страте 2 6  С математической точки зрения точка Нэша x Н , y Н  определяет такие две координаты, что при фиксированном x  x Н функция  a ( x Н , y ) достигает минимума при y  y Н (второй игрок минимизирует свой проигрыш), а при фиксированном y  y Н функция  a ( x, y Н ) достигает максимума при x  x Н (первый игрок максимизирует свой выигрыш).   Зная точку Нэша x Н , y Н , можно легко определить оптимальные страте*  гии x  x Н 1 x  , y  y Н T * Н 1 y  Н T * Н 1  и цена игры равна 6 1 5 1  5 1 5  1 5  1  5  *   a  ,   4    7   1    5  1     2  1    1    2 6 2 6 2 6 2 6        2  6 1 5 1 1 1 5 1 1 20  7  25  2 54 9  4   7   5   2     . 2 6 2 6 2 6 2 6 12 12 2 Как можно увидеть, решение совпадает с результатами, полученными аналитическим методом. и цену игры    a ( x , y ) . используя понятие равновесия по Нэшу. Решение. Для удобства запишем платежную матрицу в виде: 2.2.3. Графический метод решения игр размерности 2  2 Решению игры 2  2 можно удобную геометрическую интерпретацию. Пусть имеется игра 2  2 с платежной матрицей B1 B2 a a A A   11 12  1  a21 a22  A2 B2 A1  4 7  x   A2  5 2  1  x y 1 y Предположим, что решение игры в чистых стратегиях отсутствует. Предположим, игрок A выбрал смешанную стратегию  x1 x2  , а игрок B – свою чи- стую стратегию B j , тогда средний выигрыш игрока A определяется по форму- и запишем функцию выигрыша  a ( x, y )  4 xy  7 x (1  y )  5(1  x) y  2(1  x)(1  y ) . Отметим, что нет необходимости преобразовывать эту функцию. Определим точку Нэша: ле математического ожидания  B j  a1 j x1  a 2 j x2  a1 j  a2 j  a1 j x, j  1, 2 , где x  x2  1  x1 .   a ( x, y )  4 y  7(1  y )  5(1) y  2(1)(1  y )  0,  x   ( x, y )  a  4 x  7 x(1)  5(1  x )  2(1  x)(1)  0,  y  6 y  5  0,   6 x  3  0, 1  *T  5 , y   2 6 Н  4 7 Пример 2.2. Найти решение игры, определяемой матрицей A    ,  5 2 B1 T 1 гии каждого из игроков x *   2   y Н  5 / 6,  Н  x  1 / 2. Каждая из функций соответствует прямой линии в прямоугольной системе координат. Изобразим эти прямые на плоскости (рис. 2.1). В системе координат XOY на оси абсцисс отложим отрезок A1 A2 длиной, равной единице. Левый конец отрезка (при x = 0) соответствует стратегии A1, правый конец (при x = 1) – стратегии A2. Все промежуточные точки – смешанные стратегии игрока A. Через точки A1 и A2 проведем два перпендикуляра к оси абсцисс. На первой оси будем откладывать выигрыш при стратегии A1, а на 29 30 второй оси – выигрыш при стратегии A2. В рассмотренном примере решение игры определяется точкой пересече- Пусть противник применяет стратегию B1, тогда  B1  a11  a21  a11 x . ния стратегий B1 и B2, но это не всегда так, решение игры определяется именно При A1 выигрыш будет равен a11 , а при A2 выигрыш будет равен a21. Отложим верхней точкой нижней границы, а эта точка не всегда совпадает с точкой пере- эти точки на перпендикулярных осях соответственно, обозначим их B1 и проведем через эти точки прямолинейный отрезок, назовем этот отрезок «стратегия B1 ». Аналогично строим отрезок, соответствующей «стратегии B2 ». сечения стратегий. Рассмотрим два примера. На рис. 2.2 представлен случай, когда оптиT мальной стратегией первого игрока является стратегия A2, т.е. x *  (0, 1) . Здесь стратегия A2 явно выгоднее стратегии A1 независимо от поведения противника. Рис. 2.2. Иллюстрация к графическому методу Рис. 2.1. Иллюстрация к графическому методу На рис. 2.3 представлен случай, когда заведомо невыгодная стратегия T Далее согласно принципу максимина определим оптимальную стратегию. имеется у противника. Для этого случая x *  (1, 0) . Поскольку цель игрока B – минимизировать выигрыш игрока A за счет выбора своих стратегий, построим нижнюю границу выигрыша при стратегиях B1, B2 (ломанная отмечена на рисунке жирной линией). На этой ломанной будет лежать минимальный выигрыш игрока A при любой его смешанной стратегии. Поскольку цель игрока A – максимизировать свой выигрыш за счет выбора соотношения x2 : x1 , ищем верхнюю точку нижней границы выигрыша. Точка M, в которой этот выигрыш достигает своего максимального значения, определяет решение и цену игры. Ордината точки M – цена игры  * , ее абсцисса равна x2* , а расстояние до правого конца участка – x1* . 31 Рис. 2.3. Иллюстрация к графическому методу 32 Рассмотрим теперь, как определяется оптимальная смешанная стратегия T  второго игрока y *  y1*  y2* . Для ее нахождения можно использовать такой же подход: построить и изобразить на плоскости функции выигрыша первого игрока при различных допустимых стратегиях второго игрока:  Ai  ai1 y1  ai 2 y 2  ai1  ai 2  ai1  y , i  1, 2 , где y  y 2  1  y1 . Только в данном случае точка равновесия выбирается как нижняя точка верхней границы выигрыша. Однако можно поступить иначе (и проще). В самом общем случае при отсутствии решения в чистых стратегиях, каждая из стратегий первого игрока будет активной, а тогда возможно применение теоремы об активных стратегиях. Рис. 2.4. Иллюстрация к примеру 2.3 Т.е., если первый игрок будет применять любую из своих чистых (активных) стратегий, а второй игрок – свою оптимальную стратегий, то выигрыш будет оставаться неизменным и равным цене игры. Тогда можно составить и решить Тем самым, точка M является верхней точкой нижней границы. Определим ее координаты: следующую систему линейных уравнений:  B1   B2 , a11 y1  a12 y2   ,  a 21 y1  a22 y 2   , где  – это найденное ранее значение цены игры. Следует отметить, что вычисленные из системы значения y1* , y 2* должны удовлетворять условию нор- 2  5 x  3  7 x, 12x  5, x 5 . 12 T 1 7 5 * Таким образом, x *    и  . 12 12 12   Найдем оптимальную смешанную стратегию второго игрока. Для этого составим систему: мировки, т.е. y1*  y2*  1 . Пример 2.3. Найти графически решение игры, определяемой матрицей A   2  3  . 3 4  Решение. Определим прямые  B1  2   3  2 x  2  5 x,  B2  3  4  3x  3  7 x 1  2 y1  3 y2   12 ,   3 y  4 y   1 , 1 2  12   * 7  y1  12 ,  y *  5 .  2 12 T 7 5 Таким образом, y *   .  12 12  и построим их на графике (рис. 2.4). 2.3. Графический метод решения игр размерности 2  n и m  2 Для решения матричных игр, в которых число стратегий хотя бы одного из игроков равно двум, эффективным является графический способ, аналогичный способу решения игр 2  2 . 33 34 ем, в результате каких стратегий получена верхняя точка нижней границы, – 2.3.1. Игры размерности 2  n эти стратегии называются активными, остальные стратегии – пассивные. На Рассмотрим игру 2  n с платежной матрицей рис. 2.5 активными являются стратегии B2 и B5. Далее аналогично, как и в пре- B1 дыдущем пункте, вычисляется оптимальная стратегия второго игрока с учетом, B2 ... Bn  a11 a12 ... a1n  A1    a21 a22 ... a2n  A2 что вероятности пассивных стратегий равны нулю. У игрока A – 2 стратегии, у игрока B – n стратегий. Дадим геометриче- иметь место при определении оптимальных стратегий. Остановимся подробнее на некоторых частных случаях, которые могут   скую интерпретацию: изобразим n стратегий игрока B в виде n прямых, уравнения которых имеют вид: 1. Верхняя точка нижней границы выигрыша имеет координаты 0, * (рис. 2.6, а).  Bi  a1i x1  a 2i x2  a1i  a 2i  a1i x, i  1, ..., n . Далее определяем нижнюю границу выигрыша (ломанная B1 B2 B5 ) и верхнюю точку этой нижней границы – точку M (рис. 2.5). В этом случае оптимальной стратегией игрока A является чистая стратегия A1, поскольку x1*  1, x 2*  0 . Игроку B выгодно применять чистую страте-   гию, соответствую прямой, проходящей через точку 0, * и имеющей наибольший отрицательный наклон. Цена игры равна  * .   2. Верхняя точка нижней границы выигрыша имеет координаты 1, * (рис. 2.6, б). В этом случае оптимальной стратегией игрока A является чистая стратегия A2, поскольку x1*  0, x2*  1. Игроку B выгодно применять чистую страте-   гию, соответствую прямой, проходящей через точку 1, * и имеющей наименьший положительный наклон. Цена игры равна  * . 3. Нижняя граница выигрыша имеет горизонтальный участок (рис. 2.6, в). В этом случае максимум нижней границы будет не в одной точке, а на Рис. 2.5. Иллюстрация к графическому методу участке MM  , ордината которого равна цене игры  * . Решение для игрока A в этом случае будет неоднозначным: он может применять любую из своих сме- Ордината этой точки и будет ценой игры, абсцисса этой точки равна вероятности x2* , а расстояние от точки M до правого конца участка – x1* . Чтобы получить оптимальную смешанную стратегию игрока B, определя- шанных стратегий, соответствующих точкам оси абсцисс от x до x' . Таким образом, у игрока A существует бесконечное множество оптимальных стратегий T  x *  x1*  x2* , где x2 *  x, x', x1*  1  x2* . Решение для игрока B определяется с помощью граничных точек участка 35 36 MM  по тем же правилам, как и ранее. Нетрудно убедиться, что стратегия игрока B, которой соответствует горизонтальный участок, является его чистой оптимальной стратегией. а) б) Рис. 2.7. Иллюстрация к примеру 2.4 Из рисунка видно, что верхней точкой нижней границей является точка M в) Рис. 2.6. Иллюстрации к частным случаям графического метода Пример 2.4. Определить графическим методом решение игры, определяемой матрицей A   2  5 4 10  . 3 1  4  6 Решение. Определим функции выигрыша  B1  2  3  2x  2  x,  B2  5  1  5x  5  6 x,  B3  4   4  4x  4  8 x,  B4  10   6  10x  10  16 x и построим их на графике (рис. 2.7). 37 – точка пересечения стратегий B2 и B3 , найдем ее координаты:  B2   B3 , 5  6 x  4  8 x, 14 x  9, x 9 , 14 8   . 7 T 8 5 9 * Тем самым, x *   ,    . 7  14 14  Определим оптимальную смешанную стратегию игрока B. Пассивными являются стратегии B1 и B4, поэтому y1*  y 4*  0 . Найдем вероятности активных стратегий. Для этого составим систему и найдем ее решение: 8  2  0  5  y 2  4  y3  10  0   7 ,  3  0  1  y  4  y  6  0   8 , 2 3  7  38  * 4  y 2  7 ,  y *  3.  3 7 T 4  Таким образом, y *   0 7  3 7 T  0  – оптимальная стратегия второго иг рока.  Тем самым получаем решение задачи: x *  1  x* 3 2  x* , где x *   ,  , 5 3   T y *  0 1 0  ,  *  7 . Пример 2.5. Определить графическим методом решение игры, опреде-  2 5 9 ляемой матрицей A    .  7 5 3 2.3.2. Игры размерности m  2 Пусть теперь в матричной игре игрок B имеет две стратегии, игрок A – m Решение. Определим функции выигрыша  B1  2  7  2x  2  5 x,  B2  5  5  5x  5,  B3  9  3  9x  9  6 x стратегий. Платежная матрица такой игры имеет вид B1 B2  a11 a12  A1   A   a21 a22  A2 ...  ...  ...  am1 am2  Am и построим их на графике (рис. 2.8). Анализ такой игры во многом повторяет рассуждения, описанные для игры 2  n . Изобразим m стратегий игрока A в виде m прямых, уравнения которых имеют вид  A j  a j1 y1  a j 2 y 2  a j1  a j 2  a j1 y, j  1, ..., m , где y  y 2  1  y1 (рис. 2.9). Рис. 2.8. Иллюстрация к примеру 2.5 Получили, что максимум нижней границы выигрыша достигается на участке MM  . Определим координаты границ этого промежутка: M : 2  5 x  5, 5 x  3, x  3 / 5,  *  5; M  : 9  6 x  5, 6 x  4, x  2 / 3,  *  5. Очевидно, что стратегия B2 является оптимальной чистой стратегией второго игрока. Рис. 2.9. Иллюстрация к графическому методу 39 40 Далее определяем верхнюю границу (ломанная A5 A4 A1 ) и нижнюю точку T 4 ка y *   7 3 * 15  и цену игры   . 7 7 верхней границы – точку M. Такой подход соответствует принципу минимакса: второму игроку из наихудших вариантов (максимальные проигрыши) следует выбрать наилучший (наименьший из наибольших выигрышей первого игрока). Ордината этой точке равна цене игры  * , абсцисса этой точки – вероятности y 2* стратегии B2 , при этом вероятность стратегии B1 равна y1*  1  y 2* . В це-  T лом оптимальная смешанная стратегия второго игрока y *  y1*  y2 * . После этого определяем оптимальную смешанную стратегию игрока A. Для этого смотрим, какие стратегии пересекаются в точке M, эти стратегии называются активными стратегиями, Остальные стратегии – пассивные (их вероятности равны нулю). На рис. 2.9 активными являются стратегии A1 и A4. Далее определяем оптимальную стратегию первого игрока способом, описанным ранее. Рис. 1.10. Иллюстрация к примеру 2.6 Пример 2.6. Определить графическим методом решение игры, опреде-  6  4 3 1  ляемой матрицей A   4  2  . 0 5  1 6    Пассивными стратегии A1 , A3 и A5, следовательно, x1*  y3*  y5*  0 . Найдем вероятности активных стратегий: Решение. Определим функции выигрыша  A1  6   4  6  y  6  10 y,  A2  3  1  3 y  3  2 y,  A3  4   2  4  y  4  6 y , являются  A4  0  5  0  y  5 y, 15  3  x2  0  x4  7 ,  1  x  2  x  15 , 4  2 7  * 5  x2  7 ,  x *  2 .  4 7  Таким образом, получаем оптимальную смешанную стратегию первого  A5  1  6  1 y  1  7 y T 5  игрока x *   0 7  и построим их на графике (рис. 2.10). 2  0 . 7  Минимум верхней границы достигается в точке M, в которой пересекаются стратегии A2 и A4. Найдем координаты этой точки:  A2   A4 , 3  2 y  5 y, 7 y  3, 3 y , 7 2.4. Решение игр размерности m  n методом линейного программи- 15  . 7 Тем самым, получаем оптимальную смешанную стратегию второго игро- рования Решение любой матричной игры m  n сводится к задаче линейного программирования. 41 42 Рассмотрим игру m  n с m стратегиями A1 , A2 , ..., Am игрока A и n страте- наименьшее из отрицательных значений платежной матрицы, взятое с обрат- гиями B1 , B2 ,..., Bn игрока B, которая задается матрицей   ным знаком (  min aij ). Можно поступить иначе: прибавить нижнюю цену иг- B1 B2 ... Bn  a11 a12  A   a21 a22 ...  ... a a m 1 m2  Требуется T ры, взятую с противоположным знаком (   ), если она отрицательна, посколь- ... a1n  A1 ... a2 n  A2 ... ...  ... ... amn  Am определить тельность цены игры, поэтому ко всем элементам матрицы можно прибавить ку имеет место неравенство      . Пусть игрока A применяет свою оптимальную смешанную стратегию оптимальные стратегии игроков T x *   x1 , x2 , ..., xm  , y *   y1, y2 , ..., y n  и цену игры  * . Сначала найдем оптимальную стратегию игрока A. Эта стратегия должна x1 , x2 ,..., xm  , стратегия игрока A такова, что при любом поведении противника обеспечивает выигрыш, не меньший цены игры, можно записать следующие условия: a11 x1  a21 x2  ...  am1 xm   , a x  a x  ...  a x   , 22 2 m2 m  12 1 ........................................., a x  a x  ...  a x   , 2n 2 mn m  1n 1  x1  x2  ...  xm  1. обеспечивать выигрыш, не меньший цены игры, при любом поведении второго игрока и выигрыш, равный цене игры, при его оптимальной стратегии. Цена игры нам неизвестна, поэтому зададим ее в виде некоторого положительного числа ν. Для того что выполнялось условие ν>0 достаточно, чтобы все элементы платежной матрицы были неотрицательными. Этого всегда можно добиться, (2.1) Разделим каждое из неравенств (2.1) на положительное число ν и введем если воспользоваться аффинным правилом, определяющим допустимые правила преобразования матрицы игры и ее цену. а игрок B – только чистые стратегии. Поскольку оптимальная новые переменные xi  zi , i  1, ..., m .  Аффинное правило. Оптимальные стратегии у матричных игр, элементы матриц A и C которых связаны равенством (2.2) Тогда условия (2.1) запишутся в виде cij  aij   , i  1, ..., m, j  1, ..., n , элементам платежной матрицы одно и то же число, цена игры увеличится на  a11 z1  a21 z2  ...  am1 z m  1,  a12 z1  a22 z 2  ...  am 2 z m  1,  ........................................., a z  a z  ...  a z  1, 2n 2 mn m  1n 1 1   z1  z 2  ...  zm   . это число, а решение не изменится. Игрок A хочет сделать свой выигрыш ν максимальным, а значит, величи- где   0 , а  – произвольно, имеют одинаковые равновесные ситуации (либо в чистых, либо в смешанных стратегиях), а их цены удовлетворяют условию  C   A   . Согласно приведенному аффинному правилу, если прибавить ко всем Таким образом, будем считать, что условие ν>0 выполнено, в противном случае ко всем элементам платежной матрицы прибавить положительное число, а в конце решения выполнить соответствующую корректировку. Положительность элементов платежной матрицы гарантирует положи43 ну (2.3) 1 минимальной. Тем самым, задача сводится к минимизации правой части  последнего соотношения в (2.3). Таким образом, задача определения оптимальной смешанной стратегии 44 игрока A сводится к следующей задаче линейного программирования. игрока B свелась к следующей задаче линейного программирования. (I) Определить неотрицательные переменные z1, z2 , ..., z m так, чтобы (II) Требуется определить неотрицательные значения переменных w1, w2 , ..., wn так, чтобы они удовлетворяли линейным ограничениям вида они удовлетворяли линейным ограничениям вида n m  aij zi  1, j  1, .., n , (2.4)  aij w j  1, i  1, .., m , и при этом их линейная функция f достигала минимума и обращали в максимум линейную функцию m f   zi  min . (2.5) i 1 x видно, что задача определения оптимальной стратегии   x1 , x2 , ..., xm  сводится к типовой задаче линейного программирования. Оптимальная смешанная стратегия  y1, y2 , ..., y n  игрока B определяется аналогично. Однако при этом необходимо учесть, что цена игры ν для игрока B есть проигрыш, и, следовательно, он стремится ее минимизировать, а значит, минимизировать величину 1/ν. Оптимальная стратегия игрока B должна обеспечивать проигрыш, не больший цены игры ν, при любом поведении игрока B и проигрыш, равный це- Линейные ограничения в данном случае будут иметь следующий вид:  венных задач. Рассмотрим алгоритм решения задачи на конкретном примере. Пример 2.7. Определить с помощью методов линейного программирова-  0 1  1   ния решение игры с матрицей A    1 0 1  (игра «Камень, ножницы, бу 1 1 0    мага»). ловой точки нет, следовательно, решение ищем в смешанных стратегиях. прибавим ко всем элементам матрицы такое положительное число γ=1, чтобы (2.6) элементы матрицы стали неотрицательными. Получаем новую платежную мат- 1 2 0  ~  рицу A   0 1 2  . 2 0 1   – неотрицательные переменные, удовлетворяющие условию w1  w2  ...  wn  Не сложно увидеть, что задачи (I) и (II) представляют собой пару двойст- Поскольку среди элементов платежной матрицы есть отрицательные, то a11w1  a12 w2  ...  a1n wn  1, a w  a w  ...  a w  1,  21 1 22 2 2n n  .......... .......... .......... .......... .,  am1w1  am2 w2  ...  amn wn  1, yj (2.9) Решение. Определим нижнюю и верхнюю цены игры:   1,   1. Сед- не игры ν, при его оптимальном поведении. где w j  n g   w j  max . j 1 Отсюда *T (2.8) j 1 i 1 Составим пару двойственных задач линейного программирования, опре- 1 ,  (2.7) деляющих решение исходной задачи. которое вытекает из условия нормировки. Поскольку для игрока B цена игры ν – это проигрыш, то задача сводится к максимизации правой части в (2.7). Таким образом, задача определения оптимальной смешанной стратегии 45 46 По последней строке симплекс-таблицы (коэффициенты целевой функ- f  z1  z2  z3  min  z1  2 z3  1, 2 z  z  1,  1 2  2 z 2  z3  1,  z1, 2,3  0.  ции (I) при w4,5, 6 ) определяем оптимальное решение первой задачи: 1 1 1 z1  , z 2  , z 3  . Отсюда получаем оптимальную смешанную стратегию 3 3 3 T 1 1 1 первого игрока x*   , ,  .  3 3 3 g  w1  w2  w3  max w1  2w2  1, w  2w  1,  2 3  2 w  w  1, 1 3  w1, 2,3  0. Таблица 2.1 (II) Симплекс-методом определим решение задачи (II). Приведем ограничения задачи к каноническому виду; для этого к левой части каждого ограничения прибавим неотрицательные переменные w4,5, 6 . Получаем новую задачу, эквивалентную задаче (II): g  w1  w2  w3  max w1  2w2  w4  1, w  2w  w  1,  2 3 5  2 w  w  w  1, 1 3 6  w j  0, j  1, ..., 6.  Составим симплекс-таблицу (табл. 2.1) и выполним ее преобразования, пока не выполнится критерий оптимальности – неотрицательность элементов нижней строки. Расчетная симплекс-таблица примера 2.7 БП w4 w5 w6 g w4 w5 w1 g w2 w5 w1 g w2 w3 w1 g w1 1 2 -1 1 1 1 w2 2 1 -1 2 1 -1 1 1 w3 2 1 -1 -1/2 2 1/2 -1/2 -1/4 9/4 1/2 -3/4 1 w4 1 1 1/2 -1/2 1/2 4/9 -2/9 1/9 1/3 w5 1 1 1 1/9 4/9 -2/9 1/3 w6 1 -1/2 1/2 1/2 -1/4 1/4 1/2 1/4 -2/9 1/9 4/9 1/3 СК 1 1 1 1/2 1 1/2 1/2 1/4 3/4 1/2 3/4 1/3 1/3 1/3 1 i 1 1/2 1/4 1/2 1/3 1 1 1 1 Тем самым, получили оптимальное решение w1  , w2  , w3  , g  1 . 3 3 3 С практической точки зрение полученное решение означает, что каждому По этому решению определяем цену игры и оптимальную смешанную страте- из игроков с равной вероятностью можно принимать любую из своих стратегий гию игрока B: (показывать «Камень», «Ножницы» или «Бумага»), при этом значение выигры- 1 1 1 1  *     0, y1*   w1  , y 2*   w2  , y3*   w3  g 3 3 3 ша  *  0 означает, что в равновесной ситуации соответствует ничья. T 1 1 1 или y *   , ,  . 3 3 3 47 48 2.5. Практическое применение смешанных стратегий го максимально неблагоприятные). В этом случае фермер имеет в своём распо- Рассмотрим практическое применение смешанных стратегий на примере ряжении три чистые стратегии: конкретных конфликтных ситуаций. – первая чистая стратегия предполагает, что весь участок земли буде за- Пример 2.8 (планирование посевов). Фермер, имеющий ограниченный участок земельных угодий, может его засадить тремя различными культурами A1, A2, A3. Урожай этих культур зависит главным образом от погоды («природы»), которая может находиться в трёх различных состояниях: B1 , B2, B3. Фермер имеет информацию (статистические данные) о средней урожайности этих сеян культурой A1 ; – вторая чистая стратегия предполагает, что весь участок земли будет засеян культурой A2 ; – третья чистая стратегия предполагает, что весь участок будет засеян культурой A3. культур (количество центнеров культуры, получаемого в одного гектара земли) Как игрок, природа может также использовать три возможные стратегии: при трёх различных состояниях погоды, которая отражена в табл. 2.2. – засушливую погоду, которая соответствует первой чистой стратегии B1 ; Таблица 2.2 – дождливую погоду, которая соответствует третьей чистой стратегии B3. Расчетная данные для примера 2.8 Виды культур A1 A2 A3 B1 20 7 Возможные состояния природы B2 B3 15 10 15 5 5 10 – нормальную погоду, которая соответствует второй чистой стратегии B2; Цена (у.е./ц.) 5 7 10 Составим пару двойственных задач линейного программирования, определяющих решение исходной задачи. f  z1  z 2  z3  min торые получит фермер одного гектара земли, если он посеет соответствующую 100 z1  49 z 2  1, 75z  105z  50 z  1,  1 2 3  50 z  35 z  100 z 2 3  1,  1  z1, 2,3  0. культуру при соответствующей погоде: g  w1  w2  w3  max Определить оптимальную стратегию фермера при планировании засевов. Решение. В качестве платежной матрицы выберем матрицу доходов, ко- 100 75 50    A   49 105 35  .  0 50 100   Данная задача может быть сведена к антагонистической игре. В данном (I) 100w1  75w2  50w3  1, 49w  105w  35w  1,  1 2 3  50w2  100w3  1, w1, 2,3  0. (II) случае в качестве первого игрока выступает фермер, а в качестве второго игро- Симплекс-методом определим решение задачи (II). Приведем ограниче- ка – природа. Будем предполагать, что природа, как игрок, может вести себя та- ния задачи к каноническому виду; для этого к левой части каждого ограничения ким образом, чтобы максимально навредить фермеру, преследуя тем самым прибавим неотрицательные переменные w4,5, 6 . Получаем новую задачу, экви- противоположные интересы (эти предположения позволяют оценить тот доход, валентную задаче (II): который он может получить в том случае, если погодные условия будут для не- 49 50 По последней строке симплекс-таблицы (коэффициенты целевой функ- g  w1  w2  w3  max 100w1  75w2  50w3  w4  1, 49w  105w  35w  w  1,  1 2 3 5  50w2  100w3  w6  1, w1, 2,3  0.  ции z1  Составим симплекс-таблицу (табл. 2.3) и выполним ее преобразования, Расчетная симплекс-таблица примера 2.8 w2 75 105 50 w3 50 35 100 w4 1 w5 1 w6 1 СК 1 1 1 L w1 w5 w6 L w1 w5 w6 -1 -1 3/4 273/4 50 -1 1/2 21/2 100 1/100 -49/100 1 1 1/100 51/100 1 1 -1/4 3/4 273/4 50 -1/2 1/2 21/2 100 1/100 1/100 -49/100 1 1 1/100 1/100 51/100 1 L w1 w5 w3 1 -1/4 1/2 63 1/2 -1/2 1 1/100 1/100 -49/100 1 -1/200 -21/200 1/100 1/100 1/200 81/200 1/100 L 1/100 1/200 3/200 1 Таким w1  решение первой задачи: T  2 1 гию первого игрока x*   , 0,  .  3 3 В соответствии с полученными результатами фермеру гарантирован образом, получили культурами земли при самых неблагоприятных условиях. Оптимальная стратегия для него – выращивание двух культур, A1 и A3, причём, под первую культу- w1 100 49 w4 w5 w6 оптимальное средний доход в размере 66,67 единиц с каждого гектара используемой под Таблица 2.3 БП определяем 1 1 , z2  0, z3  . Отсюда получаем оптимальную смешанную страте100 200 пока не выполнится критерий оптимальности – неотрицательность элементов нижней строки. w4,5, 6 ) при оптимальное i ру ему следует отвести 0,67 часть всей земли, а под третью культуру 0,33 часть 1/100 1/49 всей земли. Природа «грозит» фермеру жарой 0,33 часть сезона возделывания культур и 0,67 часть сезона дождями. Пример 2.9. Директор транспортной компании А, оказывающей транспортные услуги по перевозке пассажиров в областном центре, планирует открыть один или несколько маршрутов: А1, А2, А3 и А4 . Для этого было закуплено 100 микроавтобусов. Он может поставить весь транспорт на одном из маршру- 1/50 51/1050 1/100 тов (наиболее выгодном), либо распределить по нескольким маршрутам. Спрос на транспорт, а соответственно и прибыль компании во многом зависит от того, какие маршруты в ближайшее время откроет главный конкурент – компания В. Ее руководство полностью владеет ситуацией и может открыть несколько из пяти маршрутов В1, В2, В3, В4 и В5. Оценки прибыли компании А (млн. руб.) при любом ответе В представлена платежной матрицей: B1 B2 B3 B4 B5 5  6 A 7  6 решение: 1 1 3 , w2  0, w3  ,g  . По этому решению определяем цену игры и 200 100 200 оптимальную смешанную стратегию игрока B:  *  51 1 200 *T  1 2   , y   , 0,  g 3 3 3 6 4 6 9  A1  5 3 4 8  A2 6 6 7 5  A3  7 5 4 3  A4 Составить оптимальное распределение автобусов по маршрутам игрока A. 52 Решение. Сократим размерность игры с помощью отношений доминирования: платья – 2000 рублям, цена реализации соответственно равна 5500 рублей и 3500 рублей. Определить оптимальную стратегию предприятия. B1 B2 B3 B4 B5 5  6 7  6 Решение. Игрок A (швейное предприятие) располагает двумя стратегия- B3 B4 B5 6 4 6 9  A1 4   5 3 4 8  A2 3   6 6 7 5 A3 6   7 5 4 3  A4 5 B3 B4 B5 B3 B5 6 9  A1  4 8  A2  4 6 9  A1  4 9  A1        7 5 A3  6 7 5  A3  6 5  A3  4 3  A4 Окончательно получаем матрицу игры («природа») имеет две стратегии – погода будет теплой или холодной (B1 и B2 соответственно). Матрица игры представляет собой матрицу доходов швейного предприятия в зависимости от принятой им стратегии и от погоды. Вычислим соответ- B3 B5 ствующие прибыли:  4 9  A1 A     6 5  A3 П ( A1 , B1 )  100  (5500  3000)  230  (3500  2000)  595000 , Найдем оптимальные смешанные стратегии игроков и цену игры (воспользуемся готовыми расчетными формулами из пп. 2.1.1): a35  a33 56 1    , a13  a35  a15  a33 4  5  9  6 6   a13  a15 49 5 x3*    , a13  a35  a15  a33 4  5  9  6 6  a35  a15 59 2  y3*    , a13  a35  a15  a33 4  5  9  6 3   a13  a33 46 1 y5*    , a13  a35  a15  a33 4  5  9  6 3  П ( A1 , B2 )  100  (5500  3000)  70  (3500  2000)  2000  ( 230  70)  35000 , П ( A2 , B1)  100  (5500  3000)  70  (3500  2000)  3000  (240  100)  65000 , П ( A2 , B2 )  240  (5500  3000)  70  (3500  2000)  705000 . * x1  *  ми – расчет на теплую и холодную погоду (A1 и A2 соответственно); и игрок B  595000 35000  Получаем платежную матрицу П    .   65000 705000  T 1 5  x*   , 0, , 0 ; 6 6  Вычислим оптимальные смешанные стратегии игроков и цену игры: y *T 705000  (65000) 770 11    , 595000  705000  35000  (65000) 1330 19   595000  35000 560 8 x 2*    , 595000  705000  35000  (65000) 1330 19  x1*  2 1    0, 0, , 0, ; 3 3  a13a35  a15a33 20  54 17   . a13  a35  a15  a33 4  5  9  6 3 *  Тем самым, оптимальным транспортной компании будет распределение 595000  705000  (65000)  35000 421750000 6025000    317105. 595000  705000  35000  (65000) 1330 19 По найденному решению вычислим оптимальное количество костюмов и 17 автобусов на первый маршрут, 83 автобусов – на третий маршрут, второй и четвертый маршрут использовать не выгодно. При этом прибыль составит 5,7 платьев. Предприятию следует пошить млн. р. независимо от ответа конкурента. Пример 2.10. Швейное предприятие реализуется свою продукцию через магазин. Сбыт зависит от состояния погоды. В условиях теплой погоды пред- и 11 8 3020  100   240   159 костюмов 19 19 19 11 8 3090  230   70   163 платья; тем самым оно обеспечит себе прибыль в 19 19 19 317105 руб. независимо от поведения природы. приятие реализует 100 костюмов и 230 платьев, а при прохладной погоде – 240 костюмов и 70 платьев. Затраты на изготовление одного костюма равны 3000, а 53 T  11 8  x*   , ,  19 19  54 Задания для самостоятельной работы 1. С помощью отношений доминирования сократить размерность игры, ГЛАВА 3. ПРИНЯТИЕ РЕШЕНИЙ В НЕОПРЕДЕЛЕННЫХ СИТУАЦИЯХ заданной матрицей, и найти решения игры: 1  2 а) A   3  4 2 1 2  1 2 4 ; 3 2 2  1 3 3  2 4 8 5   б) A   6 2 4 6  . 3 2 5 4   3.1. Элементы теории статистических решений Теория статистических решений (ТСР) [7] отличается от теории игр тем, что рассматривает неопределенность ситуации без конфликтной «окраски» – никто никому сознательно не противодействует. В задачах ТСР неизвестные 2. Найти графически решение матричных игр: условия операции зависят не от сознательно действующего «противника», а от  3  5   а) A   2  3  ; 3 1  5 2    объективной незаинтересованной действительности, которую в ТСР принято 2  3  5 . б) A   3 2   5  3 1 не злонамеренно. Например, могут быть заранее неизвестны: погода в некото- 3. Определить с помощью методов линейного программирования решение игры со следующими матрицами: 0 3 4  а) A    ;  2 1  3 называть «природой», «поведение» которой неизвестно, но, во всяком случае, ром районе, покупательский спрос на определенного вида продукцию, объем перевозок, который придется выполнять на железной дороге, положение на  0 1  2  5   б) A   5 0 7 5 .  5  5 0 15    3. С помощью методов линейного программирования определить решение игры «Три пальца» (пример 1.1 в п. 1.2). рынке FOREX, экономическая и финансовая политика государства, реформы в системе налогообложения, курс валют, инфляция и т.д. Соответствующие ситуации часто называют «играми с природой». Отсутствие сознательного противодействия со стороны природы, на первый взгляд, упрощает задачу выбора решения: лицу, принимающему решения (ЛПР), в «игре с природой» легче добиться успеха, ведь ему никто не мешает. Но ему труднее обосновать свой выбор. В игре против сознательного противника элемент неопределенности отчасти снимается тем, что противник такой же, как ЛПР, он думает за противника теми же категориями, принимает за него решение на основе одинаковой логики и правил. В «игре с природой» такая концепция не подходит: никто не знает, какое сопротивление будет оказано принятому решению, каковы, в конечном счете, правила этой игры. Недаром говорят, что природа «слепа». Отметим, что игры с «природой» являются вырожденным случаем антагонистической игры двух лиц, когда одна сторона (ЛПР) имеет возможность строить осмысленные стратегии поведения, а вторая сторона («природа») лишена такой возможности. 55 56 Рассмотрим такого рода ситуацию. Пусть у стороны A есть m возможных дится важной понятие «риска». стратегий А1, А2, …, Аm; что касается обстановки, то о ней можно сделать n Риском rij игрока при использовании стратегии Ai в условиях  j назы- предположений П1, П2, …, Пn – рассмотрим их как стратегии «природы». Выиг- вается разность между выигрышем, который он получил бы, если бы знал  j , рыш aij при каждой паре стратегий Ai ,  j задан матрицей и выигрышем, который он получит в тех же условиях, применяя стратегию Ai . 1  2 ...  n  a11 a12   a21 a22  ... ...   am1 am 2 Иначе, риск – мера несоответствия между разными возможными результатами ... a1n  A1  ... a2 n  A2 ... ...  ...  ... amn  Am принятия определенных стратегий (действий). Выразим риск rij через элементы матрицы выигрышей aij . Очевидно, что если бы игрок заранее знал состояние «природы»  j , он выбрал бы ту страте- Требуется выбрать такую стратегию игрока A (чистую или смешанную), гию, которой соответствует максимальной выигрыш в данном (столбце макси- которая является более предпочтительной (выгодной) по сравнению с другими. мум столбца). Обозначим его  j  max aij . Тогда согласно определению риск i Наиболее простым случаем выбора решений в условиях неопределенности является случай, когда какая-то из стратегий игрока A оказывается доминирующей над всеми остальными, – ее-то и рекомендуется выбрать. Но даже если в матрице такой стратегии не оказывается, прежде чем приступать к решению, необходимо заведомо удалить невыгодные или дублирующие стратегии игрока рассчитывается по формуле rij   j  aij .  Соответствующая матрица рисков R  rij зачастую дает более нагляд-   ную картину неопределенной ситуации, чем матрица выигрышей A  aij . A. Что же касается стратегий «природы», то здесь заведомо невыгодные страте- Чтобы понять значение риска, рассмотрим пример. гии удалять нельзя, так как «природа» свои стратегии не выбирает. Пример 2.1. Планируется операция в заранее неясных условиях, напри- В дальнейшем будем считать, что отношения доминирования к стороне A применены. мер, рыночной конъюнктуры. Относительно этих условий можно сделать различные предположения: 1,  2 ,  3 ,  4 . Ожидаемая прибыль в чистых страте- Игроку A можно выбрать стратегию поведения, исходя их принципа крайнего оптимизма или крайнего пессимизма. В первом случае из его стратегий выбирается та, которая соответствует наибольшему выигрышу ( max aij ), во i, j втором – наименьшему выигрышу ( min aij ). Очевидно, что такое поведение неi, j рационально. В ТСР представляется желательным ввести такие показатели, которые не просто давали бы выигрыш в каждой ситуации, а описывали бы степень удачности применений конкретной стратегии в конкретной ситуации с учетом того, насколько вообще эта ситуация благоприятна для нас. С этой целью в ТСР вво57 гиях Ai для различных условий  j задана матрицей выигрышей  3 6 7 11   A   5 10 6 5  . 6 8 8 4       Простроим матрицу рисков R  rij   j  aij . Вычислим максимальные элементы каждого столбца: 1  6,  2  10,  3  8,  4  11 . Получаем 3 4 1 0   R  1 0 2 6 . 0 2 0 7   58 При анализе этой матрицы становятся яснее некоторые черты игры с критерием минимального риска. Согласно критерию Сэвиджа ЛПР пытается «природой». Так в матрице выигрышей во второй строке равны первый и чет- выбрать действие, при котором величина риска принимает наименьшее значе- вертый элементы a 21  a 24  5 . Однако эти выигрыши совсем не равноценны ние в самой неблагоприятной ситуации, т.е. друг другу в смысле того, насколько удачно выбрана стратегия. При состоянии W  min max rij . природы 1 мы могли бы выиграть самое большее 6, т.е. при выборе стратегии Критерий Сэвиджа, так же как и критерий Вальда, является критерием A2 выигрыш составляет 5 по 6-балльной шкале, что очень даже неплохо, до 1i m 1 j n крайнего пессимизма. максимума не добираем 1 балл. А вот при состоянии «природы»  4 макси- 3. Критерий пессимизма-оптимизма Гурвица. Этот критерий рекомен- мально возможный выигрыш составляет 11, а выбирая стратегию A2 мы полу- дует при выборе решения не руководствоваться ни крайним оптимизмом, ни чаем 5 по 11-балльной шкале и не добираем 6 баллов, т.е. выбор стратегии A2 крайним пессимизмом. Критерий Гурвица рекомендует стратегию, которая определяется по фор- очень плох. Это выражается элементами матрицы рисков r21  1, r24  6 . Аналогичный анализ при выборе третьей стратегии показывает, что эта стратегия лучше второй. Так, для равных элементов a32  a33  8 соответствующие им риски r32  2 и r33  0 , однако этой же строке соответствует наибольший риск r34  7 . муле:   W  max  min aij  1    max a ij  , 1i m  1 j n 1 j n  где   0,1 – степень пессимизма. Если   0 , получим максимаксный критерий «крайнего оптимизма». При   1 приходим к пессимистическому максиминному критерию Вальда. 3.2. Критерии принятия решений в играх с природой При выборе оптимальной стратегии используется ряд критериев. 1. Максиминный критерий Вальда. При максиминном критерии Вальда оптимальной считается та стратегия ЛПР, которая обеспечивает ему максимум минимального выигрыша: Выбор конкретного значения параметра определяется, скорее всего, субъективными факторами: чем опаснее ситуация, тем больше надо «подстраховываться» и тем ближе к единице нужно брать значение  к единице. При отсутствии каких-либо явных предпочтений вполне логично выбрать   0,5 . 4. Критерий Лапласа. При неизвестных вероятностях состояний «приро- W  max min aij . ды» можно принять, что все они равновероятны, т.е. p ( j )  1 / n, j  1, ..., n , и 1 i  m 1 j  n Этот критерий отражает принцип гарантированного результата, т.е. ЛПР выбирает такую стратегию, которая максимизировала бы его выигрыш в самой неблагоприятной ситуации. Критерием Вальда, главным образом, пользуются в случаях, когда необходимо обеспечить успех при любых возможных условиях 2. Критерий минимаксного риска Сэвиджа. Данный критерий предполагает, что оптимальной стратегией является та стратегия, при которой величина риска в наихудшем случае минимальна. Этот критерий также называется 59 выбор решения определяется критерием Лапласа, при котором ЛПР выбирает такую стратегию Ai , что 1 n  W  max   aij  . 1i m n j 1   Выбор критерия принятия решения является наиболее сложным и ответственным этапом. Если рекомендации, вытекающие из различных критериев, совпадают – тем лучше, можно смело выбирать рекомендуемое ими решение. 60 Если эти рекомендации противоречат друг другу, анализ матрицы игры «с при- Критерий Лапласа: вычислим родой» с точки зрения разных критериев часто дает лучшее представление о  23 / 4  1 n  W  max   a ij   max  25 / 4  , 1i m n j 1   1im 30 / 4  ситуации, о достоинствах и недостатках каждого решения, чем непосредственное рассмотрение матрицы, особенно высокой размерности. Пример 2.2. Условия игры «с природой» задаются в виде матрицы выигрышей (доходов) следовательно, следует выбрать стратегию A3 . Поскольку рекомендации трех из четырех рассмотренных критериев сводятся к выбору стратегии A3 , целесообразно остановиться на этом решении. 6 3 9 5  A   3 4 5 13  .  9 6 4 11   Пример 2.3. В приморском городе решено открыть яхт-клуб. Годовой абонемент стоит 100 денежных единиц. Цена яхты – 170 денежных единиц. Требуется сделать выбор действия по критериям Вальда, Сэвиджа, Гурвица при   0,5 , Лапласа. Аренда помещения и хранение яхт обходится в 730 денежных единиц в год. Сколько следует закупить яхт (из расчета: одна яхта на 5 человек), если пред- Решение. Критерий Вальда: вычислим 3 W  max min a ij  max  3   4 , 1i m 1 j  n 1i m 4    полагаемое число членов клуба колеблется от 10 до 25 человек? Решение. Несомненно, что имеет смысл рассматривать количество приобретаемых яхт в диапазоне от двух до пяти (4 варианта) и количество потен- следовательно, следует выбрать стратегию A3 . Критерий Сэвиджа: построим матрицу рисков циальных яхтсменов от 10 до 25. Однако объем перебора будет велик, и потому ограничимся вариантами 10, 15, 20, 25 (если полученные выводы для смежных вариантов будут существенно разниться, можно провести дополнительный, 3 3 0 8 R  6 2 4 0 0 0 5 2   уточняющий расчет). Получаем стратегии Ai , i  1, 2, 3, 4 , которые состоят в том, что в яхт-клуб будет закуплено две, три, четыре или пять яхт, и стратегии и вычислим  j , j  1, 2, 3, 4 , состоящие в том, что количество членов яхт-клуба будет равно 8 W  min max rij  min  6   5 , 1im 1 j n 1i m 5    10, 15, 20 ил 25. Для того чтобы начать поиск решения, построим матрицу выигрышей, следовательно, следует также выбрать стратегию A3 . элементы которой показывают прибыль при принятии i-го решения при j–ом Критерий Гурвица: количестве членов яхт-клуба. Рассчитаем элементы этой матрицы (при расчете   3  9    W  max  min a ij  1    max aij   max 0,5 3   1  0,513   11 1i m  1 j n 1 j n  1im   4    следует учитывать, что максимально возможное количество членов яхт-клуба равно количеству яхт, умноженному на 5): p ( A1 ,  j )  10  100  2  170  730  70, j  1, 2, 3, 4 ,  6   max  8   8, 1im 7,5    p ( A2 , 1 )  10  100  3  170  730  240 , следовательно, следует выбрать стратегию A2 . 61 p ( A2 ,  j )  15  100  3  170  730  260, j  2, 3, 4 , 62 p ( A3 , 1 )  10  100  4  170  730  410 , p( A3 ,  2 )  15  100  4  170  730  90 , p ( A3 ,  j )  20  100  4  170  730  590, j  3, 4 , p( A4 , 1 )  10  100  5  170  730  580 , p( A4 ,  2 )  15  100  5  170  730  80 , p( A4 ,  3 )  20  100  5  170  730  420 , p( A4 ,  4 )  25  100  5  170  730  920 . Окончательно получаем матрицу доходов  0 330 660 990     170 0 330 660  R 340 170 0 330     510 340 170 0  и вычислим  990     660  W  min max rij  min   340 , 1im 1 j  n 1i m 340     510  следовательно, следует выбрать стратегию A3 ; это означает, что покупая 4 яхты   70  70  70  70      240 260 260 260  A .  410 90 590 590      580  80 420 920  для открываемого яхт-клуба, мы уверены, что в худшем случае убытки клуба не превысят 340 д.е. Критерий Лапласа: вычислим Определим наилучшую из стратегий с использованием критериев приня-   70    1   135    W  max  a ij   max   215 , 1i m n j 1   1i m 215   170    n тия решений. Критерий Вальда: вычислим   70      240  W  max min aij  max  70 , 1im 1 j n 1i m  410      580  следовательно, следует выбрать стратегию A1 , то есть принимая решение по следовательно, следует выбрать стратегию A3 , то есть в условиях равновероятности возникновения той или иной величины спроса на членство в яхт-клубе следует закупить 4 яхты и при этом можно рассчитывать на прибыль в размере 215 д.е. критерию Вальда, яхт-клубу следует закупить 2 яхты и максимум ожидаемого Критерий Гурвица: убытка не превысит 70 д.е. При   0,2 получаем Критерий Сэвиджа: в каждом столбце вычислим максимальный элемент   70  70  70  70      240 260 260 260  max    70 260 590 920 , 1 i  m  410 90 590 590      580  80 420 920  построим матрицу рисков    70    70    70           240   260   160  W  max 0,2    , 8   max  590  1im 390   620 , 1i m   410           580   920   620   что соответствует стратегии A4 . При   0,5 получаем 63 64    70    70    70           240   260   10   W  max 0,5    0,5    max  170 , 1i m   410  590  1im 90           580   920   170         что соответствует стратегии A4 . тыс. ц. За хранение зерна на счет элеватора вносится плата в размере 10 д. е. за 1 ц. Урожай в данном районе колеблется от 14 до 20 ц с 1 га. Какой элеватор выгоднее построить? 2. Организуются пригородные автобусные рейсы. Число пассажиров колеблется от 300 до 450 чел., из которых 10% имеют право бесплатного проезда. При   0,8 получаем Цена билета 6 руб. Вместимость автобуса – 30 чел. Эксплуатационные затраты    70    70    70           240   260    140   W  max 0,8    0,2    max  70 , 1i m   410  590  1i m  210           580   920    280         на один рейс – 50 руб. Оплата шофера за одну поездку - 60 руб. Сколько следу- что соответствует стратегии A1 . ет организовать рейсов? 3. Ежедневный спрос на булочки в продовольственном магазине колеблется от 1000 до 1500. Булочки покупаются лотками по 100 штук по цене 16 руб. и продаются по цене 22 руб. за штуку. Непроданные булочки распродают- Таким образом, согласно критерия Гурвица при   0,2 и при   0,5 следует закупить 5 яхт и ожидать прибыль порядка, не меньшую 620 д.е. и ся по цене 8 руб. на следующее утро. Какое количество булочек следует закупать магазину? 170 д.е. соответственно (надеемся на широкую популярность нашего клуба и 4. Прядильная фабрика ежемесячно получает от 35 до 50 т хлопка повы- определенную финансовую состоятельность любителей), а при   0,8 не сле- шенной влажности. Один сушильный агрегат может высушить 5 т. Затраты на дует закупать более 2 яхт (мы более осторожны в своих прогнозах и, скорее техническое обслуживание агрегата 1000 руб. (независимо от его использова- всего, предпочтем отказаться от создания клуба). ния или простоя). Потери от 1 т невысушенного хлопка - 7000 руб. Сколько аг- Окончательно получаем, что рассмотренные критерии приводят к раз- регатов разумно иметь на фабрике? личным решениям и дают тем самым информацию к размышлению (принятое решение здесь будет существенно зависеть от психологии и интуиции субъекта решения). Задания для самостоятельной работы 1. В сельскохозяйственном районе с посевной площадью 1430 га решено построить элеватор. Имеются типовые проекты элеватора мощностью на 20, 30, 40, 50 и 60 тыс. ц зерна. Привязка проекта обойдется в 37 тысяч денежных единиц. Стоимость материалов и оборудования элеватора мощностью 20 тыс. ц равна 60 тыс. денежных единиц и возрастает на 10% с ростом мощности элеватора на 10 тыс.ц. Затраты на эксплуатацию элеватора мощностью 20 тыс.ц. составляют 10 тыс. д.е. и уменьшаются на 10% при увеличении мощности на 10 65 66 ГЛАВА 4. ПРИНЯТИЕ РЕШЕНИЙ В НЕАНТАГОНИСТИЧЕСКИХ КОНФЛИКТАХ 4.1. Биматричные игровые задачи Теория антагонистических игр применима лишь в тех случаях, когда можно определить общий критерий эффективности для двух конкурирующих B1  a11 , b11    a , b  A   21 21 ...   a m1 , bm1  B2 ... a12 , b12  a22 , b2  ... ... ... ... am2 , bm 2  ... Bn a1n , b1n   A1  a2n , b2 n   A2 ,  ... ...  amn , bmn  Am однако для наглядности удобнее рассматривать матрицы отдельно. сторон, одна из которых заинтересована в увеличении, а другая – в уменьшении Здесь A – это платежная матрица игрока A, а B – платежная матрица иг- значения этого критерия. Однако значительно чаще встречаются ситуации, в рока B. Размерности этих матриц обязательно совпадают. Пусть, к примеру, иг- которых интересы игроков хотя и не совпадают, но уже не обязательно являют- рок A применяет свою стратегию A2, а игрок B – стратегию B1. Тогда выигрыши ся противоположными. Например, при встрече боевых единиц двух воюющих игроков в данной ситуации будут находиться в соответствующих платежных сторон их обоюдное стремление уничтожить друг друга не выражает антагони- матрицах на пересечении второй строки и первого столбца: выигрыш игрока A стичности конфликта. В антагонистическом конфликте цели сторон оказывают- составит a21 , а выигрыш игрока B – b21. Отрицательные элементы платежных ся строго противоположными: стремлению одной стороны уничтожить другую матриц означают величину проигрыша игрока в соответствующей ситуации. противоположным будет стремление избежать уничтожения. Если для оценки действий каждой стороны необходимо определить отдельный критерий эффек-  тегиях в биматричной игре, если выполняются неравенства: тивности, игра имеет ненулевую сумму. В случае, когда участников конфликта aij  a kj , k  1, m, – два, и критерии для конкурирующих сторон различны, ситуация описывается bij  bil , l  1, n. в классе биматричных игровых задач [7]. Биматричной называется конечная игра двух лиц с ненулевой суммой. Такая игра описывается матрицами выигрышей конфликтующих сторон. Пусть у игрока A имеется m стратегий, а у игрока B – n стратегий. Выигрыши B2 ... Bn  a11 a12  a22 a A   21 ... ...   am1 am 2 Это означает, что элемент aij является наибольшим в j-м столбце, а элемент bij – наибольшим в i-й строке. Все ситуации равновесия в чистых стратегиях, если они имеются, можно найти способом, аналогичным способу определения седловой точки матрицы в игроков задаются матрицами: B1  Пара стратегий Ai , B j является ситуацией равновесия в чистых стра- B1 ... a1n  A1  ... a2n  A2 ; ... ...  ...  ... amn  Am B2 ... Bn  b11 b12  b22 b B   21 ... ...   bm1 bm 2 ... b1n  A1  ... b2 n  A2 . ... ...  ...  ... bmn  Am Иногда биматричные игры записывают в виде одной матрицы следующе- играх с нулевой суммой. В каждом столбце матрицы A следует отметить (например, звездочкой) максимальные элементы, затем также отметить максимальные элементы в каждой строке платежной матрицы B. Пары стратегий Ai , B j , для которых оба элемента aij и bij решению игры в чистых стратегиях. Следует отметить, что в решение задачи следует записывать две цены игры,  *A и  *B , выигрыши каждого из игроков. В го вида 67 отмечены, и будут соответствовать 68 случае решения в чистых стратегиях эти значения будут равны  *A  aij и  2* A   1  *B  bij .  2*  3   1   , B    2  1*  . 0*    Как видим, в игре имеет месте быть две седловые точки. Они соответст- Рассмотрим примеры построения биматричных игр. Пример 4.1 («Студент-преподаватель»). Рассмотрим следующую ситуацию. Студент (Игрок A) готовится к зачету, который будет принимать Преподаватель (игрок B). Можно считать, что у студента две стратегии – подготовиться к сдаче зачета (+) и не подготовиться (–). У преподавателя тоже две вуют следующим ситуациям: студент готовится к зачету и преподаватель ставит зачет, студент не готовится к зачету и преподаватель не ставит зачет. Если записывать ответ на математическом языке, то это выглядит следующим образом: первый ответ –  A1 , B1   (),[], A  2, B  2 , второй ответ –  A2 , B2   (),[], A  0, B  1 . стратегии – поставить зачет [+] или не поставить [–]. Пример 4.2 («Семейный спор»). Муж (игрок A)и жена (игрок B) догова- Составим модель биматричной игры. В основу значений матриц выигры- риваются о развлечениях. У них есть два варианта – пойти на футбол (страте- ша игроков положим следующие соображения (табл. 4.1 и табл. 4.2). Таблица 4.1 гии А1 и В1) и пойти в театр (стратегии А2 и В2). Очевидно, что если пойдут вместе на одно мероприятие, то один из них получит большее удовольствие, и не Выигрыш студента [+] [–] получит ни один, если муж один пойдет в театр, а жена – одна на футбол. В ви- (+) оценка заслужена очень обидно де пары платежных матриц данную игру можно представить следующим обра- (–) удалось обмануть оценка заслужена Таблица 4.2 Выигрыш преподавателя [+] [–] (+) все нормально был неправ (–) дал себя обмануть опять придет Количественно это можно выразить, например, следующим образом: [  ] [ ] [ ] [  ]  2  1 (  )  A    1 0  ( )  2  3  ()  B     2  1  ( ) Попробуем найти решение игры в чистых стратегиях. Отметим в каждом столбце первой матрицы максимальные элементы в каждом столбце, во второй зом: B1 B2 B1 B2  3 2  A1  A     3 1  A2  1 2  A1  B     3 3  A2 Нетрудно убедиться, что решение игры будет в чистых стратегиях:  A1 , B2 , A   B  2 , то есть мужу и жене следует развлекаться отдельно друг от друга. Пример 4.3 («Дилемма заключенного»). Два заключенных находятся в разных камерах и подозреваются в совершении одного и того же преступления. Каждый из них располагает двумя стратегиями поведения: кооперативными (молчать и не давать показания) А1 и В1, и некооперативными (давать показания на другого) А2 и В2. Данную игру можно представить в виде следующих платежных матриц: матрице – максимальные элементы в каждой строке: 69 70 B1 B2 отправку потребителю одной единицы продукции равен c денежных единиц, а B1 B2   1  10  A1 A     0  6  A2   1 0  A1 B      10  6  A2 затраты на хранение на складе продукции в объеме одной единицы составляют b денежных единиц и делятся поровну между отделами П и Т. В этом случае решение также будет в чистых стратегиях. Действительно, Пусть также известно, что в интересующий период времени (например за отметим максимальные элементы в каждом столбце первой матрицы и в каж- рабочий день) отдел П может произвести продукции в объеме 5 или 10 ед., а дой строке второй матрицы отдел Т для ее перевозки выделить малую автоколонну (на 4 ед.), большую ав- B1 B2   1  10  A1 A   * *   0  6  A2 B1 B2   1 0 *  A1  B   *   10  6  A2 токолонну (7 ед.), две малые автоколонны (8 ед.) или одну большую и одну малую автоколонны (11 ед.). Моделью описанной ситуации может быть биматричная игра. и получим решение  A2 , B2 , A   B  6 . Это означает, что каждому из заключенных лучше давать показания. Пример 4.4 («Конкурирующие фирмы»). Здесь также у игроков (конкурирующих фирм) по две стратегии: стратегии сохранения цен на продаваемый Т ( 4) пример, можно представить следующим образом: B1 B2 B1 B2  5 2  A1  A   11 8  A2  5 11 A1 B     2 8  A2 Также возможен вариант различных доходов: B1 B2 B1 B2  5 2  A1  A   11 9  A2  4 10  A1  B    1 8  A2 Т (8) Т (11) 5a 5a 5a  П (5)  4a  b / 2 П     4a  3b 7 a  3b / 2 8a  b 10a  П (10) Т ( 4) Т (7 ) Т (8) Т (11)  7c  8c  11c  П (5)   4c  b / 2  Т     4c  3b  7c  3b / 2  8c  b  11c  П (10) ими товар А1, В1 и стратегии снижения цен А2 , В2. Выигрышем в данном случае будет увеличение продаж и, следовательно, дохода. Платежные матрицы, на- Т (7 ) Пример 4.6 («Microscape против Netsoft»). Каждая из фирм теряет 2 млн. долларов за период, если обе продают интернет-браузеры. Когда у фирмы нет соперника, то она, став монополистом, будет зарабатывать 10 млн. долларов за период. Фирмы могут уйти с рынка в 2015 г. (с нулевым доходом) и в 2016 г., или остаться до 2017 г. Построим платежные матрицы для каждого из игроков, исходя их условий задачи (табл. 4.3). В данной таблице доходы (в млн. долларов) фирм Microscape и Netsoft обозначены в скобках через запятую. Таблица 4.3 Предлагаем читателю самостоятельно определить наличие или отсутстДоходы фирм вие в задаче седловой точки. Netsoft Пример 4.5 («Рефлексивная игра»). Пусть имеется фирма, состоящая из двух отделов – производственного (П), в задачу которого входит производство некоторого товара, и транспортного (Т), который должен доставить произведенный товар потребителю. Известно, что доход отдела П от выпуска продук- Microscape 2015 2016 2017 2015 (0, 0) (0, 10) (0, 20) 2016 (10, 0) (–2, –2) (–2, 8) 2017 (20, 0) (8, –2) (–4, –4) ции в объеме одной единицы равен a денежных единиц, затраты отдела Т на 71 72 Определим наличие или отсутствие седловой точки в данной задаче:  0  A   10  *  20 0 0 *    2  2 , B   0   * 8*  4  0 Теорема Нэша (основная теорема биматричных игр). Каждая биматричная игра имеет хотя бы одну ситуацию равновесия, возможно, в смешанных 20*   2 8*  .   2  4  10 стратегиях. Ситуация равновесия для биматричной игры представляет собой такую Тем самым, получили две ситуации равновесия –  A1 , B3  и  A3 , B1  , то  T есть одна из фирм уходит с рынка в 2015 году с нулевым доходом, а вторая остается до 2017 года и получает максимальный доход в 20 млн. долларов. Перейдем к построению моделей биматричных игр [7]. Будем считать полный набор вероятностей применения игроком A своих чистых стратегий xT   x1 , x2 , ..., xm  смешанной стратегией игрока A; соответT ственно y   y1, y2 , ..., yn  – смешанная стратегия игрока B. Смешанные стра-  пару смешанных стратегий x* , y* , которые удовлетворяют неравенствам: A y *   x * A y * 1m1   A 1m1 ,   (4.2) T B T x *   x * B y * 1n1   B 1n1 .   (4.3) Для определения равновесной ситуации необходимо решить систему неT T равенств (4.2), (4.3) относительно x*   x1, x2 , ..., xm  , y *   y1, y2 , ..., yn  при условиях нормировки (4.1). тегии должны удовлетворять очевидным условиям: m  xi  1, xi  0, i  1, ..., m; i 1 n 4.2. Графический метод решения биматричных задач 2  2 (4.1)  y j  1, y j  0, j  1, ..., n. j 1 С помощью смешанных стратегий рассчитываются средние выигрыши  A , B игроков A и B соответственно по формулам: m n Предположим, что заведомо невыгодные стратегии из платежных матриц удалены, следовательно, можно приступить к определению ситуации равновесия. Пусть каждый игрок имеет по две стратегии. В этом случае матрицы игры имеют вид: T  A    aij xi y j  x A y; B1 i 1 j 1 B2  a11 a12  A1  A    a 21 a22  A2 m n  B    bij xi y j  x T B y. i 1 j 1 Далее возникает естественный вопрос: всегда ли в биматричной игре су- B1 B2  b11 b12  A1  B    b21 b22  A2 Смешанные стратегии игроков в игре 2  2 имеют вид: ществует равновесная ситуация (т.е. такая ситуация, отклонение от которой x T   x 1  x , y T   y 1  y , 0  x  1, 0  y  1 . любого из игроков может лишь привести к уменьшению его выигрыша при ус- Средние выигрыши игроков рассчитываются следующим образом: ловии, что второй игрок сохраняет свой выбор)? Ответ на этот вопрос дает тео- a  y  a H A  x T A y   x 1  x  11 12     a21 a22 1  y   y     (a11  a21 ) x  a21 (a12  a22 ) x  a22  1  y  рема Нэша.  (a11  a21  a12  a22 ) xy  (a12  a22 ) x  (a21  a22 ) y  a22 , 73 74 (4.4) 2) если x  1, то условие (4.9) справедливо при всех y, а условие (4.10) пе- b  y  b   H B  x T B y   x 1  x  11 12   b21 b22 1  y   y   (b11  b21 ) x  b21 (b12  b22 ) x  b22    1  y  репишется в виде: (4.5) a1 y  a2  0 ; (4.12) 3) если 0  x  1, разделим левую и правую часть неравенства (4.9) на  (b11  b21  b12  b22 ) xy  (b12  b22 ) x  (b21  b22 ) y  b22 . 1  x , левую и правую часть неравенства (4.10) на x , в результате получим: Запишем условия равновесия (4.2), (4.3) для данной задачи: a1 y  a2  0,  a1 y  a2  0,  a11 a12  y  1      A  ,  a21 a22 1  y  1  b11 b21  x  1      B  .  b12 b22 1  x  1 a1 y  a2  0.  (4.13) Тем самым, множество решений системы, содержащей условия (4.9), (4.10), – обозначим его K – будет определяться следующим образом: 1) (0, y) , если a1 y  a2  0 , 0  y  1; Перепишем условия в развернутом виде: 2) ( x, y ) , если a1 y  a2  0 , 0  y  1, 0  x  1 ; (a11  a12 ) y  a12   A ,  (a21  a22 ) y  a22   A . (4.6) 3) (1, y) , если a1 y  a2  0 , 0  y  1. Если (b11  b21 ) x  b21   B ,  (b12  b22 ) x  b22   B . (4.7) a1  a2  0 , то решением будет весь единичный 0  x  1, 0  y  1, так как условия (4.11)-(4.13) удовлетворяются при всех значениях x и y. Подставляя цену игры  A из (4.4) в условия (4.6), получим: Если a1  0, a2  0 , то выполняется либо условие (4.11), либо условие (a11  a21  a12  a22 )(1  x) y  (a12  a22 )(1  x )  0,  (a11  a21  a12  a22 ) xy  (a12  a22 ) x  0. (4.8) (4.12), поэтому решением будет либо x  0 , либо x  1 соответственно. Если a1  0 , то получаем следующие решения: Введя замену переменных a11  a21  a12  a22  a1,  a22  a12  a2 , перепишем (4.8) в виде (4.9) (4.10) a1 (1  x) y  a2 (1  x )  0,  a1xy  a2 x  0. Таким образом, множество всех приемлемых стратегий для игрока A удовлетворяет условиям (4.9), (4.10).Чтобы найти их, рассмотрим три случая: 1) если x  0 , то условие (4.10) справедливо при всех y, а условие (4.9) а) из соотношения (4.11) получаем x  0 , y  a2  ; a1 б) из соотношения (4.12) получаем x  1, y  a2  ; a1 в) из соотношения (4.13) получаем 0  x  1 , y  (4.11) 75 a2  . a1 Если a1  0 , то получаем следующие решения: а) из соотношения (4.11) получаем x  0 , y  a2  ; a1 б) из соотношения (4.12) получаем x  1, y  a2  ; a1 перепишется в виде: a1 y  a2  0 ; квадрат 76 в) из соотношения (4.13) получаем 0  x  1 , y  a2  . a1 Графическая интерпретация множества решений K игрока A представле- а) y  0 , x  b2 ; b1 б) y  1 , x  b2 ; b1 на на рис. 4.1. в) 0  y  1, x  b2 . b1 Если b1  0 , то получаем следующие решения: а) а) y  0 , x  b2 ; b1 б) y  1 , x  b2 ; b1 в) 0  y  1, x  б) Рис. 4.1. Графическая интерпретация множества решений игрока A (а) – при a1  0 , б) – при a1  0 ) b2 . b1 Графическая интерпретация множества решений L игрока B представлена на рис. 4.2. Для игрока B исследования будут аналогичны. Подставим выражение (4.5) в условие (4.7) для  B и введем обозначения: b11  b21  b12  b22  b1,  b22  b21  b2 . Тогда множество L приемлемых для игрока B решений определяется следующим образом: 1) (x, 0) , если b1x  b2  0 , 0  x  1; а) 2) ( x, y ) , если b1x  b2  0 , 0  x  1, 0  y  1; Рис. 4.2. Графическая интерпретация множества решений игрока B (а) – при 3) (x,1) , если b1x  b2  0 , 0  x  1 . Если b1  b2  0 , то решением б) будет весь единичный 0  x  1, 0  y  1. квадрат b1  0 , б) – при b1  0 ) Решением игры является пересечение множеств K и L, т.е. те значения x и Если b1  0, b2  0 , то решением будет либо y  0 , либо y  1 . y, которые являются общими для этих множеств. Графическая интерпретация Если b1  0 , то получаем следующие решения: решения биматричной игры представлена на рис. 4.3. 77 78 коэффициенты: a1  a11  a 21  a12  a 22  8  2  3  2  15, a 2  a 22  a12  2  3  5,  a2 1  . a1 3 Так как a1  0 , то множество решений K имеет вид: а) б) Рис. 4.3. Графическая интерпретация решения биматричной игры (а) – зигзаги противоположно направлены, б) – зигзаги одинаково направлены)  1, y  при   1  K   x,  при  3   0, y  при  1 0 y , 3 0  x  1, 1  y  1. 3 Определим множество решений L игрока B. Для этого рассчитаем коэфПри этом зигзаги K и L могут быть как противоположной (рис. 4.3, а), так и одинаковой направленности (рис. 4.3, б). В первом случае зигзаги имеют три фициенты: точки пересечения, а во втором – одну. Средние выигрыши при этом определя- b1  b11  b21  b12  b22  6  2  3  2  13, b2  b22  b21  2  2  4, ются по формулам (4.4), (4.5), если в них подставить полученные значения x и  y. Очевидно, что  входит в смешанную стратегию игрока B, хотя зависит b2 4  . b1 13 только от выигрышей игрока A, а  входит в смешанную стратегию игрока A, Так как b1  0 , то множество решений L имеет вид: хотя зависит только от выигрышей игрока B. 1, строить объект 2. Город – игрок B – тоже имеет две стратегии: принять пред- 4   x, 0 при 0  x  13 ,   4  L   , y  при 0  y  1,  13   4  x  1.  x,1 при 13  ложение министерства или отказать. Свои действия они применяют независимо Изобразим эти множества графически (рис. 4.4). Точка пересечения мно- друг от друга, и результаты определяются прибылью (выигрышем) согласно  4 1 жеств K и L есть точка C  ,  . Тогда оптимальными стратегиями игроков  13 3  Пример 4.7. Министерство желает построить одно из двух объектов на территории города. Городские власти могут принять предложение министерства или отказать. Министерство – игрок A – имеет две стратегии: строить объект матрицам: 8 3  , A    2  2  6  3  . B   2 2  будут смешанные стратегии Решение. Нетрудно убедиться, что в игре отсутствует решение в чистых T T 4 9 1 2 x*   ,  , y*   ,  .  13 13  3 3 стратегиях. Определим множество решений K игрока A. Для этого рассчитаем 79 80 2. Две компании Pepsi и Coke имеют по автомату в некоторой столовой. Каждой из фирм нужно решить, каким напитком наполнить свой автомат: диетическим, классическим или обоими. В зависимости от выбранных стратегий, доходы фирм следующие (табл. 4.4). Определить все ситуации равновесия в чистых стратегиях. Таблица 4.4 Доходы фирм Coke Диет. Оба Класс. Диет. 25, 25 50, 30 50, 20 Оба 30, 50 15, 15 30, 20 Класс. 20, 50 20, 30 10, 10 Рис. 4.4. Графическое решение игры из примера 4.7 При этом выигрыши сторон будут равны: 1 1 6  3  2  4 9   8 3  3   14 T  A  x Ay         ,  13  2  3  13 13  2  2  2   13    3  3 1 1  4 9  6  3  3   6 6  3  6 T  B  x B y     .    13 13   2 2  2   13 13  2  13  3 3 Pepsi 3. Две фирмы арендуют смежные участки земли над резервуаром нефти объемом 100 млн. тонн. Стоимость одной тонны – 300 долларов. Каждая из фирм должна решить бурить ли ей скважину, и если бурить, то какого размера? Пробурить и обслуживать узкую скважину стоит 100 млн. долларов, широкую – 300 млн. долларов. Но при этом через широкую скважину будет выкачиваться нефти в три раза больше. Построить платежные матрицы по условиям задачи. Задания для самостоятельной работы 1. Две конкурирующих сети ресторанов хотят определить свой реклам- Имеется ли ситуация равновесия в чистых стратегиях? 4. Найти графически решения задач из примеров 4.1-4.4. ный бюджет на следующий год. Их суммарный объем продаж равен 240 млн. рублей. Каждая из них может выделить на рекламу 6, 7, 8, 9 или 10 млн. рублей. Если одна из сетей тратит на рекламу больше, то она продаст на 190 млн. рублей. Если обе сети тратят на рекламу поровну, то и продадут они поровну. Продали на 1 рубль дают доход 0,1 рубля. Каждая сеть старается максимизировать свой доход (доход с продаж минус затраты на рекламу). Построить платежные матрицы по условиям задачи. Имеется ли ситуация равновесия в чистых стратегиях, приемлемая для обеих ресторанных сетей? 81 82 УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ Выполнение контрольной работы является обязательным элементом при 9  5  4  A     10 2  10 3 7  A   6 2 11 10 3  A     6 7 12  7  3 A      6 10  13  8 3  A     6  7 14  2 5 A     4 3 15 3 9 A    6 4 16  6 7  A     9  5 17  3 9   A    4  2 18 2 7  A   7 5 19  4 10  A    5 2  20  7  4 A      10 3  изучении дисциплины студентом. Варианты контрольного задания студент выбирает в соответствии с порядковым номером в списке группы. При выполнении и оформлении контрольной работы необходимо руководствоваться следующим: 1) перед решением каждой задачи записать полностью условие задачи; 2) решения задач излагать подробно; 3) решения располагать в порядке номеров, указанных в варианте; 4) оформлять контрольную работу можно как с помощью текстовых редакторов на компьютере, так в рукописном варианте (при этом писать следует разборчиво). Крайний срок сдачи студентом контрольной работы – дата зачета. В случае если студент не сдает работу в указанный срок, зачет не выставляется и назначается дата перезачета. Задание 2. Найти графическим методом решение игр, заданными матрицами (задачи .1 и .2). 1.1  1 3 2 3  A      2 5 1  4 1.2  2 0   A    3 5  1 4   2.1   1  3  2 3 A    5 1 0   2 2.2 2 1    A   4  1 0 2    3.1  1 2 2 3   A    2 5 1  4 3.2  1 3    A 3 1   4  2   4.1  2  3 2  2  A    2 5  3 0  4.2  2 1    A   1 1  3  6   Задание 1. Найти решение игры, заданной матрицей A: а) аналитическим методом; б) используя понятие равновесия по Нэшу; в) графическим методом. 1  2 3  A     6  2 2 3 4 A    5 1 3 6 2 A    4 5 4  8 3  A     4  5 5 1 3   A    7  2 6 7 9  A   8 2 7 2 7  A   6 3 8  7 1   A    6  2 83 84 5.1 1  4 0 2  A     2 5  3  1 5.2 2 4    A  5  2 4 2    15.1  0 1 2 3  A   1 5  5 4 15.2 0  2   A   2 1   3  1   6.1 2 1 0   4 A     2  2 3  1  6.2  4 0   A   3 2  2 6   16.1  3  3 1 1 A     2 4 1 4 16.2 1 2    A 2 0   4  5   7.1 4 2  3  2 A    0  3 3 1  7.2  3 5    A   3  3  2 1   17.1  0 3 2 1  A      1 2  3  5 17.2  1 5   A   6 0  4 3   8.1 2 0 1  3  A     2  3 3  1 8.2  1 6   A   2 5  4 2   18.1  3  3 2  2  A    1 5  3 2  18.2 1   2   A   3  5  2 6    9.1 0  4  3  1  A    2  3 3 1   9.2  2 1   A   1 3  1 4   19.1  2 4 3 1   A   2  3   1 5 19.2  4 1    A   2  2  1 1   10.1  4  3  4  3 A    5  1   2 2 10.2  4 1   A   3 5  1 6   20.1  2  5  2 1  A    4  3   1 6 20.2 4  2   A  3 6   5  1   11.1  4 0  2 3 A     3 2 5 1 11.2 6  2   A   2 14  5 9    12.1   4  3 2  3  A   2  5 1   6 12.2 1 2    A  2  4 0 3    13.1  4  3 1 3  A   1 0   1 3 13.2  1 5    A   2 7   2  3    0 3 2 3  A    5  2   1 4 14.2 14.1 85 1 5    A  0 6   4  1   Задание 3. Найти методом линейного программирования решение игры, заданной матрицей A. 1  2 3 2    6  5  4 A 4 5 2    3  1   2 2 6 5 6   2   A   9 4 5  3  2 1 2 1   3 6 9  1  4   A 5 3 1 2   3 1 2 4   4  1 6 5    3  1  3 A 2 1 3    4   3 4 86 5  6 2 4     8  3  1 A 1 2 3     3 4  1 6 2  4  5 3   A  1 2  3 4  2 4 5  6   7 2 3 3   4   A   2 1 1 2   3 1 2  1  8 5  6  4    3 1 2  A 3 4  4   3   4 2 5  6  2    3 1 1  A 2 3 2     3 1 2  10 3 1 4 6   A   4 1 0 1 1 2 2 0   12  2 3 1    1   2 3 A 2  1  2    3 4 5  14  5  1 2 1   A 2 2 3 3   2 2 1  4   16  2 3  2    4 5 6  A 6 6 1    2  3   1 18 9 11 13 15 17 1 5 3   8   A   4  1  3  3  4 2 3  2   19 20 6 5 4   2   A 3 1 2  1  2  3 1 3    2  6 3    5  1  4 A  2 1 4    1 3   0 Задание 4. Магазин имеет некоторый запас товаров ассортиментного минимума. Если запас товаров недостаточен, то необходимо завести его с базы; если запас превышает спрос, то магазин несет расходы по хранению нереализованного товара. Пусть спрос на товары лежит в пределах S=5-8 единиц, расходы по хранению одной единицы товара составляют c руб., а расходы по завозу единицы товара k руб., цена за единицу товара составляет p руб. Составить платежную матрицу, элементами которой является прибыль магазина (доход от 87 3  6  1    4  5 3   A 1 2 4      1 1  4 3 1 2   2   A   4  5 2  3  4 1 2 3   6   3 5   2  4  1 A 4 4 3     3 1 1  6 4 2   9   A   3  3 1 1  3 5 1  2   продажи с учетом расходов по хранению или по завозу). Определить оптимальную стратегию магазина по завозу товаров, используя критерии Вальда, Сэвиджа, Гурвица при   0.5 , Лапласа. 1 p  300, c  50, k  70 2 p  350, c  60, k  70 3 p  400, c  50, k  90 4 p  210 c  70, k  60 5 p  410, c  50, k  80 6 p  290 c  40, k  60 7 p  250 c  30, k  90 8 p  210 c  20, k  60 9 p  320, c  40, k  90 10 p  310 c  40, k  70 11 p  410, c  50, k  70 12 p  250 c  50, k  60 13 p  180 c  50, k  40 14 p  340 c  40, k  50 15 p  420, c  40, k  90 16 p  330 c  30, k  50 17 p  320, c  50, k  40 18 p  210 c  50, k  40 19 p  400 c  30, k  60 20 p  300 c  40, k  50 88 Задание 5. Найти решение биматричной игры, заданной парой матриц. 1  1 2  2 1 , B    A    0 4  3 6 2 5 2  2 0 A   , B    1 5  1 6 4  3 3  4 1 , B    A   2 5    1 4 6 6 3  1 4 , B    A   5 6    2 8 8 5 4  4 2 , B    A   2 5  3 6 10  6 3  5 2 , B    A    2 5 3 8 12  7 3  4 2 , B    A    2 6 1 5 14 9 4  6 3 , B    A   5 8    1 5 16 17  3 2  2 0 , B    A   1 4  2 6 18  5 2  2 5 , B    A   4 5  3 5 19  2 3  4 1 , B    A    2 5  1 3 20  5 3  4 2 , B    A   3 5 5 6 3 5 7 9 11 13 15 89  3 2 2 1 , B    A   4 5  3 4 ЗАКЛЮЧЕНИЕ В данном пособии рассмотрены краткие теоретические сведения по дис- 3 2  2 5 A   , B    1 5   3 5 циплине «Теория игр», которая изучается студентами экономических направ- 2 1 5 2 , B    A   4 7   6 4 направления подготовки «Прикладная математика и информатика» в рамках  5 3 6 2 , B    A   2 5   1 3 Издание состоит из введения, четырех глав, указаний по выполнению  7 2  5 3 , B    A   4 7  3 4  6 3  7 3 , B    A   2 7  4 5 8 4   7 2 , B    A   3 9  5 8  4 2  2 3 , B    A   4 6    3 4 лений на 2-3 курсах. Учебно-методическое пособие будет полезно студентам освоения дисциплины «Теория игр и исследования операций». контрольной работы, заключения, библиографического списка. В первой главе рассматривается основные понятия антагонистических конфликтов, приводятся примеры построения матричных игр, исследуется возможность сокращения размерности матричных игр. Во второй главе приведены методы решения антагонистических конфликтов в зависимости от размерности игровой задачи (графические и аналитические методы). В третьей главе рассматриваются вопросы принятия решения в условиях неопределенности на основании критериев Вальда, Сэвиджа, Гурвица, Лапласа. В четвертой главе изложен метод решения простейшей биматричной задачи. Каждая глава дополнена заданиями для самостоятельного выполнения и закрепления пройденного материала. В конце пособия представлены варианты задания контрольной работы и указания по ее выполнению. 90 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 12. Тарасов, Л.В. Закономерности окружающего мира: в 3 кн. / Л.В. Та- расов. – М.: Физматлит, 2004. – Кн. 2 : Вероятность в современном обществе. – 1. Акимов, В.П. Основы теории игр: учеб. пособие / В.П. Акимов. – М.: МГИМО-Университет, 2008. – 158 с. 2. Балдин, К.В. Математическое программирование: учеб. / К.В. Бал- дин, Н.А. Брызгалов, А.В. Рукосуев; под ред. К.В. Балдина. – М.: Дашков и К, 2009. – 219 с. 3. 2004. – 360 с. 13. ятельности: учебник: рек. Мин. обр. РФ / Г.П. Фомин. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2005. – 616 с. 14. Васин, А.А. Исследование операций: учеб. пособие: рек. НМС / Фомин, Г.П. Математические методы и модели в коммерческой де- Шеллинг, Т. Стратегия конфликта: пер. с англ. / Т. Шеллинг. – М.: ИРИСЭН, 2007. – 374 с. А.А. Васин, П.С. Краснощеков, В.В. Морозов. – М.: Академия, 2008. – 464 с. 4. Горлач, Б.А. Исследование операций: Учебное пособие / Б.А. Гор- лач. – СПб.: Лань, 2013. – 448 с. 5. Исследование операций в экономике: учеб. пособие: рек. Мин. обр. РФ / под ред. Н.Ш. Кремера. – М.: Маркет ДС, 2007. – 408 с. 6. Киреев, А.П. Микроэкономика для продвинутых: задачи и решения: учеб. пособие / А.П. Киреев, П.А. Киреев. – М.: Вуз. учебник: ИНФРА-М, 2013. – 160 с. 7. Колобашкина, Л.В. Основы теории игр: учеб. пособие / Л.В. Коло- башкина. – М.: БИНОМ. Лаборатория знаний, 2011. – 164 с. 8. Красс, М.С. Основы математики и её приложения в экономическом образовании: учеб.: рек. Мин. обр. РФ / М.С. Красс, Б.П. Чупрынов. – 2- изд., испр., 4-е изд., испр.3-е изд., испр. . – М.: Дело, 2001, 2003, 2002. – 688 с. 9. Мазалов, В.В. Математическая теория игр и приложения: Учебное пособие / В.В. Мазалов. – СПб.: Лань, 2010. – 448 с. 10. Писарук, Н.Н. Введение в теорию игр / Н.Н. Писарук. – Минск: БГУ, 2010. – 108 с. 11. Печерский, С.Л. Теория игр для экономистов: вводный курс: Учеб. пособие / С.Л. Печерский, А.А. Беляева. – СПб.: Изд-во Европ. Ун-та в С.Петербурге, 2001. – 343 с. 91 92 СОДЕРЖАНИЕ Введение 3 Глава 1. Основные понятия антагонистических матричных игровых задач 6 1.1. Матричные игровые задачи 6 1.2. Примеры матричных игр. Составление модели игры 7 1.3. Сокращение размерности игровой задачи 12 1.4. Решение игровых задач в «чистых» стратегиях. Принцип минимакса 15 1.5. Понятие смешанных стратегий 20 Задания для самостоятельной работы к главе 1 24 Глава 2. Методы решения антагонистических игровых конфликтов 25 2.1. Методы решения матричных игр размерности 2 2 25 2.1.1. Аналитический метод 25 2.2.2. Метод, основанный на понятии равновесия по Нэшу 28 2.2.3. Графический метод решения игр размерности 2  2 30 2.3. Графический метод решения игр размерности 2  n и m  2 34 2.3.1. Игры размерности 2  n 35 2.3.2. Игры размерности m  2 40 2.4. Решение игр размерности m  n методом линейного программирования 42 2.5. Практическое применение смешанных стратегий 49 Задания для самостоятельной работы к главе 2 55 Глава 3. Принятие решений в неопределенных ситуациях 56 3.1. Элементы теории статистических решений 56 3.2. Критерии принятия решений в играх с природой 59 Задания для самостоятельной работы к главе 3 65 Глава 4. Принятие решений в неантагонистических конфликтах 67 4.1. Биматричные игровые задачи 67 4.2. Графический метод решения биматричных задач 2  2 74 Задания для самостоятельной работы к главе 4 81 Указания по выполнению контрольной работы 83 Заключение 90 Библиографический список 91 93 Надежда Николаевна Максимова, доцент кафедры математического анализа и моделирования, канд. физ.-мат. наук Теория игр. Учебно-методическое пособие. Заказ 656. 94