Теорія ігор і прийняття рішень

В Залежно від умов зовнішнього середовища і ступеня інформативності особи приймаючої рішення (ОПР) проводиться наступна класифікація завдань прийняття рішень:

а) в умовах ризику;

б) в умовах невизначеності;

в) в умовах конфлікту або протидії (активного супротивника).

Теорія корисності та прийняття рішень.

Прийняття рішень в умовах ризику.

Критерій очікуваного значення.

Використання критерію очікуваного значення обумовлено прагненням максимізувати очікувану прибуток (або мінімізувати очікувані витрати). Використання очікуваних величин припускає можливість багаторазового вирішення однієї і тієї ж задачі, поки не будуть отримані досить точні розрахункові формули. Математично це виглядає так: нехай Х-випадкова величина з математичним очікуванням MX і дисперсией DX. Якщо x 1 , x 2 , ..., x n - значення випадкової величини (с.в.) X, то середнє арифметичне їх (вибіркове середнє) значень має дисперсію. Таким чином, коли n В® ВҐ

В® 0 і В® MX.

Іншими словами при достатньо великому обсязі вибірки різниця між середнім арифметичним і математичним очікуванням прагне до нуля (так звана гранична теорема теорії ймовірності). Отже, використання критерію очікуване значення справедливе тільки у разі, коли одне і теж рішення доводиться застосовувати досить багато раз. Вірно і зворотне: орієнтація на очікування буде приводити до невірних результатів, для рішень, які доводиться приймати невелике число разів.

Приклад 1. Потрібно прийняти рішення про те, коли необхідно проводити профілактичний ремонт ПЕОМ, щоб мінімізувати втрати через несправність. У разі якщо ремонт буде виробляється занадто часто, витрати на обслуговування будуть великими при малих втратах через випадкових поломок.

Так як неможливо передбачити заздалегідь, коли виникне несправність, необхідно знайти ймовірність того, що ПЕОМ вийде з ладу в період часу t. У цьому і полягає елемент "ризику".

Математично це виглядає так: ПЕОМ ремонтується індивідуально, якщо вона зупинилася через поломки. Через T інтервалів часу виконується профілактичний ремонт усіх n ПЕОМ. Необхідно визначити оптимальне значення Т, при якому мінімізуються загальні витрати на ремонт несправних ПЕОМ та проведення профілактичного ремонту в розрахунку на один інтервал часу.

Нехай р t - ймовірність виходу з ладу однієї ПЕОМ в момент t, а n t - випадкова величина, що дорівнює числу всіх вийшли з ладу ПЕОМ в той же момент. Нехай далі З 1 - витрати на ремонт несправної ПЕОМ і С 2 - витрати на профілактичний ремонт однієї машини.

Застосування критерію очікуваного значення в даному випадку виправдане, якщо ПЕВМ працюють протягом великого періоду часу. При цьому очікувані витрати на один інтервал складуть

ОЗ =,

де M (n t ) - математичне очікування числа вийшли з ладу ПЕОМ в момент t. Так як n t має біноміальний розподіл з параметрами (n, p t ), то M (n t ) = np t . Таким чином

ОЗ =

Необхідні умови оптимальності T * мають вигляд:

ОЗ (T * -1) Ві ОЗ (T * ),

ОЗ (T * +1) Ві ОЗ (T * ).

Отже, починаючи з малого значення T, обчислюють ОЗ (T), поки не будуть задоволені необхідні умови оптимальності.

Нехай З 1 = 100; С 2 = 10; n = 50. Значення p t мають вигляд:

T

р t

ОЗ (Т) 1 0.05 0

2 0.07 0.05 375 3 0.10 0.12 366.7 4 0.13 0.22 400 5 0.18 0.35 450

T * В® 3, ОЗ (Т * ) В® 366.7

Отже профілактичний ремонт необхідно робити через T * = 3 інтервалу часу.

Критерій "очікуване значення - дисперсія"

Критерій очікуваного значення можна модифікувати так, що його можна буде застосувати і для рідко повторюваних ситуацій.

