Реферат: Теория игр

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

«Омскийпромышленно-экономический колледж»

КУРСОВАЯРАБОТА

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

Тема:«Теория игр»

Выполнил:

КаримовРуслан Ринатович

3 курс, БП 2- 117

Руководитель:

БелгородцеваНаталья Александровна

Оценка:________________

Датазащиты:___________

2010

Содержание

Введение

Обзор литературы

1. Основные понятия теории игр

2. Игры с противодействием и нулевой суммой

3. Графический метод решения игровых задач снулевой суммой

3.1 Решение задач графическим методом

4. Сведение задач теории игр к задачам линейногопрограммирования

4.1 Решение задач

5. Игры с природой (без противодействия)

5.1 Решение задач

Заключение

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

Введение

Проблемавыполнения различных вычислений была актуальна во все времена. По мере развитияобщественно-экономических отношений усложнялись поставленные задачи, которыедля своего решения требовали разработки новых методов вычислений. На сменупростейшим арифметическим и геометрическим вычислениям пришли алгебраические итригонометрические вычисления. Организация современного производства требует нетолько наличия современных станков и оборудования, но и разработки новыхтехнологических процессов и современных методов управления производством. Длярешения каждой из поставленных задач разрабатываются математические модели, анализируякоторые удается найти наилучшее решение поставленной задачи. Созданиематематической модели – сложная кропотливая работа, которая в современных условияхпод силу коллективам разработчиков. Для создания математической модели одного итого же объекта различные коллективы могут использовать различныйматематический аппарат. После создания математической моделиспециалистами-аналитиками за дело принимаются специалисты-программисты, которыереализуют созданную модель в виде программных кодов. Далее с математическоймоделью работают специалисты-практики. Целенаправленно воздействуя на модель,они изучают ее поведение и подбирают оптимальный режим работы для реальногообъекта. Одной из таких моделей является игровая модель и поиск стратегийповедений в условиях полной или частичной неопределенности. В очень редких(исключительных) случаях для игровых моделей можно определить количественнуюоценку или указать оптимальное решение. В игровых моделях не ставится задачанайти какое-то числовое решение, а требуется лишь или очертить областьвозможных решений, или предоставить некоторые дополнительные сведения овозможном развитии событий и рекомендовать правила поведения.

Обзорлитературы

Для написаниякурсовой работы по дисциплине «Математические методы» на тему «Теория игр» явоспользовался следующей литературой:

-«Математические методы в программировании »: / Агальцов В.П., Волдайская И.В.Учебник: – М.: ИД «ФОРУМ»: ИНФРА-М, 2006. – 224с.: ил. – (Профессиональноеобразование). – (Учимся программировать).

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

-«Математическиеметоды: Учебник» / Партика Т.Л., Попов И.И. – М: ФОРУМ: ИНФРА, 2005.

-«Математическоепрограммирование» / Костевич Л., издательство «Новое знание», 2003.

В одной изкниг например «Математические методы в программировании»: / Агальцов В.П.,Волдайская И.В. Учебник: – М.: ИД «ФОРУМ»: ИНФРА-М, 2006 написано понятней,если сравнивать с другими книгами, которыми я пользовался. Но в этой книге естьтемы, которые отсутствуют или объяснены без теории, а на конкретном примере итогда сложнее понять, о чем идет речь данной теме. Тогда я обращаюсь к другимисточникам литературы в них, конечно, есть теория, но она сложнее и болееуглубленная. В одном из источников мне понравилась тема «Игры с природой (безпротиводействия)» и я решил изучить ее самостоятельно.

1.        Основныепонятия теории игр

Цель теорииигр – выработка рекомендаций для различного поведения игроков в конфликтнойситуации, т.е. выбор оптимальной стратегии для каждого из них. Различают двабольших класса игровых моделей: модели без противодействия (или их еще называют«играми с природой») и модели с противодействием (действия конкурентов нарынке).

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

