Методы решения конечных игр

Перед тем, как решать игру m×n, нужно, прежде всего, попытаться ее упростить, избавившись от лиш­них стратегий. Это делается подобно тому, как мы когда-то отбрасывали заведомо невыгодные решения в §6. Введем понятие «доминирования». Стратегия А_i игрока А называется доминирующей над стратеги­ей A_k, если в строке А_i стоят выигрыши не меньшие, чем в соответствующих клетках строки A_k, и из них по крайней мере один действительно больше, чем в соответствующей клетке строки A_k. Если все выигрыши строки A_i равны соответствующим выигрышам строки A_k то стратегия А_i называется дублирующей стра­тегию A_k. Аналогично определяются доминирование и дублирование для стратегий игрока В: доминирующей называется та его стратегия, при которой везде стоят выигрыши не большие, чем в соответствующих клет­ках другой, и по крайней мере один из них действи­тельно меньше; дублирование означает полное пов­торение одного столбца другим. Естественно, что если для какой-то стратегии есть доминирующая, то эту стратегию можно отбросить; также отбрасываются и дублирующие стратегии.

Поясним сказанное примером. Пусть игра 5×5 за­дана матрицей таблицы 27.1.

 

Таблица 27.1

 

 

 

Прежде всего заметим, что в ней стратегия А₅ дубли­рует стратегию А₂, поэтому любую из них можно от­бросить. Отбрасывая А₅, замечаем, что в строке А₁ все выигрыши больше (или равны) соответствующим выигрышам строки А₄, значит А₁ доминирует над A₄. Отбросим А4 и получим матрицу 3×5 (таблица 27.2).

Но это еще не все! Приглядевшись к таблице 27.2, замечаем, что в ней некоторые стратегии игрока В доми­нируют над другими: например, B₃ над B₄ и B₅, а В₁ — над стратегией В₂ (не забудьте, что В стремится отдать поменьше!). Отбрасывая столбцы В2, В4, В5, получаем игру 3×2 (таблица 27.3).

Наконец, в таблице 27.3 строка A₃ дублирует A₁ поэтому ее можно отбросить. Окончательно получим игру 2×2 (таблица 27.4).

 

 

Т а б л и ц а 27.2

 

Таблица27.3 Таблица27.4

 

 

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

В руководствах по теории игр обычно останавли­ваются на решении простейших игр 2×2, 2 × п и т × 2, которое допускает геометрическую интерпрета­цию, но мы этого делать не будем — сразу возьмем «быка за рога» и покажем, как можно решить любую игру т × п.

Пусть имеется игра т × п без седловой точки с мат­рицей (a_ij) (см. таблицу 27.5).

 

Т а б л и ц а 27.5

 

Допустим, что все выигрыши a_ij положительны (этого всегда можно добиться, прибавляя ко всем чле­нам матрицы достаточно большое число М; от этого

цена игры увеличится на M, а решение S*_A, S*_b не
изменится). Если все a_ij положительны, то конечно, и
цена игры, т. е. средний выигрыш при оптимальной
стратегии, тоже положителен: v > 0.

Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии

(27.1)

дающие каждой стороне максимально возможный для
нее средний выигрыш (минимальный проигрыш).

Найдем сначала S*_A. Мы знаем, что если один из
игроков (в данном случае это А) применяет свою оптимальную стратегию, то другой (В) не может улучшить свое цоложение, отступая от своей. Заставим противника (В) отступать от своей оптимальной стратегии, пользуясь чистыми стратегиями В₁ В₂,…, В_п

(а мы тем временем упорно держимся стратегии S*_A).
В любом случае наш выигрыш будет не меньше, чем и:

Разделим неравенства (27.2) на положительную величину v и введем обозначения:

(27.3)

Тогда условия (27.2) примут вид:

 

(27.4)

 

где x₁,..., х_т — неотрицательные переменные. В си­лу (27.3) и того, что р₁ + р2 +... + р_т = 1, переменные x₁,..., х_т удовлетворяют условию

(27.5)

Но v есть не что иное, как наш гарантирован­ный выигрыш; естественно, мы хотим сделать его максимальным, а значит, величину 1 / v минимальной.

