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.

Висновок

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


 

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

40828. Моделирование случайных воздействий на систему 216 KB
  Моделирование случайных воздействий на систему Моделирование случайных событий. Моделирование дискретных случайных величин. Моделирование непрерывных случайных величин. Моделирование случайных векторов 4.
40829. ПЛАНИРОВАНИЕ МАШИННЫХ ЭКСПЕРИМЕНТОВ С МОДЕЛЯМИ СИСТЕМ 223.5 KB
  Частные задачи планирования машинных экспериментов уменьшение затрат машинного времени на моделирование увеличение точности и достоверности результатов моделирования проверка адекватности модели и т. План эксперимента определяет объем и порядок проведения вычислений на ЭВМ приемы накопления и статистической обработки результатов моделирования системы S. Таким образом при машинном моделировании рационально планировать и проектировать не только саму модель Мм системы S но и процесс ее использования т. При планировании эксперимента...
40830. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1 MB
  Основные понятия и определения Выделяют четыре основные задачи линейной алгебры: решение СЛАУ вычисление определителя матрицы нахождение обратной матрицы определение собственных значений и собственных векторов матрицы. Задача отыскания решения СЛАУ с n неизвестными одна из наиболее часто встречающихся в практике вычислительных задач так как большинство методов решения сложных задач основано на сведении...
40831. АППРОКСИМАЦИЯ ФУНКЦИЙ 939 KB
  Как упростить вычисление известной функции fx или же ее характеристик если fx слишком сложная Ответы на эти вопросы даются теорией аппроксимации функций основная задача которой состоит в нахождении функции y=x близкой т. Обоснование способов нахождения удачного вида функциональной зависимости и подбора параметров составляет задачу теории аппроксимации функций. В зависимости от способа подбора параметров получают различные методы аппроксимации; наибольшее распространение среди них получили интерполяция и среднеквадратичное...
40832. ВЫЧИСЛЕНИЕ ПРОИЗВОДНЫХ И ИНТЕГРАЛОВ 654 KB
  При аппроксимации операторов численного дифференцирования и интегрирования наибольшее распространение ввиду своей простоты нашли интерполяционные формулы Ньютона. Формулы численного дифференцирования Формулы для расчета производной в точке x получаются следующим образом. Такие формулы называют простейшими формулами численного дифференцирования.3 получается три важные формулы второго порядка точности: 4.
40833. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ 748 KB
  Точное решение удается получить в исключительных случаях и обычно для нахождения корней уравнения применяются численные методы. Первая задача решается графическим методом: на заданном отрезке [ b] вычисляется таблица значений функции с некоторым шагом h строится ее график и определяются интервалы длиной h на которых находятся корни.1 в случаях и в значение корня совпадает с точкой экстремума функции и для нахождения таких корней можно использовать методы поиска минимума функции описанные в...
40834. МЕТОДЫ НАХОЖДЕНИЯ МИНИМУМА ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ 869.5 KB
  Постановка задачи Задача нахождения минимума функции одной переменной minfx нередко возникает в практических приложениях. Кроме того многие методы решения задачи минимизации функции многих переменных сводятся к многократному поиску одномерного минимума. Задача ставится следующим образом: требуется найти такое значение xm из отрезка [ b] при котором достигается минимум функции ym=fxm т.
40835. Президенти Міжнародного олімпійського комітету 165 KB
  Президенти Міжнародного олімпійського комітету МОК План лекції 1. Президенти МОК: основні моменти біографії та вплив діяльності на зміни в олімпійському русі: Д. Відповідно до Олімпійської хартії затвердженої на цьому конгресі президент МОК мав представляти країну що проводить чергові Олімпійські ігри. Вікелас у віці 59 років був обраний першим президентом МОК.
40836. Соціально-політичні і правові аспекти сучасного олімпійського спорту 79 KB
  З підвищенням рівня популярності і міжнародної ваги Олімпійських ігор останні виявилися ареною суперництва не тільки самих спортсменів і навіть не тільки їх національних збірних але держав і груп держав за світове визнання і вплив. Одним з неминучих следствій що розвернулася і продовжувалася до цього дня навколо і усередині Олімпійських ігор міждержавної політичної боротьби стали і різні способи публічної демонстрації відношення до тих або інших держав або груп держав. Це може бути демонстративна відмова в ході підготовки і проведення...