Развитие игрыво времени представляется как ряд последовательных «ходов». Ходы могут бытьсознательные и случайные. Случайный ход – результат, получаемый не решениемигрока, а каким либо механизмом случайного выбора (покупательский спрос, задержкас поставкой материалов и т.п.). Сознательный ход – выбор игроком одного извозможных вариантов действия (стратегий) и принятие решения о его осуществлении.

Конфликтнаяже ситуация, строго говоря, развивается спонтанно.

Участникамиигры (конфликтной ситуации) могут быть минимум два человека (парная игра) илинесколько человек (множественная игра). Игра развивается по оговореннымправилами. Игроки по очереди делают свои ходы. Естественно, перед каждым ходомигрок может или сохранить предыдущую стратегию или применить новую стратегию.Если игрок при выборе очередного хода придерживаются каких-либо правил, тотакая игра носит название стратегической. Однако игрок во время игры можетменять вариант своего поведения (но не правил), т.е. сменить стратегию.

Возможныеварианты (исходы) игры сводятся в прямоугольную таблицу (табл. 1.1) – платежнуюматрицу, в которой строки соответствуют различным стратегиям игрока А, столбцы– стратегиям игрока В, ai j называется выигрыш первого игрока.

Таблица 1.1

 Стратегии В1 В2 … В n А1 a11 a12 … a1n А2 a21 a22 … a2n … … … … … А m am1 am2 … amn

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

Стратегия,приносящая игроку максимальный выигрыш, называется оптимальной. Для нахожденияоптимальной стратегии необходимо проанализировать все возможные стратегии ирассчитывать на то, что разумный противник на каждую из них будет отвечатьтакой, при которой выигрыш игрока А минимален. Обычно минимальные числа вкаждой строке обозначаются α i и выписываются в виде добавочного столбца матрицы(табл. 1.2). В каждой строке будет свое α i = min aij. Предпочтительной дляигрока А является стратегия, при которой α i обращается в максимум,т.е.

α = max (min aij),

где α – гарантированныйвыигрыш (максимин).

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

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

β = min (max aij),

которое даетминимаксный выигрыш, или минимакс.

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

Если α =β = С, то число С называют чистой ценой игры или седловой точкой.

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

Таблица 2

В1 В2 … В n α i А1 a11 a12 … a1n α 1 А2 a21 a22 … a2n α 2 … … … … … … А m am1 am2 … amn α i βi β1 β2 … βn

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

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

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

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

2.        Игрыс противодействием и нулевой суммой

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

/>Пусть фирма А разработала четырестратегии, а фирма В – пять стратегий.

/>То есть фирма А — А1; А2; А3; А4 Аi, где i = 1,4.

/>/>Фирма В соответственно — В1; В2; В3; В4;В5 Вj, где j= 1,5.

Каждая фирмаот реализации своей стратегии предполагает получить какой-то доход (табл. 2.1).

Таблица 2.1

Стратегии В1 В2 В3 В4 В5 А1 5 8 7 5 4 А2 1 10 5 5 6 А3 2 4 3 6 2 А4 3 5 4 4 3

Если фирма А выберетпервую стратегию, то минимальный доход составит 4. Минимальный доход от второйстратегии – 1; от третьей – 2; от четвертой – 3. У фирмы В имеется в наличиипять стратегий. Использование первой стратегии обернется убытком в 1 единицу;второй (убыток) – 4; третьей – 3, четвертой – 4 и пятой – 2.

На первыйвзгляд фирма А должна избрать вторую стратегию (А2), чтобы получить выигрыш 10,но в ответ вторая фирма изберет первую стратегию (В1) и выигрыш фирмы Асоставит только 1.

Поэтому цельпервой фирмы можно сформулировать так: получить максимальный доход из возможныхминимальных. Введем в табл. 2.1 дополнительную строку и дополнительный столбец,в которых укажем возможные минимальные прибыли и максимальные (табл. 2.2).

Таблица 2.2

