884

Теорія ігор

Лабораторная работа

Информатика, кибернетика и программирование

Навчитись графічно розв’язувати задачі з теорії ігор та обирати найкращі альтернативи за різними критеріями при певному значенні критерію оптимізму.

Украинкский

2013-01-06

255.5 KB

13 чел.

Міністерство освіти і науки, молоді та спорту України

Національний університет «Львівська політехніка»

Інститут компютерних наук та інформаційних технологій

                                    

Лабораторна робота

з дисципліни „ Математичні методи дослідження операцій ”

на тему : «Теорія ігор»

                                                                                                                   Виконав:

                                                                                                                         ст. гр. КН-25

                                                                                                               Дубаньовський Я. М.

                                                                                                                    Прийняв:

                                                                                                                   Асистент

                                                                                                                             Прокопів Ю.О

                                                                       

                                                                                 

Львів 2012

                                                 Мета роботи

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

Хід виконання роботи

Завдання 1:

Розвязати графічно гру з наступною матрицею:

 

В1

В2

В3

В4

В5

А1

16

8

10

12

4

А2

7

9

8

3

6

А3

2

9

4

1

5

А4

5

7

6

10

1

А5

3

7

9

9

3

А6

5

6

8

2

1

 

В1

В2

В3

В4

В5

а=min(Ai)

А1

16

8

10

12

4

4

А2

7

9

8

3

6

3

А3

2

9

4

1

5

1

А4

5

7

6

10

1

1

А5

3

7

9

9

3

3

А6

5

6

8

2

1

1

b=max(Bj)

16

9

10

12

6

 

Знаходимо гарантований виграш, що визначається нижньою ціною гри a = max(ai) = 4, яка вказує на максимально чисту стратегію А1. Верхня ціна гри b= min(bj) = 6.

а != b, отже ціна гри знаходиться в межах 4<=y<=6. Знаходимо розвязок гри в змішаних стратегіях. Це пояснюється тим, що гравці не можуть оголосити один одному свої справжні стратегії, вони приховують свої дії. Гру можна вирішити, якщо дозволити гравцям вибирати свої стратегії випадково (змішувати чисті стратегії).

Іноді на підставі простого розгляду матриці гри можна сказати, що деякі чисті стратегії можуть увійти в оптимальну змішану стратегію лише з нульовою ймовірністю.

Кажуть, що i-я стратегія 1-го гравця домінує його k-ю стратегію, якщо aij ≥ akj для всіх j Э N і хоча б для одного j aij > akj. У цьому випадку кажуть також, що i-я стратегія (або рядок) - домінуюча, k-я – домінуюча.

Кажуть, що j-я стратегія 2-го гравця домінує його l-ю стратегію, якщо для всіх j Э M  aij ≤ ail і хоча б для одного i aij < ail. У цьому випадку j-ю стратегію (стовпець) називають домінуючою, l-ю – домінуюча.

Стратегія А1 домінує над стратегією А4 ( всі елементи А1 >= A4), отже виключаємо 4 рядок з матриці. Імовірність:  р4=0.

Стратегія А1 домінує над стратегією А5 ( всі елементи А1 >= A5), отже виключаємо 5 рядок з матриці. Імовірність:  р5=0.

Стратегія А1 домінує над стратегією А6 ( всі елементи А1 >= A6), отже виключаємо 6 рядок з матриці. Імовірність:  р6=0.

Стратегія А2 домінує над стратегією А3 ( всі елементи А2 >= A3), отже виключаємо 3 рядок з матриці. Імовірність:  р3=0.

16

8

10

12

4

7

9

8

3

6

З позиції програшів гравця В стратегія В1 домінує над стратегією В4 (всі елементи стовпця 1 > елементів стовпця 4), отже виключаємо 1 стовпець матриці. Імовірність q=0.

З позиції програшів гравця В стратегія В2 домінує над стратегією 5 (всі елементи стовпця 2 > елементів стовпця 5), отже виключаємо 2 стовпець матриці. Імовірність q2=0.

З позиції програшів гравця В стратегія В3 домінує над стратегією 5 (всі елементи стовпця 3 > елементів стовпця 5), отже виключаємо 3 стовпець матриці. Імовірність q3=0.

12

4

3

6

Розвяжемо задачу геометрично:

М11) = (12 – 4)х1 + 4 =8х1 + 4

М21) = (3 – 6)х1 + 6 =-3х1 + 6

.

Завдання 2:

Обрати найкращі альтернативи за критеріями Вальда, Севіджа, Гурвіца, Лапласа при значенні коефіцієнту песимізму 0.5 в грі з природою, що задана матрицею:

 

П1

П2

П3

П4

П5

A1

10

25

3

6

12

A2

3

8

22

9

4

A3

12

6

21

10

9

A4

2

24

6

15

3

Критерій Лапласа:

