Методы решения матричных игр (на примере игры «Зачет»)

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

им. Н. П. ОГАРЕВА»

 

Факультет довузовской подготовки и среднего профессионального образования

 

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

 

Методы решения матричных  игр

(на примере игры «Зачет»)

 

Студентки 309 группы      _________            _____________        М. А. Пешевой

                                                                                     (подпись)                                          (дата)

Специальность 230105 «Программное обеспечение  вычислительной техники и автоматизированных систем»

Обозначение курсовой работы        КР-02069964-230105-09-13

Руководитель работы

Преподаватель                  __________           _____________         Д. Р. Зеленова                               

                                                (подпись)                                      (дата)                          

                                                                                        Оценка:

 

Саранск 2013

 

Федеральное государственное  бюджетное образовательное учреждение  среднего профессионального образования

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. Н. П. ОГАРЁВА»

Факультет довузовской подготовки и

среднего профессионального  образования

 

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ (ПРОЕКТ)

 

Студент Пешева Мария Александровна

1 Тема «Методы решения матричных игр (на примере игры «Зачет»)».

2 Срок представления работы  защите________________________ 

3 Исходные данные для научного исследования: теоретический материал по дисциплине «Математические методы», формулировка задач для практического решения, методические рекомендации по выполнению курсовой работы.

4 Содержание курсовой работы (проекта)

4.1  Введение

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

4.3 Практическая часть

4.4. Заключение

4.5. Список использованных  источников

 

Руководитель работы (проекта) _____________         _________________

                                                                     подпись, дата             инициалы, фамилия

Задание принял к исполнению____________________________

                                                               дата, подпись 

 

Содержание

Введение                                                                                                      4

I Теоретическая часть                                                                   6

   1. Матричные игры                                                                                  6

   1.1 Определение матричной игры                                                                   6

   1.2 Принцип максимина (минимакса)                                                              8

   1.3 Смешанные стратегии                                                                               16

   1.4 Смешанное расширение игры                                                                  17

   2. Методы решения матричных игр                                                     20

   2.1 Доминирование                                                                                         20

   2.2 Решение 2 2 –игр                                                                                           23

   2.3 Графический метод решения игр 2 nи  m 2                                              26

   2.4 Сведение матричной игры к задаче линейного программирования      36

II Практическая часть                                                                  41

   1. Семейный спор                                                                                   41

   2. Студент – преподаватель (игра «Зачет»)                                         44

Заключение                                                                                                46

Список используемой литературы                                                          47

 

 

 

Введение

Теория игр имеет не очень длинную историю. Решающий поворот вееразвитии произошел  в 1928 году благодаря американцу Дж. фон Нейману.

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

Теория игр и решений  получила сильный импульс в годы второй мировой войны, когда был  введен термин "исследование операций". В типичной задаче этой тематики рассматривалась "дуэль" между самолетом и  патрульного поиска в определенном районе; другой было необходимо изыскать наилучший способ уйти от наблюдения. Математики Группы исследования операций по противолодочной защите, используя  материалы фон Неймана, относящиеся  к 1928 году, решили эту задачу.

Статистические критерии для принятия решений в условиях неопределенности были обоснованы математиком  из Колумбийского университета А. Вальдом в 1939 году. Они определяют "максимин" - критерий, которым пользуются в ожидании наихудшего результата. Л.Гурвиц и Л.Сэвидж разработали и другие критерии, подобные "критериям сожаления", где субъективные вероятности могут заставить увеличить или уменьшить риск.

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

1. изучить теорию матричных игр;

2. рассмотреть методы матричных игр на примере игры «Зачёт»;

3. сделать соответствующие выводы.

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

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

 

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

 

1. Матричные игры
1. Определение матричной игры

Описание игры включает перечень участников конфликта, задание множеств возможных действий и оценок эффективности этих действий для каждого из них. Участников конфликта принято называть игроками. Обозначим множество всех игроков через N. Далее будем считать множество N конечным. Игроков принято различать по их номерам, то есть считать N={1,2,…,n}. Множество возможных действий i-го игрока обозначим через Si. Элементы этого множества принято называть стратегиями. Каждый игрок имеет не менее двух различных стратегий, в противном случае его действия заранее определены и фактически он не участвует в игре. В результате выбора i-м игроком стратегии ∈ складывается система стратегий ()=s, которая называется ситуацией. Эффективность возможных действий игроков мы будем оценивать теми выигрышами, которые игроки получают в каждой ситуации s. выигрышигрока I в ситуации s обычно обозначается через (s). Функция (s), определенная на множестве всех ситуаций, называется функцией выигрыша игрока i.Цель i-го игрока – максимизация своей функции выигрыша.

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

                                  Г =<N,{}i∈N, {} i∈N>.                                           (1)