Стратегии В1 В2 В3 В4 В5 Минимальная прибыль фирмы А А1 5 8 7 5 4  4 А2 1 10 5 5 6  1 А3 2 4 3 6 2  2 А4 3 5 4 4 3  3 Максимальный убыток фирмы В 5 10 7 6 6

Исходя изданных (табл. 2.2) фирме А надо придерживаться стратегии А1, а фирме В –стратегии В1. Таким образом, гарантированный минимальный доход фирмы Асоставит 4, а минимально возможный убыток, который понесет фирма В, составит 5(минимально возможный проигрыш).

Минимальныйгарантированный выигрыш называется нижней ценой игры. При плохой игре фирмы Ввыигрыш может быть и большим.

Минимальновозможный проигрыш называется верхней ценой игры.

Для нашегопримера нижняя цена игры составляет 4 (минимальный гарантированный выигрышфирмы А), а верхняя цена игры – 5 (минимально возможный проигрыш фирмы В).Приведенные выше рассуждения хороши, если конкурирующая фирма заранее не знает,как себя поведет противник. Если конкурирующая фирма ознакомлена с планамиконкурента, то она может выбрать другую стратегию (отличную от осторожнойстратегии) и получить больший выигрыш (доход).

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

На практикеиногда случается, что нижняя цена игры равна верхней цене игры. В этом случаеговорят об устойчивых стратегиях игроков (конкурирующих фирм) или о задачах сседловой точкой. Задача с седловой точкой представлена в (табл. 2.3).

Таблица 2.3

Стратегии В1 В2 В3 В4 В5 Минимальная прибыль фирмы А А1 4 8 7 5 4  4 А2 1 10 5 5 6  1 А3 2 4 3 6 2  2 А4 3 5 4 4 3  3 Максимальный убыток фирмы В 4 10 7 6 6

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

Если игроваязадача не имеет седловой точки, то на практике конкурирующие фирмы (игроки)используют смешанные стратегии, т.е. попеременно используют две или болеестратегий. В этом случае использование фирмой А нескольких стратегий можнозаписать как сумму вероятностей использования каждой стратегии Sa= p1+ p2+ …+ pm .

Соответственно,использование нескольких стратегий фирмой В можно записать Sb= q1+ q2+ …+ qn. Поэтому в общем случаеисследование игровой модели сводится к определению вероятностей использованияконкретных стратегий каждой фирмой (игроком).

3.Графический метод решения игровых задач с нулевой суммой

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

Воспользуемсятабл. 2.1.

Строка(стратегия) А1 является доминирующей по отношению к строке (стратегии) А4, таккак содержит элементы, большие соответствующих элементов строки А4.Соответственно строка А4 является поглощаемой и из дальнейшего рассмотренияудаляется (табл. 3.1).

Таблица 3.1

Первый шагупрощения таблицы

Стратегии В1 В2 В3 В4 В5 А1 5 8 7 5 4 А2 1 10 5 5 6 А3 2 4 3 6 2

Первыйстолбец является доминирующим по отношению ко второму, третьему и четвертомустолбцам (поглощаемым). Поступаем аналогично (табл. 3.2).

Таблица 3.2

Второй шагупрощения таблицы

Стратегии В1 В5 А1 5 4 А2 1 6 А3 2 2

Еще разрассматриваем строки. Первая строка поглощает третью строку. Поглощаемые строки(столбцы) содержат самые плохие стратегии. Окончательно получим (табл. 3.3).

Таблица 3.3

Третий шагупрощения таблицы

Стратегии В1 В5 А1 5 4 А2 1 6

Вероятностьиспользования первой фирмой первой стратегии обозначим через p1. Тогда вероятностьиспользования второй стратегии первым игроком будет p2 = 1- p1. Ожидаемый выигрышфирмы А от применения

/> (3.1)

вторымигроком первой стратегии составит:

Аналогичнымспособом получим ожидаемый выигрыш фирмы А от применения вторым игроком:

