Специальные модели исследования операций

Глава 12. Элементы теории игр Глава 13. Модели управления запасами Глава 14. Модели сетевого планирования и управления Глава 15. Элементы теории массового обслуживания.

Элементы теории игр

Понятие об игровых моделях

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

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

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

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

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

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

В любом из этих случаев — при наличии или при отсутствии конфликта — важно понять характер неопределенности в условиях поставленной задачи.

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

В качестве примера можно привести класс задач технического обслуживания и ремонта какого-либо оборудования, когда известны (получены статистически) вероятности отказов обслуживаемых приборов.

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

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

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

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

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

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

Классическая теория игр занимается задачами построения математических моделей принятия оптимальных решений в условиях конфликта и неопределенности и методами их решения. Раздач теории игр, который занимается неконфликтными ситуациями, иногда называют теорией статистических решений.

Ознакомимся с основными понятиями классической теории игр и основными типами моделей в теории игр.

Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, — игроками, а исход конфликта — выигрышем^[1].

Для каждой формализованной игры вводятся правила, т. е. система условий, определяющая: 1) варианты действий противников; 2) объем информации каждого игрока о поведении партнеров; 3) выигрыш, к которому приводит каждая совокупность действий.

Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулем, выигрыш — единицей, а ничью — 0,5.

Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока.

Ходы могут быть личными и случайными.

Личный ход — это сознательный выбор игроком одного из возможных действий (например, ход в шахматной партии). Случайный ход — это случайно выбранное действие (например, выбор карты из перетасованной колоды или погодные условия в данный момент, если считать природу одним из игроков).

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

В соответствии с различными характеристиками принята следующая основная классификация игр:

• — стохастические и нестохастические игры (в зависимости от вида неопределенности, с которой сталкиваются игроки). В первом случае известны или могут быть по крайней мере оценены законы распределения или хотя бы числовые характеристики случайных факторов, участвующих в задаче, во втором случае нет никаких данных о неизвестных параметрах, влияющих на успех решения задачи;
• — антагонистические (игры со строгим соперничеством) и неантагонистические игры. В первом случае цели игроков противоположны, во втором — могут совпадать или один из игроков может просто не иметь никаких целей (быть нейтральным);
• — стратегические и нестратегические игры (в первых субъект системы действует независимо от остальных, преследуя свои цели, во-вторых — субъекты выбирают единую для всех стратегию);
• — парные и множественные игры (игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух);
• — конечные и бесконечные игры (игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной — в противном случае);
• — коалиционные и бескоалиционные, или кооперативные и некооперативные игры (в первых возможен обмен информацией о возможных стратегиях игроков, субъектом принятия решения служит группа или коалиция, между игроками одной коалиции имеются обязывающие соглашения, во вторых субъектом принятия решения служит индивид, игроки принимают решения независимо);
• — позиционные и непозиционные игры. В позиционных играх каждый игрок имеет свою платежную матрицу, выигрыш одного не означает проигрыш другого. Игрок должен принимать последовательно несколько решений, причем выбор стратегии опирается на предыдущие решения.

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

Антагонистическая парная игра называется игрой с нулевой суммой, если выигрыш одного из игроков а равен проигрышу другого I), т. е. для полного задания игры достаточно указать величину одного из них: b = -а.

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

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

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

Далее в параграфах (12.2−12.5) излагаются основные методы решения конфликтных, парных, стратегических, бескоалиционных, конечных, некооперативных игр, простейших с точки зрения нахождения оптимального решения, где целью является единственно выигрыш как показатель эффективности.

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

• [1] Напомним, что в играх с природой реального конфликта игроков нет.