Таким образом, задача решения игры свелась к мате­матической задаче: найти неотрицательные значения переменных x₁,..., х_т такие, чтобы они удовлетво­ряли линейным ограничениям-неравенствам (27.4) и обращали в минимум линейную функцию этих пере­менных:

(27.6)

«Ба! — скажет читатель,— что-то знакомое!» И точно — перед нами не что иное, как задача линейного программирования. Таким образом, задача решения игры т×п свелась к задаче линейного программиро­вания с п ограничениями-неравенствами и т перемен­ными. Зная x₁,..., х_т, можно по формулам (27.3) найти р₁, р₂, …, р_т и, значит, оптимальную стратегию S*_A и цену игры v.

Оптимальная стратегия игрока В находится совер­шенно аналогично, с той разницей, что В стремится хинизировать, а не максимизировать выигрыш, а значит, обратить не в минимум, а в максимум величину 1 / v, а в ограничениях-неравенствах вместо знаков ≥ будут сто­ять ≤. Пара задач линейного программирования, по ко­торой находятся оптимальные стратегии(S*_A,S*_B), на­зывается парой двойственных задач линей­ного программирования (доказано, что макси­мум линейной функции в одной из них равен мини­муму линейной функции в другой, так что все в поряд­ке—разных значений цены игры мы не получим).

Таким образом, решение игры т×п эквивалентно решению задачи линейного программирования. Нужно заметить, что и наоборот,— для любой задачи линейно­го программирования может быть построена эквивалент­ная ей задача теории игр (на том, как это делается, мы останавливаться не будем). Эта связь задач теории игр с задачами линейного программирования оказывается полезной не только для теорий игр, но и для линейного программирования. Дело в том, что существуют при­ближенные численные методы решения игр, которые в некоторых случаях (при большой размерности задачи) оказываются проще, чем «классические» методы ли­нейного программирования.

Опишем один из самых простых численных методов решения игр — так называемый метод итераций (иначе — метод Брауна — Робинсон). Идея его в сле­дующем. Разыгрывается «мысленный эксперимент», в котором стороны А и В поочередно применяют друг против друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Начинается он с того, что один из иг­роков (скажем, А) выбирает произвольно одну из своих стратегий А_i Противник (В) отвечает ему той из своих стратегий которая хуже всего для А_i, т. е. обращает его выигрыш при стратегии A_i в минимум. Дальше сно­ва очередь А — он отвечает В той своей стратегией А_к, которая дает максимальный выигрыш при стратегии В_j противника. Дальше — снова очередь противника. Он отвечает нам той своей стратегией, которая является наихудшей не для последней, примененной нами, стра­тегии А_к а для смешанной стратегии, в которой до сих пор примененные стратегии А_i, А_к встречаются с равными вероятностями. И так далее: на каждом ша­ге итерационного процесса каждый игрок отвечает на очередной ход другого той своей стратегией, которая яв­ляется оптимальной для него относительно смешанной стратегии другого, в которую все примененные до сих пор стратегии входят пропорционально частотам их применения. Вместо того чтобы вычислять каждый раз средний выигрыш, можно пользоваться просто «накоп­ленным» за предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный вы­игрыш максимален (минимален). Доказано, что такой метод сходится: при увеличении числа «партий» сред­ний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий — к их вероят­ностям, в оптимальных

смешанных стратегиях игроков.

Впрочем, лучше всего можно понять итерационный метод на конкретном примере. Продемонстрируем его на примере игры 3×3 предыдущего параграфа (табли­ца 26.5). Чтобы не иметь дела с отрицательными чис­лами, прибавим к элементам матрицы таблицы 26.5 число 5 (см. таблицу 27.6); при этом цена игры увеличится на 5, а решение S*_A, S*b не изменится.

Начнем с произвольно выбранной стратегии игрока А,— например, со стратегии А₃. В таблице 27.7 приведе­ны первые 15 шагов итерационного процесса по методу Брауна — Робинсон (читатель может самостоятельно
продолжить расчеты). В первом столбце дан номер пар-
тии (пары выборов) А, во втором — номер i выбранной
в. данной партии стратегии игрока А. В последующих
трех столбцах — «накопленный выигрыш» за первые к

партий при тех стратегиях, Таблица 27.6

