Учебная работа. Изучение игровых моделей и их применение в практике принятия решений
изучение игровых моделей и их применение в практике принятия решений
ВВЕДЕНИЕ
Менеджмент игра управленческий
Каждому опытному управленцу должно быть известно, что один из наиболее эффективных интеллектуальных инструментов менеджера — это теория принятия решений. отец научного менеджмента Анри Файоль сформулировал основные функции управления одной фразой: «Управлять — значит прогнозировать и планировать, организовывать, руководить командой, координировать и контролировать«. Но каждая из этих функций неразрывно связана с принятием решений.
На практике часто появляется необходимость согласования действий фирм, объединений, министерств и других участников проектов в случаях, когда их интересы не совпадают. В таких ситуациях теория игр позволяет найти лучшее решение для поведения участников, обязанных согласовывать действия при столкновении интересов. Теория игр все шире проникает в практику экономических решений и исследований. Ее можно рассматривать как инструмент, помогающий повысить эффективность плановых и управленческих решений.
Целью данной курсовой работы является изучение игровых моделей и их применение в практике принятия решений.
Объектом исследования являются матричные игры.
Предмет исследование: применение игровых моделей в теории принятия решений.
Для достижения поставленной цели необходимо решить следующие задачи:
изучить ключевые элементы теории игр;
решить практические задачи, используя игровые модели;
на основе полученных результатов принять решение об оптимальной стратегии игрока.
ГЛАВА 1. основные ПОНЯТИЯ ТЕОРИИ ИГР
менеджмент игра управленческий
Во многих практических задачах возникают ситуации, когда требуется принять решение, не имея достаточной информации. Неизвестными могут быть как условия осуществления какой-либо операции, так и сознательные действия лиц, от которых зависит успех этой операции. Разработаны специальные математические методы, предназначенные для обоснования решений в условиях риска и неопределенности. В некоторых, наиболее простых случаях эти методы дают возможность фактически найти и выбрать оптимальное решение. В более сложных случаях эти методы доставляют вспомогательный материал, позволяющий глубже разобраться в сложной ситуации и оценить каждое из возможных решений с различных точек зрения, и принять решений с учетом его возможных последствий. Одним из важных условий принятия решений в этом случае является минимизация риска.
При решении ряда практических задач исследования операций (в области экологии, обеспечения безопасности жизнедеятельности и т. д.) приходится анализировать ситуации, в которых сталкиваются две (или более) враждующие стороны, преследующие различные цели, причем результат любого мероприятия каждой из сторон зависит от того, какой образ действий выберет противник. Такие ситуации мы можно отнести к конфликтным ситуациям, а математическим инструментом для их решения является теория игр.
Первую попытку создать математическую теорию игр предпринял в 1921 г. Э.Борель. Как самостоятельная область науки впервые теория игр была систематизировано изложена в монографии Дж. Фон Неймана и О. Моргенштерна Теория игр и экономическое например, теория несовершенной конкуренции, теория экономического стимулирования и др.) развивались в тесном контакте с теорией игр.[4, с. 12] Теория игр с успехом применяется и в социальных науках (например, анализ процедур голосования, поиск равновесных концепций, определяющих кооперативные и некооперативные поведения лиц). Как правило, избиратели отводят кандидатов, представляющих крайние точки зрения, но при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает борьба. Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке зрения на кооперацию.[2, с. 9]
Теория игр является математической теорией конфликтных ситуаций, при помощи которой можно выработать рекомендации по рациональному образу действий участников конфликта. чтобы сделать возможным математический анализ ситуации без учета второстепенных факторов, строят упрощенную, схематизированную модель ситуации, которая называется игрой. Игра ведется по вполне определенным правилам, под которыми понимается система условий, регламентирующая возможные варианты действий игроков; объем информации каждой стороны о поведении другой; результат игры, к которому приводит каждая данная совокупность ходов.
Каждая формализованная игра (модель) характеризуется:
. количеством субъектов — игроков, участвующих в конфликте;
. вариантом действий для каждого из игроков, называемых стратегиями;
. функциями выигрыша или проигрыша (платежа) исхода конфликта;
Чтобы описать игру, необходимо сначала выявить ее участников. Это условие легко выполнимо, когда речь идет об обычных играх типа шахмат, канасты и т.п. Иначе обстоит дело с рыночными играми. здесь не всегда просто распознать всех игроков, т.е. действующих или потенциальных конкурентов. Практика показывает, что не обязательно идентифицировать всех игроков, надо обнаружить наиболее важных.
Игры охватывают, как правило, несколько периодов, в течение которых игроки предпринимают последовательные или одновременные действия. Эти действия обозначаются термином ход. действия могут быть связаны с ценами, объемами продаж, затратами на научные исследования и разработки и т.д. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор игроком одного из возможных вариантов действий и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, выбор карты из перетасованной колоды и т. п.). Для каждого случайного хода правила игры определяют распределение вероятностей возможных исходов. Игра может состоять только их личных или только из случайных ходов, или из их комбинации. Периоды, в течение которых игроки делают свои ходы, называются этапами игры. Выбранные на каждом этапе ходы, в конечном счете, определяют платежи (выигрыш или убыток) каждого игрока, которые могут выражаться в материальных ценностях или деньгах (преимущественно дисконтированная Прибыль).
Следующим основным понятием теории игр является понятие стратегии. Стратегия — это априори принятая игроком система решений (вида «если — то»), которых он придерживается во время ведения игры, которая может быть представлена в виде алгоритма и выполняться автоматически. Каждый из участников игры может выбирать свою стратегию. совокупность стратегий, которые выбрали участники игры, называется игровой ситуацией. Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтной ситуации, т. е. определение «оптимальной стратегии» для каждого из них. Оптимальные стратегии характеризуются устойчивостью, то есть ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии. Стратегия, оптимальная по одному показателю, необязательно будет оптимальной по другим. Сознавая эти ограничения и поэтому, не придерживаясь слепо рекомендаций, полученных игровыми методами, можно все же разумно использовать математический аппарат теории игр для выработки, если не в точности оптимальной, то, во всяком случае «приемлемой» стратегии. Относительно концепции стратегии следует заметить, что игрок определяет свои действия не только для этапов, которых фактически достигла конкретная игра, но и для всех ситуаций, включая и те, которые могут и не возникнуть в ходе данной игры.
Следует, однако, указать и на наличие определенных границ применения аналитического инструментария теории игр. В следующих случаях он может быть использован лишь при условии получения дополнительной информации.
Во-первых, это тот случай, когда у предприятий сложились разные представления об игре, в которой они участвуют, или когда они недостаточно информированы о возможностях друг друга. Например, может иметь место неясная информация о платежах конкурента (структуре издержек). Если неполнотой характеризуется не слишком сложная информация, то можно оперировать сопоставлением подобных случаев с учетом определенных различий.
Во-вторых, теорию игр трудно применять при множестве ситуаций равновесия. Эта проблема может возникнуть даже в ходе простых игр с одновременным выбором стратегических решений.
В-третьих, если ситуация принятия стратегических решений очень сложна, то игроки часто не могут выбрать лучшие для себя варианты. Например, на Рынок в разные сроки могут вступить несколько предприятий или реакция уже действующих там предприятий может оказаться более сложной, нежели быть агрессивной или дружественной.
Классификацию игр можно проводить по различным критериям. Детализированная классификация представлена на рисунке 1.1.
рисунок 1.1 — Классификация игр
Игры с ненулевой суммой еще называются антагонистическими играми. Исторически антагонистические игры являются первым классом математических моделей теории игр, при помощи которых описывались азартные игры. Считается, что благодаря этому предмету исследования теория игр и получила свое название. В настоящее время антагонистические игры рассматриваются как часть более широкого класса некооперативных игр. чтобы решить или смоделировать антагонистическую игру, нужно для каждого игрока указать стратегии, удовлетворяющие условию оптимальности, т.е. игрок A должен получить максимальный гарантированный выигрыш, какой бы своей стратегии не придерживался игрок B, а игрок B должен получить минимальный проигрыш, какой бы своей стратегии не придерживался игрок A.
В бескоалиционных играх игроки не имеют права вступать в соглашения, образовывать коалиции; коалиционные (кооперативные) — игроки могут вступать в коалиции. В кооперативных играх коалиции заранее определены. В этих играх приходится рассматривать не только индивидуальные действия игроков, характерные для бескоалиционных игр, но и коллективные действия игроков, объединяющихся в коалиции. В связи с этим в кооперативных играх нельзя применять понятие индивидуальных платежей. Вместо этого используют так называемую характеристическую функцию, определяющую выигрыш каждой коалиции игроков. При этом предполагается, что выигрыш пустой коалиции равен нулю.
Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C, то против неё выступает коалиция N C. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2N, где N — количество игроков), то выигрыш для C будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме представляется парой (N, v), где N — множество всех игроков, а v : 2N → R — это характеристическая функция.
По форме выделяют игру экстенсивной и нормальной формы. Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной. Пример экстенсивной игры изображен на рисунке 1.2.
рисунок 1.2 — Игра в экстенсивной форме для двух игроков
Чтобы найти решение в экстенсивной форме, работа начинается с конца. Для игрока 1 лучшей последовательностью ходов является та, где он зарабатывает 8 очков, а противник только 2. Поэтому игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
игра в нормальной форме (или стратегической форме) состоит из трех элементов: множества игроков, множества чистых стратегий каждого игрока, множества платежных функций каждого игрока. таким образом, игру в нормальной форме можно представить в виде n-мерной матрицы (таблицы), элементы которой это n-мерные платежные вектора.
Матричная игра — это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока А в виде матрицы. строка матрицы соответствует номеру применяемой стратегии игрока А, столбец — номеру применяемой стратегии игрока В; на пересечении строки и столбца матрицы находится выигрыш игрока А, соответствующий применяемым стратегиям.
Биматричная игра — это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец — стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице — выигрыш игрока 2.)
Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной. доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения.
Если функция выигрышей является выпуклой, то такая игра называется выпуклой. Для них разработаны приемлемые методы решения, состоящие в отыскании чистой оптимальной стратегии (определённого числа) для одного игрока и вероятностей применения чистых оптимальных стратегий другого игрока. такая задача решается сравнительно легко.
Нормальная форма представления имеет более общий характер. Все внимание концентрируется на стратегическом аспекте игры. Поэтому в данной курсовой работе будут подробно рассмотрены матричные игры, так как удобным способом решения.
ГЛАВА 2. ОБЩИЕ задачи В ТЕОРИИ ИГР
.1 Матричная игра с нулевой суммой
Матричная игра называется игрой с нулевой суммой, если в этой игре выигрыш одного игрока равняется проигрышу другого игрока. каждая матричная игра с нулевой суммой имеет платежную матрицу. Для того чтобы построить эту матрицу, обозначим одного из игроков символом A, а другого − символом B, и предположим, что A1, A2, …, Am − стратегии, которые может применять игрок A, а B1, B2, …, Bn − стратегии, которые может применять игрок B. Такая игра называется игрой типа m×n.
Платежная матрица игры будет выглядеть следующим образом:
(2.1.1)
Элементы cij (i = 1, 2, …, m; j = 1, 2, …, n) равны выигрышам игрока A (и проигрышам игрока B) при применении игроками стратегий Ai и Bj соответственно.
Если игрок A выберет стратегию Ai, то все его возможные выигрыши будут элементами i — й строки матрицы C. В наихудшем для игрока A случае, когда игрок B применяет стратегию, соответствующую минимальному элементу этой строки, выигрыш игрока A будет равен числу. следовательно, для получения наибольшего выигрыша, игроку A нужно выбирать ту из стратегий, для которой число максимально.
Стратегия игрока А, соответствующая наибольшему из чисел, называется максиминной. Если игрок А будет придерживаться максиминной стратегии, то ему гарантирован выигрыш, не меньший, чем число α, при любом поведении игрока В. Число α называется нижней ценой игры и рассчитывается по формуле:
(2.1.2)
Проанализируем теперь платежную матрицу с точки зрения игрока B, заинтересованного в том, чтобы игрок A выиграл, как можно меньше.
Если игрок B выберет стратегию Bj, то все возможные выигрыши игрока A будут элементами j — го столбца платежной матрицы С. В наихудшем для игрока B случае, когда игрок A применяет стратегию, соответствующую максимальному элементу этого столбца, выигрыш игрока B будет равен числу. следовательно, игроку B нужно выбрать такую стратегию, для которой число минимально. Такая стратегия называется минимаксной. Если игрок В применяет минимаксную стратегию, то игрок А не может выиграть больше, чем число β, которое называется верхней ценой игры и рассчитывается по формуле:
(2.1.3)
каждый игрок придерживается принципа осторожности, то есть стремится обеспечить себе максимально возможный выигрыш при любых действиях противника. Также этот принцип, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, называют «принципом минимакса», а минимаксную стратегию и максиминную стратегию называют общим термином «минимаксные стратегии». Иногда возникает ситуация, при которой
(2.1.4) такая игра называется игрой с седловой точкой. Для игры с седловой точкой общее Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии Аi* и Вj*, образующие седловую точку, называются оптимальными. Элемент платежной матрицы ci*j*, который соответствует минимаксным стратегиям Ai* и Bj, является одновременно минимальным в своей строке и максимальным в своем столбце и называется седловой точкой. Следовательно, выполняется равенство v= ci*j*. Тройка (i*, j*, v) считается решением матричной игры с седловой точкой. Если возникает ситуация, когда нижняя цена игры отличается от верхней цены игры, то игра является игрой без седловой точки. Для любой игры без седловой точки выполнено неравенство α < β.
Если партнеры играют только один раз, то игрокам целесообразно придерживаться принципа минимакса, как в игре с седловой точкой, так и в игре без седловой точки. В случае многократного повторения игры с седловой точкой игрокам также целесообразно придерживаться принципа минимакса. Если же многократно повторяется игра без седловой точки, то постоянное использование минимаксных стратегий становится невыгодным. действительно, в игре без седловой точки элемент платежной матрицы ci*j*, соответствующий минимаксной стратегии игрока A, не обязан быть минимальным в своей строке. Следовательно, игрок B, зная о том, что игрок A в следующей игре будет использовать минимаксную стратегию Ai*, может выбрать стратегию, отвечающую минимальному элементу строки i*. В результате выигрыш игрока A уменьшится от величины ci*j* до величины α. Аналогично может поступить и игрок A, неожиданно применив против игрока B стратегию, соответствующую максимальному элементу столбца j*. Более того, доказано, что при многократно повторяемой игре без седловой точки игроку A, для обеспечения среднего выигрыша, большего, чем α, следует чередовать свои стратегии A1, A2, …, Am. Игроку B для улучшения результата также целесообразно чередовать свои стратегии B1, B2, …, Bn. В играх, которые повторяются многократно, каждая из стратегий A1, A2, …, Am называется чистой стратегией. Стратегия игрока А, состоящая в том, чтобы применять чистые стратегии A1, A2, …, Am, чередуя их по случайному закону с частотами p1, …, pm , называется смешанной стратегией pI=(p1,p2,…pm). Платежная функция при этом определяется как математическое ожидание выигрыша первого игрока при применении игроками смешанных стратегий p и q и равна: (2.1.5) Сумма частот p1, …, pm должна быть равна единице. Чистые и смешанные стратегии игрока B определяются аналогично. Стратегии SA и SB называются оптимальными, если M(P,Q*)≤M(P*,Q*)≤M(P*,Q) (2.1.6) В 1928 году фон Нейманом была доказана основная теорема теории игр, утверждающая, что каждая игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий. Поскольку все чистые стратегии являются частными случаями смешанных стратегий, то из основной теоремы теории игр можно получить следующие следствия: .Любая игра имеет цену. . цена игры удовлетворяет неравенству α ≤v ≤ β . 3. Средний выигрыш остается равным цене игры, если один из игроков придерживается своей оптимальной стратегии, а другой игрок применяет свои полезные стратегии с любыми частотами. При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы: 1.Исключить из платежной матрицы заведомо невыгодные (доминирующие) стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов). 2.Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой. .Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение. рассмотрим аналитический метод решения игры типа 2 x 2. необходимо найти решение для игры без седловой точки типа 2 x 2 с платежной матрицей , то есть найти оптимальную стратегию pI=(p1,p2,…pm) игрока А. оптимальная стратегия обеспечивает игроку A выигрыш, равный цене игры v, даже если игрок B не выходит за пределы своих полезных стратегий. В данной игре обе чистые стратегии игрока B являются полезными, поскольку в противном случае игра имела бы решение в области чистых стратегий, то есть была бы игрой с седловой точкой. Для нахождения оптимальной стратегии нужно найти неизвестные p1, p2, v, которые удовлетворяют следующей системе из трех линейных уравнений: (2.1.7) Решение этой системы имеет вид: (2.1.8) Аналогичным образом можно найти и оптимальную стратегию игрока В: (2.1.9) Игры размером m×n решаются с помощью приведения к задачам линейного программирования. 2.2 Графический метод решения игровых задач с нулевой суммой Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии, то есть игры 2×2, 2×n, m×2. рассмотрим игру типа 2×n без седловой точки, платежная матрица которой имеет вид: (2.2.1) Решение игры такого типа может быть найдено графическим методом. Для этого необходимо провести через точку (1; 0) координатной плоскости Oxy прямую l, перпендикулярную оси абсцисс. после этого для каждой из стратегий Bi (i=1,2,…, n) провести прямую, уравнение которой: (2.2.2) Эта прямая соединяет точку (0, a1i) на оси Оу с точкой (0, a2i) на прямой l. Ось Оу отвечает за стратегию A1, а прямая l − за стратегию A2. Графически это изображено на рисунке 2.1 и 2.2:
рисунок 2.1 — Изображение прямой bi
Рисунок 2.2 — Решение игры графическим методом Если игрок А применяет смешанную стратегию pI=(p1,p2,…pm), то его выигрыш в случае, если противник применяет чистую стратегию Bi, равен (2.2.3) Этому выигрышу соответствует точка М на прямой bi с абсциссой p2 (рисунок 2.2). Ломаная b1MNb3, отмеченная на графике жирной линией, позволяет определить минимальный выигрыш игрока А при любом поведении игрока В. Точка N, в которой эта ломаная достигает максимума, определяет решение и цену игры. Ордината точки N равна цене игры v, а ее абсцисса p2 — частоте применения стратегии A1 в оптимальной смешанной стратегии игрока А. далее непосредственно по графику нужно найти пару «полезных» стратегий игрока В, пересекающихся в точке N (если в точке N пересекается более двух стратегий, то выбрать любые две из них). Пусть это будут стратегии Bi и Bj. Поскольку выигрыш игрока А, если он придерживается оптимальной стратегии, не зависит от того, в каких пропорциях игрок В применяет эти стратегии, то неизвестные p1, p2, v, определяются из системы уравнений: (2.2.4) Оптимальная стратегия игрока B имеет вид:
Для нахождения частот q1 и q2 используется соотношение: (2.2.5) Следует отметить, что иногда точка N не является пересечением двух стратегий, а попадает на одну из прямых х = 0 или х = 1. В этом случае решением игры будут соответствующие чистые стратегии. Для игры m×2 решение находится совершенно аналогично. Действительно, поскольку выигрыш игрока А одновременно является проигрышем игрока В, то для решения задачи нужно построить ломаную, соответствующую верхней границе выигрыша игрока А, а затем найти на ней точку с минимальной ординатой. Для игр с седловой точкой рассмотрим следующий пример. Пусть нам задана матрица
Верхняя и нижняя цены игры равны, то есть β=α=2. значит эта игра имеет седловую точку. оптимальными стратегиями игроков I и II будут P*=(1;0) и Q*=(1;0). В графическом виде решение игры представлено на рисунке 2.3.
рисунок 2.3 — Решение игры с седловой точкой Анализируя график, видно, что стратегия В2 не выгодна, а стратегия А1 лучше, чем стратегия А2. .3 Определение смешанных стратегий с помощью линейной оптимизации Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Рассмотрим игру m×n , определяемую матрицей:
Пусть для данной матричной игры α≠β, определим такие значения вероятностей выбора стратегий для игрока 1 (p1,p2, …, pm) и для игрока 2 (q1,q2, …, qm) , при которых игроки достигали бы своего максимально гарантированного выигрыша. Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений — при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что v>0. Применение игроком I оптимальной смешанной стратегии pI*, гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры v. Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I — свою оптимальную стратегию pI*. Тогда средний выигрыш игрока I будет равен: vi=a1jp1+a1jp2+…+aijpi+…+amjpm, j= (2.3.2) учитывая, что vj не может быть меньше v, записываются следующие условия: (2.3.3) Чтобы определить значение v, разделим обе части каждого из уравнений на v. Величину pi/v обозначим через xi, а qj/v — через uj. Для игрока 1 получим новую систему неравенств: (2.3.4) Для игрока 1 необходимо найти максимальную цену игры v. Следовательно, значение 1/v должно стремиться к минимуму. Целевая функция задачи будет иметь следующий вид:
(2.3.5) (2.3.5) Таким образом, задача определения оптимальной смешанной стратегии свелась к стандартной задаче линейной оптимизации: найти неотрицательные значения переменных xi, i=1,2,…m, минимизирующие целевую функцию (2.3.5) и удовлетворяющие условиям (1.4.4). Решение задачи линейной оптимизации позволяет найти цену игры v и оптимальную стратегию pI*=(p1,p2, …, pm ) первого игрока: ;; i=1, 2, …, m (2.3.6) Аналогично можно показать, что оптимальная стратегия второго игрока qII*=(q1,q2, …, qn ) определяется по формулам: , j=1, 2, …, n (2.3.7) (2.3.8) где uj— неотрицательные решения задачи линейной оптимизации, двойственной по отношению к исходной задаче: Для игрока 2 необходимо найти минимальную цену игры v. Следовательно, значение 1/v должно стремиться к максимуму. (2.3.9) таким образом, оптимальные стратегии первого и второго игроков могут быть найдены путем решения пары двойственных задач линейной оптимизации, представленной в таблице 2.1. Таблица 2.1 — Пара двойственных задач Исходная задачаДвойственная задача Цена игры и вероятности применения стратегий игроками I и II равны: (2.3.10)
Значения xi и uj не могут быть отрицательными, так как являются значениями вероятностей выбора стратегий игроков. цена игры вычисляется на основе коэффициентов выигрышей платежной матрицы. Поэтому, для того, чтобы гарантировать условие неотрицательности для всех переменных, необходимо, чтобы все коэффициенты матрицы были неотрицательными. Решить двойственную задачу можно с помощью симплекс-метода или с помощью команды Поиск решений продукта Microsoft Office Excel. .4 Игры с природой Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком один. Игроку два (природа) не важен результат, либо он не способен к осмысленным решениям. или, возможно, условия не зависят от действий игрока, а определяются внешними факторами: реакция рынка, который не будет вредить одному конкретному игроку, государственная политика, реальная природа. Различают два вида задач в играх с природой: ·задача о принятии решений в условиях риска, когда известны вероятности, с которыми природа принимает каждое из возможных состояний; ·Задачи о принятии решений в условиях неопределенности, когда нет возможности получить информацию о вероятностях появления состояний природы; Выбор оптимальной стратегии в играх с природой определяется рядом критериев, таких как: 1.Критерий Лапласа. В основе критерия лежит предположение: поскольку о состояниях обстановки ничего не известно, то их можно считать равновероятными. Исходя из этого действуют формула:
(2.4.1) оптимальной стратегий является та, у которой критерий максимальный. 2.Критерий Вальда. Это максиминный критерий, стратегия выбирается из условия max(minaij) и совпадает с нижней ценой игры. Игрок исходит из предположения о том, что природа будет действовать наихудшим для него образом, поэтому данный критерий считается пессимистическим. 3.Критерий максимума является оптимистическим и выбирается из условия max(maxaij). .Критерий Гурвица рекомендует стратегию, определяемую по формуле: (2.4.2) Это критерий обобщенного максимина. Согласно данному критерию при оценке и выборе систем неразумно проявлять как осторожность, так и азарт, а следует, учитывая самое высокое и самое низкое значения эффективности, занимать промежуточную позицию (взвешиваются наихудшие и наилучшие условия). Для этого вводится коэффициент оптимизма α (0 ≤ α ≤ 1), характеризующий отношение к риску лица, принимающего решение. Эффективность систем находится как взвешенная с помощью коэффициента α сумма максимальной и минимальной оценок. 5.Критерий Сэвиджа. Суть его заключается в выборе стратегии, не допускающей слишком высоких потерь. Для этого используется матрица рисков, элементы которой отражают убытки, которые понесет игрок в том случае, если для каждого состояния природы не будет выбрано наилучшей стратегии, т.е. определяется как разность между максимальным и текущим значениями оценок эффективности в столбце: (2.4.3) после преобразования матрицы используется критерий минимакса. ГЛАВА 3. ПРИМЕНЕНИЕ ТЕОРИИ ИГР ДЛЯ ПРИНЯТИЯ СТРАТЕГИЧЕСКИХ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ Два конкурирующих предприятия «МобильныеТелеСистемы» (МТС) и «Велком» предоставляют услуги связи на рынок Беларуси. Перечень предлагаемых услуг включает мобильную связь, как на территории страны, так и за рубежом, мобильный и домашний Интернет, телевиденье и так далее. Кроме услуг предприятия предоставляют товары мобильной связи, такие как телефоны, смартфоны, планшеты, модемы и прочее оборудование. МТС и «Велком» являются самыми крупными в стране операторами связи и их доли рынка соответственно равны 42,5% и 45,1%. [20] Оба предприятия имеют одинаковую стратегическую цель — увеличить долю на рынке и Прибыль за счет привлечения новых клиентов при минимальных затратах. Для достижения этой цели существует несколько стратегий: 1)модернизация компаний; 2)привлечение иностранных инвесторов; )стимулирование продаж. В процессе принятия решения о правильном выборе стратегии роста необходимо воспользоваться инструментами теории игр. Для простоты восприятия информации предприятия «МТС» и «Велком» и обозначаются соответственно, как предприятия А и В, а вышеперечисленные стратегии, как А1(В1), А2(В2) и А3(В3). Анализ показал, что при осуществлении обоими предприятиями указанных мероприятий доля (в %) предприятия на рынке мобильной связи изменится следующим образом:
Так как предприятия ведут борьбу за долю рынка, то выигрыш одного предприятия означает проигрыш другого. Такая задача может быть сведена к матричной игре с нулевой суммой. При этом коэффициенты матрицы означают изменение в доле рынка. В случае, если это изменение положительно, то выигрывает предприятие А, если отрицательно — предприятие В. Для решения матричной игры сначала необходимо избавится от отрицательных коэффициентов. Для этого необходимо увеличить коэффициенты на любое целое число L. В данной задаче L=6, поэтому получаем новую матрицу:
В данной матрице нет ни доминируемых, ни дублирующих стратегий. По формулам (2.1.2) и (2.1.3) находятся нижняя и верхняя цены игры:
таким образом, нижняя и верхняя цена игры в матрице совпадают. Это значит, что имеются чистые стратегии роста, которые являются оптимальными для обоих предприятий в условиях данной задачи. Стратегии A1 и B3 — чистые оптимальные стратегии для предприятий А и В соответственно. Чтобы найти цену игры v, соответствующее первоначальной матрице, необходимо вычесть число L, прибавленное на начальном этапе. В итоге v=1. Таким образом, предприятие «МТС» должно использовать стратегию А1, то есть проводить модернизацию компании. При этом доля рынка увеличится на 1%. В свою очередь, оптимальной стратегией для «Велком», чтобы сохранить лояльность клиентов, является В3, то есть стимулирование продаж, вследствие которого доля рынка уменьшится только на 1%. Рассмотрим случай для компании «МТС». между предприятиями стоит острая конкурентная борьба за лояльность каждого абонента. При выборе оператора связи белорусы основываются на соотношении цены и качества услуг. Поэтому для сохранения конкурентоспособности на рынке предприятиям необходимо проводить своевременную модернизацию. Ключевыми проектами для технических специалистов МТС являются: замена оборудования на более современное (А1), строительство новых и увеличение пропускной способности действующих базовых станций (А2), а также расширение Ethernet-сети (А3). Каждый проект подразумевает увеличение издержек предприятия. Для выполнения ремонтных работ необходимо пригласить бригаду специалистов. От работы бригады в значительной степени зависит качество и время на модернизацию компании: она может быть выполнена с запозданием (В1), в срок (В2) или со значительным опережением (В3). Таким образом, возникает ситуация, в которой необходимо принять решение в условиях неопределенности. Такая ситуация называется игрой с природой, где в качестве игрока А выступает компания МТС, а в качестве «природы» — ремонтная бригада. Проанализировав все Издержки ремонтных работ, эксперты получили следующую матрицу затрат (коэффициенты матрицы отрицательные, так как характеризуют затраты, то есть проигрыш игрока А): Таблица 3.1 — Матрица затрат B1B2B3А1-6-9-4А2-10-6-2А3-1-2-8 Матрица A не имеет доминирующих стратегий, следовательно, упростить ее нельзя. Также игра не имеет седловой точки, так как α=-8, β=-2. теперь для принятия решения о выборе оптимальной стратегии необходимо рассчитать несколько критериев. .Критерий Лапласа:(A1) =-(6+9+4)/3=-19/3=-6,33; K(A2) =-(10+6+2)/3=-18/3=-6; K(A3) =-(1+2+8)/3=11/3=-3,67. лучшая стратегия по этому критерию — А3. .Критерий Вальда:(A1)=-9, K(A2)=-10, K(A3)=-8. лучшая стратегия по этому критерию — А3. .Критерий Гурвица с показателями 0,3 и 0,8, то есть рассматривается один из худших вариантов стечения обстоятельств и один из лучших. ·Если α=0,8 — высокая степень оптимизма:(A1) = 0,8*(-4) + 0,2*(-9) = -5;(A2) = 0,8*(-2) + 0,2*(-10) = -3,6;(A3) = 0,8*(-1) + 0,2*(-8) = -2,4. лучшая стратегия по этому критерию — А3. ·Если α=0,3 — низкая степень оптимизма:(A1) = 0,3*(-4) + 0,7*(-9) = -7,5;(A2) = 0,3*(-2) + 0,7*(-10) = -7,6;(A3) = 0,3*(-1) + 0,7*(-8) = -5,9. лучшая стратегия по этому критерию — А3. .Критерий Сэвиджа: Матрица рисков будет выглядеть следующим образом: Таблица 3.2 — Матрица рисков B1B2B3А1572А2940А3006 теперь необходимо использовать критерий минимакса. Максимальные значения по строкам равны: (A1) =7, K(A2) =9, K(A3)=6. лучшая стратегия по этому критерию — А3. Таким образом, анализируя каждый критерий, оптимальной стратегией является А3, то есть компания МТС должна расширить Ethernet-сети. Применив эту стратегию, компания сможет минимизировать свои издержки до 3,27 миллиардов белорусских рублей и увеличить количество пользователей на 1%. теперь рассмотрим стратегию роста компании «Велком». Для того, чтобы сохранить свою долю на рынке или допустить ее минимальное уменьшение, компания приняла решение об использовании эффективных средств стимулирования продаж. Компания рассматривает три варианта решения этой задачи: реклама о новых услугах на телевидении, в интернете, в газетах (А1), промо-акции, позволяющие подробнее ознакомится клиентам с новыми услугами (А2), проведение различных конкурсов (А3). При реализации услуг компания будет получать Прибыль, которая зависит от интенсивности спроса потребителя: отсутствие спроса (В1), мгновенный спрос (В2), Спрос через определенное время (В3). Анализируя различные состояния спроса, экспертами компании была составлена матрица прибыли, коэффициенты которой отражают Прибыль от предоставления новых услуг за вычетом всех расходов на мероприятия, по стимулированию продаж: B1B2B3А1258А27610А312108 Получаем игру с платежной матрицей
Необходимо найти нижнюю и верхнюю цены игры:
следовательно, игра не имеет седловой точки, значит нужно найти решение игры в смешанных стратегиях. В этой матрице первую строку можно отбросить как невыгодную, так как ее элементы меньше соответствующих элементов второй строки. Матрица примет вид
Элементы первого столбца больше соответствующих элементов второго столбца, поэтому его можно также отбросить. Игра значительно упростилась:
По формуле (2.1.7) находим:
следовательно, смешанная стратегия компании PA = (0; 0,33; 0,67). Далее нужно найти смешанную стратегию для игрока В. По формуле (2.1.8) находим:
таким образом, смешанная стратегия потребителя QВ = (0; 0,33; 0,67). Также эту задачу можно решить с помощью линейной оптимизации. Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов совпадала с платежной матрицей С, а коэффициенты при неизвестных в целевой функции и свободные члены неравенств были бы равны единице. Эту задачу лучше решать на максимум, так как предприятие старается максимизировать свою Прибыль. Задача будет иметь вид: Таблица 3.4 — Условия задач исходная задачаДвойственная задача Чтобы решить эту задачу, можно воспользоваться программным продуктом Microsoft Office Excel. исходные данные изображены на рисунке 3.1.
Рисунок 3.1 — Сетка для решения задачи В ячейках В2:С3 расположена платежная матрица, в ячейках В4:С4 — максимальные элементы по столбцам, в D2:D3 — минимальные элементы по строкам. В ячейках Е2:Е3 и В5:С6 будут находится вероятности использования стратегий игрока А и В соответственно. неизвестные Xj и Ui будут располагаться в ячейках В11:С11 и G2:G3. Целевая функция для первого игрока — Е11, для второго — Е12, цена игры — ячейка Е13. Для начала необходимо найти ограничения. В ячейку J1 записывается =СУММПРОИЗВ(B2:B3;G2:G3), в ячейку С13 записывается формула =СУММПРОИЗВ(B2:C2;B11:C11). То есть необходимые элементы матрицы перемножаются с необходимыми неизвестными переменными. В ячейки для нахождения целевых функций записываются формулы суммы переменных. Для нахождения целевой функции игрока А используется инструмент Поиск решений (Данные — Поиск решений). параметры поиска решений:
Рисунок 3.2 — Параметры поиска решений Аналогичным способом находится целевая функция игрока В, поменяв некоторые параметры. В результате получаем f(max)=f(min)=0,1; Xj=(0,04;0,08); Ui=(0,04;0,08). цена игры находится по формуле (2.3.10) — v=8,667. Вероятности использования чистых стратегий каждым игроком находятся по формуле (2.3.10) и равны Qj= (0,33; 0,67), Pi= (0,33; 0,67). Из полученных результатов следует вывод, что компания «Велком» не должна расходовать средства на рекламу в данной задаче, 33% денежных средств необходимы для проведения промо-акций, и 67% — на проведение различных конкурсов с розыгрышами призов, которые привлекут внимание новых клиентов. Такая тактика обеспечит компании средний выигрыш, равный 8,667 миллиардов белорусских рублей независимо от спроса. Подводя итоги работы, можно сделать вывод, что два конкурирующих оператора сотовой связи МТС и «Велком» в ходе своих мероприятий по увеличению числа пользователей изменят свои доли на рынке на 1%. Причем МТС увеличит долю с помощью мобилизации компании (а именно расширение Ethernet-сети), а «Велком» минимально уменьшит долю рынка с помощью стимулирования продаж, которое включает проведение промо-акций и конкурсов. ЗАКЛЮЧЕНИЕ В заключение следует особо подчеркнуть, что теория игр является очень сложной областью знания. При обращении к ней надо соблюдать известную осторожность и четко знать границы применения. Слишком простые толкования, принимаемые фирмой самостоятельно или с помощью консультантов, таят в себе скрытую опасность. Анализ и консультации на основе теории игр из-за их сложности рекомендуются лишь для особо важных проблемных областей. С помощью теории игр предприятие получает возможность предусмотреть ходы своих партнеров и конкурентов. Опыт фирм показывает, что использование соответствующего инструментария предпочтительно при принятии однократных, принципиально важных плановых стратегических решений. В данной работе были изучены ключевые моменты теории игр, классификация игр по различным критериям. Игра — это действительный или формальный конфликт, в котором имеется, по крайней мере, два участника (игрока), каждый из которых стремится к достижению собственных целей. каждая игра имеет определенное количество игроков, ходов, стратегий. Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Теория игр, имеющая в запасе арсенал методов решения матричных игр, позволяет эффективно решать сложные задачи несколькими методами и из их множества выбрать наиболее эффективные, а также упрощать исходные матрицы игр. Также были разобраны решения основных и наиболее популярных типов игр. Это матричные игры с чистыми стратегиями, со смешанными стратегиями, игры с природой, причем решение игры можно найти не только аналитическим методом, но и с помощью графиков. Также каждую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования. Все полученные знания были применены для решения практических задач и нахождения оптимальных стратегий в различных конфликтных ситуациях. Таким образом, все задачи, поставленные в начале работы выполнены, а цель достигнута. список ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1.Берж К. Общая теория игр нескольких лиц. — М.: Физматгиз, 1961. — 126 с. 2.Василевич Л.Ф. Теория игр: Учебное пособие. — М.: КИИМ, 2000 — 147 с. .Васин А. А. Теория игр и модели математической экономики — М. : МАКС Пресс, 2005. — 272 с. .Вентцель Е.С. Элементы теории игр. — М.: Физматгиз, 1961. — 67 с. 5.Воробьев Н.Н, Теория игр для экономистов-кибернетиков. — М.: Наука, 1985. — 272 с. 6.Гермейер Ю.Б. Игры с непротивоположными интересами. — М.: Наука, 1976. — 327 с. 7.Данилов Н.Н. Игровые модели принятия решения. — Кемерово: КемГУ, 1981. — 122 с. .Данилов Н.Н. Теоретико-игровое моделирование конфликтных ситуаций. — Томск: Изд-во ТГУ, 2005. — 445 с. .Карлин С. Математические методы в теории игр, программирования и экономике. — М.: мир, 1964. — 838 с. .Колесник Г. В. Теория игр. — 3-е изд. — М. : Либроком, 2012. — 152 с. .Костевич Л.С., Лапко А.А, Теория игр. исследование операций. — Минск: Вышэйшая школа, 1982. 229 с. .Кремер Н.Ш. Теория вероятностей и математическая статистика. Учебник. — М.: ЮНИТИ-ДАНА, 2001. .Лабскер Л. Г. Теория игр в экономике (практикум с решениями задач) — М. : КноРус, 2012. — 264 с. .Мак-Кинси Д. Введение в теорию игр. — М.: Физматгиз, 1960. — 420 с. 15.Мулен Э. Кооперативное принятие решений: аксиомы и модели. — М.: Мир, 1991. .Оуэн Г. Теория игр. — М.: Вузовская книга, 2004. 17.Печерский С. Л. Теория игр для экономистов. Вводный курс. — СПб. : Изд-во европейского университета, 2001. — 342 с. .Протасов И.Д. Теория игр и исследование операций. Учебное пособие. — М.: Гелиос АРВ, 2006. .Тернер Д. вероятность, статистика, исследование операций: Пер. с англ. — М.: Высш.шк., 1971. .Центр электронного бизнеса TUT.BY [Электронный ресурс] / ООО «тут БАЙ МЕДИА». — Минск, 2000. — Режим доступа : HTTP://42.tut.by/. — Дата доступа : 26.11.2014.
Учебная работа. Изучение игровых моделей и их применение в практике принятия решений