Якщо х - с. в. з дисперсією DX, то середнє арифметичне має дисперсію, де n - число Слоган в. Отже, якщо DX зменшується, і ймовірність того, що близько до MX, збільшується. Отже, доцільно ввести критерій, в якому максимізація очікуваного значення прибутку поєднується з мінімізацією її дисперсії.

Приклад 2. Застосуємо критерій "очікуване значення - дисперсія" для прикладу 1. Для цього необхідно знайти дисперсію витрат за інтервал часу, тобто дисперсію

з Т =

Т.к. n t , t = - с.в., то з Т також с.в. С.в. n t має біноміальний розподіл з M (n t ) = np t і D (n t ) = np t (1-p t ). Отже,

D (з Т ) = D () = D () =

= == N {-},

де З 2 n = const.

З прикладу 1 випливає, що

М (з Т ) = М (з (Т)).

Отже шуканим критерієм буде мінімум виразу

М (з (Т)) + До D (з Т ).

Зауваження. Константу "до" можна розглядати як рівень не схильності до ризику, тому "До" визначає "ступінь можливості" дисперсії Д (з Т ) по відношенню до математичному очікуванню. Наприклад, якщо підприємець, особливо гостро реагує на великі негативні відхилення прибутку вниз від М (з (Т)), то він може вибрати "до" значно більше 1. Це надає більшої ваги дисперсії і призводить до вирішення, уменьшающему ймовірність великих втрат прибутку.

При к = 1 отримуємо задачу

За даними з прикладу 1 можна скласти таку таблицю

Т

p t

p t 2

М (з (Т)) + D (з (Т)) 1 0.05 0.0025 0 0 500.00 2 0.07 0.0049 0.05 0.0025 6312.50 3 0.10 0.0100 0.12 0.0074 6622.22 4 0.13 0.0169 0.22 0.0174 6731.25 5 0.18 0.0324 0.35 0.0343 6764.00

З таблиці видно, що профілактичний ремонт необхідно робити протягом кожного інтервалу Т * = 1.

Кри...терій граничного рівня.

Критерій граничного рівня не дає оптимального рішення, максимизирующего, наприклад, прибуток або мінімізує витрати. Швидше він відповідає визначенню прийнятного способу дій.

Приклад 3. Припустимо, що величина попиту x в одиницю часу (інтенсивність попиту) на деякий товар задається безперервної функцією розподілу f (x). Якщо запаси в початковий момент невеликі, в подальшому можливий дефіцит товару. В іншому випадку до кінця розглянутого періоду запаси нереалізованого товару можуть виявитися дуже великими. В обох випадках можливі втрати.

Т.к. визначити втрати від дефіциту дуже важко, ЛПР може встановити необхідний рівень запасів таким чином, щоб величина очікуваного дефіциту не перевищувала А 1 одиниць, а величина очікуваних надлишків не перевищувала А 2 одиниць. Іншими словами, нехай I - шуканий рівень запасів. Тоді

очікуваний дефіцит =,

очікувані надлишки =.

При довільному виборі А 1 і А 2 зазначені умови можуть виявитися суперечливими. У цьому випадку необхідно послабити одне з обмежень, щоб забезпечити допустимість.

Нехай, наприклад,

Тоді

== 20 (ln + - 1)

== 20 (ln + - 1)

Застосування критерію граничного рівня призводить до нерівностям

ln I - Ві ln 20 - 1 = 1.996 -

ln I - Ві ln 10 - 1 = 1.302 -

Граничні значення А 1 і А 2 повинні бути вибрані так, що б обидва нерівності виконувалися хоча б для одного значення I.

Наприклад, якщо А 1 = 2 і А 2 = 4, нерівності приймають вид

ln I - Ві 1.896

ln I - Ві 1.102

Значення I повинно знаходитися між 10 і 20, тому саме в цих межах змінюється попит. З таблиці видно, що обидві умови виконуються для I, з інтервалу (13,17)

I 10 11 12 13 14 15 16 17 18 19 20

ln I -

1.8 1.84 1.88 1.91 1.94 1.96 1.97 1.98 1.99 1.99 1.99