которые применяли
игроки в предыдущих партиях и при стратегиях В₁
В2, В₃ игрока В в данной
партии (получается прибавлением элементов соответствующей строки к тому, что было строкой выше). Из этих накопленных выигрышей в таблице 27.7 подчеркнут минимальный (если их несколько, подчеркиваются все). Подчеркнутое число определяет ответный выбор игрока В в данной партии — он выбирает ту стратегию, которая соответствует подчеркнутому числу (если их несколько, берется любая). Таким образом определяется номер / оптимальной (в данной партии) стратегии В (ставится в следующем столбце). В последующих

 

 

Таблица 27.7

 

 

трех столбцах дается накопленный выигрыш за к партий соответственно при стратегиях А₁,А2,Аз игрока А (получается прибавлением элементов столбцаBj к тому, что было строкой выше). Из этих значений в таблице 27.7 «надчеркнуто» максимальное; оно определяет вы­бор стратегии игрока А в следующей партии (строкой ниже). В последних трех столбцах таблицы 27.7 даны: v — нижняя оценка цены игры, равная минимальному накопленному выигрышу, деленному на число партий k; v — верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на k; — сред­нее арифметическое между ними (оно служит лучшей, чем нижняя и верхняя, приближенной оценкой цены игры).

Как видно, величина v* незначительно колеблется около цены игры v = 5 (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5). Подсчитаем по таблице 27.7 частоты р₁, р₂, р₃, q₁, q₂, q₃ стратегий игроков. Получим:

 

что не так уж сильно отличается от вероятностей р₁, р₂, р₃ q₁, q₂, q₃ равных, как мы указывали раньше, для первой, второй и третьей стратегий соответственно 1/4 = 0,25, 1/2 = 0,50, 1/4 = 0,25. Такие сравнительно хорошие приближения мы получили уже при 15 ите­рациях — это обнадеживает! К сожалению, дальше процесс приближений будет идти не так резво. Сходи­мость метода Брауна — Робинсон, как показывает опыт, очень медленная, Существуют способы, позволя­ющий как бы «подхлестнуть» еле плетущийся процесс, но мы на них останавливаться не будем.

Очень важным преимуществом итерационного мето­да решения игр является то, что его трудоемкость сравнительно медленно возрастает с увеличением раз­мерности игры т × n, тогда как трудоемкость метода линейного программирования растет при увеличении размерности задачи гораздо быстрее.

 

* * *

Таким образом, читатель получил некоторое пред­ставление о теории антагонистических игр и о мето­дах решения матричных игр.

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

Прежде всего, на практике не так уж часто встре­чаются строго антагонистические конфликты разве только в настоящих «играх» (шашки, шахматы, кар­ты и т. п.). Вне этих искусственных ситуаций, где од­на сторона стремится во что бы то ни стало обратить выигрыш в максимум, а другая — в минимум, такие конфликты почти не встречаются. Казалось бы, где, как не в области боевых действий должна была бы с успехом применяться теория игр? Ведь здесь мы встре­чаемся с самыми «свирепыми» антагонизмами, с самой резкой противоположностью интересов! Но оказывает­ся, что конфликтные ситуации в этой области срав­нительно редко удается свести к парным играм с ну­левой суммой. Схема строгого антагонизма применима, как правило, только к операциям малого масштаба, ог­раниченным по значению. Например, сторона А — груп­па самолетов, налетающих на объект, сторона В— средства противовоздушной обороны объекта; первая стремится максимизировать вероятность уничтожения объекта, вторая — ее минимизировать. Здесь схема парной игры с нулевой суммой может найти приме­нение. Но возьмем чуть более сложный пример: две группировки боевых единиц (типа танков, самолетов, кораблей) ведут бой. Каждая сторона стремится по­разить как можно больше боевых единиц противника. В этом примере антагонизм ситуации теряет свою чистоту: она уже не сводится к парной игре с нуле­вой суммой. Если цели участников конфликта не пря­мо противоположны, а просто не совпадают, матема­тическая модель становится много сложнее: мы уже не можем интересоваться выигрышем только одной стороны; возникает так называемая «биматричная игра», где каждый из участников стремится максими­зировать свой выигрыш, а не просто минимизировать выигрыш противника. Теория таких ягр гораздо слож­нее, чем теория антагонистических игр, а главное, из этой теории не удается получить четких рекоменда­ций по оптимальному образу действий сторон [26].

