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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Описание и программирование матричных игр

Информация:

Тип работы: курсовая работа. Добавлен: 02.07.2012. Сдан: 2011. Страниц: 27. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Федеральное агентство по образованию ФГОУ ВПО
Брянский  государственный технический университет  политехнический колледж 

0211691 230105
 
Курсовая  работа
По дисциплине «Математические методы»
Тема  работы: «Описание и программирование матричных игр» 

Преподаватель: Певнев А.А
Группа: 36 про 07
Студента: Серпкова Н.И Захаров В.И
Оценка:  
Дата:  
 
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 (бальная оценка).
   Фактическая оценка i-го критерия по k - му показателю товара t с учетом весовых коэффициентов:
   
(3.6.1)

   Идеальное, т. е. максимальное или наилучшее, значение i-го критерия по k-му показателю товара t с учетом весовых коэффициентов:
   
(3.6.2)

   Значение k-го показателя по товару t , выраженное в процентах, рассчитывается по формуле:
   
(3.6.3)

   Значения  комплексных показателей  попадают в один из интервалов: от 0 до 33, от 33 до 67, от 67 до 100. Вследствие такого разбиения значений показателей на 3 интервала анализируемый товар занимает одно из 27 возможных положений в трехмерной матрице позиционирования товара.
       
   Номера  кубиков данной матрицы соответствуют номерам маркетинговых стратегий, которые рекомендуется применять при планировании товарного ассортимента. Выделяются 5 основных стратегий 22 дополнительные, развивающие и конкретизирующие основные стратегии. Они служат для выработки действий предприятия в части изменения рыночной доли, проведения инвестиционной, программной и сбытовой политики в соответствии с занимаемым статусом товара.  

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

   Маркетинговой стратегии №2 подчиняются товары, подлежащие снятию с производства. Объем реализации этих товаров падает. Фирмы начинают выходить из конкурентной борьбы, количество конкурентов уменьшается. Цены на товары низкие. Прибыль резко сокращается. Эти товары постепенно заменяются новыми, отвечающими требованиям рынка.
   Маркетинговая стратегия №3 применяется к товарам, которые требуют усовершенствования и модернизации. Здесь требуются значительные инвестиции. Товарная политика подвержена жесткой специализации. Такая политика оказывается оптимальной для эффективной деятельности небольшой фирмы или когда фирма периодически меняет специализацию, используя ее для освоения новых рынков или адаптируясь к меняющемуся спросу.  

   Маркетинговой стратегии №4 подчиняются товары "новой волны". Фирма выходит  на рынок с принципиально новым  товаром и обычно занимает исключительное положение на рынке. Конкуренции практически нет. Прибыли пока тоже нет или она еще очень незначительна. Покупатель инертен по отношению к только что появившемуся товару. Необходимо убедить покупателя испытать новый товар. Также данная стратегия рекомендуется для товаров, которые начинают массово продаваться. Растет объем реализации, фирма начинает получать прибыль.  

   Маркетинговая стратегия №5 рекомендуется для  товаров, активно продающихся на рынке. Рынок насыщен данным видом  товара. Уменьшается объем продаж этих товаров. Основной спрос исходит от консервативных покупателей, в то время как новаторы ищут товар-заменитель. Фирма стремится к дальнейшему совершенствованию продукта и ищет для него новые сферы применения. 

   Значения  матрицы выигрышей для игроков  находим как расстояния между точками в трехмерном единичном кубе по формулам:
   
