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

     Развитие  математического моделирования  привело к созданию автоматизированных систем для управления производством, что позволяет резко увеличить производительность труда и избежать субъективного влияния “человеческого” фактора при принятии решений. А поскольку принятие решений является основной частью работы менеджеров любого звена, то понимание всех тонкостей процесса принятия решений в различных условиях, знание и применение различных методов и моделей принятия решений играет значительную роль в повышении эффективности работы управленческого персонала. При этом решение той или иной управленческой задачи осуществляется в условиях, когда имеют место ограничения технико-экономического или какого-либо другого характера.

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

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

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

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

1.1 Основные понятия, классификация и история зарождения теории игр

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

      Для рассмотрения теории игр введем следующие  понятия:

игра (в математике) - это идеализированная математическая модель коллективного поведения: несколько игроков влияют на исход игры, причем их интересы различны [7];

ход - регулярное действие, выполняемое игроком во время игры;

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

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

     Теория  игр зародилась как теория рационального  поведения  двух игроков с противоположными интересами. Истоки теоретико-игровых рассуждений восходят с работам Баше де Мезирака (середина 17 века), а в экономике еще 150 лет назад теория дуополии (конкуренции двух фирм) О.Курно была развита на основе соображений, которые мы сейчас относим к теории игр. Однако самым великим событием стала публикация в 1944 г. работы фон Неймана и Моргенштерна «Теория игр и экономическое поведение. Авторы этой книги провозгласили революцию в экономической мысли, утверждая, что «теория стратегических игр — это тот самый инструмент, с помощью которого будет развиваться теория экономического поведения». Однако, несмотря на такие обещания, теория игр до определенной степени находилась в тени в течение последующих двух десятилетий. Нобелевскими лауреатами по экономике за достижения в области теории игр стали: Роберт Ауманн, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Томас Шеллинг. Теория игр также нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр, а в 2001 по мотивам книги был снят фильм «Игры разума».

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

     Далее рассмотрим классификацию игр.

      Классификация игр проводится по: количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д. [2, 7, 8].

     В зависимости от количества игроков различают игры двух и n  игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Оказывается, что для самой теории игр скачок, от двух участников к трем имеет огромное значение, тогда как добавление шестого игрока уже не столь существенно. Этот парадокс объясняется тем, что когда число игроков (возможно, с противоречивыми интересами) больше двух то возникает возможность сговора или образования коалиции: переход от двух игроков к трем заставляет вводить понятие коалиции, а переход от пяти к шести игрокам лишь увеличивает число возможных коалиций.

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

      По  характеру взаимодействия игры делятся на бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;  коалиционные (кооперативные) – могут вступать в коалиции. В кооперативных играх коалиции заранее определены.

      По  характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.

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

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

      По  виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые и др.

      Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш  игрока I в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока I, столбец – номеру применяемой стратегии игрока II; на пересечении строки и столбца матрицы находится выигрыш игрока I, соответствующий применяемым стратегиям). Если игрок I имеет m стратегий, а игрок II – n стратегий, то игра может быть задана (m ; n) – maтрицей А = ||aij||, где aij есть выигрыш игрока I, если он выберет стратегию i (i  = -1, ..., m), а игрок II – стратегию j (j = 1, ..., n).

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

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

      Модель биматричной игры представлена как Y=(X₁,X₂,H₁,H₂), где X₁(X₂) – конечное множество стратегий первого (второго) игрока и H₁(H₂) – функция выигрыша первого (второго) игрока.

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

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

1.2 Платёжная матрица и уменьшение ее порядка, принятие решений в играх с чистыми стратегиями

      В общем виде матричная игра может  быть записана следующей платёжной  матрицей (рис. 1.1), где Ai – названия стратегий игрока I, Bj – названия стратегий игрока II, aij – значения выигрышей игрока I при выборе им i – й стратегии, а игроком II – j – й стратегии. Поскольку данная игра является игрой с нулевой суммой, значение выигрыша для игрока II является величиной, противоположенной по знаку значению выигрыша игрока I. 

      Рис. 1.1 Общий вид платёжной матрицы  матричной игры

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

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

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

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

      V_н =  max_i min_j  a_ij (1)