Второе критическое замечание будет касаться по­нятия «смешанных стратегий». Если речь идет о мно­гократно повторяемой ситуации, в которой каждая сторона может легко (без дополнительных затрат) варьировать свое поведение от случая к случаю, оп­тимальные смешанные стратегии в самом деле могут повысить средний выигрыш. Но бывают ситуации, ког­да решение надо принять одно-единственное (например, выбрать план строительства системы оборонительных сооружений). Разумно ли будет «передоверить свой выбор случаю»,— грубо говоря, бросить монету, и если выпал герб, выбрать первый вариант плана, а если решка — второй? Вряд ли найдется такой руководи­тель, который в сложной и ответственной ситуации решится делать выбор случайным образом, хотя бы это и вытекало из принципов теории игр!

Наконец, последнее соображение: в теории игр счи­тается, что каждому игроку известны все возможные стратегии противника, неизвестно лишь то, какой именно из них он воспользуется в данной партии игры. В реальном конфликте это обычно не так: перечень возможных стратегий противника как раз неизвестен, и наилучшим решением в конфликтной ситуации неред­ко будет именно выйти за пределы известных против­нику стратегий, «ошарашить» его чем-то совершенно новым, непредвиденным!

Как видно из вышеизложенного, теория игр в ка­честве основы для выбора решения (даже в острокон­фликтной ситуации) имеет много слабых мест. Значит ли это, что ее не нужно изучать, что она вовсе не нужна в исследовании операций? Нет, не значит. Те­ория игр ценна прежде всего самой постановкой за­дач, которая учит, выбирая решение в конфликтной си­туации, не забывать о том, что противник тоже мыс­лит, и учитывать его возможные хитрости и уловкп. Пусть рекомендации, вытекающие из игрового подхо­да, не всегда определенны и не всегда осуществимы — все же полезно, выбирая решение, ориентироваться, в числе других, и на игровую модель. Не надо только выводы, вытекающие из этой модели, считать оконча­тельными и непререкаемыми[5]).

 

§ 28. Задачи теории статистических решений

Близкой по идеям и методам к теории игр являет­ся теория статистических решений. От те­ории игр она отличается тем, что неопределенная си­туация не имеет конфликтной окраски — никто нико­му не противодействует, но элемент неопределенности налицо. В задачах теории статистических решений не­известные условия операции зависят не от сознатель­но действующего «противника» (или других участни­ков конфликта), а от объективной действительности, которую в теории статистических решений принято называть «природой». Соответствующие ситуации час­то называются «играми с природой». «Природа» мыс­лится как некая незаинтересованная инстанция («рав­нодушная природа»,—по Пушкину), «поведение» ко­торой неизвестно, но во всяком случае не злонаме­ренно.

Казалось бы, отсутствие сознательного противодей­ствия упрощает задачу выбора решения. Оказывается, нет: не упрощает, а усложняет. Правда, принимающе­му решение в «игре с природой» в самом деле «легче» добиться успеха (ведь ему никто не мешает!), но ему «труднее» обосновать свой выбор. В игре про­тив сознательного противника элемент неопределен­ности отчасти снимается тем, что мы «думаем» за про­тивника, «принимаем» за него решение, самое небла­гоприятное для нас самих. В игре же с природой та­кая концепция не подходит: кто ее знает, как она, ма­тушка, себя поведет? Поэтому теория статистических решений —наиболее «шаткая» в смысле рекомендаций наука. Все же у нее есть право на существование и на внимание со стороны лиц, занимающихся исследова­нием операций.

Рассмотрим игру с природой: у нас (сторона А) имеется т возможных стратегий А₁, А2,..., А_т, что касается обстановки, то о ней можно сделать п пред­положений: П₁, П₂,..., П_n. Рассмотрим их как «стра­тегии природы». Наш выигрыш a_ij при каждой паре стратегий А_i, П_i задан матрицей (таблица 28.1).

Требуется выбрать такую стратегию игрока А (чис­тую или, может быть, смешанную, если это возможно), которая является более выгодной по сравнению с дру­гими.