(3.6.4)

   
   Где (x1,x2,x3), (y1,y2,y3) -координаты товаров в кубе, r - расстояние между товарами в кубе. 

   Пусть первый игрок - это << Конкурент >>, а второй - << Фирма >>. Стратегии  игрока 1 расположены по строкам, а игрока 2 - по столбцам матрицы выигрышей. Рассмотрим алгоритм фиктивного разыгрывания на примере игры этих двух игроков (1 - << Конкурент >>, 2 - << Фирма >>) с нулевой суммой с функцией игры: (3.6.5). (3.6.5), (3.6.6)- наборы стратегий игроков.
      Разыгрывается игра с( ) – матрицей (3.6.7)
      В первой партии оба игрока выбирают совершенно произвольные чистые стратегии (например, первого столбца и первой строки соответственно). 
      Пусть векторы (3.6.8) - смешанные стратегии игроков 1 и 2 соответственно, тогда можно считать разумным следующее их поведение:

      Игрок 1 выбирает такую чистую стратегию i из набора своих 10 стратегий x, которая максимизирует его средний выигрыш (3.6.9), при условии, что игрок 2 использует свою смешанную стратегию .
      Игрок 2 выбирает такую чистую стратегию j из набора своих 10 стратегий y, которая минимизирует его средний проигрыш (3.6.10), при условии, что игрок 1 использует свою смешанную стратегию . Итак, предположим, что за первые k разыгрываний игрок 1 использовал i- ю стратегию , раз , а игрок 2 - j-ю стратегию , раз . Тогда в (k+1)-й стратегии игрок 1 будет использовать -ю стратегию , а 2 – свою - ю стратегию, - значение матричной игры. 
      Значение игры ограничено сверху и снизу: (3.6.11) 
      С помощью этого итеративного процесса находим приближенное решение задачи и .

    = (0,17;0,05;0,11;0,15;0,09;0,11;0,1;0,07;0,03;0,12);
    =(0,22;0,03;0,09;0,17;0,12;0,13;0,07;0,05;0,04;0,08).
    =134,126
 

4. Метод Брауна-Робинсона решения матричных игр

 
   Часто в практических задачах нет необходимости находить точное решение матричной игры. Достаточно найти приближённое решение, которое даёт средний выигрыш, близкий к цене игры и приближённые оптимальные стратегии игроков.
   Ориентировочное значение цены игры  может дать уже простой анализ матрицы выигрышей и определение нижней и верхней цен игры. Если они близки, то поисками точного решения заниматься не обязательно, так как достаточно выбрать чистые минимаксные стратегии. Если же они не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых рассмотрим метод итераций.
   Пусть разыгрывается матричная игра с матрицей размера . Идея метода – многократное фиктивное разыгрывание игры с заданной матрицей. Одно разыгрывание игры будем называть партией, число которых неограниченно.
   В 1-ой партии оба игрока выбирают совершенно произвольные чистые стратегии. Пусть  игрок 1 выбрал i-ю стратегию, а игрок 2 – j-ю стратегию. Во второй партии игрок 1 отвечает на ход игрока 2 той своей стратегией, которая даёт ему максимальный  выигрыш. В свою очередь, игрок 2, отвечает на этот ход игрока 1 своей стратегией, которая обращает его проигрыш в минимум. Далее третья партия.
   С ростом числа шагов процесса смешанные стратегии, которые приписываются игрокам, приближаются к их оптимальным стратегиям. Этот процесс приближённого нахождения оптимальных стратегий игроков называется итеративным , а его шаги – итерациями.
   Итак, предположим, что за первые разыгрываний игрок 1 использовал i-ю чистую стратегию раз (4.1), а игрок 2 j-ю чистую стратегию раз (4.2). Тогда их смешанными стратегиями будут векторы (4.3), (4.4).
   Игрок 1 следит за действиями игрока 2 и с  каждым своим ходом желает получить как можно больший выигрыш. Поэтому  в ответ на применение игроком 2 своей  смешанной стратегии , он будет использовать чистую стратегию , которая обеспечит ему лучший результат при разыгрывании (k+1)-ой партии. Игрок 2 поступает аналогично. В худшем случае каждый из  
 
 
 
 

них может  получить:

    (4.5)
   где - наибольшее  значение проигрыша игрока 2 и - наименьшее значение выигрыша игрока 1.
   Рассмотрим  отношения, которые определяют средние  значения проигрыша игрока 2 и выигрыша игрока 1:
   
(4.6)

   Пусть н - цена  матричной игры .  Её  значение будет больше выигрыша игрока 1, но меньше проигрыша игрока 2, т. е.
   
(4.7)

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

   Пример. Найти приближённое решение игры с матрицей
А=
.(4.9)

   Пусть игру начнёт игрок 2. Он произвольно  выбирает одну из своих чистых стратегий. Предположим, что он выбрал свою 1-ю стратегию, а игрок 1 отвечает своей 2-й стратегией. Занесём данные в таблицу. 