или найти  минимальные значения по каждой из строк платёжной матрицы, а затем  определить максимальное из этих значений.  Величина Vн называется максимином матрицы или нижней ценой игры (1).

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

      V_в = min_j max_i a_ij (2).

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

      В случае, если значения Vн и Vв не совпадают, при сохранении правил игры (коэффициентов aij ) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве Vн = Vв = V. В этом случае говорят, что игра имеет решение в чистых стратегиях и называется игрой с седловой точкой, а стратегии, в которых достигается V - оптимальными чистыми стратегиями. Величина V называется чистой ценой игры[8].

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

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

      Далее рассмотрим пример платежных матриц, в которых как существует, так  и не существует решения в чистых стратегиях.

Рис. 1.2 Платёжная матрица, в которой существует решение в чистых стратегиях

Рис. 1.3 Платёжная матрица, в которой не существует решения в чистых стратегиях

     В матрице (рис. 1.2) существует решение  в чистых стратегиях.  При этом для игрока I оптимальной чистой стратегией будет стратегия A1, а для игрока II – стратегия B4.

     В матрице (рис. 1.3) решения в чистых стратегиях не существует, так как нижняя цена игры достигается в стратегии A1 и её значение равно 2, в то время как верхняя цена игры достигается в стратегии B4 и её значение равно 3.

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

      A_k* < A_k** (3),

где A_k* и A_k** - значения выигрышей при выборе игроком, соответственно, стратегий K* и K**.

В случае, если выполняется соотношение A_k* = A_k**, стратегия K* называется дублирующей по отношению к стратегии K**.

      Рассмотрим  на примере платежную матрицу  с доменируемыми и дублирующими стратегиями.

Рис. 1.4 Платёжная матрица с доминируемыми  и дублирующими стратегиями

В платежной  матрице (рис. 1.4) стратегия A1 является доминируемой по отношению к стратегии A2, стратегия B6 является доминируемой по отношению к стратегиям B3, B4 и B5, а стратегия B5 является дублирующей по отношению к стратегии B4. Данные стратегии не будут выбраны игроками, так как являются заведомо проигрышными и удаление этих стратегий из платёжной матрицы не повлияет на определение нижней и верхней цены игры, описанной данной матрицей.

      Множество недоминируемых стратегий, полученных после уменьшения размерности платёжной  матрицы, называется ещё множеством Парето (по имени итальянского экономиста Вильфредо Парето, занимавшегося  исследованиями в данной области) [7].

1.3 Понятие о матричных играх и принятие решений в смешанных стратегиях

      Исследование  в матричных играх начинается с нахождения её чистой цены. Если матричная  игра имеет решение в чистых стратегиях, то нахождением чистой цены заканчивается  исследование игры. Если же в игре нет  решения в чистых стратегиях, то можно найти нижнюю и верхнюю  цены этой игры, которые указывают, что игрок I не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.

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

      Стратегии, применённые с вероятностью, отличной от нуля, называются активными стратегиями.

      Доказано [1, 2, 4, 7, 8, 11], что для всех игр со смешанным расширением существует оптимальная смешанная стратегия, значение выигрыша при выборе которой находится в интервале между нижней и верхней ценой игры:

      V_н  £ V £ V_в (4).

При этом условии (4) величина V называется ценой игры.

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

      Рассмотрим  матрицу парной игры на примере:

Рис. 1.5 Матрица парной игры

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

      Исходная  матрица (рис. 1.5) преобразуется в  следующую (рис. 1.6):

Рис. 1.6 Преобразованная матрица

Соответственно  для игрока II не выгодна стратегия В3, поскольку она имеет

 наибольший  платеж = 4. Следовательно матрица преобразуется еще раз (рис.

1.7). 

Рис. 1.7 Повторно преобразованная матрица

      Решение игровых задач в табличном  или матричном виде всегда начинается с вычеркивания дублирующих и  заведомо невыгодных стратегий. После  чего приступают к приведению игровой  матрицы к задаче линейного программирования (ЗЛП). Процесс приведения матричных игровых задач в смешанных стратегиях к ЗЛП будет подробно рассмотрен позднее, а далее рассмотрим последний вид игровой стратегии.

1.4 Cтатистические игры, принятие решений в «играх с природой»

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