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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


Реферат/Курсовая Решение матричных игр методом Брауна

Информация:

Тип работы: Реферат/Курсовая. Добавлен: 17.12.2012. Сдан: 2011. Страниц: 16. Уникальность по antiplagiat.ru: < 30%

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


Содержание 
 
 

 

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

     «Теория игр – раздел математики, предметом  которого является изучение математических моделей принятия оптимальных решений  в условиях конфликта...».
     Математическая  теория игр способна не только указать  оптимальный путь к решению некоторых проблем, но и прогнозировать их исход. Матричные игры серьёзно изучаются специалистами, так как они довольно просты и к ним могут быть сведены игры общего вида. Поэтому теория матричных игр  хорошо развита, существуют различные методы поиска решения игр.
     Но  в большинстве случаев решение  матричных игр представляет собой  трудный и громоздкий процесс. Есть примеры, когда даже для матриц размера 3?3, процесс поиска решения довольно трудоёмкий.
     Кроме того, выигрыши игроков в каждой ситуации не всегда определяются точными измерениями. В процессе сбора данных об изучаемом явлении, анализа этих данных и введения при построении модели различных предположений накапливаются ошибки. Они же могут выражаться числами в матрице выигрышей. Поэтому точность в определении значения игры и оптимальных стратегий игроков оправдана не всегда.
     А также, следует заметить, что погрешность  в оценке игроком своего выигрыша не может привести к практически  серьёзным последствиям и небольшое  отклонение игрока от оптимальной стратегии  не влечёт за собой существенного изменения в его выигрыше.
     Поэтому возникает потребность в разработке численных методов решения матричных  игр. В настоящее время в теории игр известны несколько способов приближенного решения матричных  игр. 
 


      Основные  понятия
 
   Будем рассматривать только парные антагонистические  игры, т. е. игры в которых участвуют  только два игрока – две противоборствующие стороны и выигрыш одного из игроков  равен проигрышу другого. Кроме  того, будем считать, что каждый игрок  имеет лишь конечное число стратегий:
U1={a1, a2,..., am} – множество стратегий первого игрока;
U2={b1, b2, ... bn} – множество стратегий второго игрока.
      Будем называть эти стратегии чистыми  в отличие от смешанных, которые  будут введены далее.
      Множество U1?U2 – декартово произведение множеств стратегий игроков называется множеством ситуаций в игре. Для каждой ситуации должен быть определён итог игры. Так как игра антагонистическая  достаточно определить выигрыш а одного из игроков, скажем первого. Тогда выигрыш второго игрока будет равен (-а). Таким образом, имеем матрицу выигрышей первого игрока (для второго игрока матрица выигрышей будет -А):
A=
     Определение. Система Г={U1, U2, A} называется матричной игрой двух лиц.
     Разыгрывание  матричной игры сводится к выбору игроком 1 i-ой строчки матрицы выигрышей, а игроком 2 - j-го столбца. После этого игрок 1 получает выигрыш равный аij, а игрок 2 – (-аij).
     При правильной игре игрок 1 может всегда гарантировать себе выигрыш, который  назовём нижним значением цены игры. Обозначим его: 
.

     В свою очередь, игрок 2 может гарантировать  себе проигрыш, который назовём верхним  значением цены игры. Обозначим его:
     
.

     Чистые  стратегии  i* и j*, соответствующие называются максиминной и минимаксной стратегиями.
     Лемма 1. В матричной игре .
     Определение. Ситуация (i*,j*) называется ситуацией равновесия, если для iI1,2,…,m, jI1,2,…,n выполняется неравенство:
     
.

     Ситуация равновесия это такая ситуация, от которой ни одному из игроков не выгодно отклоняться. В этом случае стратегии i*, j* называют оптимальными стратегиями игроков.
     Чтобы такая ситуация существовала необходимо и достаточно равенство верхней  и нижней цен игры, т. е. .
     Определение. Пусть(i*,j*) -  ситуацией равновесия в матричной игре. Тогда число называется значением или ценой игры.
     Например, в игре ГА с матрицей А= существует не одна ситуация равновесия. В данной игре их две: (1, 1) и (1, 3).
     Множество всех ситуаций равновесия в матричной  игре обозначим через Z(Г).
     Лемма о масштабе 1. Пусть Г и Г/ - две матричные игры с матрицей выигрышей А={aij} и A/={a/ij}, причём А/=bА+ a, b=const, a=const.