Определение 1. Игра (1) называется антагонистической, если в ней участвуют два игрока и значения функций выигрыша в каждой ситуации равны по величине и противоположны по знаку.

Следовательно, для задания антагонистической игры достаточно указать функцию выигрыша только одного из игроков. ((s)=(s)). Поэтому под антагонистической игрой понимается совокупность

Г=<А, В, Н>,

где А и В – соответственно множества стратегий игроков I и II, а Н – функция выигрыша игрока I.

Определение 2. Конечная антагонистическая  игра в нормальной форме называется матричной игрой.

Это название можно объяснить следующей возможностью описания игр такого рода. Поскольку множество возможных действий каждого из игроков в этом случае конечно, можно положить А{1,2,…,m}, В{1,2,…,n}, где m и n – соответственно число стратегий игроков I и II, а значения функций Н представить в виде следующей матрицы:

H =

Здесь =Н( i, j) – выигрыш игрока I в ситуации ( i, j), где i- номер строки (стратегия игрока I), j – номер столбца (стратегия игрока II). Матрица Н называется матрицей игры или матрицей выигрышей.

Матричная игра полностью  определяется своей матрицей выигрышей. Поэтому часто вместо выражения  “игра с матрицей выигрышей Н” употребляется выражение “игра  Н”.

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

 

2. Принцип максимина (минимакса)

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

Пусть игрок I выбрал стратегию A, тогда игрок II выберет такую стратегию j∈B, которая максимизирует его выигрыш и тем самым минимизирует выигрыш его противника. Стратегия игрока I, обеспечивающая ему наибольший выигрыш из всех возможных, независимо отдействий противника будет состоять в выборе такого A, для которого минимальный выигрыш будет наибольшим, то есть

= .

Величину 

                                       (3)

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

 ≥ v (Г),  j∈B.                                        (4)

Аналогично стратегия  , определяемая равенством

= = (Г),

Называется минимаксной  стратегией игрока II, а соответствующее значение (Г) (или просто ) – верхним значением (верхней ценой) игры.

Если игрок II придерживается данной стратегии, то его проигрыш будет не больше минимаксного значения, то есть

 ≤  (Г), j∈ А.                                      (5)

Полагая, что в неравенстве  (4) j = , а в выражении (5) i = , получим:

 ≤ H(, ) ≤ .       (6)

Принцип, которого придерживается игрок I, называется принципом максимина, так как его гарантированный выигрыш равен величине (3). Игрок II также придерживается этого принципа, так как

= -.

Из не равенства (6) следует, что во всякой матричной игре ≤ . При этом возможны два следующих случая:

 < ; = .                                              (7)

В первом случае игрок I может обеспечить себе выигрыш , игрок II в состоянии ему не дать больше, чем . Вопрос о разделе между игроками разности - (а в рассмотренном случае она положительна) остается таким образом, открытым. Это влечет за собой неопределенность в действиях игроков.

Пример 1

.

Нахождение  и   матрицы Н может быть проведено по следующей схеме:

.

                   

                                    

 

 

 

 

 

< ; 2-я строка – максиминная стратегия; 1-й столбец – минимаксная стратегия. Применение максиминой стратегий приводит к выигрышу игрока I, равному (разность    достается игроку II, но можно привести пример, когда эта разность достигается игроку I). Однако игрок Iв игре , отклоняясь от максиминной и выбирая первую стратегию, может выиграть 4 > 3  (приусловии, что игрок IIпридерживается минимаксной стратегии). Но игрок II, разгадав намерения игрока I, может выбрать свою четвертую стратегию и тем самым наказать его (даст ему 2> 3). Игрок Iв свою очередь может изменить решение и выбрать такую стратегию, при которой будет наказан игрок II, и так далее и это будет происходить во всех играх, в которых .