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.

Висновок

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


 

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

17927. Анализ эффективности использования основных средств 84.5 KB
  Лекция 7. Анализ эффективности использования основных средств Основные средства совокупность материальных активов в форме средств труда которые многократно участвуют в процессе производственнокоммерческой деятельности и переносят на продукцию свою стоимость ч...
17928. Платежные системы. Конспект лекций 3.65 MB
  Средством межфилиальных расчетов были авизо по МФО, которые складывались и направлялись в расчетно-кассовые центры (РКЦ) при Центральном банке. Авизо, как правило, пересылались средствами спецпочты (бумажные почтовые авизо) или телеграфом (телеграфные авизо).
17929. ТЕОРЕТИЧНІ ТА ОРГАНІЗАЦІЙНІ ОСНОВИ ФІНАНСОВОГО МЕНЕДЖМЕНТУ 284 KB
  Основний зміст фінансового менеджменту полягає в управлінні формуванням, розподілом і використанням фінансових ресурсів суб’єктів господарювання та оптимізації обороту їх грошових коштів
17930. СИСТЕМА ЗАБЕЗПЕЧЕННЯ ФІНАНСОВОГО МЕНЕДЖМЕНТУ. АНАЛІЗ ФІНАНСОВИХ ЗВІТІВ 786.5 KB
  Організаційний механізм – це совокупність правил, організаційно-правових нормативів і стандартів, що визначають та регулюють структуру фінансового управління.
17931. Внутрішньофірмове фінансове прогнозування та планування 72.5 KB
  3. Внутрішньофірмове фінансове прогнозування та планування 3.1. Завдання та методи фінансового планування і прогнозування 3.2. Система фінансових планів підприємства 3.3. Сутність та особливості бюджетування внутрішніх підрозділів підприємства 3.4. Розробка бюджетів с...
17932. Управління грошовими потоками на підприємстві 558 KB
  4. Управління грошовими потоками на підприємстві 4.1. Поняття грошового потоку його склад та значення в забезпеченні кругообігу капіталу 4.2. Управління грошовими потоками 4.3. Управління грошовими потоками від операційної діяльності 4.5. Управління грошовими потоками ...
17933. Управління прибутком на підприємстві 226 KB
  5. Управління прибутком на підприємстві 5.1. Зміст та завдання управління прибутком підприємства 5.2. Формування прибутку від операційної діяльності 5.3. Управління операційними витратами 5.4. Управління операційним прибутком підприємства 5.5. Роль операційного аналіз
17934. Математичні основи фінансового менеджменту. Прості та складні відсотки 55 KB
  6. Математичні основи фінансового менеджменту. Прості та складні відсотки 6.1. Об'єктивна необхідність визначення вартості грошей у часі 6.2. Нарахування простих відсотків 6.3. Розрахунок майбутньої вартості грошового потоку методом компаундування Література 6. Матем...
17935. Ануїтети. Визначення вартості грошей у часі та її використання у фінансових розрахунках 60 KB
  7. Ануїтети. Визначення вартості грошей у часі та її використання у фінансових розрахунках 7.1. Розрахунок теперішньої вартості ануїтетів 7.2. Розрахунок теперішньої вартості грошового потоку методом дисконтування Література 7. Ануїтети. Визначення вартості грошей у