Якщо імовірності станів природи правдоподібні, то для їхньої оцінки використовують принцип Лапласа, згідно з яким всі стани природи вважаються рівно імовірними.

q1 = q2 = ... = qn = 1/n.

qi = 1/5

Ai

П1

П2

П3

П4

П5

∑(aij)

A1

2

5

0.6

1.2

2.4

11.2

A2

0.6

1.6

4.4

1.8

0.8

9.2

A3

2.4

1.2

4.2

2

1.8

11.6

A4

0.4

4.8

1.2

3

0.6

10

pj

0.2

0.2

0.2

0.2

0.2

0

Вибираємо з (11.2; 9.2; 11.6; 10)  максимальний елемент max = 11.2

Висновок: вибираємо стратегію N=3.

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

Згідно з критерієм Вальда, за оптимальну стратегію приймається чиста стратегія, яка в найгірших умовах гарантує максимальний виграш, тобто

a = max(min aij)

Критерій Вальда орієнтує статистику на найбільш неблагополучні стани природи, тобто цей критерій виражає песимістичну оцінку ситуації.

Ai

П1

П2

П3

П4

П5

min(aij)

A1

10

25

3

6

12

3

A2

3

8

22

9

4

3

A3

12

6

21

10

9

6

A4

2

24

6

15

3

2

Вибираємо із (3,3,6,2) максимальний елемент max = 6.

Висновок: вибираємо стратегію N=3.

Критерій Севіджа:

Критерій мінімального ризику Севіджа рекомендує вибирати в якості оптимальної стратегії ту, при якій величина максимального ризику мінімізується в найгірших умовах, тобто забезпечується:

a = min(max rij)

Критерій Севіджа орієнтує статистику на найбільш несприятливі стани природи, тобто цей критерій виражає песимістичну оцінку ситуації.

Знаходимо матрицю ризиків.

Ризик – міра невідповідності між різними можливими результатами прийняття певних стратегій. Максимальний виграш в j-му стовпці bj = max(aij) характеризує благополучність стану природи.

1-й стовпець матриці ризиків:

r11 = 12 - 10 = 2; r21 = 12 - 3 = 9; r31 = 12 - 12 = 0; r41 = 12 - 2 = 10;

2-й стовпець матриці ризиків:

r12 = 25 - 25 = 0; r22 = 25 - 8 = 17; r32 = 25 - 6 = 19; r42 = 25 - 24 = 1;

3-й стовпець матриці ризиків:

r13 = 22 - 3 = 19; r23 = 22 - 22 = 0; r33 = 22 - 21 = 1; r43 = 22 - 6 = 16;

4-й стовпець матриці ризиків:

r14 = 15 - 6= 9; r24 = 15 - 9 = 6; r34 = 15 - 10 = 5; r44 = 15 - 15 = 0;

5-й стовпець матриці ризиків:

r15 = 12 - 12 = 0; r25 = 12 - 4 = 8; r35 = 12 - 9 = 3; r45 = 12 - 3 = 9;

Ai

П1

П2

П3

П4

П5

A1

2

0

19

9

0

A2

9

17

0

6

8

A3

0

19

1

5

3

A4

10

1

16

0

9

Ai

П1

П2

П3

П4

П5

max(aij)

A1

2

0

19

9

0

19

A2

9

17

0

6

8

17

A3

0

19

1

5

3

19

A4

10

1

16

0

9

16

Вибираємо з (19,17,19,16,) мінімальний елемент min=16

Висновок: вибираємо стратегію N=4.

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

Критерій Гурвіца є критерієм песимізму – оптимізму. За оптимальну приймається та стратегія, для якої виконується співвідношення:

max(si)

де si = y min(aij) + (1-y)max(aij)

При у=1 отримаєм критерій Вальде, при у=0 – оптимістичний критерій (максімакс).

Критерій Гурвіца враховує можливість як і найгіршого, так і найкращого для людини стану природи.

Вибір Y: чим гірші наслідки помилкових рішень, тим більше бажання застрахуватись від помилок, тим Y ближче до 1.

Розрахунок Si:

Згідно умови завдання коефіцієнт y=0.5;

s1 = 0.5•3+(1-0.5)•25 = 14

s2 = 0.5•3+(1-0.5)•22 = 12.5

s3 = 0.5•6+(1-0.5)•21 = 13.5

s4 = 0.5•2+(1-0.5)•24 = 13

Ai

П1

П2

П3

П4

П5

min(aij)

max(aij)

y min(aij) + (1-y)max(aij)

A1

10

25

3

6

12

3

25

14

A2

3

8

22

9

4

3

22

12.5

A3

12

6

21

10

9

6

21

13.5

A4

2

24

6

15

3

2

24

13

Вибираємо з (14,12.5,13.5,13,) максимальний елемент max=14

Висновок: вибираємо стратегію N=1.

Таким чином, у результаті рішення статистичної гри за різними критеріями частіше за інших рекомендувалася стратегія A3.

Висновок

