Федеральное агентство по образованию ФГОУ ВПО

Брянский  государственный технический университет  политехнический колледж 

 

Курсовая  работа

По дисциплине «Математические методы»

Тема  работы: «Описание и программирование матричных игр» 

 

2010 

 

1. Введение

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

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

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

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

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

   Математическая  теория игр способна не только указать  оптимальный путь к решению некоторых  проблем, но и прогнозировать их исход. Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

 Главный момент, рассмотренный в теории исследования операций — выбор, принятие решения.

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

 Субъект характеризуется наличием возможности выбора и наличием цели.

 

 Перед субъектом стоят две проблемы — необходимость выбора (при этом, бездействие рассматривается как один из вариантов выбора, который присутствует всегда) и степень неопределенности, в которой совершается выбор. Если все исходы зависят только от выбора, и все варианты выбора известны, то получается выбор в условиях полной детерминированности; такие задачи решаются с помощью методов оптимизации, и такие задачи далее не рассматриваются.

 В ситуации с неполной определенностью возможны варианты:

• Есть другая оперирующая сторона, и их интересы противоположны — антагонистические игры. Неопределенность состоит в том, что неизвестно, какое решение примет другая сторона.
• Другая оперирующая сторона не противодействует и не взаимодействует с целью помочь. Неопределенность связана с недостаточными знаниями.
• Есть другие оперирующие стороны, и интересы субъектов не являются противоположными. Неопределенность в том, что неизвестно, как будут поступать другие и, возможно, в недостатке знаний.
• Множество субъектов могут совместно преследовать одну цель.

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

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

   Игры, в которых игроки осведомлены  о состоянии своем и партнеров, а также о прошлом поведении участников игры, относятся к категории игр с полной информацией (типичные примеры - шахматы, "крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против "природы").

   Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой.

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

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

   ИГРОКОМ (лицом, стороной, или коалицией) называется отдельная совокупность интересов, отстаиваемая в игре. Если данную совокупность интересов отстаивает несколько  участников игры, то они рассматриваются  как один игрок. Игроки, имеющие противоположные по отношению друг к другу интересы, называются  противниками. В игре могут сталкиваться интересы двух или более противников.

     

   Простейшими являются игры 2 лиц с нулевой  суммой.

   Пусть в такой игре игрок 1 имеет m выборов  и игрок 2 - n выборов. Если игрок 1 делает свой i - й выбор, а игрок 2 - свой j - й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен . Такая игра называется матричной и матрица: (1.1) называется матрицей выигрышей (платежной матрицей).

   При ведении игры игрок должен ориентироваться  на оптимальную политику партнера и  наказывать его за отступления от таковой.

 

2. Аннотация

 

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

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

   В первом параграфе приведены основные понятия и утверждения теории матричных игр.

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

   Параграф  третий посвящён изложению приближённого  решения игры методом Брауна-Робинсона (метод фиктивного разыгрывания) и его обоснованию. Приведён пример применения алгоритма для конкретной матричной игры.

В третьем  параграфе рассмотрен ещё один метод  – монотонный итеративный алгоритм приближённого решения матричных  игр.

 

3. Теоретическая часть

3.1. Общая постановка игры двух лиц

 

   Модель  игры двух лиц - одна из простейших моделей: в ней всего две оперирующих  стороны.

   

   Пусть заданы две оперирующие стороны (два игрока). У каждого из игроков  есть множество возможных действий: у первого — , у второго — . Или, что, то же самое, и — множества стратегий первого и второго игроков, соответственно. Каждый игрок может выбрать любую из своих стратегий.

   Если  первый игрок выбирает стратегию (3.1.1), второй игрок выбирает стратегию (3.1.2) (при этом, помним, что бездействие — тоже стратегия), то формируется пара (3.1.3), называемая исходом игры. Каждый исход для каждого игрока имеет привлекательность (или выгодность, выигрыш, полезность). Эту привлекательность мы зададим с помощью функций выигрыша игроков: ( 3.1.4)— функция выигрыша первого игрока, (3.1.5) — функция выигрыша второго игрока, (3.1.6), ( 3.1.7). Функции выигрыши также называются функциями полезности и целевыми функциями.

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

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

   Задача  первого игрока состоит в том, чтобы максимизировать свою функцию  полезности:

   

(3.1.8)

   Второй  игрок максимизирует свою функцию  полезности:

   

(3.1.9)

   Кроме сделанного описания, принимаются гипотезы:

• Гипотеза полной информированности. Каждому из игроков точно известны его собственное множество стратегий и множество стратегий второго игрока, а также обе функции полезности. Единственное, что неизвестно каждому из игроков, — это выбор другого игрока. (Хотя, заметим, что во многих практических примерах игр двух лиц эта гипотеза не выполняется).

 

• Гипотеза  рационального поведения игроков. Каждый из игроков считает другого не глупее себя: если первый игрок узнал какую-либо информацию об игре, то и второй игрок ее тоже знает; в другой формулировке: все интересы игрока заключены в максимизации его целевой функции.

 

3.2. Антагонистические игры

 

   Антагонистические игры (или игры с нулевой суммой) — это такие игры, в которых цели игроков прямо противоположные. Т.е., величина выигрыша одно игрока равна величине проигрыша другого игрока:

   

(3.2.1)

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

   

(3.2.2)

   Тогда в игре будет всего  исходов. С каждым и сходом связан выигрыш первого игрока :

   

(3.2.3)

   Обозначим за C матрицу, элементами которой являются величины выигрыша первого игрока:

   

(3.2.3)

   Тогда, если оба игрока имеют конечные множества  стратегий, антагонистическая игра полностью C. 

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

   Для этой игры множества стратегий можем  задать:

   

(3.2.4)

   Матрица игры:

   

(3.2.5)

 

   

3.3. Существование равновесия

 

   Рассмотрим  вопрос о существовании равновесия. В качестве примера рассмотрим игру в пальцы:

   

(3.3.1)

   Гарантированные результаты для первого игрока есть , гарантирующая стратегия есть . Для второго: , гарантирующие стратегии - .

  Рассмотрим  исход  . Первому игроку выгоднее воспользоваться третьей стратегий, второму игроку — второй стратегией. Таким образом, не является равновесным исходом игры. Аналогичным образом приходим к выводу, что и не является равновесным исходом игры.

   В связи с этим возникает вопрос: как играть игрокам и как определить, существует ли равновесный исход.

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

   Формально определим все используемые определения. Имеется множество D стратегий первого игрока, множество G стратегий второго игрока, первый игрок выбирает стратегию , второй игрок выбирает стратегию , и определяется исход игры . На множестве исходов игры задается функция выигрыша первого игрока (3.3.2), которая определяет выигрыш первого игрока, который равен проигрышу второго игрока.

   Далее, определяется функция  гарантированного результата первого игрока при выборе им :

   

(3.3.3)

   Гарантированный результат  первого игрока:

   

(3.3.4)

   И гарантированный  результат  первого игрока:

   

(3.3.5)

   Аналогично, для второго игрока определим  функцию гарантированного результата , его гарантированный результат и гарантирующую стратегию :

   Значение  называется максимином функции , — максиминная стратегия, a — минимакс, и — минимаксная стратегия.

   Определим ситуацию равновесия в игре следующим образом:

   

(3.3.6)

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

   

   Эти неравенства соответствуют в седловой точке функции . Т.е., пара является ситуацией равновесия тогда и только тогда, когда - седловая точка.

   Стратегии игроков, соответствующие ситуации равновесия, называют равновесными стратегиями.

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

   Лемма 1. Для любой антагонистической игры всегда имеет место , или (3.3.7), если соответствующие минимумы и максимумы достигаются. Т.е., в антагонистической игре гарантированный выигрыш одного игрока не может быть больше гарантированного проигрыша другого игрока.

   Доказательство: Пусть - гарантирующая стратегия первого игрока, - гарантирующая стратегия второго игрока, гарантированные результаты есть и , и пусть они достигаются на исходах и :

   

(3.3.8)

   Заметим, что:

   

(3.3.9)

   (из условия, что - гарантированный результат первого игрока, т.е )(3.3.9)

   

(3.3.10)

   (так,  как  , и минимум берется по всем ) 

   Аналогичным образом, получаем:

   

(3.3.11)

   Совмещая  эти два неравенства, получаем:

   

(3.3.12)

   Ранее было дано определение положения  равновесия через седловую точку. Это определение не является конструктивным. Чтобы получить конструктивное определение, сформулируем следующее утверждение. 

   Лемма 2. Исход игры является ситуацией равновесия тогда и только тогда, когда (3.3.13)

   Замечание 1. Эта лемма задает определение положения равновесия, эквивалентное определению положению равновесия через седловую точку:

   

(3.3.14)

   Замечание 2. Лемма дает конструктивное определение положения равновесия.

   

   

   Если  в игре есть равновесный исход, то гарантирующая стратегия является оптимальной.

   Для матричной игры с матрицей условие существования равновесия есть:

   

(3.3.15)

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

 

   

3.4. Механизм случайности

 

   Зададим для первого игрока вектор (3.4.1), где — вероятность выбора первым игроком I - ой стратегии, и (3.4.2), (3.4.3)- Игрок, применяя механизм случайного выбора, выбирает стратегию .

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

   

(3.4.4)

— стандартный  симплекс в m-мерном пространстве. 

   Второму игроку также надо сделать свой выбор. Пусть второй игрок выбирает смешанную стратегию (3.4.5), где — вероятность выбора вторым игроком своей -й чистой стратегии, Q — множество смешанных стратегий второго игрока, (3.4.6).

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

   Определим математические ожидания выигрышей  игроков при применении их смешанных  стратегий.

   Пусть матрица выигрышей при чистых стратегиях есть:

   

(3.4.7)

   Тогда вероятность чистого исхода есть:

   

(3.4.8)

   Так как  и независимы. Тогда математическое ожидание выигрыша первого игрока есть

   

(3.4.9)

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

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

   Другая  особенность — замена выигрыша математическим ожиданием выигрыша.

     

3.5. Нахождение равновесного решения.

 

   Разберем  простой случай — игра, где у  каждого игрока есть по две стратегии. Матрица игры имеет вид:

   

(3.5.1)

   Если  имеется ситуация равновесия, то она достигается применением гарантирующей стратегии. Пусть ситуации равновесия не существует.

   Можно показать, что у каждого из игроков  спектр его равновесной смешанной  стратегии содержит обе чистые стратегии. Таким образом, если (3.5.2) - равновесная стратегия одного из игрока, то (3.5.3).

   

(3.5.4)

   Приравнивая ожидания, получаем:

   

(3.5.5)

   Далее, .

   

(3.5.6)

   Аналогично, для второго игрока:

   

(3.5.7)

 

   

3.6. Игровые методы в планировании товарного ассортимента фирмы.

 

   Одно  из ключевых мест в маркетинге занимает товарная политика. Главная цель товарной политики - это определение набора товарных групп, наиболее предпочтительного для успешной работы на рынке и обеспечивающего эффективную деятельность фирмы. В маркетинге разработаны свои методы и модели для управления товарной политикой фирмы. К ним относится матрица Бостонской Консалтинговой Группы (БКГ). Результат этой модели представлен в виде набора словесных рекомендаций по каждой группе товара.

   Фирма выпускает 10 наименований косметических  средств. Обозначим:

• Шампунь
• бальзам для волос
• молочко для снятия макияжа
• крем для лица
• лосьон-тоник
• маска для лица
• скарб для тела
• крем для рук
• пенка для умывания
• молочко для тела

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

   Матрица БКГ - это трехмерная матрица, координатами которой служат комплексные показатели: "привлекательность рынка товара", " конкурентная позиция предприятия " и "конкурентоспособность товара ". Критерии, оценки и источники информации выбраны исходя из основных направлений маркетинговых исследований при формировании товарной политики. Это исследование возможностей предприятия и конкурентной среды, изучение рынка и учет влияния внешних факторов. Оценка "конкурентной позиции предприятия" осуществляется на основе анализа собственных возможностей по сравнению с конкурентами. Расчет показателя "привлекательность рынка" требует данных о динамике рынка товаров. При этом учитываются внешние факторы, а именно государственная политика, риск и др. Показатель "конкурентоспособность товара" оценивается с помощью технико-экономических показателей собственных товаров и товаров-конкурентов. Методика расчета комплексных показателей основана на бальных оценках критериев и их коэффициентах значимости, устанавливаемых экспертами. В качестве экспертов могут выступать специалисты службы перспективного развития, отдела маркетинга и руководства фирмы. Бальные оценки, проставляемые экспертами, принимают значения от 1 до 10.

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