Автор работы: Пользователь скрыл имя, 09 Апреля 2014 в 19:56, курсовая работа
Математическая теория игр способна не только указать оптимальный путь к решению некоторых проблем, но и прогнозировать их исход. Матричные игры серьёзно изучаются специалистами, так как они довольно просты и к ним могут быть сведены игры общего вида. Поэтому теория матричных игр хорошо развита, существуют различные методы поиска решения игр.
Методы решения матричных игр
(курсовая работа)
СОДЕРЖАНИЕ
Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта.
Математическая теория игр способна не только указать оптимальный путь к решению некоторых проблем, но и прогнозировать их исход. Матричные игры серьёзно изучаются специалистами, так как они довольно просты и к ним могут быть сведены игры общего вида. Поэтому теория матричных игр хорошо развита, существуют различные методы поиска решения игр.
В большинстве случаев решение матричных игр представляет собой трудный и громоздкий процесс. Есть примеры, когда даже для матриц размера 3´3, процесс поиска решения довольно трудоёмкий.
Кроме того, выигрыши игроков в каждой ситуации не всегда определяются точными измерениями. В процессе сбора данных об изучаемом явлении, анализа этих данных и введения при построении модели различных предположений накапливаются ошибки. Они же могут выражаться числами в матрице выигрышей. Поэтому точность в определении значения игры и оптимальных стратегий игроков оправдана не всегда.
А также, следует заметить, что погрешность в оценке игроком своего выигрыша не может привести к практически серьёзным последствиям и небольшое отклонение игрока от оптимальной стратегии не влечёт за собой существенного изменения в его выигрыше.
Целью теории игр является определение оптимальной стратегии для каждого игрока.
В настоящее время в теории игр известны несколько способов приближенного решения матричных игр.
Цель данной работы – изучить методы решения матричных игр.
Основными задачами является:
Теория игр впервые была систематически изложена Дж. фон Нейманом и О. Моргенштерном в 1994 г., хотя отдельные исследования в этой области публиковались ещё в 1920 годах. Дж. фон Нейман и О. Моргенштерн написали книгу, которая содержала в основном экономические примеры, т.к. описать конфликт легче в числовой форме. После второй мировой войны всерьез теорией игр заинтересовались военные, т.к. увидели в ней аппарат для исследования стратегических решений. Затем внимание снова переключилось на экономические проблемы. Сейчас ведется большая работа, направленная на расширение сферы применения теории игр.
Теория игр – это теория математических моделей, интересы участников которых различны, причем они достигают своей цели различными путями. Столкновение противоположных интересов участников приводит к возникновению конфликтных ситуаций. Необходимость анализировать такие ситуации была причиной возникновения теории игр, задачей которой является выработка рекомендаций к рациональным действиям участников конфликта.
Чтобы исключить трудности, возникающие при анализе конфликтных ситуаций и в результате наличия многих факторов, строится упрощенная модель ситуации. Такая модель называется игрой. Конфликтная ситуация в игровой модели развивается по определенным правилам.
Различают три вида причин неопределенности результата игры:
Теория матричных игр позволяет рассматривать и с легкостью решать задачи принятия решений в ситуациях с несколькими участниками, когда значение целевой функции для каждого зависит от решений, принимаемых остальными участниками. Важная роль в матричных играх отводится конфликтам и совместным действиям.
Характерная черта общественного, социально-экономического явлений состоит в множественности и многосторонности интересов и в наличии сторон, выражающих эти интересы. Классическим примером подобной ситуации является столкновение интересов покупателя и продавца, т.е когда на рынок выходят несколько производителей, обладающих достаточной силой для воздействия на цену товара. Более сложные ситуации возникают при наличии объединений и коалиции лиц на рынке, участвующих в столкновении интересов, например, когда ставки заработной платы определяются союзами или объединениями предпринимателей, при анализе результатов голосования в парламенте.
Конфликт может возникнуть из-за различия целей, которые отражают не только несовпадающие интересы, но и многосторонние интересы одного и того же лица. Например, разработчик экономической политики обычно преследует множество целей, согласуя противоречивые требования, такие как рост объемов производства, повышение доходов. Так же конфликт может проявиться не только в результате сознательных действий участников, но и как результат действий тех или иных стихийных сил. Данные случаи конфликтом могут встретиться как в социологии, так и в психологии, биологии, политологии, военном деле. Самыми простыми примерами матричных игр являются карточные и спортивные игры.
Каждая модель социально-экономического явления должна отражать черты конфликта, т.е. описывать:
В теории матричных игр предполагается, что функция выигрыша и множества стратегий, доступна и известна каждому из игроков, т.е. каждый игрок знает свою функцию выигрыша и набор имеющихся в его распоряжении стратегий, а также функций выигрыша и стратегий всех остальных игроков, и в соответствии с этой информацией организует свое поведение.
Различные виды игр можно классифицировать по числу игроков, числу стратегий, свойствам функции выигрыша, возможности предварительных переговоров и взаимодействия между игроками в ходе игры.
В зависимости от числа игроков различают игры с двумя, тремя и более участниками. В теории оптимизации представлены игры как с одним игроком, так и с бесконечным числом игроков. Согласно принципу классификации – по количеству стратегий – различают конечные и бесконечные игры. В конечных играх игроки располагают конечным числом возможных стратегий. Сами стратегии в конечных играх нередко называются чистыми стратегиями. Соответственно, в бесконечных играх игроки имеют бесконечное число возможных стратегий.
Третий способ классификации – по свойствам функций выигрыша (платежных функций). Особым случаем в теории игр является ситуация, когда выигрыш одного из игроков равен проигрышу другого (т.е. прямой конфликт между игроками). Подобные игры называют играми с нулевой суммой или антагонистическими играми. Прямой противоположностью играм такого типа являются игры с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно. Между этими крайними имеются множество игр с ненулевой суммой, где имеются и конфликты, и согласованные действия игроков.
В зависимости от возможности предварительных переговоров между игроками различают кооперативные и некооперативные игры. Игра называется кооперативной, если до начала игры игроки образуют коалиции и принимают соглашения о своих стратегиях. А игры, в которых игроки не могут координировать свои стратегии, называются некооперативными. Необходимо отметить, что все антагонистические игры могут служить примером некооперативных игр.
Антагонистические игры являются разновидностью матричных игр, в которых выигрыш одного игрока равен проигрышу другого. Их ещё называют играми с нулевой суммой.
Наиболее часто приводимым примером игр с ненулевой суммой является игра «Дилемма заключенного». Суть игры состоит в том, что два преступника ожидают приговора суда за содеянное. Адвокат конфиденциально предлагает каждому из преступников облегчить его участь, если он сознается и даст показания против сообщника, которому грозит угодить в тюрьму за совершенное преступление на 10 лет. Если никто не сознается, то обоим угрожает заключение на определенный срок (например, 1 год) по обвинению в незначительном преступлении. Если сознаются оба преступника, то, с учетом чистосердечного признания, им обоим грозит попасть в тюрьму на 5 лет. Каждый заключенный имеет на выбор 2 стратегии: не сознаться или сознаться, выдав при этом сообщника.
В итоге можно
получить следующую матрицу «
(5,5) (0,10)
(10,0) (1,1)
Основным допущением при решении данных игр является то, что каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях партнера.
В игре могут участвовать как два игрока (её называют парной), так и множество. Но наибольшее практическое значение имеют парные игры, в которых участников обозначают за A и B. Простейшим видом стратегической игры – игра двух лиц с нулевой суммой (т.е. сумма выигрышей сторон равна нулю).
Игра состоит из двух ходов: игрок A выбирает одну из своих возможных стратегий Ai ( i = 1, 2, …, m), а игрок B выбирает стратегию Bj( j = 1, 2, .., n), причем каждый участник делает выбор в полной ситуации незнании выбора другого игрока. В результате выигрыши φ1 (Ai, Bj)и φ2 (Ai, Bj) каждого из игроков удовлетворяют соотношению
- φ1 (Ai, Bj)+ φ2 (Ai, Bj)=0
Если φ1 (Ai, Bj)= φ (Ai, Bj), то φ2 (Ai, Bj)= - φ (Ai, Bj)
Цель игрока А – максимизировать функцию φ (Ai, Bj), а игрока В – минимизировать эту же функцию. Каждый из игроков может выбирать одну из переменных, от которых зависит значение функции. Если игрок А выбирает некоторую из стратегий Ai, то это может влиять на значение функции φ (Ai, Bj). Влияние Ai на величину значения φ (Ai, Bj) является неопределенным, а определенность имеет место только после выбора, например, игроком B переменной Bj (при этом Bj определяется другим игроком).
Пусть φ (Ai, Bj)=aij, тогда составим матрицу:
А=
Строки матрицы соответствуют стратегиям Ai, столбцы – стратегиям Bj. Матрица А называется матрицей игры, а элемент aij матрицы – выигрыш игрока А, если он выбрал стратегию Ai, а игрок B выбрал стратегию Bj.
Пусть игрок А выбрал некоторую стратегию Ai, тогда в худшем случае он получит выигрыш, равный min aij. Поэтому предвидя такую возможность, игрок А должен выбрать ту стратегию, которая позволит максимизировать его минимальный выигрыш α : α =max min aij. Величина α - гарантированный выигрыш игрока А – называется нижней ценой игры, а стратегия Ai0, обеспечивающая получение α - максиминной.
Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии Bj его Bj проигрышнее превысит максимального из значений элементов j-го столбца матрицы, т.е. меньше или равен max aij. Рассматривая множество max aij для различных значений j, игрок В выбирает такое значение j, при котором его максимальный проигрыш β минимизируется: β = min max aij. Величина β называется верхней ценой игры, а соответствующая выигрышу β стратегия Bj - минимаксной.
Фактический выигрыш игрока А при разумных действиях обоих участников ограничен нижней и верхней ценой игры. Если эти выражения будут равны, т.е. max min aij = min max aij = v, то выигрыш игрока А – вполне определенное число, значит игра называется вполне определенной, а выигрыш – значением игры и равен элементу матрицы ai0j0.
Вполне определенные игры называют играми с седловой точкой. Элемент ai0j0 в матрице такой игры является одновременно минимальным в строке i0, максимальным в столбце j0 и называется седловой точкой.
Седловой точке соответствуют оптимальные стратегии игроков, их совокупность – это решение игры, которое обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение от его оптимальной стратегии не может быть выгодно.
Точка называется седловой из-за формы графика функции выигрыша в точке ai0j0, которая напоминает седло, убывая при изменении одной из переменных и возрастая при изменении другой переменной.
Необходимо отметить, что в случае, если цена антагонистической игры равна 0, игра называется справедливой.
Задача: определить верхнюю и нижнюю цены для игр, заданных платежными матрицами А и В:
A= B=
Решение: минимальное значение aij в строках матрицы А равны соответственно 2,3,1. Максимальное значение из них равно 3. Следовательно, α1 - нижняя цена игры, которой соответствует матрица A, равна 3.
α1 =min{2;3;4}=3