ln I -

1.3 1.29 1.28 1.26 1.24 1.21 1.17 1.13 1.09 1.04 0.99

Будь з цих значень задовольняє умовам задачі.

Прийняття рішень в умовах невизначеності.

Будемо припускати, що особі, що приймає рішення не протистоїть розумний супротивник.

Дані, необхідно для прийняття рішення в умови невизначеності, зазвичай задаються в формі матриці, рядки якої відповідають можливим діям, а стовпчики - можливим станам системи.

Нехай, наприклад, з деякого матеріалу потрібно виготовити виріб, довговічність якого при допустимих витратах неможливо визначити. Навантаження вважаються відомими. Потрібно вирішити, які розміри має мати виріб з даного матеріалу.

Варіанти рішення такі:

Е 1 - Вибір розмірів з міркувань максимальної довговічності;

Е m - вибір розмірів із міркувань мінімальної довговічності;

E i - проміжні рішення.

Умови потребують розгляду такі:

F 1 - умови, що забезпечують максимальної довговічність;

F n - умови, що забезпечують min довговічність;

F i - проміжні умови.

Під результатом рішення e ij = е (E i ; F j ) тут можна розуміти оцінку, відповідну варіанту E < sub> i і умовам F j і характеризують прибуток, корисність або надійність. Зазвичай ми будемо називати такий результат корисністю рішення.

Тоді сімейство (матриця) рішень має вигляд:

F 1

F 2

. . .

F n

E 1

e 11

e 12

. . .

e 1n

E 2

e 21

e 22

. . .

e 2n

. . . . . . . . . . . . . . . . . . .

E m

e m1

e m2

. . .

e mn

Щоб прийти до однозначного і по можливості найвигідніший варіант вирішення необхідно ввести оціночну (цільову) функцію. При цьому матриця рішень зводиться до одному стовпцю. Кожному варіанту E i приписується, таким чином, деякий результат e ir , що характеризує, в цілому, все наслідки цього рішення. Такий результат ми будемо надалі позначати тим же символом e ir .

Класичні критерії прийняття рішень.

1. Мінімаксний критерій.

Правило вибору рішення відповідно до мінімаксного критерієм (ММ-критерієм) можна інтерпретувати наступним чином:

матриця рішень доповнюється ще одним стовпцем з найменших результатів e ir кожного рядка. Необхідно вибрати ті варіанти в рядках яких стоять найбільше значення e ir цього стовпця.

Вибрані т.а. варіанти повністю виключають ризик. Це означає, що приймає рішення не може зіткнутися з гіршим результатом, ніж той, на який він орієнтується. Ця властивість дозволяє вважати ММ-критерій одним з фундаментальних.

Застосування ММ-критерію буває виправдано, якщо ситуація, в якій приймається рішення наступна:

1 o . Про можливість появи зовнішніх станів F j нічого не відомо;

2 o . Доводиться рахуватися з появою різних зовнішніх станів F j

3 o . Рішення реалізується тільки один раз;

4 o . Необхідно виключити якої б то не було ризик.

2. Критерій Байєса - Лапласа.

Позначимо через q i - ймовірність появи зовнішнього стану F j .

Відповідне правило вибору можна інтерпретувати в такий спосіб:

матриця рішень доповнюється ще одним стовпцем що містить математичне очікування значень кожної з рядків. Вибираються ті ва...ріанти, в рядках яких коштує найбільше значення e ir цього стовпця.

При цьому передбачається, що ситуація, в якій приймається рішення, характеризується наступними обставинами:

1 про . Ймовірності появи стану F j відомі і не залежать від часу.

2 про . Рішення реалізується (теоретично) нескінченно багато раз.

3 про . Для малого числа реалізацій рішення допускається деякий ризик.

При достатньо великій кількості реалізацій середнє значення поступово стабілізується. Тому при повній (нескінченної) реалізації небудь ризик практично виключений.

Т.ч. критерій Байеса-Лапласа (BL-критерій) більш оптимістичний, ніж мінімаксний критерій, проте він передбачає велику інформованість і досить тривалу реалізацію.