Під час виконання цієї лабораторної роботи я навчився розвязувати графічно задачі з теорії ігор та обирати найкращі альтернативи за критеріями Вальда, Севіджа, Гурвіца та Лапласа.


 

А также другие работы, которые могут Вас заинтересовать

24179. Время правления Ярослава Мудрого 30.48 KB
  его сын Ярослав посаженный княжить в Новгороде наняв варягов отказался платить традиционную дань 2000 гривен 1 гривна = ок. Но в современной историографии есть версия что их убил Ярослав Мудрый мудрый в старину означало хитрый. В это время варяги нанятые Ярославом ведут себя бесцеремонно в Новгороде и новгородцы убивают их часть.
24180. Внешняя и внутренняя политика в годы правления Владимира Мономаха 28.06 KB
  Немудрено ведь годы правления Владимира Мономаха фактически начались еще при князе Всеволоде его отце и он активно участвовал во всех государственных делах при Святополке. Внутренняя политика в годы правления Владимира Мономаха. Князь сразу же принял решение расширить и обновить Русскую правду которую стали называть в результате его решительных действий Устав Владимира Мономаха.
24181. Причины феодальной раздробленности Древнерусского государства 42.71 KB
  Причины феодальной раздробленности Древнерусского государства Для возникновения феодальной раздробленности были экономические социальные и этнические причины. Появление изгоев и закупов свидетельствует о наличии расслоения в старой свободной общине и создании категорий крестьян вынужденных вступать в поземельную зависимость не от государства а от частных господ. На этом более высоком уровне феодализации политическая раздробленность Древнерусского государства была закономерной и вела к укреплению его функций в интересах отдельных земель...
24182. Положительные и отрицательные последствия феодальной раздробленности 17.63 KB
  Положительные: 1 трудности жизни на юге заставляли людей уходить на север и восток страны заселяя и осваивая эти прежде неразвитые окраины древней Руси. Значение периода феодальной раздробленности в русской истории У политической раздробленности как у любого исторического явления есть и положительные и отрицательные стороны: 1. Положительные: исчезла пропасть между центрами и окраинами; последние превратились в самостоятельные княжества которые по уровню хозяйственного социальнополитического и культурного развития превосходили Киевскую...
24183. Сущность социальных отношений 47 KB
  Социальные нормы это средства социальной регуляции поведения индивидов и групп. Социальная роль это социальная функция модель поведения объективно заданная социальной позицией личности в системе социальных и межличностных отношений. С социальной стратификацией связано понятие социальной мобильности. Под социальной мобильностью понимается любой переход индивида или социального объекта ценности то есть всего того что создано или модифицировано человеческой деятельностью из одной социальной позиции в другую.
24184. Классификация социальных процессов 50 KB
  В тех случаях когда цели и способы их достижения у индивида или группы не могут удовлетворить индивида компромисса достичь не удается и индивид не приспосабливается к новым условиям окружающей среды. Ассимиляция ссимиляция это процесс взаимного культурного проникновения через который личности и группы приходят к разделяемой всеми участниками процесса общей культуре. Это всегда двухсторонний процесс в котором каждая группа имеет возможности для проникновения своей культуры в другие группы пропорционально своему размеру престижу и другим...
24185. Применение имитационного моделирования 47.5 KB
  Имитационное моделирование это частный случай математического моделирования. Применение имитационного моделирования К имитационному моделированию прибегают когда: дорого или невозможно экспериментировать на реальном объекте; невозможно построить аналитическую модель: в системе есть время причинные связи последствие нелинейности стохастические случайные переменные; необходимо сымитировать поведение системы во времени. Цель имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов...
24186. АЛЛЕРГИЯ 276 KB
  В поддержании аллергического иммунного ответа важны долговременные клетки памяти в т. Схема 1 Классификация аллергических реакций: Влмфзависимые Активные Немедленная по ДжеллКумбсу гуморальные и анафилаксия 1й тип реагины Тлмфзависимые Пассивные Отсроченная 5 ч 2й цитолиз клеточные АТ и клетки Замедленная дни 3й имм. Неклеточные структуры тканей коллагена миелина базальной мембраны почек вовлекаются соседние клетки вторично. Медиаторы: гаммаинтерферон...
24187. ПАТОЛОГИЯ ВОДНО-СОЛЕВОГО ОБМЕНА 289.5 KB
  Эфферентная часть: основной механизм регуляция почек диуреза: а Вегетативная нервная симпатическая адреналин чревный нерв снижение диуреза; б Гипоталамогипофизарная регуляция: супраоптические и паравентрикулярные ядра АДГ задний гипофиз почечные канальцы гиалуронидаза активация реабсорбции тоже снижение диуреза; в передний гипофиз АКТГ надпочечники альдостерон почечные канальцы сукцинатдегидрогеназа усиление реабсорбции Na и пассивно воды г диэнцефальный мозг адреногломерулотропин ...