но-мер пар
тии
стратегия второго
игрока
выигрыш игрока 1 при его стратегиях стратегия первого
игрока
проигрыш  игрока 2 при его  стратегиях
u w n
1 2 3 1 2 3
1 1 0 4 2 2 4 1 2 4 1 5/2
   Таблица 1. Выбранные игроками стратегии и их выигрыши при них на первом шаге. 

   В столбце u находится наибольший средний выигрыш 4 игрока 1, полученный им в первой партии; в столбце w стоит наименьший средний проигрыш 1, полученный игроком 2 в первой партии; в столбце n находится среднее арифметическое n=(u+w)/2=5/2(4.10), т. е. приближенное значение цены игры, полученное в результате проигрывания одной партии.
Так как  игрок 1 выбрал 2-ю стратегию, то игрок 2 может проиграть:
    4, если применит свою 1-ю стратегию;
    1, если применит свою 2-ю стратегию;

    2, если  применит свою 3-ю стратегию.
   Поскольку он желает проиграть как можно  меньше, то в ответ применит свою 2-ю стратегию.
   Тогда первый игрок получит выигрыш  равный 3, 1, 0 соответственно при своих 1-й, 2-й, 3-й стратегиях, а его суммарный выигрыш за две партии составит:
    0+3=3 при его 1-й стратегии;
    4+1=5 при его 2-й стратегии;
    2+0=2 при его 3-й стратегии.
   Из  всех суммарных выигрышей наибольшим является 5, который получается при 2-й стратегии игрока 1. Значит, в этой партии он должен выбрать именно эту стратегию.
   При 1-й стратегии игрока 1 игрок 2 проигрывает 4, 1, 2 соответственно 1-й, 2-й, 3-й его  стратегиям, а суммарный проигрыш за обе партии составит:
    4+4=8 при его 1-й стратегии;
    1+1=2 при его 2-й стратегии;
    2+2=4 при его 3-й стратегии.
   Все полученные данные занесём в таблицу. В столбец u ставится наибольший суммарный выигрыш игрока 1 за две партии, деленный на число партий, т. е. 5/2; в столбец w ставится наименьший суммарный проигрыш игрока 2, деленный на число партий, т. е. 2/2; в столбец n ставится среднее арифметическое этих значений, т. е. 7/2. 

но-мер пар
тии
стратегия второго
игрока
выигрыш игрока 1 при его стратегиях стратегия первого
игрока
проигрыш  игрока 2 при его  стратегиях
u w n
1 2 3 1 2 3
1 2
1 2
0 3
4 5
2 2
2 2
4 8
1 2
2 4
4 5/2
1 2/2
5/2 7/2
   Таблица 2. Выбранные игроками стратегии и их выигрыши при них на первых двух шагах. 

   В третьей партии игрок 2 выбирает свою 2-ю стратегию, так как из всех суммарных проигрышей наименьшим является 2.
     Таким образом, продолжая этот  процесс далее, составим таблицу  разыгрываний игры за 20 итераций (партий). 
 
 
 