Тогда Z(Г)=Z(Г/) и n/= bn+a (где n/ - значение цены игры Г/, n - значение цены игры Г).
      Эта лемма имеет большое практическое значение, так как большинство  алгоритмов для решения матричных  игр основано на предположении, что  матрица игры положительна. В случае, когда матрица имеет неположительные элементы, следует прибавить ко всем элементам матрицы число наибольшее по абсолютной величине, из всех отрицательных элементов.
     Существуют  игры, в которых ситуации равновесия в чистых стратегиях не существует. Тогда игрокам бывает не выгодно придерживаться своих минимаксных и максиминных стратегий, так как они могут получить больший выигрыш, отклонившись от них. В этом случае игрокам разумно действовать случайно, т. е. выбирать стратегии произвольно и не сообщать о выборе сопернику. Такие стратегии игроков будем называть смешанными.
     Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.
     Так если игрок 1 имеет m чистых стратегий, то его смешанная стратегия x – это набор чисел x=(x1,x2,…,xm), которые удовлетворяют соотношениям , =1. Аналогичным образом определяется смешанная стратегия y игрока 2.
     Определение. Оптимальными стратегиями игроков называются стратегии, которые при многократном повторении обеспечивают игрокам  максимально возможный средний выигрыш (или минимально возможный средний проигрыш).
     Таким образом, процесс игры при использовании  игроками своих смешанных стратегий  превращается в случайное испытание, которое назовём ситуацией в смешанных стратегиях. Она обозначается так (x, y), где x и y – смешанные стратегии игроков 1 и 2 соответственно.
     Для ситуации в смешанных стратегиях каждый игрок определяет для себя средний выигрыш, который выражается в виде математического ожидания его выигрышей: .
     От  матричной игры пришли к новой  игре ={X, Y, K}, где X, Y – множества смешанных стратегий игроков, а K – функция выигрышей в смешанных стратегиях. Такую игру называют смешанным расширением матричной игры.
       Цели игроков остаются прежними: игрок 1 желает получить максимальный  выигрыш, а игрок 2 стремится  свести свой проигрыш к минимуму. Поэтому для смешанного расширения  игры, аналогичным образом определяются  верхнее и нижнее значение цены игры, только теперь игроки выбирают свои смешанные стратегии. Обозначим их:
     

       В этом случае остаётся справедливой  лемма 1, т. е. .
     Определение. Ситуация (x*,y*) в игре образует ситуацию равновесия, если для всех x IX, yIY выполняется равенство:
     K(x, y*)?K(x*,y*)?K(x*,y).
     Чтобы ситуация равновесия в смешанном  расширении игры существовала необходимо и достаточно равенство верхней  и нижней цен игры, т. е. , где n - цена игры.
     Для случая смешанного расширения игры также справедлива лемма о масштабе.
     Лемма о масштабе 2.
     Пусть ГА и ГА/ - две матричные игры А/=aА+ В, , a=const, В – матрица с одинаковыми элементами b, т. е. b ij=b для всех i, j.