3 про . Критерій Севіджа.

Величину a ij можна трактувати як максимальний додатковий виграш, який досягається, якщо в стані F j замість варіанта E i вибирати інший, оптимальний для цього зовнішнього стану варіант. Величину a ij можна інтерпретувати і як втрати (штрафи) виникають у стані F j при заміні оптимального для нього варіанти на варіант E i . В останньому випадку e ir представляє собою максимально можливі (За всіма зовнішніми станам F j , j =) втрати у разі вибору варіанта E i .

Відповідне критерієм Севіджа правило вибору тепер трактується так:

1). Кожен елемент матриці рішень віднімається з найбільшого результату max e ij відповідного стовпця.

2). Різниці a ij утворюють матрицю залишків. Ця матриця поповнюється стовпцем найбільших разностей e ir . Вибирають ті варіанти, в рядках яких коштує найменше для цього стовпця значення.

Вимоги, пропоновані до ситуації, в якій приймається рішення, збігаються з вимогою до ММ-критерію.

4 про . Приклад і висновки.

З вимог, що пред'являються до розглянутих критеріям стає ясно, що в слідстві їх жорстких вихідних позицій вони застосовні тільки для ідеалізованих практичних рішень. У випадку, коли можлива занадто сильна ідеалізація, можна застосовувати одночасно по черзі різні критерії. Після цього серед декількох варіантів ЛПР вольовим методом вибирає остаточне рішення. Такий підхід дозволяє, по-перше, краще проникнути в усі внутрішні зв'язки проблеми прийняття рішень і, по-друге, послаблює вплив суб'єктивного фактора.

Приклад. При роботі ЕОМ необхідно періодично призупиняти обробку інформації та перевіряти ЕОМ на наявність в ній вірусів. Призупинення в обробці інформації призводить до певних економічних витрат. У разі ж якщо вірус вчасно виявлений не буде, можлива втрата і деякої частини інформації, що призведе і ще до великих збитків.

Варіанти рішення такі:

Е 1 - повна перевірка;

Е 2 - мінімальна перевірка;

Е 3 - відмова від перевірки.

ЕОМ може знаходитися в наступних станах:

F 1 - вірус відсутня;

F 2 - вірус є, але він не встиг пошкодити інформацію;

F 3 - є файли, що бідують у відновленні.

Результати, включають витрати на пошук вірусу та його ліквідацію, а також витрати, пов'язані з відновленням інформації мають вигляд:

Таблиця 1.

ММ-критерій критерій BL

F 1

F 2

F 3

e ir = e ij

e ir

e ir =

e ir

E 1

-20.0 -22.0 -25.0 -25.0 -25.0 -22.33

E 2

-14.0 -23.0 -31.0 -31.0 -22.67

E 3

0 -24.0 -40.0 -40.0 -21.33 -21.33

Згідно ММ-критерію слід проводити повну перевірку. Критерій Байєса-Лапласа, в припущенні, що всі стани машини рівноймовірно.

P (F j ) = q j = 0.33,

рекомендується відмовитися від перевірки. Матриця залишків для цього прикладу і їх оцінка (в тисячах) згідно з критерієм Севіджа має вигляд:

Критерій Севіджа

F 1

F 2

F 3

e ir = a ij

e ir

E 1

+20.0 0 0 +20.0

E 2

+14.0 +1.0 +6.0 +14.0 +14.0

E 3

0 +2.0 +15.0 +15.0

Приклад спеціально підібраний так, що кожен критерій пропонує нове рішення. Невизначеність стану, в якому перевірка застає ЕОМ, перетворюється в неясність, яким критерієм слідувати.

Оскільки різні критерії пов'язані з різними умовами, в яких приймається рішення, краще всього для порівняльної оцінки рекомендації тих чи інших критеріїв отримати додаткову інформацію про саму ситуацію. Зокрема, якщо прийняте рішення відноситься до сотням машин з однаковими параметрами, то рекомендується застосовувати критерій Байеса-Лапласа. Якщо ж число машин не велике, краще користуватися критеріями минимакса або Севідж.

Похідні критерії.

