Всего на сайте:
282 тыс. 988 статей

Главная | Статистика

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 2 страница  Просмотрен 247

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

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

Игра - упрощенная формализованная модель реальной кон­фликтной ситуации. Математически формализация означает, что выработаны определенные правила действия сторон в процессе игры: варианты действия сторон; исход игры при данном вари­анте действия; объем информации каждой стороны о поведении всех других сторон.

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

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

Игрок - одна из сторон в игровой ситуации. Стратегия иг­рока - его правила действия в каждой из возможных ситуаций игры. Существуют игровые системы управления, если процесс управления в них рассматривается как игра.

Платежная матрица (матрица эффективности, матрица игры) включает все значения выигрышей (в конечной игре). Пусть игрок 1 имеет т стратегий Аi, а игрок 2 - п стратегий Вj, ( ; ). Игра может быть названа игрой тхп. Представим мат­рицу эффективности игры двух лиц с нулевой суммой, сопрово­див ее необходимыми обозначениями (табл. 2.1).

Таблица 2.1

В данной матрице элементы – значения выигрышей игро­ка 1 – могут означать и математическое ожидание выигрыша (среднее значение), если выигрыш является случайной величи­ной. Величины ,– соответственно мини­мальные значения элементов , по строкам и максимальные - по столбцам. Их содержательный смысл будет отражен ниже.

В теории игр не существует установившейся классификации видов игр. Однако по определенным критериям некоторые виды можно выделить.

Количество игроков. Если в игре участвуют две сто­роны, то ее называют игрой двух лиц. Если число сторон больше двух, ее относят к игре п игроков. Наибольший интерес вызыва­ют игры двух лиц. Они и математически более глубоко прорабо­таны и в практических приложениях имеют наиболее обширную библиографию [3, 7, 12, 13].

Количество стратегий игры. По этому критерию игры делятся на конечные и бесконечные. В конечной игре каж­дый из игроков имеет конечное число возможных стратегий. Если хотя бы один из игроков имеет бесконечное число возможных стратегий, игра является бесконечной.

Взаимоотношения сторон. Согласно данному кри­терию игры делятся на кооперативные, коалиционные и бескоа­лиционные. Если игроки не имеют право вступать в соглашения, образовывать коалиции, то такая игра относится к бескоалицион­ным; если игроки могут вступать в соглашения, создавать коали­ции - коалиционной. Кооперативная игра - это игра, в которой заранее определены коалиции.

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

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

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

Матричная игра - конечная игра двух игроков с нулевой суммой. В общем случае ее платежная матрица является прямо­угольной (см. табл. 2.1). Номер строки матрицы соответствует номеру стратегии, применяемой игроком 1. Номер столбца соот­ветствует номеру стратегии игрока 2. Выигрыш игрока 1 являет­ся элементом матрицы. Выигрыш игрока 2 равен проигрышу игрока 1. Как показано в приложении, матричные игры всегда имеют решения в смешанных стратегиях. Они могут быть реше­ны методами линейного программирования.

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

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

Если функция выигрышей может быть разделена на сумму произведений функций одного аргумента; то игра относится к сепарабельной.

Количество ходов. Согласно этому критерию игры можно разделить на одношаговые и многошаговые. Одношаго­вые игры заканчиваются после одного хода каждого игрока. Так, в матричной игре после одного хода каждого из игроков проис­ходит распределение выигрышей. Многошаговые игры бывают позиционными, стохастическими, дифференциальными и др. Подробнее см. [3,7,12,13].

Информированность cmoрон. По данному крите­рию различают игры с полной и неполной информацией. Если каждый игрок на каждом ходу игры знает все ранее приме­ненные другими игроками на предыдущих ходах стратегии, такая игра определяется как игра с полной информацией. Если игроку не все стратегии предыдущих ходов других игроков известны, то игра классифицируется как игра с неполной ин­формацией. Мы далее убедимся, что игра с полной информа­цией имеет решение. Решением будет седловая точка при чистых стратегиях.

Степень неполноты и н формации. По этому кри­терию игры подразделяются на статистические (в условиях час­тичной неопределенности) и стратегические (в условиях полной неопределенности, см. разд. 3.2). Игры с природой (см. гл. 3, 6) часто относят к статистическим играм. В статистической игре имеется возможность получения информации на основе статис­тического эксперимента, при котором вычисляется или оценива­ется распределение вероятностей состояний (стратегий) приро­ды.

С теорией статистических игр тесно связана теория приня­тия экономических решений.

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

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

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

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

Таким образом, максиминной стратегии отвечает строка мат­рицы, которой соответствует элемент ai. Какие бы стратегии ни применял игрок 2, игрок 1 максиминной чистой стратегией га­рантировал себе выигрыш, не меньший, чем a. Таково оптималь­ное поведение игрока 1.

Подход игрока 2. Своими оптимальными стратегиями он стремится уменьшить выигрыш игрока 1, поэтому при каж­дой j-й чистой стратегии он отыскивает величину своего макси­мального проигрыша