Тогда Z( )=Z(ГА/) и nА/= anА+b (где nА/ - значение цены игры ГА/, nА - значение цены игры ГА).
      Теорема. В смешанном расширении матричной игры всегда существует ситуация равновесия.
 

      Метод Брауна решения систем нелинейных уравнений
        Суть  метода
     Часто в практических задачах нет необходимости находить точное решение матричной игры. Достаточно найти приближённое решение, которое даёт средний выигрыш, близкий к цене игры и приближённые оптимальные стратегии игроков.
     Ориентировочное значение цены игры может дать уже  простой анализ матрицы выигрышей и определение нижней и верхней цен игры. Если они близки, то поисками точного решения заниматься не обязательно, так как достаточно выбрать чистые минимаксные стратегии. Если же они не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых рассмотрим метод итераций.
     Пусть разыгрывается матричная игра ГА с матрицей А={aij} размера (m?n). Идея метода – многократное фиктивное разыгрывание игры с заданной матрицей. Одно разыгрывание игры будем называть партией, число которых неограниченно.
     В 1-ой партии оба игрока выбирают совершенно произвольные чистые стратегии. Пусть  игрок 1 выбрал i-ю стратегию, а игрок 2 – j-ю стратегию. Во второй партии игрок 1 отвечает на ход игрока 2 той своей стратегией, которая даёт ему максимальный выигрыш. В свою очередь, игрок 2, отвечает на этот ход игрока 1 своей стратегией, которая обращает его проигрыш в минимум. Далее третья партия.
     С ростом числа шагов процесса смешанные  стратегии, которые приписываются  игрокам, приближаются к их оптимальным стратегиям. Этот процесс приближённого нахождения оптимальных стратегий игроков называется итеративным, а его шаги – итерациями.
     Итак, предположим, что за первые k разыгрываний игрок 1 использовал i-ю чистую стратегию ik раз (i=1,…,m), а игрок 2 j-ю чистую стратегию раз (j=1,…,n). Тогда их смешанными стратегиями будут векторы .
       Игрок 1 следит за действиями  игрока 2 и с каждым своим ходом  желает получить как можно больший выигрыш. Поэтому в ответ на применение игроком 2 своей смешанной стратегии yk, он будет использовать чистую стратегию ik+1 , которая обеспечит ему лучший результат при разыгрывании (k+1)-ой партии. Игрок 2 поступает аналогично. В худшем случае каждый из них может получить:

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

     Пусть ? - цена  матричной игры ГА. Её значение будет больше выигрыша игрока 1, но меньше проигрыша игрока 2, т. е.
       . (1)
     Таким образом, получен итеративный процесс, позволяющий находить приближённое решение матричной игры, при этом степень близости приближения к истинному значению игры определяется длиной интервала
     
.

     Сходимость  алгоритма гарантируется следующей  теоремой.
Теорема.    .
      Указывая  на наличие квадратичной сходимости метода Брауна, отмечают, что рассчитывать на его большую по сравнению с методом Ньютона эффективность в смысле вычислительных затрат можно лишь в случае, когда фигурирующие в нем частные производные заменяются разностными отношениями.
     Пусть задано число ?>0. Требуется найти значение игры с точностью до величины ? , а также ? –максиминную и ? –минимаксную смешанные стратегии игроков.
     Метод Брауна состоит в многократном фиктивном  разыгрывании матричной игры, при  котором игроки по определенным правилам выбирают свои чистые стратегии. Пусть за k повторений игры первый игрок ri раз выбрал стратегию i? I=1,…,m, а второй lj раз выбрал стратегию j, j=1,…,n. Векторы частот выбора чистых стратегий

Являются смешанными стратегиями игроков.
        Описание  алгоритма
Определим итерационный процесс Брауна.
Шаг 1. Игроки выбирают произвольно стратегии i1 и j1.
     Пусть за k повторений игры первый игрок выбрал стратегии i1,…,ik, а второй – стратегии j1,…,jk. При этом p(k) и q(k) – соответствующие векторы частот.
Шаг k+1. Игроки выбирают стратегии ik+1 и jk+1 из условий


     Каждый  игрок выбирает свою чистую стратегию  как наилучший ответ на соответствующий  вектор частот партнера. Если наилучших  ответов несколько, то выбирается любой  из них.
     Покажем, что v1(k) и v2(k) – оценки для значения v матричной игры:

Действительно

     Для доказательства сходимости последовательностей {v1(k)}, {v2(k)} к значению игры v нам потребуется обобщенный итерационный процесс.
     Пусть c(0) – два вектора, удовлетворяющие условию Возьмем

     Пусть определены стратегии  и векторы c(0), c(1),…, c(k),  d(0), d(1),…, d(k). Возьмем

     И положим для всех i=1,…,m, j=1,…,n

     Таким образом, вектор c(k+1) есть сумма вектора c(0) и столбцов матрицы A с номерами j1,…, jk. Нетрудно видеть, что

     При нулевых векторах c(0) и d(0) построенный итерационный процесс совпадает с процессом Брауна. Поскольку множества и могут соержать более одного элемента последовательности {c(k)}, {d(k)} определяются в ходе итерационного процесса не однозначно.
Определим, как  и ранее, последовательности величин

     Далее будет доказана их сходимость к значению игры v для любых векторов c(0), d(0).
Из неравенств

Следует, что

Отсюда
(5.8)

Покажем, что
(5.9)

Будем использовать обозначение

   С помощью  него условие  можно записать в виде
        Теоретическое обоснование