1 про . Критерій Гурвіца.

Намагаючись зайняти найбільш врівноважену позицію, Гурвіц припустив оцінну функцію, яка знаходиться десь між точкою зору крайнього оптимізму та крайнього песимізму:

e ir = {Ce ij + (1 - C) e ij },

де З-ваговий множник.

Правило вибору згідно з критерієм Гурвіца..., формується таким чином:

матриця рішень доповнюється стовпцем, що містить середнє зважене найменшого та найбільшого результатів для кожного рядка. Вибираються ті варіанти, в рядках яких стоять найбільші елементи e ir цього стовпця.

При С = 1 критерій Гурвіца перетворюється на ММ-критерий. При С = 0 він перетворюється в критерій "азартного гравця"

e ir = e ij ,

тобто ми стаємо на точку зору азартного гравця, що робить ставку на те, що В«ВипадеВ» найвигідніший випадок.

В технічних додатках складно вибрати ваговій множник С, тому важко знайти кількісну характеристику для тих часткою оптимізму і песимізму, які присутні при прийнятті рішення. Тому найчастіше С: = 1 / 2 .

Критерій Гурвіца застосовується у разі, коли:

про ймовірностях появи стану F j нічого не відомо;

з появою стану F j необхідно рахуватися;

реалізується тільки мала кількість рішень;

допускається деякий ризик.

2 про . Критерій Ходжа-Лемана.

Цей критерій спирається одночасно на ММ-критерій і критерій Баес-Лапласа. З допомогою параметра n виражається ступінь довіри до використовуваному розподілів ймовірностей. Якщо довіра велике, то домінує критерій Баес-Лапласа, в іншому випадку - ММ-критерій, тобто ми шукаємо

e ir = {n + (1-n) e ir }, 0 ВЈ n ВЈ 1.

Правило вибору, відповідне критерію Ходжа-Лемана формується таким чином:

матриця рішень доповнюється стовпцем, складеним з середніх зважених (з вагою n Вє const) математичне очікуваннями і найменшого результату кожного рядка (*). Відбираються ті варіанти рішень в рядках якого варто найбільшого значення цього стовпця.

При n = 1 критерій Ходжа-Лемана переходить в критерій Байеса-Лапласа, а при n = 0 стає мінімаксного.

Вибір n суб'єктивний т. к. Ступінь достовірності небудь функції розподілу - справа темна.

Для застосування критерію Ходжа-Лемана бажано, щоб ситуація в якій приймається рішення, задовольняла властивостям:

ймовірності появи стану F j невідомі, але деякі припущення про розподілі ймовірностей можливі;

при

Цей При цьому

Т.к. У випадку ж, коли При цьому

Правило

матриця цього стовпця.

В

Умови

ймовірності появи стану F j невідомі;

з рахуватися;

рішення

Якщо

Прагнення критеріїв.

Правило

матриця рішень доповнюється

і

відповідної рядки.

математичне сподівання.

з . Значення

Застосування

ймовірності

необхідно комплексі;

досить надійним.

Умова

істотно Вом числі реалізацій ця умова перестає бути таким уже й важливим. Воно навіть допускає розумні альтернативи. При цьому не відомо, однак, чітких кількісних вказівок, в яких випадках ця умова слід було б опускати.

5 про . Критерій творів.

e ir : = e ij

Правило вибору в цьому випадку формулюється так:

Матриця рішень доповнюється новим стовпцем, що містить твори всіх результатів кожного рядка. Вибираються ті варіанти, в рядках яких знаходяться найбільші значення цього стовпця.

Застосування цього критерію зумовлюється такими обставинами:

ймовірності появи стану F j невідомі;

з появою кожного з станів F j по окремо необхідно рахуватися;

критерій застосовний і при малому числі реалізацій рішення;

деякий ризик допускається.

Критерій творів пристосований в першу чергу для випадків, коли всі e ij додатні. Якщо умова позитивності порушується, то слід виконувати деяке зрушення e ij + а з деякою константою а> ГЇe ij ГЇ. Результат при цьому буде, природно залежати від а. На практиці найчастіше