/>(3.2)

В выражения (3.1)и (3.2) подставим конкретные значения.

/>

/>

На оси хотложим две точки 0 и 1. Через эти точки проведем прямые линии, параллельныеоси у. Затем в первое выражение подставим 0 вместо p1, а потом – единицу. Ипо двум точкам построим прямую линию.

Аналогичнопостроим вторую прямую линию. Пересечение двух прямых линий и даст решениезадачи (рис. 3.1).

/> /> /> /> /> />   /> /> />

Рис. 3.1. Графическийспособ определения стратегий фирмы  А

4p1 + 1= — 2p1 + 6

4p1 + 2p1 = — 1 + 6

6p1 = 5

p1 = 0,83

Итак, вероятностьиспользования первой стратегии фирмой А составляет 0,83  (p1 = 0,83), а второй стратегии p2 = 1 – 0,83 – соответственно 0,17    (p2 = 0,17).

Аналогичноопределим оптимальную стратегию поведения фирмы В:

Пусть у1 –вероятность выбора второй игрой 5 стратегией, у2 — 6 стратегией. (p4 + p5 = 1, p5 = 1- p4)

(a11 – a12) · у1 + a12 = (5 – 4) у1 + 4 = у1+ 4;

(a21 – a22) · у1 + a22 = (1 – 6) у1 + 6 = -5у1 + 6.

/>

Рис. 3.2. Графическийспособ определения стратегий фирмы  В

у1 + 4 = -5у1 + 6

6 у1 = 2

у1 = 0,33

Вероятность использованияпервой стратегии фирмой В составляет   0,33 (у1 = 0,33), а второй стратегии у2=1- 0,33 – соответственно 0,67 (у2 = 0,67).

3.1Решение задач графическим методом

Пример 1: Рассмотримигру заданной платежной матрицей:

/> /> /> /> /> /> /> /> /> /> /> <td/> <td/> /> /> />/>/> /> /> /> /> /> /> /> /> /> />

4×5

  /> /> /> />

Решение:

Проверим естьли седловая точка :

α = max (2,2,3,2) = 3

β = min (7,6,6,4,5) = 4 α ≠β

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

Невыгодные стратегии для первого игрока: 4, 2 Невыгодные стратегии для второго игрока: 1, 2, 3

/>

/> /> /> /> /> /> /> /> /> />

 p1

  /> /> />

 1 – p1

  /> /> /> /> />

 p4

 

Пусть p1 – вероятность с которой первыйигрок должен   применять 1 стратегию, p3 – вероятность применения 3стратегией, p3=1- p1.

Ожидаемыйвыигрыш 1 игрока, если второй выбрал 4 стратегию:

p1 · 4 + (1 — p1) · 3 = p1 + 3;

Ожидаемыйвыигрыш 1 игрока, если второй выбрал 5 стратегию:

p1 · 2 + (1 — p1) · 5 = -3 p1 + 5;

/>

  p1 + 3 = -3p1 + 5

  4 p1 = 2

  p1 = 1/2, p3 =1/2 .

Первомуигроку для получения гарантированного выигрыша 3,5 (1/2+3) рекомендуетсячередовать стратегии 1 и 3.

Рассмотримвторого игрока.

Пусть p4 – вероятность выбора вторымигроком 4 стратегией, p5 — 5 стратегией. (p4 + p5 = 1, p5 = 1- p4)

Ожидаемыепроигрыш второго игрока, если первый выберет 1 стратегию.

p4 · 4 + (1- p4) · 2 = 2 p4 + 2

Ожидаемыепроигрыш второго игрока, если первый выберет 3 стратегию.

p4 · 3 + (1- p4) · 5 = -2 p4 + 5

/>

2p4  + 2 = -2p4  +5

4p4  =3

p4  =3/4

p5  =1/4

ν = 3/4 · 2 + 2 = 3,5