но-мер пар
тии
Страте- гия
второго
игрока
выигрыш игрока 1 при его стратегиях Страте- гия
первого
игрока
проигрыш  игрока 2 при его  стратегиях
u w n
1 2 3 1 2 3
1 2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1 2
2
2
3
3
1
3
3
3
3
3
2
2
2
2
2
2
2
3
0 3
6
9
10
11
11
12
13
14
15
16
19
22
25
28
31
34
37
38
4 5
6
7
9
11
15
17
19
21
23
25
26
27
27
29
30
31
32
34
2 2
2
2
5
8
10
13
16
19
22
25
25
25
25
25
25
25
25
28
2 2
1
1
1
1
2
2
2
2
2
2
2
2
2
2
1
1
1
1
4 8
8
8
8
8
12
16
20
24
28
32
36
40
44
48
48
48
48
48
1 2
5
8
11
14
15
16
17
18
19
20
21
22
23
24
27
30
33
36
2 4
5
6
7
8
10
12
14
16
18
20
22
24
26
28
29
30
31
32
4 5/2
6/3
9/4
10/5
11/6
15/7
17/8
19/9
21/10
23/11
25/12
26/13
27/14
27/15
29/16
31/17
34/18
37/19
38/20
1 2/2
5/3
6/4
7/5
8/6
10/7
12/8
14/9
16/10
18/11
20/12
21/13
22/14
23/15
24/16
27/17
30/18
31/19
32/20
5/2 7/2
11/6
15/8
17/10
19/12
25/14
27/16
33/18
37/20
41/22
45/24
47/26
49/28
50/30
53/32
58/34
64/36
68/38
70/40
   Таблица 3. Выбранные игроками стратегии и их выигрыши при них на 20 шагах.
       
   Из  таблицы видно, что в 20-ти проигранных  партиях стратегии 1, 2, 3 для второго  игрока встречаются соответственно 2, 10, 8 раз, следовательно, их относительные  частоты  равны 2/20, 10/20, 8/20. Стратегии 1, 2, 3 для игрока 1  встречаются соответственно 8, 12, 0 раз, следовательно, их относительные частоты равны 8/20, 12/20, 0, а приближённое значение цены игры равно 70/40.
   Таким образом, получили приближённое решение  игры: (4.11), (4.12), n=1,57.
   Такой итеративный процесс ведёт игроков  к цели медленно. Часто для получения  оптимальных стратегий, дающих игрокам  выигрыш, приходится проделывать сотни  итераций. При этом скорость сходимости заметно ухудшается с ростом размерности матрицы и ростом числа стратегий игроков. Это также является следствием не монотонности последовательностей и . Поэтому, практическая ценность этого метода имеет место, когда вычисления проводятся на достаточно быстродействующих вычислительных машинах. Но наряду с таким недостатком можно выделить и достоинства метода итераций:
    Этот метод даёт возможность найти ориентировочное значение цены игры и приближённо вычислить оптимальные стратегии игроков.
    Сложность и объём вычислений сравнительно слабо возрастают по мере увеличения числа стратегий игроков (m  и n).
 


5. Монотонный итеративный алгоритм решения матричных игр

 
   Предлагаемый  для рассмотрения алгоритм реализуется  только для одного игрока в отличие  от первого, который работает для  двух игроков. Алгоритм позволяет находить точно и приближенно оптимальную  стратегию игрока 1 и значение цены игры n. С помощью алгоритма можно   получить заданную  точность решения, причём число шагов, необходимых для достижения результатов, слабо зависит от размерности матрицы выигрышей.
   
   Особенность этого алгоритма в способности  генерировать строго монотонно возрастающую последовательность оценок цены игры, что не свойственно ранее предлагаемому алгоритму.
   Рассмотрим  смешанное расширение =(X,Y,K)(5.1) матричной игры ГА с матрицей А размера (m?n)(5.2). Процесс разыгрывания игры состоит из нескольких шагов. Пусть каждый из игроков имеет конечное число стратегий.
   Введём  следующие обозначения:
   аi – i-я строка матрицы выигрышей;
   xN=(x1N,x2N,…,xmN)(5.3) IX – m-мерный вектор,  приближение оптимальной стратеги первого игрока на N-шаге (N-номер шага);
   cN=( )(5.4) –n-мерный вектор, определяющий средний накопленный выигрыш на N-шаге. 
   Зададим начальные условия. Пусть на 0-шаге с0= , x0=(0,…, 1,…, 0)(5.6), где 1 занимает i0-ю позицию.
   Определим итеративный процесс  следующим образом: по известным векторам xN-1, cN-1   находим векторы   xN и cN , которые вычисляются по следующим формулам:
(5.7)

    где параметр 0?eN?1, а векторы     вводятся далее.
         Как отмечалось, вектор сN определяет средний накопленный выигрыш игрока 1 на N шаге. Компоненты этого вектора – это числа. В худшем случае игрок 1 может получить минимальное из этих чисел. Примем его за нижнюю оценку цену игры, которую обозначим:
   
. (5.8)

     Запомним  множество  индексов JN-1=( ), (k<n), на которых    
 
 

будет достигается этот минимум, т. е.
.(5.9)


   Далее рассмотрим подыгру  ГN игры   ГА с матрицей выигрышей АN={ }(5.10), i=1,…,m, jN-1IJN-1. Матрица выигрышей состоит из столбцов данной матрицы, номера которых определяются множеством индексов JN-1. В этой подыгре ГN находим одну из оптимальных смешанных стратегий игрока 1:  (5.11).
