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.

Висновок

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


 

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

38868. Призначення, будова і принцип роботи приладу типу МТМ-РЭ-160 366 KB
  Управління технологічними процесами з використанням автоматичних засобів включає в себе виконання наступних основних задач: контроль параметрів процесів (температури, тиску в апаратах, складу і якості рідин і газів і т. д.); регулювання параметрів (підтримання їх у заданих значеннях)
38869. Изучение системно-характерологических отношений личности с разным уровнем готовности к риску 247 KB
  Техногенные прорывы плотин дамб шлюзов перемычек аварии на коммунальных системах жизнеобеспечения и предприятиях внезапное обрушение зданий сооружений аварии на энергетических системах пожары взрывы транспортные аварии аварии с выбросом радиоактивных химических и биологических веществ; 3 экологическиеизменение состояния суши атмосферы гидросферы и биосферы; 4 биологические инфекционные заболевания эпидемии нашествия насекомых и животных и 5 социального характеравойны революции региональные конфликты и т. По...
38870. Разработка однолинейной схемы электрической подстанции 561.5 KB
  Расчет параметров короткого замыкания. Расчет параметров цепи короткого замыкания необходим для дальнейшей проверки выбранных токоведущих частей и оборудования подстанции по режиму короткого замыкания на термическую и электродинамическую стойкость и для проверки чувствительности релейной защиты. Последствиями термического и электродинамического воздействия токов короткого замыкания могут быть: механическое разрушение сборных шин частей аппаратуры токоведущих частей генераторов и трансформаторов; перегрев и расплавление...
38871. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ И ЗАЩИТЕ ДИПЛОМНЫХ РАБОТ (ПРОЕКТОВ) 432.5 KB
  В методических указаниях включены основные требования предъявляемые к структуре содержанию и оформлению дипломной работы проекта; краткие рекомендации по содержанию дипломной работы проекта и оформлению отзыва и рецензии; описана процедура защиты дипломной работы проекта. ВЫБОР НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ [5] 3 ВЫБОР ТЕМЫ ДИПЛОМНОЙ РАБОТЫ ПРОЕКТА [5.3 Формулирование темы дипломной работы проекта [5.5] 4 НАУЧНОЕ РУКОВОДСТВО ДИПЛОМНОЙ РАБОТОЙ ПРОЕКТИРОВАНИЕМ [6] 5 ИЗЛОЖЕНИЕ МАТЕРИАЛОВ ДИПЛОМНОЙ РАБОТЫ ПРОЕКТА [7] 6 СТРУКТУРА И...
38872. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ДИПЛОМНЫХ РАБОТ 619.5 KB
  Дипломная работа - выпускная квалификационная работа студента, предназначенная для объективного контроля степени сформированности знаний, умений и навыков решать задачи по видам профессиональной деятельности, установленным образовательным стандартом специальности, и предусматривающая проведение анализа и разработки актуальных вопросов, проблем в соответствующей области знаний согласно требованиям задания на выпускную квалификационную работу.
38873. МЕТОДИЧНІ ВКАЗІВКИ до виконання розділу «ОХОРОНА ПРАЦІ » в дипломних проектах 406 KB
  Передбачити в технологічних цехах та відділеннях де може статися вибух пожежа отруєння людей відділення отримання спирту та інші аварійне освітлення. Основними організаційними заходами є: експлуатація обладнання у відповідності з технічними характеристиками згідно паспорту заводувиробника; проведення своєчасного профілактичного ремонту обладнання; розміщення обладнання з підвищеним рівнем шуму і вібрації в ізольованому приміщенні дробильнопресове відділення; дотримання режимів праці та відпочинку; використання...
38874. МЕТОДИЧНІ ВКАЗІВКИ ЩОДО ВИКОНАННЯ дипломної роботи 200.5 KB
  Мета роботи – презентація студентом вміння виконувати наукове дослідження з теорії та вміння використовувати теоретичні знання для вирішення конкретних практичних завдань, а також виявлення ступеня підготовки випускника до самостійної практичної діяльності.
38875. Производство леворина. Ферментация с получением мицелиальной массы 295 KB
  Массовая доля основного вещества не менее 985; 2.Массовая доля влаги не более 05; 3.Массовая доля веществ нерастворимых в соляной кислоте не более 01 В состав питательной среды на ферментации 4.Массовая доля влаги не более 9; 5.
38876. Определение степени художественной адекватности и принципов художественного перевода произведений А.П. Чехова на белорусский язык 334 KB
  Толстой и другие плодотворно работали не только в сфере изящной словесности но и в области художественного перевода. Интерес к подобного рода переводам проявился в науке уже давно. В книге Искусство перевода классик украинской поэзии Максим Рыльский делится опытом перевода поэзии Пушкина Лермонтова Мицкевича размышляет о значении культурного взаимообмена между родственными народами о переводе как сотворчестве.