Ответ: Из 4игр 3 надо сыграть 4 стратегией, 1 игру – 5 стратегией, и тогда проигрыш будетне больше 3,5, для первого игрока 1 надо сыграть 2 стратегией и 1 – второйстратегией.

Пример 2: Решитьигру, заданную матрицей

/>

/>

/>

Решение:

Проверим еслили седловая точка:

α = max (2,4) = 4

β = min (6,5) = 5 α ≠β

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

Ожидаемыйвыигрыш 1 игрока если второй выбрал 1 стратегию:

А1 · 2 + (1 — А1) · 6 = -4А1 + 6;

Ожидаемыйвыигрыш 1 игрока если второй выбрал 2 стратегию:

А1 · 5 + (1 — p1) · 4 = А1 + 4;

/>

  — 4А1 + 6 = А1+ 4

  — 4А1+ А1 = 4 – 6

   — 5А1=- 2

    А1=2/5, А2= 3/5.

Первомуигроку для получения гарантированного выигрыша 4/>,

(2/5+4)рекомендуется играть 1 стратегией.

Рассмотримвторого игрока.

Пусть В1 –вероятность выбора второй игрой 4 стратегией,

(В1 + В2 = 1,В2 = 1- В1)

Ожидаемыйпроигрыш второго игрока, если первый выберет 1 стратегию.

В1 · 2 + (1-В1) · 5 = — 3 В1 + 5

Ожидаемыйпроигрыш второго игрока, если первый выберет 2 стратегию.

В1 · 6 + (1-В1) · 4 = 2 В1 + 4

/>

  — 3В1 + 5 = 2 В1+ 4

  — 3В1– 2 В1 = 4 – 5

   — 5В1=- 1

    В1=1/5, В2= 4/5.

    ν = 1/5 · 2 + 4 = 4/>

Ответ: Из 2игр 2 надо сыграть 1 стратегией, 1 игру – 2 стратегией, и тогда проигрыш будетне больше 4/>.

Пример 3: Решитьигру, заданную матрицей

/>

Проверим еслили седловая точка:

α = max (7,6) = 7

β = min (10,9,9) = 9 α ≠β

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

Невыгодная стратегия для второго игрока: 3

 p1

  />/> /> /> /> /> /> /> />

 1 – p1

  /> />

 p4

  <td/>

 1 – p4

 

Ожидаемый выигрыш 1 игрока, есливторой выбрал 1 стратегию:

 p1 · 7 + (1 — p1) · 10 = -3p1+ 10;

 

Ожидаемыйвыигрыш 1 игрока, если второй выбрал 2 стратегию:

p1 · 9 + (1 — p1) · 6 = 3 p1 + 6;

/>

-3p1 + 10 = 3p1 + 6

 -3p1 — 3p1 = -10 + 6

 -6p1= -4

  p1 = 2/3, p2 =1/3 .

Первомуигроку для получения гарантированного выигрыша 7/>, (2/3+7) рекомендуется играть 1стратегией.

Рассмотримвторого игрока.

Ожидаемыепроигрыш второго игрока если первый выберет 1 стратегию.

p4 · 7 + (1- p4) · 9 = -2 p4 + 9

Ожидаемыепроигрыш второго игрока если первый выберет 2 стратегию.

p4 · 10 + (1- p4) · 6 = 4 p4 + 6

/>

-2p4 + 9 = 4p4 + 6

 -2p4 — 4p4 = 6 – 9

 -6p4= -3

  р4 =1/2, p5 =1/2 .

Ответ: Из 2игр (для первого) 2 надо сыграть 3 стратегией и 1 – 3 стратегией, (для второго)1 надо сыграть 2 стратегией и 1 – 2 стратегией.

Пример 4: Решитьигру, заданную матрицей

/>

Проверим еслили седловая точка:

α = max (5,4,2,1) = 5

β = min (6,8) = 6 α ≠β

седловойточки нет, игра в чистой стратегии не решается. Найдем смешанную стратегиюигроков.

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

Невыгодная стратегия для первого игрока: 2,3

