МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
Северо-Казахстанский государственный университет им. М. Козыбаева
Факультет Информационных Технологий
Кафедра Информационные Системы
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
«Применение алгоритмов теории игр в экономических системах»
050703.DO.ИС-06-2
автор: Дьяченко О.Г.
______________
(фамилия, инициалы) (подпись, дата)
РУКОВОДИТЕЛЬ: к. т. н., доцент
__________
(степень, звание) (подпись, дата)
Лаптева Е.В.
(фамилия, инициалы)
Петропавловск, 2008
СОДЕРЖАНИЕ
СОДЕРЖАНИЕ. 3
ВВЕДЕНИЕ. 4
1АНАЛИТИЧЕСКАЯ ЧАСТЬ. 7
1.1Теория игр: определение, предмет, цели и задачи, применение. 7
1.2Основные понятия, используемые в теории игр. 11
1.3Классификация игр. 12
1.4Представление игр. 15
1.5Матричные игры. Игры с нулевой суммой. Решение матричных игр в чистых стратегиях17
1.6Игры в смешанных стратегиях. 21
1.6.1Уменьшение порядка платёжной матрицы.. 21
1.6.2Понятие о матричных играх со смешанным расширением. 22
1.6.3Геометрический метод решения игр. 26
1.7Понятие о статистических играх. 27
1.7.1Критерий максимального математического ожидания выигрыша. 28
1.7.2Критерий недостаточного основания Лапласа. 29
1.7.3Максиминный критерий Вальда. 30
1.7.4Критерий минимаксного риска Сэвиджа. 31
1.7.5Критерий пессимизма-оптимизма Гурвица. 31
1.7.6Критерий Ходжа-Лемана. 32
2ПРОЕКТНАЯ ЧАСТЬ. 34
2.1Пример 1. Решение матричной игры в чистых стратегиях. 34
2.2Пример 2. Решение матричной игры со смешанным расширением. 39
2.3Пример 3. Решение статистической игры.. 44
ЗАКЛЮЧЕНИЕ. 49
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 50
ВВЕДЕНИЕ
Игры разума рождают прибыль.
Теория, которая грозит стать практикой.
Теория игр в современной экономике больше, чем просто теория. Она может привести к вполне практической прибыли, надо только знать, как ее применить. Несмотря на то, что сейчас теорию игр в той или иной мере преподают на большинстве экономических факультетов, управленцы-практики предпочитают работать так, будто ее не существует. Математики уверены: менеджеры не понимают, от какого мощного инструмента отказываются.
Вся экономика - это процесс принятия решений в условиях неопределенности. Теория игр, занимающаяся моделированием этого процесса, может служить источником для принятия решений отдельных компаний, повышать их стабильность и благосостояние. Она может быть положена в основу формирования межфирменных союзов, может спрогнозировать последствия соответствующих решений. Один из выводов теории игр в том, что прибыль в экономике в большей степени определяется не количеством ресурсов, а системой правил и контрактными соглашениями между экономическими контрагентами [1].
Роберт Ауманн, лауреат Нобелевской премии по экономике (2005 г.), вспоминает: «Я заинтересовался теорией игр потому, что она имеет большое практическое значение. Я понял, насколько важными могут быть исследования в этой области для бизнеса».
В 1990-х гг. правительство США устраивало аукцион на право использования частот для операторов мобильной связи. Планируемая выручка от аукциона составляла $4,5 млрд, однако с помощью привлечения специалистов в области теории игр реальная выручка составила почти $45 млрд, то есть в 10 раз больше.
Еще один пример, актуальный для многих компаний, - работа с профсоюзами. Однажды в университете, где работал Ауман, началась забастовка преподавателей. Руководство долго не хотело принимать требования забастовщиков, и учебный процесс был парализован на 2 месяца. По истечении этого срока преподаватели собрались и устроили голосование: продолжать забастовку или прекратить ее. Большинство высказалось за продолжение борьбы. Как только результаты голосования стали известны руководству, они сразу приняли решение выполнить все выдвигаемые требования. В результате двухмесячного простоя университет потерял большие деньги. Этого можно было избежать, если бы руководство сразу пошло на уступки. Почему они этого не сделали? Потому что у них не было информации о том, насколько сильна решимость преподавателей настаивать на своем. Как только такая информация появилась, решение было принято.
Несмотря на все преимущества, вопрос применения теории игр, например в российских компаниях, пока остается открытым. Слишком формализованный процесс «игры» создает определенные трудности.
"Теория игр довольно сложна: она включает в себя постулаты, теоремы, графы, интегралы, - говорит Валерий Павлов [1], - Применение ее весьма трудоемко: необходимо разработать и формализовать модель игры, множество параметров необходимо выявить, отсеять и учесть. Из-за трудоемкости применения теории игр процесс "игры" возможен, если затраты на ее создание минимальны: кто-то формализовал игру до игры (компьютеризировал) или игра протекает как общение между людьми.
Результат игры спорен: множество процессов, параметров и факторов остаются неучтенными, поэтому и результат остается как один из возможных".
Того же мнения придерживается и Иван Лимбах [1]: «Теория игр, безусловно, полезная для осмысления математическая модель. Однако напрямую оценивать актуальность ее практического применения в сегодняшней практике сложно. В первую очередь необходимы четкие методики для каждой сферы, в которой данная модель будет применяться.
Будучи правильно осмысленной, теория игр может быть использована в различных областях деятельности.
Практическое использование теории игр может помочь в решении психологических проблем между сотрудниками организации».
Роберт Ауманн получил Нобелевскую премию по экономике за то, что в течение долгих лет доказывал: теория игр - это не просто любопытные задачки, а инструмент моделирования экономических процессов.
Актуальность: теорию игр можно применять для решения ряда экономических задач. Эти задачи могут быть решены очень быстро с помощью заранее выработанных алгоритмов. Сейчас моментальное решение неожиданно возникающих проблем очень существенно, так как конкуренция растет с каждым днем все больше и больше. К тому же с помощью теории игр можно выработать такую оптимальную стратегию, при которой система не будет существенно изменяться под управлением каких-то внешних воздействий, да и потери будут не столь существенными.
Цель курсового проекта: определить круг задач, возникающих в экономических системах, которые можно решить с помощью теории игр.
Задачи проекта:
1. Ознакомление с теорией игр;
2. Постановка задачи с позиции теории игр;
3. Исследование методов теории игр;
4. Обзор программных средств для решения задач теорией игр;
5. Решение задач методами теории игр в примерах.
1 АНАЛИТИЧЕСКАЯ ЧАСТЬ
1.1 Теория игр: определение, предмет, цели и задачи, применение
Разумная человеческая деятельность в большинстве случаев состоит в том, что человеку для достижения тех или иных целей приходится принимать решения. При этом представляется вполне естественным стремление принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. Научные постановки вопроса о выборе оптимальных решений встречались и встречаются в различных теоретических и прикладных дисциплинах — медицине, праве, военном деле, экономике, технике и т. д.. По мере развития и математизации этих дисциплин соответствующие процессы принятия решений формализуются и приобретают характер математических моделей. Теория математических моделей принятия оптимальных решений составляет ныне обширную отрасль науки, называемую исследованием операций.
Особое место среди условий, в которых приходится принимать решения, занимают условия конфликта. Это особое положение определяется, во-первых, практической важностью, которую имеют конфликты в жизни и развитии общества, и, во-вторых, специфической сложностью конфликта как явления, в связи с которым приходится принимать решение. Дело в том, что в условиях конфликта принимающему решения субъекту приходится считаться не только со своими собственными целями, но также с теми целями, которые ставят перед собой его партнеры. Помимо этого, он должен учитывать, кроме объективных, известных ему обстоятельств конфликта, еще и те решения, которые принимают его противники и которые ему самому, вообще говоря, неизвестны. Из сказанного вытекает, что раздел исследования операций, занимающийся теорией математических моделей принятия оптимальных решений в условиях конфликтов, является весьма специфическим и весьма сложным. Этим разделом является теория игр.
Поскольку теория игр есть теория моделей принятия решений, она не занимается этими решениями как психологическими, волевыми актами; не занимается она и вопросами их фактической реализации. В рамках теории игр принимаемые решения выступают как достаточно упрощенные и идеализированные схемы реальных явлений. При этом, разумеется, степень этого упрощения не должна превосходить известных пределов, за которыми модель уже утрачивает существенные черты явления.
Далее, теория игр есть теория математических моделей; она является разделом математики. Это значит, что конструируемые в ней модели являются формальными, знаковыми (а не макетными или аналоговыми) моделями и их формирование и средства их анализа также формальны [2].
Определения понятия теории игр:
· специальный раздел математики, который был разработан для изучения процесса принятия решений в сложных обстоятельствах;
· раздел математики, изучающий формальные модели принятия оптимальных решений в условиях конфликта;
· математический метод изучения оптимальных стратегий в играх;
· термин представляет собой русский эквивалент английского theory of games
и используется для обозначения комплекса математич. моделей конфликтных ситуаций и способов их разрешения;
· серьезное и результативное исследование способов распространения концепции операционального поведения на ситуации, в которых присутствуют и борьба, и выторговывание, и просчет поведения конкурентов.
В теории игр рассматриваются такие ситуации, когда имеются два участника выполнения операции, каждый из которых преследует противоположные цели. В качестве участников могут выступать коллективы, конкурирующие предприятия и т. д. Во всех случаях предполагается, что операция проводится против разумного противника (конкурента), преследующего свои собственные цели и сознательно противодействующего достижению цели другим участником [3].
Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.
Она пытается предсказать результат на основе интерактивных моделей, в которых решения каждой стороны влияют на решения других сторон. Смысл «игры» здесь является следующим: действие со стороны одного игрока приводит к действиям со стороны других.
В условиях конфликта стремление противника скрыть свои предстоящие действия порождает неопределённость. Наоборот, неопределённость при принятии решений (например, на основе недостаточных данных) можно интерпретировать как конфликт принимающего решения субъекта с природой. Поэтому теория игр рассматривается также как теория принятия оптимальных решений в условиях неопределённости. Она позволяет математизировать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии. Перспективен подход с позиций теории игр к проблемам управления, планирования и прогнозирования [4].
Предметом теории игр
являются такие ситуации, в которых важную роль играют конфликты и совместные действия. Типичными примерами подобных ситуаций могут служить планирование боевых операций противоборствующих армий и рекламирование конкурирующих товаров.
Цель теории игр
- выработка рекомендаций для различного поведения игроков в конфликтной ситуации, то есть выбор оптимальной стратегии для каждого из них.
Задачу теории игр
можно сформулировать так: как должен вести себя (какую стратегию применять) разумный игрок в конфликте с разумным противником (или противниками), чтобы обеспечить себе в среднем наибольший возможный выигрыш [5].
Идея теории игр исторически относится к работам Талмуд (Talmmud) и Сун Цзы (Sun Tzu). Однако, современная кодификация приписывается Джону фон Нейману (John von Neumann) и Оскару Моргенштерну (Oskar Morgenstern John). Они опубликовали Theory of Games and Economic Behavior (Теория игр и экономическое поведение) в 1944. В начале 1950-ых годов, Джон Нэш (John Nash) обобщил их результаты и подвел основу современной области теории игр (Game Theory [6].
Теория игр нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгуо судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума». (Таким образом, теория игр — одна из немногих областей математики, за достижения в которой можно получить нобелевскую премию.) Некоторые американские телевизионные шоу периодически ссылаются на теорию в своих эпизодах.
Нематематический вариант теории игр представлен в работах Томаса Шеллинга, нобелевского лауреата по экономике 2005 г..
Нобелевскими лауреатами по экономике за достижения в области теории игр стали: Роберт Ауманн, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Томас Шеллинг [7].
В ходе своего развития теория игр переросла эти рамки и превратилась в общую математическую теорию конфликтов. В рамках теории игр в принципе поддаются математическому описанию военные и правовые конфликты, спортивные состязания, «салонные» игры, а также явления, связанные с биологической борьбой за существование.
Применение теории игр:
· Подготовка деловых переговоров;
· Анализ будущих условий на рынке;
· Стратегический процесс принятия решений;
· Оценка жизнеспособности новых рискованных начинаний, бизнес модели, программы, проекта, продукта, услуги или технологии.
Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики [8].
1.2 Основные понятия, используемые в теории игр
Основным в теории игр является понятие игры, являющееся формализованным представлением о конфликте. Точное описание конфликта в виде игры состоит поэтому в указании того, кто и как участвует в конфликте, каковы возможные исходы конфликта, а также кто и в какой форме заинтересован в этих исходах [9].
· Игра
представляет собой совокупность известных всем игрокам правил, которые определяют, что может делать игрок и каковы последствия и выигрыши в результате каждого отдельного их действия;
· Игра
- это идеализированная математическая модель коллективного поведения: несколько игроков влияют на исход игры, причем их интересы различны [10].
Лица, принимающие решения, называются игроками
(деловые партнеры, фирмы, страны), а целевая функция — платежной функцией
. В теории игр рассматриваются задачи принятия решений с несколькими участниками. Выигрыш каждого игрока и определяется этой платежной функцией.
Ход
- это момент игры, когда игроки должны произвести выбор одного из возможных вариантов.
Периоды, в течение которых игроки делают свои ходы, называются этапами игры. Выбранные на каждом этапе ходы в конечном счете определяют “платежи” (выигрыш или убыток) каждого игрока, которые могут выражаться в материальных ценностях или деньгах. Партией игры
называется некоторая определенная совокупность ходов и выборов совершающихся для достижения цели игры. Существенной чертой любой игры
является то, что выигрыш каждого игрока зависит обычно не только от сделанного им самим выбора, но и от выбора других игроков.
Еще одним основным понятием данной теории является стратегия игрока
. Под ней понимаются возможные действия, позволяющие игроку на каждом этапе игры выбирать из определенного количества альтернативных вариантов такой ход, который представляется ему “лучшим ответом” на действия других игроков. Относительно концепции стратегии следует заметить, что игрок определяет свои действия не только для этапов, которых фактически достигла конкретная игра, но и для всех ситуаций, включая и те, которые могут и не возникнуть в ходе данной игры. То есть, стратегия
- это набор правил, формулируемых до игры, которые определяют выбор варианта в любой из могущих возникнуть ситуаций. Наилучшие стратегии для каждого из игроков называют решением игры.
Результат игры, на который рассчитывают оба игрока называют ценой игры
- победа или поражение, которые не всегда имеют количественное выражение, можно выразить (условно) числами (например, в шахматах: 1, 0, 1
/2
)
[11].
1.3 Классификация игр
Различные виды игр можно классифицировать, основываясь на том или ином принципе: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д.
В зависимости от количества игроков различают игры двух и n игроков
. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения.
По количеству стратегий игры делятся на конечные и бесконечные
. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий, игра называется бесконечной.
По характеру взаимодействия игры делятся на бескоалиционные
: игроки не имеют права вступать в соглашения, образовывать коалиции; коалиционные
(кооперативные) – могут вступать в коалиции и принимают взаимообязывающие соглашения о своих стратегиях. Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.
По характеру выигрышей игры делятся на: игры с нулевой суммой и игры с постоянной разностью.
Игры с нулевой суммой
- общий капитал всех игроков не меняется, а перераспределяется между игроками. В игре с нулевой суммой и двумя участниками выигрыш одного из них равен проигрышу другого. Таким образом, в играх с нулевой суммой существует конфликт между игроками, и поэтому их называют также антагонистическими играми.
Они отражают суть принципа: «мой проигрыш - ваш выигрыш мой выигрыш - ваш проигрыш» и представляют собой ситуации чистого конфликта без всяких элементов сотрудничества. Примерами таких игр может служить покер, где один выигрывает все ставки других; либо банальное воровство
.
Игры с постоянной разностью
, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща. Игрой с отличной от нуля суммой является торговля
, где каждый участник извлекает выгоду. Сюда также относятся го, шашки и шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война
.
По виду функций выигрыша игры делятся на: матричные, биматричные.
Матричная игра
– это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования.
Биматричная игра
– это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец – стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице – выигрыш игрока 2.) [12].
Также существуют следующие типы игр:
· Симметричные и несимметричные
Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные. В частности, таковой является: «Дилемма заключённого». В качестве несимметричных игр можно привести «Ультиматум».
· Параллельные и последовательные
В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все
не сделают свой ход. В последовательных, или динамических
, играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Эта информация может быть даже не совсем полной
, например, игрок может узнать, что его противник из десяти своих стратегий точно не выбрал
пятую, ничего не узнав о других.
· С полной или неполной информацией
Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игр — с неполной информацией. Например, вся «соль» «Дилеммы заключённого»
или «Сравнения монеток
» заключается в их неполноте.
В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки и другие.
Часто понятие полной информации путают с похожим — совершенной информации
. Для последнего достаточно лишь знание всех доступных противникам стратегий, знание всех их ходов необязательно [13].
1.4 Представление игр
Представить игру можно двумя следующими способами:
Первый способ
предполагает следующее:
1) перечисление ходов, которые могут делать игроки;
2) определение информации, которой располагают игроки в процессе игры;
3) определение возможных вариантов действий игроков;
Игра «Ультиматум» в экстенсивной форме.
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной
.
На рисунке 1. 1 — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии
); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
Рисунок 1.1 -
Представление игр в экстенсивной форме
4) указание предельных размеров платежей в конце игры.
Игру, описанную подобным образом, называют игрой
в развернутой,
или экстенсивной форме,
а само описание, как правило, составляют в виде дерева игры,
аналогичного дереву решений.
Игры в развернутой форме называют также позиционными играми.
Игру в развернутой форме называют игрой с полной информацией,
если в ней нельзя делать одновременно несколько ходов и если участникам известны выборы, сделанные при предшествующих ходах, включая и случайные ходы. Примером игры с полной информацией являются шахматы. Покер представляет собой игру с неполной информацией,
так как игрокам неизвестно, какие карты находятся на руках у противника [12].
Второй способ
описания игры состоит в том, что рассматриваются все возможные стратегии каждого игрока и определяются платежи, соответствующие любой возможной комбинации стратегий всех игроков. Описанная таким образом игра называется игрой в нормальной форме
.
Нормальная форма игры двух участников состоит из платежной матрицы
, показывающей, какую сумму получает каждый из игроков при любой из возможных стратегий (см. рисунок 1.2).
Элементами этой матрицы являются пары чисел, первое из которых определяет величину выигрыша игрока 1, а второе — игрока 2.
Рисунок 1.2 - Платежная матрица для игры двух участников
Игрок 1 выбирает одну из m стратегий A1,
A2
,…,Am
. Игрок 2 выбирает одну из n стратегий B1
, B2
,…,Bn
. Пара чисел на пересечении строки и столбца, которые соответствуют стратегиям, избранным игроками, показывает величину выигрыша каждого из них. Если игрок 1 выбирает Ai
, а игрок 2 -Bj
, то выигрыши игроков 1 и 2 равны соответственно aij
и bij
(i=1,..,m; j=1,..,n).
Платежная матрица имеет размерность m×n, где m — (конечное) число возможных стратегий игрока 1, а n — (конечное) число возможных стратегий игрока 2. Предполагается, что каждому из игроков известны все элементы платежной матрицы [14].
1.5 Матричные игры.
Игры с нулевой суммой. Решение матричных игр в чистых стратегиях
Матричные игры — игры, в которых участвуют два игрока (1 и 2) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий.
Игра называется игрой с нулевой суммой
, если одна сторона выигрывает то, что проигрывает другая, т. е. сумма выигрышей 1 и 2 равна нулю. В жизни часто встречаются конфликты, в которых это условие не выполняется. Например, в военном столкновении вполне возможно, что проигрывают обе стороны. Однако во многих случаях можно, не слишком искажая сущность явления, рассматривать парные конфликты как игры с нулевой суммой.
Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i = 1,2,...,m , второй имеет n
стратегий j = 1,2,...,n .
Каждой паре стратегий (i ,
j) поставлено в соответствие число аij
,
выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i -
ю стратегию, а 2 – свою j -ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i -ю стратегию, 2 – свою j -ю стратегию , после чего игрок 1 получает выигрыш а
ij
за счёт игрока 2 (если а
ij
<
0, то это значит, что игрок 1 платит второму сумму | аij
| ). На этом игра заканчивается.
Каждая стратегия игрока i =; j = часто называется чистой стратегией.
Если рассмотреть матрицу
,
то проведение каждой партии матричной игры с матрицей А
сводится к выбору игроком 1 i-й строки, а игроком 2 j -го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij
.
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А
следующим образом: для каждого значения i (i =), определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2 (), т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i -ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо
, при которой этот минимальный выигрыш будет максимальным, т.е. находится
. (1)
Число α, определённое по формуле (1) называется нижней чистой ценой
игры
и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.
Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается ,
т.е. определяется максимальный выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1
стратегию, при которой игрок 1 получит минимальный выигрыш, т.е. находит
. (2)
Число β, определяемое по формуле (2), называется чистой верхней ценой
игры
и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше α, а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем β.
Если в игре с матрицей А , то говорят, что эта игра имеет седловую
точку
в чистых стратегиях и чистую цену
игры .
Седловая точка
– это пара чистых стратегий (iо
,jо
)
соответственно игроков 1 и 2, при которых достигается равенство . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:
. (3)
Таким образом, исходя из (3), седловой элемент ai
0
j
0
является минимальным в iо
-й строке и максимальным в jо
-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо
,jо
)
игроков 1 и 2, образующая седловую точку и седловой элементai
0
j
0
, называется решением игры
. При этом iо
и jо
называются оптимальными чистыми
стратегиями
соответственно игроков 1 и 2 [15].
Пример
Рисунок 1.3 – Пример решения матричных игр в чистых стратегиях.
Седловой точкой является пара (iо
= 3; jо
= 1), при которой g = α = β = 2.
Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 = α = β, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца [16].
1.6 Игры в смешанных стратегиях
1.6.1 Уменьшение порядка платёжной матрицы
Порядок платёжной матрицы (количество строк и столбцов) может быть уменьшен за счёт исключения доминируемых и дублирующих стратегий.
Стратегия K* называется доминируемой
стратегией K**, если при любом варианте поведения противодействующего игрока выполняется соотношение Ak
*
< Ak
**
, где Ak
*
и Ak
**
- значения выигрышей при выборе игроком, соответственно, стратегий K* и K**.
В случае, если выполняется соотношение Ak
*
= Ak
**
, стратегия K* называется дублирующей по отношению к стратегии K**.
Например, в матрице (см. таблицу 1).
Таблица 1
Платёжная матрица с доминируемыми и дублирующими стратегиями
| B1 | B2 | B3 | B4 | B5 | B6 | |
| A1 | 1 | 2 | 3 | 4 | 4 | 7 |
| A2 | 7 | 6 | 5 | 4 | 4 | 8 |
| A3 | 1 | 8 | 2 | 3 | 3 | 6 |
| A4 | 8 | 1 | 3 | 2 | 2 | 5 |
Стратегия A1 является доминируемой по отношению к стратегии A2, стратегия B6 является доминируемой по отношению к стратегиям B3, B4 и B5, а стратегия B5 является дублирующей по отношению к стратегии B4. Данные стратегии не будут выбраны игроками, так как являются заведомо проигрышными и удаление этих стратегий из платёжной матрицы не повлияет на определение нижней и верхней цены игры, описанной данной матрицей.
Множество недоминируемых стратегий, полученных после уменьшения размерности платёжной матрицы, называется ещё множеством Парето [17].
1.6.2 Понятие о матричных играх со смешанным расширением
Исследование в матричных играх начинается с нахождения её чистой цены. Если матричная игра имеет решение в чистых стратегиях, то нахождением чистой цены заканчивается исследование игры. Если же в игре нет решения в чистых стратегиях, то можно найти нижнюю и верхнюю цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.
Смешанной стратегией
игрока называется полный набор чистых стратегий, применённых в соответствии с установленным распределением вероятностей. Матричная игра, решаемая с использованием смешанных стратегий, называется игрой со смешанным расширением.
Стратегии, применённые с вероятностью, отличной от нуля, называются активными стратегиями.
Доказано, что для всех игр со смешанным расширением существует оптимальная смешанная стратегия, значение выигрыша при выборе которой находится в интервале между нижней и верхней ценой игры
[9]:
.
При этом условии величина g называется ценой игры.
Кроме того, доказано, что, если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остаётся неизменным и равным цене игры v, независимо от того, каких стратегий придерживается другой игрок, если только он не выходит за пределы своих активных стратегий. Поэтому, для достижения наибольшего гарантированного выигрыша второму игроку также необходимо придерживаться своей оптимальной смешанной стратегии.
Игры, в которых выполняется строгое неравенство, называются не полностью определенными играми без седловой точки
.
Пример такой игры, для которой α = -2 < 4 =βприведен на рисунке 1.4.
Рисунок 1.4 -
Игра двух участников с нулевой суммой, не имеющая седловую точку
Расширим понятие стратегии за счет смешанных (или случайных) стратегий
. Смешанная стратегия представляет собой вероятностную комбинацию чистых стратегий, т.е. ряд чистых стратегий, взятых в случайном порядке с некоторыми вероятностями.
Смешанные стратегии игроков 1 и 2 можно указать с помощью вектора вероятностей:
В теории игр доказано, что любая парная конечная игра с нулевой суммой имеет, по крайней мере, одно решение в смешанных стратегиях. Таким образом, каждая конечная игра имеет цену - g - средний выигрыш, приходящийся на одну партию, удовлетворяющий условию:
Решить игру
– найти цену игры и оптимальные стратегии.
Игра mn, (где m³3, n³3) заданную платежной матрицей А:
Пусть платежная матрица не содержит седловой точки, т.е. игра решается в смешанных стратегиях: .
Применение игроком 1 оптимальной смешанной стратегии S1
*
гарантирует ему средний выигрыш не меньше цены игры g независимо от поведения игрока 2(gj
≥ g).
Игрок 2, применяя оптимальную смешанную стратегию S2
*
, гарантирует для себя минимальный проигрыш (gI
g).
Учитывая данное условие, задачу линейного программирования можно записать следующим образом:
1) для игрока 1:
(4)
2) для игрока 2:
(5)
Смысл этих систем уравнений заключается в следующем:
игрок 1 стремится увеличить цену игры (g→max), т.е. он действует так, чтобы его средний выигрыш при использовании его стратегии с вероятностями рi
для любой j-й стратегии игрока 2 был не меньше величины g, которую он стремится увеличить. Игрок 2 стремится уменьшить свой проигрыш (g→min), т.е. он действует так, чтобы его средний проигрыш при использовании его стратегий с вероятностями qj
при любой i-й стратегии игрока 1 не превышал величину g, которую он стремиться уменьшить.
Разделив левую и правую часть неравенств (4) и (5) на цену игры g > 0 и обозначив
(6)
получим уравнения (7) и (8) в следующем виде:
(7)
. (8)
Из равенств и выражений (6) следует, что переменные (xi
) и (yj
) удовлетворяют условиям: . Таким образом, цена игры определяется как: .
Оптимальные стратегии определяются как:
.
Теорема:
Применение оптимальной смешанной стратегии обеспечивает игроку максимальный средний выигрыш (или минимальный средний проигрыш), равный цене игры γ, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных (оптимальных смешанных) стратегий [15].
1.6.
Графический метод решения игр выполняется по шагам:
1) В системе координат XOY по оси абсцисс (ОХ) откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка Х=0) соответствует стратегии А1
, правый (точка Х=1) – стратегии А2
. Промежуточные точки Х соответствуют некоторым смешанным стратегиям S1
=(p1
, p2
).
2) По оси ординат (OY) откладываются выигрыши при стратегии А1
. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии А2
.
Пусть имеется игра с платежной матрицей: .
Если игрок 2 применяет стратегию В1
, то выигрыш игрока 1 при использовании чистых стратегий А1
и А2
составляет соответственно 0,4 и 0,6. Соединим эти точки прямой В1
В1
.
Ордината любой точки отрезка В1
В1
равна величине выигрыша игрока 1 при принятии им стратегии А1
и А2
с соответствующими вероятностями р1
и р2
.
Аналогично прямая В2
В2
соответствует стратегии игрока 2. Точка пересечения В1
В1
и В2
В2
определяет цену игры γ. Ординаты точек В2
В2
равны среднему стратегий А1
и А2
с вероятностями р1
и р2
.
Ломаная В1
NB2
– нижняя граница выигрыша, получаемая игроком 1. В точке N он максимален.
Таким образом, оптимальная стратегия первого игрока: S1
*
=(0,375; 0,625); цена игры (максимальный выигрыш) γ =55% [18].
Рисунок 1.5 – Графическая интерпретация решения игры
1.7
Понятие о статистических играх
Принятие управленческих решений предполагает наличие ситуаций выбора наиболее выгодного варианта поведения из нескольких имеющихся вариантов в условиях неопределённости. Такие задачи могут быть описаны матричными играми особого типа, в которых игрок взаимодействует не со вторым игроком, а с окружающей средой. Объективно окружающая среда не заинтересована в проигрыше игрока. В процессе принятия решения о выборе варианта поведения игрок имеет информацию о том, что окружающая среда может принять одно из нескольких возможных состояний и сталкивается с неопределённостью относительно того конкретного состояния, которое примет окружающая среда в данный момент времени.
Матричная игра, в которой игрок взаимодействует с окружающей средой, не заинтересованной в его проигрыше, и решает задачу определения наиболее выгодного варианта поведения с учётом неопределённости состояния окружающей среды, называется статистической игрой или «игрой с природой». Игрок в этой игре называется лицом, принимающим решение (ЛПР).
В общем виде платёжная матрица статистической игры приведена в таблице 2.
Таблица 2
Общий вид платёжной матрицы статистической игры
| S1 | S2 | … | Sn | |
| A1 | A11
|
A12
|
… | A1n
|
| A2 | A21
|
A22
|
… | A2n..
|
| … | … | … | … | … |
| An | Am1
|
Am2
|
… | Amn
|
В данной игре строки матрицы (Ai
) - стратегии ЛПР, а столбцы матрицы (Sj
) – состояния окружающей среды.
Критерии принятия решения
ЛПР определяет наиболее выгодную стратегию в зависимости от целевой установки, которую он реализует в процессе решения задачи. Результат решения задачи ЛПР определяет по одному из критериев принятия решения. Для того, чтобы прийти к однозначному и по возможности наиболее выгодному варианту решению, необходимо ввести оценочную (целевую) функцию. При этом каждой стратегии ЛПР (Ai
) приписывается некоторый результат Wi
, характеризующий все последствия этого решения. Из массива результатов принятия решений ЛПРвыбирает элемент W, который наилучшим образом отражает мотивацию его поведения [17].
1.7.1 Критерий максимального математического ожидания выигрыша
Критерий максимального математического ожидания выигрыша применяется в тех случаях, когда ЛПР известны вероятности состояний окружающей среды. Платёжная матрица дополняется столбцом, каждый элемент которого представляет собой значение математического ожидания выигрыша при выборе соответствующей стратегии ЛПР:
(9)
где pj
–вероятность j-го состояния окружающей среды.
Оптимальной по данному критерию
считается та стратегия ЛПР, при выборе которой значение математического ожидания выигрыша максимально: W = maxWi
Применение критерия максимального математического ожидания выигрыша, таким образом, оправдано, если ситуация, в которой принимается решение, следующая:
1. ЛПР известны вероятности всех состояний окружающей среды;
2. Минимизация риска проигрыша представляется ЛПР менее существенным фактором принятия решения, чем максимизация среднего выигрыша.
Необходимость иметь информацию о вероятностях состояний окружающей среды ограничивает область применения данного критерия.
1.7.2 Критерий недостаточного основания Лапласа
Данный критерий используется при наличии неполной информации о вероятностях состояний окружающей среды в задаче принятия решения. Вероятности состояний окружающей среды принимаются равными и по каждой стратегии ЛПР в платёжной матрице определяется, таким образом, среднее значение выигрыша:
. (10)
Оптимальной по данному критерию считается та стратегия ЛПР, при выборе которой значение среднего выигрыша максимально: W = maxWi
.
Использование данного критерия оправдано в следующей ситуации:
1. ЛПР не имеет информации, либо имеет неполную информацию о вероятностях состояний окружающей среды;
2. Вероятности состояний окружающей среды близки по своим значениям;
3. Минимизация риска проигрыша представляется ЛПР менее существенным фактором принятия решения, чем максимизация среднего выигрыша.
1.7.3 Максиминный критерий Вальда
Правило выбора решения в соответствии с максиминным критерием (ММ-критерием) можно интерпретировать следующим образом:
Платёжная матрица дополняется столбцом, каждый элемент которого представляет собой минимальное значение выигрыша в соответствующей стратегии ЛПР:
Wi
= minj
a
ij
. (11)
Оптимальной по данному критерию считается та стратегия ЛПР, при выборе которой минимальное значение выигрыша максимально: W = maxWi
.
Выбранная таким образом стратегия полностью исключает риск. Это означает, что принимающий решение не может столкнуться с худшим результатом, чем тот, на который он ориентируется.
Применение ММ-критерия оправдано, если ситуация, в которой принимается решение следующая:
1. О возможности появления состояний окружающей среды ничего не известно;
2. Решение реализуется только один раз;
3. Необходимо исключить какой бы то ни было риск.
1.7.4 Критерий минимаксного риска Сэвиджа
Величина (a
max
j
– a
ij
), где a
max
j
- максимальный элемент j – го столбца, может быть интерпретирована как дополнительный выигрыш, получаемый в условиях состояния окружающей среды Sj
при выборе ЛПР наиболее выгодной стратегии, по сравнению с выигрышем, получаемым ЛПР при выборе в тех же условиях любой другой стратегии. Эта же разность может быть интерпретирована как величина возможного проигрыша при выборе ЛПР I – й стратегии по сравнению с наиболее выгодной стратегией.
На основе данной интерпретации разности выигрышей производится определение наиболее выгодной стратегии по критерию минимаксного риска.
Для определения оптимальной стратегии по данному критерию на основе платёжной матрицы рассчитывается матрица рисков, каждый коэффициент которой (rij
) определяется по формуле: rij
= a
max
j
– a
ij
.
Матрица рисков дополняется столбцом, содержащим максимальные значения коэффициентов rij
по каждой из стратегий ЛПР: Ri
= maxj
rij
.
Оптимальной по данному критерию считается та стратегия, в которой значение Ri
минимально: W = minRi
.
Ситуация, в которой оправдано применение критерия Сэвиджа, аналогична ситуации ММ-критерия, однако наиболее существенным в данном случае является учёт степени воздействия фактора риска на величину выигрыша.
1.7.5 Критерий пессимизма-оптимизма Гурвица
В практике принятия решений ЛПР руководствуется не только критериями, связанными с крайним пессимизмом или учётом максимального риска. Стараясь занять наиболее уравновешенную позицию, ЛПР может ввести оценочный коэффициент, называемый коэффициентом пессимизма, который находится в интервале [0, 1] и отражает ситуацию, промежуточную между точкой зрения крайнего оптимизма и крайнего пессимизма. Данный коэффициент определяется на основе статистических исследований результатов принятия решений или личного опыта принятия решений в схожих ситуациях.
Платёжная матрица дополняется столбцом, коэффициенты которого рассчитываются по формуле:
Wi
= C×minj
a
ij
+ (1-C) ×maxj
a
ij
,
(12)
где C – коэффициент пессимизма.
Оптимальной по данному критерию считается стратегия, в которой значение Wi
максимально: W = maxWi
.
При С
=1 критерий Гурвица превращается в ММ-критерий. При С
= 0 он превращается в критерий “азартного игрока”, делающего ставку на то, что «выпадет» наилучший случай.
Критерий Гурвица применяется в ситуации, когда :
1. Информация о состояниях окружающей среды отсутствует или недостоверна;
2. Необходимо считаться с появлением каждого состояния окружающей среды;
3. Реализуется только малое количество решений;
4. Допускается некоторый риск.
1.7.6 Критерий Ходжа-Лемана
Этот критерий опирается одновременно на ММ-критерий и критерий максимального математического ожидания выигрыша. При определении оптимальной стратегии по этому критерию вводится параметр достоверности информации о распределении вероятностей состояний окружающей среды, значение которого находится в интервале [0, 1]. Если степень достоверности велика, то доминирует критерий максимального математического ожидания выигрыша, в противном случае – ММ-критерий
Платёжная матрица дополняется столбцом, коэффициенты которого определяются по формуле:
, (13)
где u – параметр достоверности информации о вероятностях состояний окружающей среды.
Оптимальной по данному критерию считается та стратегия, в которой значение Wi
максимально: W = maxWi
.
Данный критерий применим в следующем случае:
1. Имеется информация о вероятностях состояний окружающей среды, однако эта информация получена на основе относительно небольшого числа наблюдений и может измениться;
2. Принятое решение теоретически допускает бесконечно много реализаций;
3. При малом числе реализации допускается некоторый риск [17].
2 ПРОЕКТНАЯ ЧАСТЬ
Решать задачи теории игр можно в таких программных средах, как Tora, Per, Excel, LINDO61, LINGO8. Следующие рассматриваемые примеры будут частично решаться в средах MicrosoftExcel, Tora.
MSExcel удобен тем, что он установлен на любом компьютере, всем знаком и прост в применении. А программная система оптимизации Tora является самодостаточной системой в том смысле, что все инструкции и пояснения, необходимые для работы с этой программой, заключены в названиях пунктов меню, командных кнопок, опций и других элементов управления. Tora может работать только с разрешением экрана 800×600 или 1024×768 пикселей.
2.1 Пример 1. Решение
матричной игры в чистых стратегиях
Пример решения матричной игры в чистых стратегиях, в условиях реальной экономики, в ситуации борьбы двух предприятий за рынок продукции региона
Задание:
Два предприятия производят продукцию и поставляют её на рынок региона. Они являются единственными поставщиками продукции в регион, поэтому полностью определяют рынок данной продукции в регионе.
Каждое из предприятий имеет возможность производить продукцию с применением одной из трёх различных технологий.
В зависимости от качества продукции, произведённой по каждой технологии, предприятия могут установить цену единицы продукции на уровне 10, 6 и 2 денежных единиц соответственно.
При этом предприятия имеют различные затраты на производство единицы продукции (см. таблицу 3).
Таблица 3
Затраты на единицу продукции, произведенной на предприятиях региона (д.е.).
| Технология | Цена реализации единицы продукции, д.е. | Полная себестоимость единицы продукции, д.е. | |
| Предприятие 1 | Предприятие 2 | ||
| I | 10 | 5 | 8 |
| II | 6 | 3 | 4 |
| III | 2 | 1.5 | 1 |
В результате маркетингового исследования рынка продукции региона была определена функция спроса на продукцию: Y = 6 – 0.5.
Данные о спросе на продукцию в зависимости от цен реализации приведены в таблице 4.
Таблица 4
Спрос на продукцию в регионе, тыс. ед.
| Цена реализации 1 ед. продукции, д.е. | Средняя цена реализации 1 ед. продукции, д.е. | Спрос на продукцию, тыс. ед. | |
| Предприятие 1 | Предприятие 2 | ||
| 10 | 10 | 10 | 1 |
| 10 | 6 | 8 | 2 |
| 10 | 2 | 6 | 3 |
| 6 | 10 | 8 | 2 |
| 6 | 6 | 6 | 3 |
| 6 | 2 | 4 | 4 |
| 2 | 10 | 6 | 3 |
| 2 | 6 | 4 | 4 |
| 2 | 2 | 2 | 5 |
Значения Долей продукции предприятия 1, приобретенной населением, зависят от соотношения цен на продукцию предприятия 1 и предприятия 2. В результате маркетингового исследования эта зависимость установлена и значения вычислены (см. таблицу 5).
Таблица 5
Доля продукции предприятия 1, приобретаемой населением в зависимости от соотношения цен на продукцию
| Цена реализации 1 ед. продукции, д.е. | Доля продукции предприятия 1, купленной населением | |
| Предприятие 1 | Предприятие 2 | |
| 10 | 10 | 0,31 |
| 10 | 6 | 0,33 |
| 10 | 2 | 0,18 |
| 6 | 10 | 0,7 |
| 6 | 6 | 0,3 |
| 6 | 2 | 0,2 |
| 2 | 10 | 0,92 |
| 2 | 6 | 0,85 |
| 2 | 2 | 0,72 |
По условию задачи на рынке региона действует только 2 предприятия. Поэтому долю продукции второго предприятия, приобретённой населением, в зависимости от соотношения цен на продукцию можно определить как единица минус доля первого предприятия.
Стратегиями предприятий в данной задаче являются их решения относительно технологий производства продукции. Эти решения определяют себестоимость и цену реализации единицы продукции. В задаче необходимо определить:
1. Существует ли в данной задаче ситуация равновесия при выборе технологий производства продукции обоими предприятиями?
2. Существуют ли технологии, которые предприятия заведомо не будут выбирать вследствие невыгодности?
3. Сколько продукции будет реализовано в ситуации равновесия? Какое предприятие окажется в выигрышном положении?
Решение задачи
1. Определим экономический смысл коэффициентов выигрышей в платёжной матрице задачи. Каждое предприятие стремится к максимизации прибыли от производства продукции. Но кроме того, в данном случае предприятия ведут борьбу за рынок продукции в регионе. При этом выигрыш одного предприятия означает проигрыш другого. Такая задача может быть сведена к матричной игре с нулевой суммой. При этом коэффициентами выигрышей будут значения разницы прибыли предприятия 1 и предприятия 2 от производства продукции. В случае, если эта разница положительна, выигрывает предприятие 1, а в случае, если она отрицательна – предприятие 2.
2. Рассчитаем коэффициенты выигрышей платёжной матрицы. Для этого необходимо определить значения прибыли предприятия 1 и предприятия 2 от производства продукции. Прибыль предприятия в данной задаче зависит:
· от цены и себестоимости продукции;
· от количества продукции, приобретаемой населением региона;
· от доли продукции, приобретённой населением у предприятия.
Таким образом, значения разницы прибыли предприятий, соответствующие коэффициентам платёжной матрицы, необходимо определить по формуле (16):
D = p×(S×R1-S×C1) – (1-p) ×(S×R2-S×C2), (14),
где D – значение разницы прибыли от производства продукции предприятия 1 и предприятия 2;
p - доля продукции предприятия 1, приобретаемой населением региона;
S – количество продукции, приобретаемой населением региона;
R1 и R2 - цены реализации единицы продукции предприятиями 1 и 2;
C1 и C2 – полная себестоимость единицы продукции, произведённой на предприятиях 1 и 2.
Количество продукции, которое население региона приобретёт при средней цене 4 д.е., равно 4 тыс. ед. (см. таблицу 4). Доля продукции, которую население приобретёт у предприятия 1, составит 0,85, а у предприятия 2 – 0,15 (см. таблицу 5). Вычислим коэффициент платёжной матрицы a
32
по формуле (16):
a
32
= 0,85×(4×2-4×1,5) – 0,15×(4×6-4×4) = 0,5 тыс. ед.,
где i=3 – номер технологии первого предприятия, а j=2 – номер технологии второго предприятия.
Аналогично вычислим все коэффициенты платёжной матрицы. В платёжной матрице стратегии A1 – A3 – представляют собой решения о технологиях производства продукции предприятием 1, стратегии B1 – B3 – решения о технологиях производства продукции предприятием 2, коэффициенты выигрышей – разницу прибыли предприятия 1 и предприятия 2.
Таблица 6
Платёжная матрица в игре «Борьба двух предприятий за рынок продукции региона».
| B1 | B2 | B3 | Minj
|
|
| A1 | 0,17 | 0,62 | 0,24 | 0,17 |
| A2 | 3 | - 1,5 | - 0,8 | - 1,5 |
| A3 | 0,9 | 0,5 | 0,4 | 0,4 |
| Maxi
|
3 | 0,62 | 0,4 |
В данной матрице нет ни доминируемых, ни дублирующих стратегий. Это значит, что для обоих предприятий нет заведомо невыгодных технологий производства продукции. Определим минимальные элементы строк матрицы. Для предприятия 1 каждый из этих элементов имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Минимальные элементы матрицы по строкам имеют значения: 0,17, -1,5, 0,4.
Определим максимальные элементы столбцов матрицы. Для предприятия 2 каждый из этих элементов также имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Максимальные элементы матрицы по столбцам имеют значения: 3, 0,62, 0,4.
Нижняя цена игры в матрице равна 0,4. Верхняя цена игры также равна 0,4. Таким образом, нижняя и верхняя цена игры в матрице совпадают. Это значит, что имеется технология производства продукции, которая является оптимальной для обоих предприятий в условиях данной задачи. Эта технология III, которая соответствует стратегиям A3 предприятия 1 и B3 предприятия 2. Стратегии A3 и B3 – чистые оптимальные стратегии в данной задаче.
Значение разницы прибыли предприятия 1 и предприятия 2 при выборе чистой оптимальной стратегии положительно. Это означает, что предприятие 1 выиграет в данной игре. Выигрыш предприятия 1 составит 0,4 тыс. д.е. При этом на рынке будет реализовано 5 тыс. ед. продукции (реализация равна спросу на продукцию, таблица 4). Оба предприятия установят цену за единицу продукции в 2 д.е. При этом для первого предприятия полная себестоимость единицы продукции составит 1,5 д.е., а для второго – 1 д.е (см. таблицу 3). Предприятие 1 окажется в выигрыше лишь за счёт высокой доли продукции, которую приобретёт у него население.
2.2 Пример 2. Решение матричной игры со смешанным расширением
Пример решения матричной игры со смешанным расширением. Платёжную матрицу игры составим на основе исходных данных задачи, решённой при выполнении занятия 3, заменив лишь значения долей продукции предприятия 1, приобретаемой населением в зависимости от соотношений цен (см. таблицу 7).
Таблица 7
Доля продукции предприятия 1, приобретаемой населением в зависимости от соотношения цен на продукцию
| Цена реализации 1 ед. продукции, д.е. | Доля продукции предприятия 1, купленной населением | |
| Предп. 1 | Предп. 2 | |
| 10 | 10 | 0,31 |
| 10 | 6 | 0,33 |
| 10 | 2 | 0,18 |
| 6 | 10 | 0,7 |
| 6 | 6 | 0,3 |
| 6 | 2 | 0,2 |
| 2 | 10 | 0,9 |
| 2 | 6 | 0,85 |
| 2 | 2 | 0,69 |
Применив к исходным данным задачи формулу (16) определения разницы прибыли от производства продукции, получим следующую платёжную матрицу
Таблица 8
Платёжная матрица в игре «Борьба двух предприятий за рынок продукции региона».
| B1 | B2 | B3 | minj
|
|
| A1 | 0,17 | 0,62 | 0,24 | 0.17 |
| A2 | 3 | -1,5 | -0,8 | -1.5 |
| A3 | 0,75 | 0,5 | 0,175 | 0,175 |
| maxi
|
3 | 0.62 | 0.24 |
В данной матрице (см. таблицу 8) нет доминируемых или дублирующих стратегий. Нижняя цена игры равна 0,175, а верхняя цена игры равна 0,24. Нижняя цена игры не равна верхней. Поэтому решения в чистых стратегиях не существует и для каждого из игроков необходимо найти оптимальную смешанную стратегию.
Решение задачи
1. В данной матрице имеются отрицательные коэффициенты. Для соблюдения условия неотрицательности в задачах линейного программирования прибавим к каждому коэффициенту матрицы модуль минимального отрицательного коэффициента. В данной задаче к каждому коэффициенту матрицы необходимо прибавить число 1,5 – значение модуля наименьшего отрицательного элемента матрицы. Получим платёжную матрицу (см. таблицу 9).
Таблица 9
Платёжная матрица, преобразованная для выполнения условия неотрицательности
| B1 | B2 | B3 | |
| A1 | 1,67 | 2,12 | 1,74 |
| A2 | 4,5 | 0 | 0,7 |
| A3 | 2,25 | 2 | 1,675 |
2. Опишем задачу линейного программирования для каждого игрока в виде системы линейных неравенств:
Для игрока 1:
1,67×x1 + 4,5×x2 + 2,25×x3 ³ 1
2,12×x1 + 0×x2 + 2×x3 ³ 1
1,74×x1 + 0,7×x2 + 1,675×x3 ³ 1
x1³ 0; x2³ 0; x3³ 0
min Z = x1 + x2 + x3
Для игрока 2:
1,67×y1 + 2,12×y2 + 1,74×y3 £ 1
4,5×y1 + 0×y2 + 0,7×y3 £ 1
2,25×y1 + 2×y2 + 1,675×y3 £ 1
y1³ 0; y2³ 0; y3³ 0
max Z = y1 + y2 + y3
3. Решим обе задачи с использованием Excel:
Рисунок 2.2 – Поиск решения для первого игрока.
Аналогично для 2 игрока:
Рисунок 2.3 – Поиск решения для 2 игрока
В результате решения задачи получим следующие значения целевой функции и переменных: Z = 0,5771, γ* = 1/0,5771 = 1,7328; x1 = 0,5144, x2 = 0, x3 = 0,0626; y1 = 0,0582, y3 = 0,5189.
4. Для определения значений вероятностей выбора стратегий игроков 1 и 2 умножим значения переменных на γ*. P1
= x1×γ* = 0,8914, p2
=0, p3
= x3×γ* = 0,1083: q1
= y1×γ* = 0,1008, q2
= 0, q3
= y3×γ* = 0,8991.
5. Определим значение цены игры. Для этого из величины γ* вычтем 1,5 (значение модуля наименьшего отрицательного элемента) γ = 1,7328 - 1,5 = 0,2328.
Проверим правильность решения задачи с помощью программы Tora:
Рисунок 2.4 – Решение задачи в Tora.
Таким образом, в данной игре выиграет предприятие 1 (значение γ > 0). Для достижения своей оптимальной стратегии (получения максимального математического ожидания гарантированного выигрыша) предприятие 1 должно выбирать технологию 1 с вероятностью 0,8914, а технологию 3 – с вероятностью 0,1083. Предприятие 2, соответственно, должно выбирать технологию 1 с вероятностью 0,1008, а технологию 3 – с вероятностью 0,8991. Значение математического ожидания выигрыша предприятия 1 составит 0,2328 тыс. д.е.
2.3 Пример 3. Решение статистической игры
Рассмотрим пример решения статистической игры в экономической задаче.
Сельскохозяйственное предприятие производит капусту. Оно имеет возможность хранить произведённую капусту в течение всего сезона реализации – с осени до начала лета следующего года. Хозяйство может выбрать одну из трёх стратегических программ реализации капусты в течение сезона реализации:
A1 - реализовать всю капусту осенью, непосредственно после уборки;
A2 - заложить часть капусты на хранение и реализовать её в течение осенних и зимних месяцев;
A3 – заложить всю капусту на хранение и реализовать её в весенние месяцы.
Сумма затрат на производство, хранение и реализацию капусты для хозяйства при выборе им каждой из стратегий составляет соответственно 20, 30 и 40 тыс. денежных единиц.
На региональном рынке капусты может сложиться одна из следующих трёх ситуаций:
S1 - поступление капусты на рынок происходит равномерно в течение всего сезона реализации и рынок не испытывает сезонных колебаний цен реализации продукта;
S2 - в осенние месяцы на рынок поступает капусты немного больше, чем зимой и весной. В связи с этим наблюдаются небольшие сезонные колебания цен – в начале зимы цены немного возрастают по сравнению с осенним уровнем и держатся стабильными в течение всех последующих месяцев сезона реализации;
S3 - в осенние месяцы на рынок поступает капусты значительно больше, чем зимой и весной. Объёмы капусты, поступающей в течение сезона реализации, постоянно уменьшаются.Значения суммы выручки предприятия от реализации капусты при выборе каждой из стратегий реализации и формировании различных ситуаций на рынке представлены в таблице 10.
Таблица 10
Выручка от реализации капусты, тыс. д.е.
| Стратегии хозяйства | Выручка от реализации капусты, тыс. д.е. | ||
| S1 | S2 | S3 | |
| A1 | 30 | 25 | 22 |
| A2 | 30 | 40 | 33 |
| A3 | 30 | 40 | 60 |
В задаче необходимо определить:
1. Какая стратегия хозяйства является наиболее выгодной, если известны значения вероятностей состояний рынка капусты региона: 0,3, 0,6 и 0,1 соответственно;
2. Какая стратегия хозяйства является наиболее выгодной, если информация о вероятностях состояний рынка капусты отсутствует и предприятию необходимо:
а) получить минимально гарантированный выигрыш;
б) учесть значения риска от принятия различных решений;
в) определить наиболее выгодную стратегию, если коэффициент пессимизма равен 0,3;
3. Определить наиболее выгодную стратегию, если информация о вероятностях состояний рынка не является вполне достоверной и параметр достоверности информации равен 0,7.
Решение
1. Составим платёжную матрицу данной игры. Её коэффициентами будут значения прибыли от производства капусты, получаемые как разница суммы выручки от реализации капусты и затрат на производство, хранение и реализацию капусты (см. таблицу 11).
Таблица 11
Платёжная матрица задачи определения наиболее выгодной стратегии реализации капусты
| S1 | S2 | S3 | |
| A1 | 10 | 5 | 2 |
| A2 | 0 | 10 | 3 |
| A3 | -10 | 0 | 20 |
3. Определим наиболее выгодную стратегию по критерию максимального математического ожидания выигрыша:
W1
= 10×0,3 + 5×0,6 + 2×0,1 = 6,2
W2
= 0×0,3 + 10×0,6 + 3×0,1 = 6,3
W3
= -10×0,3 + 0×0,6 + 20×0,1 = -1
Таблица 12
Определение оптимальной стратегии в статистической игре по критерию максимального математического ожидания
| S1 | S2 | S3 | Wi | |
| Pj | 0,3 | 0,6 | 0,1 | |
| A1 | 10 | 5 | 2 | 6.2 |
| A2 | 0 | 10 | 3 | 6.3 |
| A3 | -10 | 0 | 20 | -1 |
Оптимальной по данному критерию при указанных значениях вероятностей состояния рынка капусты будет стратегия A2 (W = 6,3) (см. таблицу 12).
3. Определим наиболее выгодные стратегии предприятия по ММ-критерию, критерию недостаточного основания Лапласа (НО-критерий) и критерию пессимизма-оптимизма.
Таблица 13
Определение оптимальной стратегии в статистической игре по максиминному критерию, критерию недостаточного основания Лапласа и критерию пессимизма-оптимизма
| S1 | S2 | S3 | Wi (ММ) | Wi (НО) | Wi (ПО) | |
| A1 | 10 | 5 | 2 | 2 | 5,67 | 7,6 |
| A2 | 0 | 10 | 3 | 0 | 4,33 | 7 |
| A3 | -10 | 0 | 20 | -10 | 3,33 | 11 |
Значения Wi
для ММ-критерия:
W1
= min (10, 5, 2) = 2
W2
= min (0, 10, 3) = 0
W3
= min (-10, 0 20) =-10
W = maxWi
= W1
Оптимальной стратегией по максиминному критерию является стратегия A1 (W = 2). Определим оптимальную стратегию по критерию недостаточного основания Лапласа. По данному критерию оптимальной является стратегия A1 (W = 5,67).
По критерию пессимизма-оптимизма при коэффициенте пессимизма, равном 0,3 – стратегия A3 (W = 11).
4. Определим наиболее выгодную стратегию по критерию минимаксного риска. Для этого рассчитаем матрицу рисков (см. таблицу 14).
Таблица 14
Определение оптимальной стратегии в статистической игре по критерию минимаксного риска с помощью построения матрицы рисков
| S1 | S2 | S3 | Ri | |
| A1 | 0 | 5 | 18 | 18 |
| A2 | 10 | 0 | 17 | 17 |
| A3 | 20 | 10 | 20 | 20 |
Оптимальной стратегией по критерию минимаксного риска является стратегия A2 (W = 17).
6. Определим наиболее выгодную стратегию предприятия по критерию Ходжа-Лемана (см. таблицу 15).
Таблица 15
Определение оптимальной стратегии в статистической игре по критерию Ходжа-Лемана
| S1 | S2 | S3 | Wi | |
| Pj | 0,3 | 0,6 | 0,1 | |
| A1 | 10 | 5 | 2 | 4,94 |
| A2 | 0 | 10 | 3 | 4,41 |
| A3 | -10 | 0 | 20 | -3,7 |
По критерию Ходжа-Лемана оптимальной для хозяйства будет стратегия A1 (W = 4,94).
ЗАКЛЮЧЕНИЕ
Задачи, в которых возникают ситуации, где важную роль играют конфликты и совместные действия можно решать с помощью теории игр.
Решение задачи заключается в том, как должен вести себя разумный игрок в конфликте с разумным противником, чтобы обеспечить себе в среднем наибольший возможный выигрыш.
Для правильного применения теории игр в решении задач нужно знать основные понятия теории игр, их классификацию, уметь делать правильную постановку задачи с позиции теории игр и осуществлять их решение.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. http://www.spbgid.ruindex.phpnews=125958 актуальна на 15.11.2008.
2. Оуэн Г. Теория игр.- М.:Мир, 1971.- 230с.
3. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, Главная редакция физико-математической литературы, 1985. – 272 с.
4. Вентцель Е.С. Элементы теории игр. – М.: Наука, 1961. – 67 с.
5. http://pasadvice.narod.ru/stat/teorigr.htm актуальна на 29.10.2008.
6. Балдин К.В., Воробьев С.Н., Уткин В.Б. Управленческие решения. - М.: Издательство – торговая корпорация «Дашков и Кͦ», 2006. - 496 с.
7. http://www.12manage.com/methods_game_theory_ru.html актуальна на 14.11.2008.
8. http://www.ecsocman.edu.ru/db/msg/54933.html актуальна на 3.11.2008.
9. Мулен Э. Теория игр с примерами из математической экономики: Пер с франц.- М.: Мир, 1985.-200 с.
10.Воробьев Н.Н. Теория игр. – М.: Наука, 1976. – 64 с.
11.Васин А.А., Морозов В.В. Введение в теорию игр с приложениями к экономике. – М.: 2003. – 278 с.
12.Интрилигатор М. Математические методы оптимизации и экономическая теория. - М.: Айрис – пресс, 2002. - 576 с.
13.http://ru.wikipedia.org/wiki/ актуальна на 11.11.2008.
14.Волков И.К., Загоруйко Е.А. Исследование операций. - М.: Издательство МГТУ им. Н.Э. Баумана, 2000. - 436 с.
15.Харина О.Ю. Методическое пособие для студентов экономических специальностей г Петропавловск, 2005. - 85с.
16.Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. – М.: Наука, 1984. – 495 с.
17.Лапшин К.А. Игровые модели и принятие решений. - М.: Москва, 2001. 45 с.
18.Таха, Хемди А. Введение в исследование операций. - М.: Издательский дом «Вильямс», 2005. – 912 с.
19.Шевчук Е.В., Касимов И.Р. Методическое пособие по выполнению курсовых проектов и работ: учебно-методическое пособие. Петропавловск: СКГУ им. М. Козыбаева, 2007. – 30 с.
20.Шинтемирова А.У., Морозова О.В. Инструкции по выполнению письменных работ студентами бакалавриата. - Петропавловск: СКГУ им. М. Козыбаева, 2006. – 60 с.