После нахождения , находим вектор (5.12) по правилу:
(5.13).

   И рассмотрим игру (2?n), в которой у игрока 1 две чистые стратегии, а у игрока 2 – n чистых стратегий. Эта игра задаётся матрицей (5.14), решая которую, находим вероятность использования игроком 1 своей стратегии. Это даёт нам коэффициент eN.
   Далее вычисляем xN, сN и переходим к следующему шагу. Процесс продолжаем до тех  пор, пока не выполнится равенство eN=0, потому что по теореме о минимаксе , а их равенство (что и нужно) достигается в этом случае, или пока не будет достигнута требуемая точность вычислений.  

   Пример. Решить  игру с матрицей А= (5.15).
   Итерация 0. 1. Пусть игрок 1 выбрал свою 1-ю стратегию, т. е. А0 = [0, 1, 2]. Тогда за начальные условия примем следующие: x0 = (1, 0, 0) – приближение оптимальной стратегии игрока 1; c0=a1=(0, 1, 2) – возможный выигрыш игрока 1.
   Найдём  множество индексов , на которых игрок 1 может получить, в худшем случае, наименьший выигрыш: , значит множество индексов J0={1}. Для этого индекса выигрыш равен 0. Это есть значение нижней оценки цены игры, т. е. .
   На  этом шаге определим, пользуясь начальными значениями, компоненты векторов . Для этого рассмотрим подыгру (5.16). Для этой подыгры оптимальной стратегией игрока 1 будет его 2-ая стратегия, так как она принесёт ему наибольший выигрыш.
   Обозначим её через  :  =(0, 1, 0)(5.17). Зная  , можем вычислить =0а1+1а2+0а3=а2=(4, 2, 1)(5.18).
   Найдём e1. Для этого рассмотрим подыгру (2?3) с матрицей (5.19).  Решая матрицу графическим способом, получаем, что e1=1/2.
   Проведённые вычисления позволяют найти значения векторов x1, c1:
   x1=1/2x0+1/2 =1/2(1, 0, 0)+1/2(0, 1, 0)=(1/2, 1/2, 0);(5.20)
   c1=1/2c0+1/2 =1/2(0, 1, 2)+1/2(4, 2, 1)=(2, 3/2, 3/2).(5.21)
   
   Итерация1. Так как e1 не равно 0, то процесс продолжается дальше. Теперь за начальные условия примем найденные значения векторов x1, c1. С их помощью вычисляем , которые с большей точностью будут близки к истинным оптимальным стратегиям игрока 1.
   Итак, пусть x1=(1/2, 1/2, 0),  c1=(2, 3/2, 3/2)(5.22).
     Найдём множество индексов  , на которых игрок 1 может получить наименьший выигрыш: , значит, J1={2,3}. Для этих индексов выигрыш равен 3/2. Это есть значение нижней оценки цены игры, т. е. . Заметим, что .
   Далее найдём компоненты векторов . Для этого рассмотрим подыгру (5.23). В силу симметричности матрицы ее решением будет вектор (1/2, 1/2), т. е. 1/2a1+1/2a2+0a3=
   =(4/2, 3/2, 3/2).(5.24)
   Вычислим  коэффициент e2. Для этого решим подыгру (2?3): (5.25). Стратегии игроков совпадают, поэтому e2=0. В этом случае цена игры совпадает со своим нижним значением, т. е. .  Возвращаемся к предыдущему шагу.
   Итак, оптимальной стратегией игрока 1 является x*=x1=(1/2, 1/2, 0) и  .Задача решена.
   На  первый взгляд алгоритм практически  трудно реализовать, так как не известно, какого размера будет получена матрица для подыгры ГN. Но на самом деле с вероятностью 1 на каждом шаге придётся решать подыгру размера не больше чем m?2.[9]
   
         Инженерами-программистами алгоритм был реализован на языке  программирования Фортран-IV. Вычислительные эксперименты, проведённые на ЭЦВМ ЕС-1030, показали,  что для игр размерности от 25?25 до 100?100, элементы, матрицы выигрышей которых были заполнены случайными числами, алгоритм позволяет найти искомое приближение за 100-1000 итераций, причём их число слабо зависит от размера матрицы. Для решения одной задачи машина затрачивает не дольше 8 минут. Ими же были разработаны различные модификации алгоритма. [9]
 

  6. Конструкторская часть