/>

/> /> /> /> /> /> /> /> />

 p1

  /> /> />

 1 — p1

  /> />

 р4

  <td/>

 1 – p4

 

Ожидаемый выигрыш 1 игрока, есливторой выбрал 1 стратегию:

 

p1 · 6 + (1 — p1) · 1 = 5 p1 + 1;

Ожидаемый выигрыш 1 игрока, есливторой выбрал 2 стратегию:

 

p1 · 5 + (1 — p1) · 8 = -3 p1 + 8;

/>

5 p1 + 1 = -3p1+ 8

 5 p1 + 3p1= 8 – 1

 8 p1= 7

  p1= 7/8, p2 =1/8 .

Рассмотримвторого игрока.

Ожидаемыепроигрыш второго игрока, если первый выберет 1 стратегию.p4 · 6 + (1- p4) · 5 = p4 + 5

Ожидаемыепроигрыш второго игрока, если первый выберет 2 стратегию.

p4· 1 + (1- p4) · 8 = -7 p4 + 8

/>

p4 + 5 = -7p4+ 8

 p4 + 7 p4= 8 – 5

 8 p4= 3

  р4 = 3/8, p5 =5/8 .

 u = />.

Ответ: Из 4игр (для первого) 7 надо сыграть 8 стратегией и 1 – 8, (для второго) 3 надосыграть 8 стратегией и 5 – 8.

4. Сведениезадач теории игр к задачам линейного

программирования

Предположим,что цена игры положительна (u > 0). Если это не так, то согласно свойству 6всегда можно подобрать такое число с, прибавление которого ко всем элементамматрицы выигрышей даёт матрицу с положительными элементами, и следовательно, сположительным значением цены игры. При этом оптимальные смешанные стратегииобоих игроков не изменяются.

Свойство 1.Тройка (хо, yо, u) является решением игры G = (Х,Y, А) тогда итолько тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y, кА+а), где а –любое вещественное число, к > 0.

Свойство 2.Для того, чтобы хо = (/>) была оптимальной смешаннойстратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточновыполнение следующих неравенств

/> (j = />) />

Аналогичнодля игрока 2: чтобы yо = (/>, ...,/>, ...,/>) была оптимальной смешаннойстратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

/> (i = />) />

Из последнегосвойства вытекает: чтобы установить, является ли предполагаемые (х, y) и u решением матричной игры,достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другойстороны, найдя неотрицательные решения неравенств (*) и (**) совместно соследующими уравнениями

/>, /> />

получимрешение матричной игры.

Итак, пустьдана матричная игра с матрицей А порядка m х n. Согласно свойству 7оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков1 и 2 и цена игры u должны удовлетворять соотношениям.

/> />

/> />

Разделим всеуравнения и неравенства в (4.4) и (4.5) на u (это можно сделать, т.к.по предположению u > 0) и введём обозначения:

/> />, /> />,

Тогда (1) и(2) перепишется в виде:

/>, />, />, />,

/>, />, />, />.

Посколькупервый игрок стремится найти такие значения хi и, следовательно, pi, чтобы цена игры uбыла максимальной, то решение первой задачи сводится к нахождению такихнеотрицательных значений pi />, при которых

/>, />. />

Посколькувторой игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры u была наименьшей, торешение второй задачи сводится к нахождению таких неотрицательных значений qj, />, при которых

/>, />. />