С первого взгляда кажется, что эта задача похожа на игру двух игроков А и П с противоположными ин­тересами и должна решаться теми же методами. Но это не совсем так. Отсутствие противодействия со сто­роны природы делает ситуацию качественно другой[6]).

 

Если даже в матрице игры с природой нет одной доминирующей над всеми другими, все же полезно посмотреть, нет ли в ней дублирующих стратегий и уступающих другим при всех условиях (как мы это делали, упрощая матрицу игры). Но здесь есть одна тонкость: так мы можем уменьшить только число стра­тегий игрока Л, но не игрока Я —ему ведь все равно, много или мало мы выиграем! Предположим, что «чист­ка» матрицы произведена, и ни дублирующих, ни за­ведомо невыгодных игроку А стратегий в ней нет.

Чем же все-таки руководствоваться при выборе ре­шения? Вполне естественно, должна учитываться мат­рица выигрышей (а_ij). Однако в каком-то смысле кар­тина ситуации, которую дает матрица (а_ij), неполна и не отражает должным образом достоинств и недостат­ков каждого решения.

Поясним эту (далеко не простую) мысль. Предпо­ложим, что выигрыш а_ij при нашей стратегии A_i и со­стоянии природы П_j больше, чем при нашей стратегии A_k и состоянии природы П_i: а_ij > а_kl. Но за счет чего больше? За счет того, что мы удачно выбрали стра­тегию A_i? Необязательно. Может быть, просто состоя­ние природы П_j выгоднее нам, чем П_i. Например, со­стояние природы «нормальные условия» для любой опе­рации выгоднее, чем «наводнение», «землетрясение» и т. п. Желательно ввести такие показатели, которые не просто давали бы выигрыш при данной стратегии в каждой ситуации, но отражали бы «удачность» или «неудачность» выбора данной стратегии в данной ситуации.

С этой целью в теории решений вводится понятие «риска». Риском r_ij игрока Л при пользовании стра­тегией A_i в условиях П_j называется разность между выигрышем, который мы получили бы, если бы знали условия П_j и выигрышем, который мы получим, не зная их и выбирая стратегию A_i.

Очевидно, если бы мы (игрок A) знали состояние природы П_j, мы выбрали бы ту стратегию, при кото­рой наш выигрыш максимален. Этот выигрыш, макси­мальный в столбце П_j мы уже раньше встречали и обозначили βj. Чтобы получить риск r_ij, нужно из βj вычесть фактический выигрыш а_ij:

(28.1)

Для примера возьмем матрицу выигрышей (а_ij)(таблица 28.3) и построим для нее матрицу рисков (r_ij) (таблица 28.4).

При взгляде на матрицу рисков (таблица 28.4) нам становятся яснее некоторые черты данной «игры с природой». Так, в матрице выигрышей (а_ij)(таблица 28.3)

 

 

 

во второй строке первый и последний элементы были равны друг другу: а₁₂ = a₃₄ = 3. Однако эти вы­игрыши совсем не равноценны в смысле удачного вы­бора стратегии: при состоянии природы П₁ мы могли выиграть самое большее 4, и наш выбор стратегии А₂ почти совершенно хорош; а вот при состоянии П4 мы могли бы, выбрав стратегию А и получить на целых 6 единиц больше, т. е. выбор стратегии А₂ очень плох. Риск — это «плата за отсутствие информации»: в таб­лице 28.4 r₂₁ = 1, r₂₄ = 6 (тогда как выигрыши а_ij в том и другом случае одинаковы). Естественно, нам хотелось бы минимизировать риск, сопровождающий выбор решения.

Итак, перед нами — две постановки задачи о выбо­ре решения: при одной нам желательно получить мак­симальный выигрыш, при другой — минимальный риск.

Мы знаем, что самый простой случай неопределен­ности — это «доброкачественная» или стохастическая неопределенность, когда состояния природы имеют ка­кие-то вероятности Q1, Q₂,..., Q_n и эти вероятности нам известны. Тогда естественно (со всеми оговорка­ми, сделанными по этому поводу в § 5) выбрать ту стратегию, для которой среднее значение выигрыша, взятое по строке, максимально:

(28.2)

 

 