а : = ГЏe ij ГЇ +1.

Якщо ж ніяка константа не може бути визнана має сенс, то критерій творів не застосуємо.

Приклад.

Розглянемо той же приклад (табл. 1).

Побудова оптимального рішення для матриці рішень про перевірки за критерієм Гурвіца має вид (при С = 0.5, в 10 3 ):

х

СE ij

(1-С) e ij

e ir

e ir

-20.0 -22.0 -25.0 -12.5 -10.0 -22.5 -14.0 -23.0 -31.0 -15.5 -7.0 -22.5 0 -24.0 -40.0 -20.0 0 -20.0 -20.0

В даному прикладі у рішення є поворотна точка щодо вагового множника З: до З = 0.57 як оптимального вибирається Е 3 , а при великих значеннях - Е 1 .

Застосування критерію Ходжа-Лемана (q = 0.33, n = 0.5, в 10 3 ):

e ij

n

(1-n) e ij

e ir

e ir

-22.33 -25.0 -11.17 -12.5 -23.67 -23.67 -22.67 -31.0 -11.34 -15.5 -26.84 -21.33 -40.0 -10.67 -20.0 -30.76

Критерій Ходжа-Лемана рекомендує варіант Е 1 (повна перевірка) - так само як і ММ-критерій. Зміна рекомендованого варіанта відбувається тільки при n = 0.94. Тому рівномірний розподіл станів розглянутої машини повинно розпізнаватися з дуже високою ймовірністю, щоб його можна було вибрати по більшого математичного очікуванню. При цьому число реалізацій рішення завжди залишається довільним.

Критерій Гермейера при q j = 0.33 дає наступний результат (в):

e ir = e ij q j

e ir

-20.0 -22.0 -25.0 -6.67 -7.33 -8.33 -8.33 -8.33 -14.0 -23.0 -31.0 -4.67 -7.67 -10.33 -10.33 0 -24.0 -40.0 0 -8.0 -13.33 -13.33

В як оптимального вибирається варіант Е 1 . Порівняння варіантів з допомогою величин e ir показує, що спосіб дії критерію Гермейера є навіть більш гнучким, ніж у ММ-критерію.

В таблиці, наведеної нижче, рішення вибирається відповідно до BL (MM)-критерієм при q 1 = q 2 = q 3 = 1 / 2 (дані в 10 3 ).

-20.0 -22.0 -25.0 -23.33 0 -20.0 0 -14.0 -23.0 -31.0 -22.67 +6.0 -14.0 +6.0 0 -24.0 -40.0 -21.33 +15.0 0 +20.0

Варіант Е 3 (відмова від перевірки) приймається цим критерієм тільки тоді, коли ризик наближається до. В іншому випадку оптимальним виявляється Е 1 . У багатьох технічних і господарських завданнях припустимий ризик буває набагато нижче, складаючи зазвичай тільки незначний відсоток від загальних витрат. У подібних випадках буває особливо цінно, якщо неточне значення розподілу ймовірностей позначається не дуже сильно. Якщо при цьому виявляється неможливим встановити припустимий ризик заздалегідь, не залежно від прийнятого рішення, то допомогти може обчислення очікуваного ризику. Тоді стає можливим подумати, чи виправданий такий ризик. Таке дослідження зазвичай дається легше.

Результати застосування критерію твори при а = 41 Г— 10 3 і а = 200 Г— 10 3 мають вигляд:

e ir = e ij

e ir

+21 +19 +16 6384 6384 а = 41 +27 +18 +10 4860 +41 +17 +1 697 +180 +178 +175 5607 а = 200 +186 +177 +169 5563 +200 +176 +160 5632 5632

Умова e ij > 0 для даної матриці не здійснимо. Тому до елементів матриці додається (по зовнішньому сваволі) спочатку а = 41 Г— 10 3 , а потім а = 200 Г— 10 3 .

Для а = 41 Г— 10 3 оптимальним виявляється варіант Е 1 , а для а = 200 Г— 10 3 - варіант Е 3 , так що залежність оптимального варіанту від а очевидна.