Формулы (3) и(4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив этизадачи, получим значения pi />, qj /> и u.Тогда смешанныестратегии, т.е. xi и yj получаются по формулам:

/> />

4.1Решение задач

Пример 5: Найтирешение игры, определяемой матрицей.

/>

Решение.

Составимтеперь пару взаимно-двойственных задач :

/> />

Решим вторуюиз них

Б.п.  q1  q2  q3  q4  q5  q6 Решение  å Отношение

/>

 -1  -1  -1  0  0  0  0  -3

/> q4

 1  2  0  1  0  0  1  5  —  q5  1  0  1  0  1  0  1  4

 />

 q6  2  1  0  0  0  1  1  5  — Б.п.  q1  q2  q3  q4  q5  q6 Решение  å Отношение

/>

 0  -1  0  0  1  0  1  1

/>/> q4

 1  2  0  1  0  0  1  5

 />

 q3  1  0  1  0  1  0  1  4  —  q6  2  1  0  0  0  1  1  5

 />

Б.п.  q1  q2  q3  q4  q5  q6 Решение  å Отношение

/>

 />

 0  0

 />

 1  0

 />

 />

 q2

 />

 1  0

 />

 0  0

 />

 />

 q3  1  0  1  0  1  0  1  4  q6

 />

 0  0

/>

 0  1

 />

 />

Изоптимальной симплекс-таблицы следует, что/>

(q1, q2, q3) = (0;/>; 1),

а изсоотношений двойственности следует, что

( p1, p2, p3) = (/>; 1; 0).

Следовательно,цена игры с платёжной матрицей А1 равна

/>. />,

а игры сплатёжной матрицей А:

/>.

При этомоптимальные стратегии игроков имеют вид:

Х = (х1, х2,х3) = (uр1;uр2;uр3)= />= />

Y = (y1, y2, y3) = (uq1; uq2; uq3) = />= />.

5. Игры сприродой (без противодействия)

В играх спротиводействием фирме А (одному игроку) противостоит другая фирма – В (игрок).Фирма В выбирает целенаправленную стратегию поведения с тем, чтобы уменьшитьвыигрыш фирмы А (следовательно, и свой проигрыш).

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

1.        КритерийВальде (пессимистический).

Всоответствии с этим критерием следует применять самую осторожную стратегию,которая сведет к минимуму вероятность (риск) проигрыша и доставит минимальнуюприбыль. Эта стратегия обеспечивается критерием:

max (min a ij ).(5.1)

где минимумвыбирается по каждой строке.

То есть этоткритерий совпадает с нижней ценой игры.

2.        Критериймаксимума (оптимистический).

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

max (max a ij ).(5.2)

где максимумвыбирается по каждой строке.

3.        КритерийГурвица.

КритерийГурвица занимает промежуточное значение между критерием Вальде и критериеммаксимума. Сам игрок определяет вероятность своего «везения»

max(α min a ij+ (1- α) max a ij ) .(5.3)

Ответственноелицо, принимающее решение, определяет значение коэффициента α. Если потеримогут быть весьма значительными, то значение коэффициента α приближается кединице, иначе к 0.

4.        КритерийСэвиджа.

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

r ij= max a ij — a ij.(5.4)

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

min(max (max a ij — a ij).(5.5)

где максимумвыбирается в каждом конкретном столбце.

Для примеравозьмем таблицу стратегий (табл. 5.1) и составим для нее таблицу рисков (табл.5.2).

Если фирма(игрок) выберет стратегию А1, а природа реализует стратегию В1, то фирмаполучит максимально возможную прибыль 5 (недополученная прибыль составит 0).Фирма угадала состояние природы. Но если природа реализует стратегию В4, тофирма вместо максимально возможной прибыли 12 получит прибыль 5, анедополученная прибыль составит 7.

Таблица 5.1

Таблица стратегий

Стратегии В1 В2 В3 В4 В5 А1 5 8 7 5 4 А2 1 10 5 5 6 А3 2 4 3 6 2 А4 3 5 4 12 3 max a ij 5 10 7 12 6

Таблица 5.2

Таблицарисков

Стратегии В1 В2 В3 В4 В5 А1 2 7 2 А2 4 2 7 А3 3 6 4 6 4 А4 2 5 3 3

5.1 Решениезадач

Пример 1: Швейнаяфабрика на летний сезон может реализовать два вида костюмов: 1200 костюмов поцене 520 руб. и 200 костюмов по цене 1000 руб., если погода будет жаркой. Еслипогода будет холодной, то фабрика может реализовать 650 костюмов первого вида и700 костюмов второго вида.

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

Решение:

Швейная фабрикарасполагает двумя стратегиями: А1 — погода будет жаркой и А2 – погода будетхолодной.

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

1200 · 520 +200 · 1000 = 624 000 + 200 000 = 824 000 руб.

Если фабрикавоспользуется первой стратегией, но погода будет холодной, то прибыль фабрикисоставит:

650 · 520 +200 · 1000 – (1200 – 650) · 520 = 338 000 + 200 000 – 286 000 =252 000 руб.

Если фабрикавоспользуется второй стратегией и погода действительно будет холодной, топрибыль фабрики составит:

650 · 520 +700 · 1000 = 338 000 + 700 000 = 1 038 000 руб.

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

650 · 520 +200 · 1000 – (700 – 200) · 1000 = 338 000 + 200 000 – 500 000 =38 000 руб.

Составим матрицуприбыли (таб. 5.3).

Таблица 5.3

Матрицаприбыли

Стратегии В1 В2 А1 824 000 252 000 А2 38 000 1 038 000

α = max (252 000; 38 000) =252 000 руб.

β = min (824 000; 1 038000) = 824 000 руб.

Такимобразом, цена игры находится в диапазоне от 252 000 руб. до 824 000руб.

Минимальныйгарантированный доход швейной фабрики составит 252 000 руб., но возможен идоход в 824 000 руб.

Определимплан выпуска изделий швейной фабрикой. Вероятность выбора стратегии А1обозначим через х1, а вероятность выбора стратегий А2 – через х2. Учитывая, чтох2 = 1 — х1, можем записать:

(a11 – a12)· х1 + a12 = (824 000 – 38 000)· х1 + 38 000 = 786 000 х1 + 38 000;

(a21 – a22)· х1 + a22 = (252 000 –1 038 000) · х1 + 1 038 000 = -786 000 х1 + 1 038 000;

786 000 х1 +786 000 х1 = 1 038 000 – 38 000

1 572000 х1 = 1 000 000

х1 = 0,64; х2= 1 – 0,64х2 = 0,36;

0,64 (1200;200) + 0,36 (650; 700) = (1002; 380).

Цена игрысоставит: 786 000 х1 + 38 000 = 541 040 руб.

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

Определимкритерии.

1.        КритерийВальде:

max(min a ij) = max (38 000; 252 000) = 252 000 руб.

Швейнойфабрике целесообразно использовать стратегию А1 .

2.        Критериймаксимума:

max(max a ij ) = max (824 000; 1 038 000) = 1 038 000 руб.

Швейнойфабрике целесообразно использовать стратегию А2 .

3.        КритерийГурвица:

пусть α= 0,4, тогда для стратегии А1

α min a ij + (1- α) max a ij =0,4 · 252 000 + (1 – 0,4) · 824 000 = 595 200 руб.

для стратегииА2

α min a ij + (1 — α) max a ij = 0,4 · 38 000 + (1 – 0,4) · 1 038 000 = 638 000 руб.

Швейнойфабрике целесообразно использовать стратегию А2 .

4.        КритерийСэвиджа:

Максимальныйэлемент в первом столбце – 824 000, во втором столбце –1 038 000.

Матрицарисков будет иметь вид:

/>

Швейнойфабрике целесообразно использовать стратегию А1 или А2 .

Заключение

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

Списоклитературы

1. « Математические методы в программировании »:/ Агальцов В.П., Волдайская И.В. Учебник: – М.: ИД «ФОРУМ»: ИНФРА-М, 2006.– 224с.: ил. –(Профессиональное образование). – (Учимся программировать).

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

3. «Математические методы: Учебник» / Партика Т.Л.,Попов И.И. – М: ФОРУМ: ИНФРА, 2005.

4.«Математическое программирование» / КостевичЛ., издательство «Новое знание», 2003.