Любопытно отметить, что та же стратегия, кото­рая обращает в максимум средний выигрыш, обраща­ет в минимум и средний риск:

(28.3)

 

так что в случае стохастической неопределенности оба подхода («от выигрыша» и «от риска») дают одно и то же оптимальное решение.

Давайте чуточку «испортим» нашу неопределен­ность и допустим, что вероятности Q₁, Q₂,…, Q_n в принципе существуют, но нам неизвестны. Иногда в этом случае предполагают все состояния природы рав­новероятными (так называемый «принцип недостаточ­ного основания» Лапласа), но вообще-то это делать не рекомендуется. Все-таки обычно более или менее ясно, какие состояния более, а какие — менее вероятны. Для того чтобы найти ориентировочные значения ве­роятностей Q₁, Q₂,…, Q_n можно, например, восполь­зоваться методом экспертных оценок (см. § 5). Хоть какие-то ориентировочные значения вероятностей со­стояний природы все же лучше, чем полная неизвест­ность. Неточные значения вероятностей состояний природы в дальнейшем могут быть «скорректирова­ны» с помощью специально поставленного эксперимен­та. Эксперимент может быть как «идеальным», пол­ностью выясняющим состояние природы, так и не­идеальным, где вероятности состояний уточняются по косвенным данным. Каждый эксперимент, разумеется, требует каких-то затрат, и возникает вопрос: окупают­ся ли эти затраты возрастанием эффективности? Ока­зывается, «идеальный» эксперимент имеет смысл про­водить только в случае, когда его стоимость меньше, чем минимальный средний риск (см., например, [61).

Однако не будем больше заниматься случаем сто­хастической неопределенности, а возьмем случай «дур­ной неопределенности», когда вероятности состояний природы либо вообще не существуют, либо не подда­ются оценке даже приближенно. Ну что же? Обстанов­ка неблагоприятна для принятия «хорошего» реше­ния — попытаемся найти хотя бы не самое худшее.

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

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

(28.4)

 

(28.4)

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

2. Критерий минимаксного риска Сэвиджа. Этот критерий — тоже крайне пессимистический, но при вы­боре оптимальной стратегии советует ориентироваться не на выигрыш, а на риск. Выбирается в качестве оп­тимальной та стратегия, при которой величина риска в наихудших условиях минимальна:

 

(28.5)

Сущность такого подхода в том, чтобы всячески избегать большого риска при принятии решения. В смысле «пессимизма» критерий Сэвиджа сходен с критерием Вальда, но самый «пессимизм» здесь пони­мается по-другому.

3. Критерий пессимизма-оптимизма Гурвица. Этот критерий рекомендует при выборе решения не руко- водствов^аться ни крайним пессимизмом («всегда рас­считывай на худшее!»), ни крайним, легкомысленным оптимизмом («авось кривая вывезет!»). Согласно этому критерию выбирается стратегия из условия

(28.6)

где х — «коэффициент пессимизма», выбираемый меж­ду нулем и единицей. При х = 1 критерий Гурвица превращается в критерий Вальда; при х = 0 — в кри­терий «крайнего оптимизма», рекомендующий выбрать ту стратегию, при которой самый большой выигрыш в строке максимален. При 0 < х < 1 получается нечто среднее между тем и другим. Коэффициент х выбира­ется из субъективных соображений — чем опаснее си­туация, чем больше мы хотим в ней «подстраховать­ся», чем менее наша склонность к риску, тем ближе к единице выбирается х.

При желании можно построить критерий, анало­гичный H, исходя не из выигрыша, а из риска, но мы на этом не будем останавливаться.

«Что же,— спросит читатель,— выбор критерия — субъективен, выбор коэффициента х — тоже субъекти­вен, значит и решение тоже принимается субъективно, т. е., грубо говоря, произвольно? Где же тут наука? При чем тут математика? Может быть, лучше было бы просто, без математических затей, выбрать решение по своему произволу?»

В какой-то мере читатель прав — выбор решения в условиях неопределенности всегда условен, субъекти­вен. И все же в какой-то (ограниченной) мере мате­матические методы полезны и тут. Прежде всего, они позволяют привести игру с природой к матричной фор­ме, что далёко не всегда бывает просто, особенно когда стратегий много (в наших примерах их было очень мало). Кроме того, они позволяют заменить простое лицезрение матрицы выигрышей (или рисков), от ко­торого, когда матрица велика, может просто «зарябить в глазах», последовательным численным анализом си­туации с разных точек зрения, выслушать рекоменда­ции каждой из них и, наконец, остановиться на чем-то определенном. Это аналогично обсуждению вопроса с различных позиций, а в споре, как известно, рождает­ся истина. Так что не ждите от теории решений окон­чательных, непререкаемых рекомендаций — единствен­ное, чем она может помочь — это советом...

Если рекомендации, вытекающие из различных критериев, совпадают — тем лучше, значит, можно смело выбрать рекомендуемое решение: оно скорее всего «не подведет». Если же, как это часто бывает, рекомендации противоречат друг другу, не надо забы­вать, что у нас голову на плечах. Задумаемся над эти­ми рекомендациями, выясним, насколько к разным ре-
зультатам они приводят, уточним свою точку зрения
и произведем окончательный выбор. Не надо забывать,
что в любых задачах обоснования решений некоторый

Таблица 28.5

произвол неизбежен — хо-
тя бы при построении ма-
тематической модели, вы-:
боре показателя эффективности. Вся математика, применяемая в исследовании операций, не отменяет этого произвола, а позволяет только «поставить его на свое место».

Рассмотрим элементарный пример «игры с природой» 4 X 3, матрица выигрышей которой (a_ij) дана в таблице 28.5. Поглядим на матрицу и попробуем сразу, без расчетов, указать, какой стратегией пользоваться? Несмотря на малый
размер матрицы, это не так-то легко.

Теперь попробуем помочь себе, пользуясь крите­риями Вальда, Сэвиджа и Гурвица, причем в послед­нем возьмем х = 0,6 (перевес чуть-чуть в сторону пес­симизма). Что-то они нам скажут?

1. Слово имеет критерий Вальда. Подсчитаем ми­нимумы по строкам (см. таблицу 28.6) и выберем ту стратегию, при которой минимум строки максимален (равен 25). Это — стратегия A₃.

 

Т а б л и ц а 28.6

 

 

2. Слово имеет критерий Сэвиджа. Перейдем от матрицы выигрышей (таблица 28.6) к матрице рисков (таблица 28.7), в правом дополнительном столбце за­пишем максимальное в строке значение риска Y*.

Из чисел правого столбца минимальное (60) соот­ветствуетстратегиям А₂ и А₃ значит, обе они опти­мальны по Сэвиджу.

Таблица 28.7

 

Т а б л и ц а 28.7

 

3. Слово имеет критерий Гурвица (при x = 0,6). Опять перепишем таблицу 28.5, но на этот раз в пра­вых трех дополнительных столбцах поставим: мини­мум строки a_i, ее максимум w₁ и величину h_i = ха_i + (1 — х) w_i, округленную до целых единиц (см. табли­цу 28.8).

Максимальное значение h_i = 47 соответствует стра­тегии А₃.

Итак, в данном случае все три критерия согласно говорят в пользу стратегии А₃, которую есть все ос­нования выбрать.

 

Таблица 28.8

 

А теперь возьмем случай, когда между критерия­ми возникает «спор». Матрица выигрышей (а_ij) (с за­ранее выписанными столбцами минимумов строк а_i, максимумами строк w_i и значениями h_i (при x= 0,6) дана в таблице 28.9.

По критерию Вальда оптимальной является стра­тегия А1, по критерию Гурвица с х = 0,6 — стратегия

Таблица 28.9

A₃. Посмотрим, что скажет критерий Сэвиджа. Матри­ца рисков с дополнительным столбцом, содержащим максимумы строк дана в таблице 28.10.

Минимальным в последнем столбце является чис­ло 38, так что критерий Сэвиджа, так же как- и кри­терий Гурвица, «голосует» за стратегию А₃.

Над этим стоит поразмыслить. Если мы очень бо­имся малого выигрыша «11», который нас может пос­тигнуть при стратегии А₃, ну что же — выберем стра­тегию А₁, рекомендуемую крайне осторожным критери­ем Вальда, при котором мы, по крайней мере, можем себе гарантировать выигрыш «19», а может быть, и боль­ше. Если же наш пессимизм не так уж мрачен, по­жалуй, надо остановиться на стратегии А₃, рекомен­дуемой двумя из трех критериев.

Таблица 28.10

 

Читатель, конечно заметил, что тут мы говорим на каком-то нематематическом языке, а скорее на языке «рассуждений и здравого смысла». Что поделаешь — в неопределенности ничего хорошего нет, и при от­сутствии нужной информации никакая математика не поможет нам в однозначном выборе «оптимального» решения. Жизнь есть жизнь, будущее полно неопре­деленностей, и нам зачастую приходится принимать отнюдь не строго оптимальные, а «приемлемые» реше­ния, при обсуждении которых разные «подходы» и «критерии» выступают в качестве как бы спорящих сторон.

В заключение отметим следующее: все три крите­рия (Вальда, Сэвиджа и Гурвица) были сформулиро­ваны нами для чистых стратегий, но каждый из них может быть распространен и на смешанные, подобно тому, как мы это делали в теории игр. Однако сме­шанные стратегии в игре с природой имеют лишь' ограниченное (главным образом, теоретическое) зна­чение. Если в игре против сознательного противника смешанные статегии иногда имеют смысл как «трюк», вводящий в заблуждение противника, то в игре против «равнодушной природы» этот резон отпадает. Кроме того, смешанные стратегии приобретают смысл только при многократном повторении игры. А если уж мы ее повторяем, то неизбежно начинают вырисовываться какие-то вероятностные черты ситуации, и мы ими мо­жем воспользоваться для того, чтобы применить «сто­хастический подход» к задаче, а он, как мы знаем, смешанных стратегий не дает. Кроме того, в ситуаци­ях с «дурной» неопределенностью, когда нам мучи­тельно не хватает информации, главная задача — эту информацию получить, а не выдумывать хитроумные методы, позволяющие без нее обойтись. Одна из ос­новных задач теории статистических решений — это как раз планировании эксперимента, цель которого — выяснение или уточнение каких-то данных. На вопро­сах планирования эксперимента мы здесь останавливать­ся не будем: это отдельный предмет, требующий серьез­ного внимания. По этому вопросу мы отошлем читате­ля к специальным руководствам [29, 30], а также к интересно написанной популярной книге [27]. Основ­ной принцип теории планирования эксперимента состоит в том, что любое принятое заранее решение должно пересматриваться с учетом полеченной новой информации.

 

* * *

 

 

Таким образом, наш краткий обзор, посвященный задачам, принципам и методологии исследования опе­раций, закончен. В нем автор стремился ознакомить читателя не только с возможностями, но и с ограни­чениями математических методов, применяемых для обоснования решений. Главное — ни один из этих ме­тодов не избавляет человека от необходимости думать. Но не просто думать, а пользоваться при этом матема­тическими расчетами. Помня, что, по меткому выраже­нию Хемминга,— «главная цель расчетов — не цифры, а понимание».

 

ЛИТЕРАТУРА

1. С а а т и Т. JI. Математические методы исследования операций.— М.: Воениздат, 1963 (около 25 п. л.).

2. В е н т ц е л ь Е. С. Теория вероятностей (первые Ша­ги).—М.: Знание, 1977 (около 3,5 п. л.).

3. П о д и н о в с к и й В. В., Гаврилов В. М. Оптими- зация по последовательно применяемым критериям.— М.: Со­ветское радио, 1975 (около 8 п. л.).

4 Карпелевич Ф. И., Садовский JI. Е. Элементы линейной алгебры и линейного программирования.— М.: Наука,

1967 (около 15 п. л.).

5. Ю д и н Д. Б., Гольштейн Е. Г. Линейное програм­мирование.— М.: Наука, 1967 (около 40 п. л.).

6. В е н т ц е л ь Е. С. Исследование операций.— М.: Совет­ское радио, 1972 (около 35 п. л.).

7. В а г н е р Г. Основы исследования операций.— М.: Мир, 1972 (в трех томах, общий объем около 80 п. л.).

8. 3 у х о в и ц к и й С. И., Авдеева Л. И. Линейное и выпуклое программирование.— М.: Наука, 1964 (около 17 п. л.).

9. Турин Л. С., Д ы м а р с к и