Определение Будем говорить, что i-ая строка (j-ый столбец)матрицы A существенна (существенен) на отрезке шагов [s, s+t], если для некоторого шага t’   it’=i (jt’=j).
Лемма1  Пусть все строки и столбцыматрицы A существенны на отрезке шагов Тогда

Доказательство. Покажем сначала, что в условиях леммы справедливы неравенства

     Докажем (5.11) Пусть для l-ой строки выполнено равенство . Из условия луммы вытекает, что найдется такой номер шага t’ что Тогда


     Поскольку все последние разности не превосходят  at. Неравенство (5.12) доказывается аналогично. Покажем также, что справедливо неравенство

Пусть vT – значение игры с матрицей AT, транспонированной к A. Тогда

Отсюда

     Домножая  это неравенство на s+t выводим (5.13). Неравенство (5.10) получается сложением неравенств (5.11)-(5.13). Лемма доказана.
Лемма2.  Для произвольной матрицы A и произвольного ?>0 найдется такой номер шага k0, что для любых последовательностей c(k), d(k), k=0,1,… итерационного процесса
Доказательство. Утверждение леммы верно для 1?1 матриц A, поскольку тогда c(k)=d(k) для всех k?1. Примем, что лемма верна для всех подматриц матрицы A и докажем, что она верна и для A. Выберем k1 таким образом, чтобы для любых последовательностей c1(k), d1(k), k=0,1,… итерационного процесса, соответствующего подматрице A1= (aij)i?I,j?J, полученной из A вычеркиванием строки или столбца, было выполнено неравенство

     Докажем, что если для матрицы A некоторая строка (столбец) несущественна (несущественен) на отрезке [s,s+k1], то справдедливо неравенство

     Предположим, например, что подматрица A1 получается вычеркиванием из A несущественной l-й строки. Положим I={1,…,m}\{l},

     Поскольку l-я строка матрицы несущественна, и в итерационном процессе можно взять   Итерациооный процесс для матрицы A1 можно продолжать и при k>k1.
На основании  выбора k1   

и неравенство (5.14) доказано.
     Мы  теперь можем показать, что для  любых последовательностей c(k), d(k), k=0,1,… итерационного процесса   при
     Рассмотрим  целое k>k1 и представим его в виде k=(q+t)k1 , где 0?q<1, а t>0 – целое (qk1 – остаток от деления k на k1).
Случай 1. Найдется такое целое положительное число h?t , что все строки и столбцы матрицы A на отрезке [(q+h-1)k1,(q+h)k1] существенны. Беря наибольшее из таких h имеем:

     Это неравенство получено повторным применением неравенства (5.14), поскольку на каждом из отрезков

Некоторая строка или столбец матрицы A несущественны.
Из леммы1 на основании выбора h имеем

Из (5.15) и (5.16) получаем

Случай 2. В каждом отрезке [(q+h-1)k1,(q+h)k1], h=1,…,t, некоторая строка или столбец несущественны. Следовательно, как и при выводе (5.15),

     В обоих случаях, используя неравенство  tk1?k, получим Лемма доказана.
     Из  леммы2 вытекает неравенство (5.9) и сходимость последовательностей v1(k),v2(k), k=0,1,… к значению цены иигры v.
     Вернемся  к методу Брауна. Сформулируем правило  остановки. Пусть задано число ?>0. Будем останавливаться на шаге k0, когда впервые выполнено неравенство

     Из (5.7) и (5.17) следует, что величины v1(k0),v2(k0) приближают значение v матричной игры с точностью до ?. Покажем, что p(k0) – ?-максиминная стратегия первого игрока. Действительно,

Аналогично, q(k0) – ?-минимаксная стратегия второго игрока.
Теорема. В методе Брауна а любые предельные точки p0, q0 последовательностей {p(k)}, {q(k)} являются оптимальными смешанными стратегиями игроков.
Доказательство. Сходимость последовательностей {v1(k)} и {v2(k)} к значению игры v вытекает из леммы2. Пусть p0 – любая предельная точка последовательности {p(k)}. Покажем, что p0 – оптимальная смешанная стратегия первого игрока. Действительно, поскольку последовательность {p(k)} принадлежит компакту P, без потери общности (выделяя соответствующую подпоследовательность) можно считать, что она сходится к p0
и т.д.................


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


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


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


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


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