в каждом j-м столбце, т.е. определяет максимальный выигрыш игрока 1, если игрок 2 применит j-ю чистую стратегию. Из всех своих n j-х чистых стратегий он отыскивает такую, при которой игрок 1 получит минимальный выигрыш, т.е. определяет чистую верхнюю цену игры («минимакс»):

Чистая верхняя цена игры показывает, какой максимальный выигрыш может гарантировать игрок 1, применяя свои чистые стратегии, - выигрыш, не меньший, чем a. Игрок 2 за счет ука­занного выше выбора своих чистых стратегий не допустит, что­бы игрок 1 мог получить выигрыш, больший, чем b. Таким об­разом, минимаксная стратегия отображается столбцом платеж­ной матрицы, в котором находится элемент b (см. табл. 2.1). Она является оптимальной чистой гарантирующей стратегией игро­ка 2, если он ничего не знает о действиях игрока 1.

Чистая цена игры v - цена данной игры, если нижняя и вер­хняя ее цены совпадают:

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

Пример 2.1. Определить верхнюю и нижнюю цены при за­данной матрице игры и указать максиминную и минимаксную стратегии. Представим матрицу игры с обозначениями страте­гий bj, a.j, (табл. 2.2).

Т а б л и ц а 2.2

Решение. Определим нижнюю цену игры:

; ; (см. столбец ).

Определим верхнюю цену игры:

; ; ; (см. строку bj).

Таким образом, , т.е.

Значит, – чистая цена игры при стратегиях А2 и B1. Следовательно, имеем игру с седловой точкой.

Пример 2.2. Определим максиминную и минимаксную стра­тегии при заданной матрице эффективности (табл. 2.3).

Решение. Определим максиминную стратегию:

; ;

Максиминная стратегия - строка А2.

Таблица 2.3

Определим минимаксную стратегию:

Минимаксная стратегия - столбец В2. Здесь , следова­тельно, седловой точки нет.

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

В этом случае мы имеем игру с седловой точкой.

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

• чистая стратегия игрока 1;

• чистая стратегия игрока 2;

• седловой элемент.

Оптимальные чистые стратегии — это чистые стратегии, об­разующие седловую точку.

В игре без седловой точки, если игрок 1 информирован о стратегии, принятой игроком 2, он сможет принять оптималь­ную стратегию, которая не совпадает с максиминной.

Пример 2.3. Дана матрица игры

Допустим, игроку 1 стало известно, что игрок 2 принял минимаксную стратегию. Игрок 1 должен выбрать оптимальную стратегию при условии, что B2 стратегия игрока 2 ( = 5).

Решение. Определим максиминную стратегию игрока 1:

Стратегия игрока 1 – А2 - максиминная.

Выберем оптимальную стратегию для игрока 1. Ею будет не максиминная А2, дающая игроку 1 выигрыш = 4, а та страте­гия, которая соответствует . В этом случае его максималь­ный гарантированный выигрыш будет равен верхней цене игры , поэтому он выберет свою оптимальную стратегию А1, зная, что игрок 2 выбрал свою стратегию В2. Таким образом, рас­смотренный пример дает результат, отличный от результата при игре с седловой точкой.

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

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

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

2.2. СМЕШАННЫЕ СТРАТЕГИИ

Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 1 не получит выигрыша, превосходящего верхнюю цену игры, и что игроку 1 гарантирован выигрыш, не меньший нижней цены игры. В примере 2.3 игрок 1 получил по своей оптимальной стратегии А1, отличной от максиминной, выигрыш, равный верхней цене игры. Такова плата за информи­рованность о стратегии игрока 2. Это крайний случай. Не улуч­шится ли результат игрока 1, если информация о действиях противной стороны будет отсутствовать, но игрок будет много­кратно применять чистые стратегии случайным образом с опре­деленной вероятностью?

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

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

• игра без седловой точки;

• игроки используют случайную смесь чистых стратегий с заданными вероятностями;

• игра многократно повторяется в сходных условиях;

• при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

• допускается осреднение результатов игр.

Применяются следующие обозначения смешанных стратегий.

Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А1, А2,..., Аm с соответствующими вероятностями р1, р2, ..., рm,

где ,

Для игрока 2

где ,

qj вероятность применения чистой стратегии Вj.

В случае, когда pi = 1 , для игрока 1 имеем чистую стратегию:

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

,

где и - векторы;

рi и qj - компоненты векторов.

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

.

Игрок 2 добивается того, чтобы выполнялось условие

.

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

Цена игры g – средний выигрыш игрока 1 при использовании обоими игроками смешанных стратегий. Следовательно, реше­нием матричной игры являются:

1) - оптимальная смешанная стратегия игрока 1;

2) - оптимальная смешанная стратегия игрока 2;

3) g - цена игры.

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

Существует основная теорема математических игр (доказа­тельство см. в приложении).

Теорема 2.1. Для матричной игры с любой матрицей A вели­чины

И

существуют и равны между собой: .

