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.

Висновок

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


 

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

81535. Регуляция водно-солевого обмена. Строение и функции альдостерона и вазопрессина 199.48 KB
  Основные гормоны участвующие в тонкой регуляции водносолевого баланса и действующие на дистальные извитые канальцы и собирательные трубочки почек: антидиуретический гормон АДГ альдостерон и предсердный натриуретический фактор ПНФ. Антидиуретический гормон Антидиуретический гормон АДГ или вазопрессин пептид с молекулярной массой около 1100 Д содержащий 9 аминокислот соединённых одним дисульфидным мостиком. АДГ синтезируется в нейронах гипоталамуса в виде предшественника препрогормона который поступает в аппарат Гольджи и...
81536. Система ренин-ангиотензин-альдостерон. Биохимические механизмы возникновения почечной гипертонии, отеков, дегидратации 105.02 KB
  Главным механизмом регуляции синтеза и секреции альдостерона служит система ренинангиотензин. Субстратом для ренина служит ангиотензиноген. Ангиотензиноген α2глобулин содержащий более чем 400 аминокислотных остатков.
81537. Роль гормонов в регуляции обмена кальция и фосфатов (паратгормон, кальцитонин). Причины и проявления гипо- и гиперпаратироидизма 106.8 KB
  Паратгормон Паратгормон ПТГ одноцепочечный полипептид состоящий из 84 аминокислотных остатков около 95 кД действие которого направлено на повышение концентрации ионов кальция и снижение концентрации фосфатов в плазме крови. Скорость распада гормона уменьшается при низкой концентрации ионов кальция и увеличивается если концентрация ионов кальция высока. Секреция ПТГ регулируется уровнем ионов кальция в плазме: гормон секретируется в ответ на снижение концентрации кальция в крови.
81538. Строение, биосинтез и механизм действия кальцитриола. Причины и проявление рахита 137.84 KB
  Действие гормона направлено на повышение концентрации кальция в плазме крови. Низкая концентрация фосфатов и ионов Са2 в крови также ускоряет синтез кальцитриола причём ионы кальция действуют опосредованно через паратгормон. Так например в клетках кишечника кальцитриол индуцирует синтез Са2переносящих белков которые обеспечивают всасывание ионов кальция и фосфатов из полости кишечника в эпителиальную клетку кишечника и далее транспорт из клетки в кровь благодаря чему концентрация ионов кальция во внеклеточной жидкости поддерживается на...
81539. Строение и секреция кортикостероидов. Изменения катаболизма при гипо- и гиперкортицизме 159.94 KB
  Гормоны коры надпочечников кортикостероиды. В коре надпочечников синтезируется более 40 различных стероидов различающихся по структуре и биологической активности. В коре надпочечников образуются предшественники андрогенов из которых наиболее активный дегидроэпиандростерон ДЭА и слабый андростендион. Самый мощный андроген надпочечников тестостерон синтезируется в надпочечниках в небольшом количестве.
81540. Регуляция синтезами секреции гормонов по принципу обратной связи 126.07 KB
  Поддержание уровня гормонов в организме обеспечивает механизм отрицательной обратной связи. Изменение концентрации метаболитов в клеткахмишенях по механизму отрицательной обратной связи подавляет синтез гормонов действуя либо на эндокринные железы либо на гипоталамус. Синтез и секреция тропных гормонов подавляется гормонами эндокринных периферических желёз.
81541. Половые гормоны: строение, влияние на обмен веществ и функции половых желез, матки и молочных желез 133.12 KB
  Биосинтез эстрогенов как биохимический процесс представляет собой ароматизацию С19стероидов катализируемую комплексом ферментов локализованных в микросомах. У женщин детородного возраста основная масса эстрогенов синтезируется в яичнике содержащем зреющий фолликул или желтое тело. Синтез эстрогенов в фолликуле определяется взаимодействием двух стероидпродуцирующих структур зернистого слоя и текаклеток. Синтез эстрогенов в зреющем фолликуле является одним из основных факторов определяющих функцию гипофизарноовариальной системы т.
81542. Гормон роста, строение, функции 102.09 KB
  Гормон роста соматотропин пептидный гормон образуется в соматотропных клетках аденогипофиза. Молекула СТГ состоит из 191 аминокислотного остатка на восемь остатков меньше чем в молекуле пролактина и в отличие от пролактина содержит не три а два внутримолекулярных дисульфидных мостика Гормоном роста соматотропин называют за то что у детей и подростков а также молодых людей с ещё не закрывшимися зонами роста в костях он вызывает выраженное ускорение линейного в длину роста в основном за счет роста длинных трубчатых костей...
81543. Метаболизм эндогенных и чужеродных токсических веществ: реакции микросомального окисления и реакции конъюгации с глутатионом, глюкуроновой кислотой, серной кислотой 144.87 KB
  В ЭР существуют две такие цепи первая состоит из двух ферментов NDPHP450 редуктазы и цитохрома Р450 вторая включает фермент NDHцитохромb5 редуктазу цитохром b5 и ещё один фермент стеароилКоАдесатуразу. Электронтранспортная цепь NDPHP450 редуктаза цитохром Р450. Восстановленный FMN FMNH2 окисляется цитохромом Р450 Цитохром Р450 гемопротеин содержит простетическую группу гем и имеет участки связывания для кислорода и субстрата ксенобиотика. Название цитохром Р450 указывает на то что максимум поглощения комплекса...