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.

Висновок

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


 

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

36914. Выделение и перемещение фрагментов изображения, кадрирование изображений 158.5 KB
  dobe Photoshop Тема: Выделение и перемещение фрагментов изображения кадрирование изображений Цель: приобрести навыки работы с инструментами выделения фрагментов изображений научиться перемещать и копировать выделенные фрагменты. Краткие теоретические сведения В данном уроке используются следующие инструменты: Инструмент Zoom Масштаб позволяет получать изображение на экране в увеличенном или в уменьшенном виде. Инструмент Crop Рамка позволяет выделить прямоугольный фрагмент изображения и удалить ту его часть которая осталась за...
36915. КОМПЬЮТЕРНАЯ СИСТЕМА PROJECT EXPERT. ФОРМИРОВАНИЕ ФИНАНСОВОЙ МОДЕЛИ ПРОЕКТА 47.5 KB
  ФОРМИРОВАНИЕ ФИНАНСОВОЙ МОДЕЛИ ПРОЕКТА Цель: изучить систему команд Project Expert формирования финансовой модели инвестиционного проекта для предприятия. Построив с помощью Project Expert финансовую модель собственного предприятия или инвестиционного проекта можно получить такие возможности: разработать детальный финансовый план и определить потребность в денежных средствах на перспективу; определить схему финансирования предприятия оценить возможность и эффективность привлечения денежных средств из различных источников; разработать...
36916. Структура управления регионального международного аеропорта (РМА) 55 KB
  Непосредственно генеральному директору аэропорта подчиняются его замы и директора по направлениям а также самостоятельные структурные подразделения и службы. Типовая структура РМА представлена на схеме: Деятельность отдельных подразделений и служб аэропорта Основные функции службы качества: 1. разработка перспективных направлений повышения качества услуг авиакомпаниям и клиентам аэропорта; 2.
36917. Исследование статической и динамической характеристики термопары 188 KB
  Исследование статической и динамической характеристики термопары. Ознакомиться со схемами включения измерительного прибора в цепь термопары. Экспериментально получить статическую и динамическую характеристики термопары. Определить математическую модель термопары.
36918. Знакомство с математическим пакетом Scilab 141.5 KB
  Знакомство с математическим пакетом Scilb Scilb это система компьютерной математики которая предназначена для выполнения инженерных и научных вычислений таких как: решение нелинейных уравнений и систем; решение задач линейной алгебры; решение задач оптимизации; дифференцирование и интегрирование; обработка экспериментальных данных интерполяция и аппроксимация метод наименьших квадратов; решение обыкновенных дифференциальных уравнений и систем. Кроме того Scilb предоставляет широкие возможности по созданию и редактированию...
36919. ОРГАНИЗАЦИЯ РАБОЧЕГО ПРОСТРАНСТВА MS EXCEL. ВВОД И ФОРМАТИРОВАНИЕ ДАННЫХ. СОРТИРОВКА И ФИЛЬТРАЦИЯ ДАННЫХ 730.5 KB
  ВВОД И ФОРМАТИРОВАНИЕ ДАННЫХ. СОРТИРОВКА И ФИЛЬТРАЦИЯ ДАННЫХ Цель работы: изучить рабочее пространство приложения MS Excel научиться применять различные параметры форматирования к данным сортировать данные и проводить их фильтрацию по заданным условиям. Изучить параметры форматирования данных в MS Excel и научиться их настраивать. Научиться создавать последовательности данных.
36920. Установка и настройка сервера DHCP 14.43 KB
  Установка и настройка сервера DHCP Цель Изучить процесс установки авторизации сервера DHCP создания области и настройки параметров области Исходная конфигурация компьютера Компьютеры с операционной системой Windows 2003 Server с созданными контроллерами домена. Результат Сервер с установленной и настроенной службой DHCP Требования к отчету Теореретические сведения: Общие сведения о службе DHCP. Последовательность выполняемых действий Установка службы DHCP Авторизация сервера DHCP в ctive Directory Создание области и...
36921. Word. Основные возможности 122 KB
  Любой текст имеет формат определенного типа. Базовый формат текста зависит от стиля который применен к абзацу содержащему этот текст. Процесс изменения формата называется форматированием а следствием изменения формата является изменение внешнего вида документа. Стиль это набор запомненных команд форматирования символов и или абзацев.
36922. Word: Способы запуска. Создание, открытие, сохранение, закрытие файла (документа) 93 KB
  Панели инструментов и их настройка. Контекстное меню в области панелей инструментов. ДЕЙСТВИЯ С ФАЙЛАМИ И ОКНАМИ ФАЙЛОВ Выполните действия связанные с созданием сохранением и закрытием файла: создайте файл для чего: 1й способ: нажмите кнопку Создать файл по умолчанию на Стандартной панели инструментов; 2й способ: нажмите сочетание клавиш CtrlN; 3й способ: выполните команды меню ФайлðСоздать.; в появившемся окне Сохранение документа в раскрывающемся списке Папка откройте Вашу папку если Вашей папки нет то можно создать ее...