Следует отметить, что при выборе оптимальных стратегий игроку 1 всегда будет гарантирован средний выигрыш, не мень­ший, чем цена игры, при любой фиксированной стратегии игро­ка 2 (и, наоборот, для игрока 2). Активными стратегиями игро­ков 1 и 2 называют стратегии, входящие в состав оптимальных смешанных стратегий соответствующих игроков с вероятностя­ми, отличными от нуля. Значит, в состав оптимальных смешан­ных стратегий игроков могут входить не все априори заданные их стратегии.

2.3. РЕШЕНИЕ ЗАДАЧ В СМЕШАННЫХ СТРАТЕГИЯХ (ЧАСТНЫЙ СЛУЧАЙ)

Решить игру - означает найти цену игры и оптимальные стратегии. Рассмотрение методов нахождения оптимальных сме­шанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 2х2. Игры с седловой точкой специально рассматриваться не будут. Если получена седловая точка, то это означает, что имеются невыгодные стратегии, от которых следу­ет отказываться. При отсутствии седловой точки можно полу­чить две оптимальные смешанные стратегии. Как уже отмеча­лось, эти смешанные стратегии записываются так:

Значит, имеется платежная матрица

При этом

откуда получаем оптимальные значения и :

Зная и находим g:

Вычислив g, находим и :

Задача решена, так как найдены векторы

и цена игры g. Имея матрицу платежей А, можно решить задачу графически. При этом методе алгоритм решения весьма прост (рис.

2.1):

1. По оси абсцисс откладывается отрезок единичной длины.

2. По оси ординат откладываются выигрыши при стратегии А1.

3. На линии, параллельной оси ординат, в точке 1 отклады­ваются выигрыши при стратегии А2.

4. Концы отрезков обозначаются для a11b11, a12 – b21, a22b22, a21 – b12 и проводятся две прямые линии b11 b12 и b21 b22.

5. Определяется ордината точки пересечения с. Она равна g. Абсцисса точки с равна р21 = 1 – р2).

Рис. 2.1. Оптимальная смешанная стратегия

Данный метод имеет достаточно широкую область приложе­ния. Это основано на общем свойстве игр т´п, состоящем в том, что в любой игре т´п каждый игрок имеет оптимальную сме­шанную стратегию, в которой число чистых стратегий не боль­ше, чем min(m,n). Из этого свойства можно получить известное следствие: в любой игре 2´п и т´2 каждая оптимальная страте­гия и содержит не более двух активных стратегий. Значит, любая игра 2´n и т´2 может быть сведена к игре 2´2. Следовательно, игры 2´т и т´2 можно решить графическим методом.

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

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

Задача 2.1. Выбрать оптимальный режим работы новой систе­мы ЭВМ, состоящей из двух ЭВМ типов А1 и А2. Известны выигрыши от внедрения каждого типа ЭВМ в зависимости от внешних условий, если сравнить со старой системой.

При использовании ЭВМ .типов А1 и А2 в зависимости от характера решаемых задач В1 и В2 (долговременные и краткос­рочные) будет разный эффект. Предполагается, что максималь­ный выигрыш соответствует наибольшему значению критерия эффекта от замены вычислительной техники старого поколения на ЭВМ А1 и А2.

Итак, дана матрица игры (табл. 2.4), где А1, А2 - стратегии руководителя; В1, В2 - стратегии, отражающие характер решае­мых на ЭВМ задач.

Таблица 2.4

Требуется найти оптимальную смешанную стратегию руково­дителя и гарантированный средний результат g, т.е. определить, какую долю времени должны использоваться ЭВМ типов А1 и А2.

Решение. Запишем условия в принятых индексах:

а11 = 0,3; а12 = 0,8; а21 = 0,7; а22 = 0,4 .

Определим нижнюю и верхнюю цены игры:

a1 = 0,3; a2 = 0,4; a = 0,4;

b1 = 0,7; b2 = 0,8; b = 0,7.

Получаем игру без седловой точки, так как

Максиминная стратегия руководителя вычислительного цен­тра – А2.

Для этой стратегии гарантированный выигрыш равен a = 0,4 (40 %) по сравнению со старой системой.

Решение для определения g, р1 и р2 проведем графически (рис. 2.2).

Рис. 2.2. Графическая интерпретация алгоритма решения

Алгоритм решения:

1. По оси абсцисс отложим отрезок единичной длины.

2. По оси ординат отложим выигрыши при стратегии А1.

3. На вертикали в точке 1 отложим выигрыши при стратегии А2.

4. Проводим прямую b11 b12, соединяющую точки а11,a21.

5. Проводим прямую b21b22, соединяющую точки а12, а22.

6. Определяем ординату точки пересечения с линий b11b12 и b21b22. Она равна g.

7. Определим абсциссу точки пересечения с. Она равна р2, а р1=1–р2

Выпишем решение и представим оптимальную стратегию игры:

Вывод. При установке новой системы ЭВМ, если неизвес­тны условия решения задач заказчика, на работу ЭВМ А1 долж­но приходиться 37,5 % времени, а на работу ЭВМ А2 - 62,5 %. При этом выигрыш составит 55 % по сравнению с предыдущей системой ЭВМ.

Предыдущая статья:ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 1 страница Следующая статья:ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ 3 страница
page speed (0.0232 sec, direct)