6.1 Разработка архитектуры программной системы

 
   При решении поставленной задачи оптимально использовать для представления  информационных материалов язык C++, который является языком высокого уровня и позволяет быстро и эффективно создавать приложения.
   Для реализации "такой-то программы" была выбрана среда программирования Nokia QT версии 4.5.0 фирмы Nokia, так как она предоставляет наиболее широкие возможности для программирования приложений для различных платформ.
   
   С++ – это язык для быстрого создания приложений. Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic или в других инструментах визуального проектирования. В QT также входят локальные библиотеки для работы с базами данных, библиотеки визуальных компонентов, и прочее хозяйство, необходимое для того, чтобы чувствовать себя совершенно уверенным при профессиональной разработке информационных систем или просто кросплатформеных приложений.
   Прежде  всего, QT c++ предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать. QT cодержит большой набор компонентов и классов, поэтому в QT должны быть прежде всего заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются – это имеет немаловажное значение и для конечных пользователей.
   Преимущества  С++ по сравнению с аналогичными программными продуктами.
    быстрота разработки приложения;
    высокая производительность разработанного приложения;
    низкие требования разработанного приложения к ресурсам компьютера;
    наращиваемость за счет встраивания новых компонент и инструментов в среду C++;
 
 
 
 
 
    возможность разработки новых компонент и  инструментов собственными средствами QT (QT поставляется с полным исходным кодом);
    удачная проработка иерархии объектов.
   Система программирования с++, рассчитана на программирование различных приложений и предоставляет большое количество компонентов для этого.
   К тому же работодателей интересует, прежде всего, скорость и качество создания программ, а эти характеристики может  обеспечить только среда визуального  проектирования, способная взять  на себя значительные объемы рутинной работы по подготовке приложений, а также согласовать деятельность группы постановщиков, кодировщиков, тестеров и технических писателей. Возможности QT C++ полностью отвечают подобным требованиям и подходят для создания систем любой сложности.
     

   В приложении приведена реализация итеративного метода Брауна-Робинсона решения  матричных игр в среде программирования QT 4.5.0 для платформы win32, на языке C++.
   Пользователь  вводит матрицу выигрышей размера  , где , .
   Далее машина запрашивает информацию о  том, кто из игроков начинает игру, какую стратегию он выбирает и  количество итераций.
   Во  второй таблице выводятся результаты разыгрывании игры за определённое число  итераций.
 

   

6.2 Разработка структуры данных

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

6.3 Разработка программного алгоритма

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

    Пользователь  ввел матрицу.
    Проверить, не являются ли все введенные элементы нулями?
    Если все элементы равны нулям, вывести сообщение и не продолжать работу.
    Найти минимальный элемент матрицы.
    Проверить наличие отрицательных элементов в матрице пользователя.
    Если есть отрицательные элементы, вычесть из них минимальный элемент, перезаполнить матрицу.
    Какой игрок ходит первым?
    Если первым ходит первый игрок, перейти к шагу 10, иначе к шагу 13
    Сформировать матрицу выигрышей первого игрока.
    Сформировать матрицу выигрышей второго игрока.
    Перейти к шагу 15
    Сформировать матрицу выигрышей второго игрока.
    Сформировать матрицу выигрышей первого игрока.
    Вывести информацию о выигрышах игроков на экран в виде таблицы.
 

     

Рисунок 1. Блок схема работы функции ‘PlayerOne’
 



 

 


 

/*Функция определения  следующего хода для игрока 1*/
int MainWindow::PlayerOne()
{
    int a2, Max;
    Max = this->win_plone[this->a][0]; 

    if(this->pl == 1)
        a2 = m;
    else
        a2 = n;
    int id = 0;
    for(int i = 0; i < a2; i++)
        if(this->win_plone[a][i] > Max)
        {
            Max = this->win_plone[a][i];
            id = i;
        }
    return id;// Max
}
/*Функция определения  следующего хода для игрока 2*/
int MainWindow::PlayerTwo()
{
    int a2, Min;
    Min = this->win_pltwo[this->a][0];
    if(this->pl == 1)
        a2 = n;
    else
        a2 = m;
    int id = 0;
    for(int i = 0; i < a2; i++)
        if(this->win_pltwo[a][i] < Min)
        {
            Min = this->win_pltwo[a][i];
            id = i;
        }

    return id;//Min
}
void MainWindow::StartBtn()
{
    this->m = this->ui->tableWidget->rowCount();
    this->n = this->ui->tableWidget->columnCount(); 

    /*
      Предположим, что:
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.