Методи прийняття рішень за умов

Апріорної невизначеності

3.1 Основні положення статистичної теорії прийняття рішень

Розглянемо спрощену дихотомічну (двохальтернативну) модель прийняття рішень. Нехай на вході СПР (рис. 3.1.1а), яка функціонує за умов дії на неї випадкового фактора f(t), роздільно у часі відбуваються дві події А₁і А₂. За основну приймемо гіпотезу про наявність на вході події А₁, а за альтернативну – гіпотезу про наявність на вході події А₂. Множина випадкових векторів на виході системи утворює підмножину простору допустимих рішень – розбиття , яке поділяється роздільною гіперповерхнею на області класу і класу (рис. 3.1.16).

а) б)

Рисунок 3.1.1– Дихотомічна модель прийняття рішень:

а) інформаційна модель СПР; б) розбиття простору

допустимих рішень на два класи

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

Якщо для двохальтернативного рішення відомі ймовірності і , тоді можна використовувати критерій максимума правдоподібності, який дозволяє мінімізувати повну ймовірність помилкового рішення:

, (3.1.1)

де – помилка першого роду;

– помилка другого роду.

З урахуванням, що , де – друга достовірність, перетворимо вираз (3.1.1) до вигляду

(3.1.2)

Необхідною умовою мінімізації Р_пом є від’ємність виразу в квадратних дужках в (3.1.2). Звідки маємо відношення правдоподібності:

(3.1.3)

Таким чином, за критичне значення критерію максимума правдоподібності слід прийняти .

У випадку, коли , тобто мають місце найбільш важкі в статистичному сенсі умови прийняття рішень, використовують критерій ідеального спостерігача, для якого згідно з (3.1.3) і рішення приймається за алгоритмом: якщо , то приймається гіпотеза , інакше – гіпотеза .

На практиці широке застосування знайшов статистичний критерій Неймана-Пірсона, який дозволяє мінімізувати вираз (3.1.1) при заданих обмеженнях на одну із помилок. Звичайно приймається . Тоді як поріг класифікації приймається величина

3.2. Мінімізація залишкової невизначеності за

статистичними критеріями

Залишкова невизначеність після прийняття рішень характеризується умовною ентропією, яка в статистичній теорії прийняття рішень подається у вигляді функції [10]

, (3.2.1)

де – логарифмічна функція втрат.

Відомо, що ймовірність прийняття гіпотези за умови дорівнює

p( )= (3.2.2)

де – умовна функція щільності розподілу ймовірностей.

Функція (3.2.2) обчислюється як результат інтегрування функції щільності розподілу ймовірностей по області , якщо і - по області , якщо . Ймовірність p( ) визначається як

p( )= (3.2.3)

де – обсяг, що відповідає області класу .

Після підстановки (3.2.2) і (3.2.3) у вираз (3.2.1) обчислимо його похідну по змінній роздільної гіперповерхні та прирівняємо її нулю:

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

що дає відношення правдоподібності :

= . (3.2.4)

Для вибору порогу розпізнавання за критерієм Неймана-Пірсона у праці [10] за формулою (3.2.4) побудовано номограму, наведену на рис. 3.2.1. Тут криві однакових рівнів відповідають значенням критерію при різних значеннях першої достовірності та помилки першого роду при

Рисунок 3.2.1– Номограма для обчислення порогу

розпізнавання за критерієм Неймана-Пірсона

Оскільки при функція (3.2.1) не належить робочій області свого визначення, то значення критерію визначаються тільки за кривими, що знаходяться в області номограми вище прямої . Для цього необхідно задати на вісі абсцис допустиме (прийнятне) значення помилки першого роду і відновити з нього перпендикуляр. За порогове можна вибирати будь-яке значення, яке перетинає перпендикуляр при . При цьому необхідно враховувати, що менше значення порогу розпізнавання гарантує більшу достовірність, але забезпечує меншу надійність (завадозахищеність) прийняття рішень. Знайдене за номограмою значення критерію Неймана-Пірсона мінімізує залишкову невизначеність (3.2.1).

3.3. Детерміновані теоретико-ігрові моделі прийняття рішень

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

Таблиця 3.3.1– Таблиця платежів

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

Величина характеризує в теорії ігор платіж і звичайно задається евристично.

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

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

. (3.3.1)

У цьому випадку виграш називаеться максиміном, який забезпечує гарантований прибуток за будь-яких станів природи.

Критерій мінімакса або втрачених можливостей.Цей критерій мінімізує програш у результаті втрачених можливостей. Тому поміняв місцями max і min у виразі (3.4.1) отримаємо критерій мінімакса:

. (3.3.2)

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

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

. (3.3.3)

Приклад 3.3.1 [14].Нехай задано матрицю виграшів (табл. 3.3.2).

Таблиця 3.3.2 – Матриця виграшів

	1	11
	10	6
	0	14

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

Знайдемо оптимальну стратегію за максимінним критерієм (3.3.1):

Таким чином, можна зробити висновок, що максимінною стратегією є .

Для визначення мінімаксної стратегії сформуємо із урахуванням табл. 3.3.2 матрицю втрачених можливостей (табл. 3.3.3).

Таблиця 3.3.3 – Матриця втрачених можливостей

Для табл. 3.3.3 за критерієм (3.3.2) знайдемо мінімаксну стратегію:

Таким чином, за мінімаксним критерієм оптимальною так само є стратегія .

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

Бачимо, що стратегія є оптимальною за всіма основними критеріями теорії ігор.

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

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

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

Таблиця 3.4.1–Таблиця платежів

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

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

. (3.4.1)

Приклад 3.4.1. Нехай відомі ймовірності і . Тоді отримаємо табл. 3.4.2.

Таблиця 3.4.2 – Матриця виграшів

	0,25	0,75

За формулою (3.4.1) маємо:

Таким чином, краще всього використовувати стратегію .

Для дослідження впливу значень ймовірності на вибір оптимальної стратегії позначимо її через змінну p. На рис. 3.4.1 показано області вибору оптимальної стратегії залежно від значень ймовірності р, які відкладаються на вісі абсцис від нуля до одиниці. Оскільки має місце , то на лівій вісі ординат відкладено згідно з табл. 3.5.2 виграші для фактора ( , а на правій вісі-для фактора .

Рисунок 3.4.1– Області вибору оптимальних стратегій

Як показано на рис. 3.4.1, при 0 < p < 1/9 краще використовувати стратегію , а при 4/9 < p < 1 – стратегію . При p=4/9 однаково, яку із стратегій або використовувати. Стратегію ні при яких значеннях ймовірності p застосовувати недоцільно.

3.5 Вибір оптимальних змішаних стратегій за умов

неповної невизначеності. Байесівський підхід

Знайдемо середній виграш для кажної допустимої стратегії S_l за теоремою про повну ймовірність:

. (3.5.1)

Стратегія, для якої функцяя U(S_l), що визначається за формулою (3.5.1), є максимальною, називаеться байесівською.

Розглянемо випадок, коли ОПР отримує деяку апріорну інформацію шляхом проведення експерименту без урахування вартості його проведення. У цьому випадку збільшення гарантованого виграшу досягається використанням не однієї стратегії, а декількох, які називаються змішаною стратегією.

Приклад 3.5.1 [14]. Для отримання гарантованої середньої корисності від запланованих турпоходів турист перед кожним турпоходом дзвонить у бюро погоди, отримуючи прогностичну інформацію. У найпростішому випадку турист повинен вибрати одну з таких альтернативних стратегій: b₁ – одягнутися стосовно до теплої погоди; b₂ – одягнутися стосовно до холодної погоди.

Як експерт по проведенню багатоденних турпоходів турист складає матрицю виграшів (табл. 3.5.1), де q₁ – тепла погода і q₂ – холодна погода

Таблиця 3.5.1– Матриця виграшів

За критерієм максиміну перевага віддається стратегії : max{min[10;0]; min{4,7}; min [0;4]}= 4. Легко перевірити, що за іншими критеріями стратегія так само є оптимальною. Таким чином, турист при виборі стратегії b₂ за критерієм максимину отримує 4 у. о. «корисності».

Тепер ускладнемо задачу. Нехай турист отримує одну із трьох відповідей: z₁ – очікується тепла погода; z₂ – очікується холодна погода; z₃ – прогноз невизначений. При цьому за накопиченими статистичними даними відомі ймовірності кожної з відповідей для двох станів природи (табл. 3.5.2)

Таблица 3.5.2– Імовірності станів природи

Тоді задача формулюється так: яку із двох стратегій b₁ або b₂ слід вибрати залежно від одного з трьох результатів експерименту. У цьому випадку маємо 2³ змішані стратегії, які наведено в таблиці 3.5.3.

Таблиця 3.5.3– Матриця змішаних стратегій

Тут стратегія S₁ є легковажною, оскільки незалежно від результату експерименту турист одягається як для теплої погоди. Стратегія S₂ – песимістична, оскільки незалежно від результату експерименту турист одягається як для холодної погоди.

Прийнятними вважаються стратегії S₃ і S₄.

Для формування таблиці корисностей обчислемо за даними табл. 3.5.1 і 3.5.2 для кожної із стратегій {S_l } і двох станів природи взважені суми корисностей U(q₁,S_l) і U(q₂,S_l):

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

У результаті отримаємо матрицю виграшів (табл. 3.5.4)

Таблиця 3.5.4 – Матриця виграшів

Виключемо з табл. 3.5.4 “погані” стратегії S₂ , S₅ і S₆, які мають середні виграші меньше ніж за іншими стратегіями. Тоді замість табл. 3.5.4 отримаємо табл. 3.5.5, в якій стратегії, що залишилися, називаються допустимими.

Таблиця 3.5.5– Матриця виграшів

З табл. 3.5.5 видно, що стратегія S₇=(b₂, b₂, b₁) є максимінною, за якою треба одягнутися тепло, якщо прогнозується тепла або холодна погода, и легко, якщо прогноз невизначений. Ця стратегія гарантує середню корисність у 5,2 у. о. на один турпохід. Для порівняння нагадаємо, що стратегія b₂ гарантує середню корисність тільки у 4 у. о.

Таким чином, використання змішаної стратегії при отриманні додаткової інформації збільшує величину виграшу.

3.6. Метод Белмана за умов невизначеності

Застосування методу Беллмана для розв’язання багатокрокових задач прийняття рішень за умов невизначеності розглянемо на конкретному прикладі.

Приклад 3.6.1[15].Торгівельна фірма повинна прийняти рішення про закупівлю партії товару у зовнішнього виробника з наступною перепродажею товару на протязі року в своїх торгівельних точках. Таким чином, умови прийняття рішення, в основному, характеризуються невизначеністю майбутнього попиту на цей товар, який може з часом змінюватися. За умовами контракту додаткову закупівлю товару фірма може здійснити лише через чотири місяці після початку календарно­го року. Таким чином, необхідно забезпечити правильне рішення як при початковій закупівлі, так і при можливій додатковій закупівлі товару з метою забезпечення максимального очікуваного прибутку. Щомісячний торгівельний прибуток, що може отримати фірма в кожній із можливих ситуацій, наведено в табл. 3.6.1.

Таблица 3.6.1 – Прибуток, що одержується при різних

рівнях попиту

У даному модельному прикладі прогнозується, що сумарний торгівельний щомісячний прибуток від продажу докупленого через чотири місяці товару буде декілька менше, ніж при початковій закупівлі великої партії, і складатиме 180 у. о. в місяць при високому попиті і 40 у. о. – при низькому попиті. Витрати на закупівлю великої та малої партії товару відповідно складають 1000 і 200 у.о., а витрати на можливу додаткову закупівлю товару (через чотири місяці) дорівнюють 840 у. о. Попередні маркетингові дослідження показали, що ймовірність високого попиту на даний товар дорівнює 0,75, а низького – 0,25. Треба рекомендувати керівництву торгівельної фірми таке вирішення проблеми, щоб забезпечити максимальний очікуваний через рік прибуток. За умов апріорної невизначеності мова може тут йти тільки про максимізацію математичного сподівання обсягу прибутку, що очікується. Якщо ситуація з торгівельною фірмою є унікальною (одиничною), тоді доцільно для формування рішення реалізовувати принцип гарантованого результату на базі максимінного критерію, що в будь-якому випадку корисно на першій стадії дослідження з метою попередньої оцінки потенційних можливостей. Подамо сформовану задачу у вигляді дерева рішень (рис. 3.6.1). Тут квадратиками зображено розв’язуючі вершини, а кружечками – допоміжні вершини, що характеризують невизначений стан середовища. Позначення відповідають табл. 3.6.1, а змінні y_t означають таке: – рішення про додаткову закупівлю товару через чотирі місяці; – рішення про відмову від додаткової закупівлі.

Рисунок 3.6.1 – Дерево рішень

Розв’язання задачі здійснимо за методом Беллмана шляхом просуванням по розв’язуючим вершинам графа справа-наліво. Таким чином, спочатку обробляється розв’язуюча вершина 4 (рис. 3.6.2).

Рисунок 3.6.2– Обчислення прибутку, що очікується, для

вершини 4

Із отриманих двох чисол 380 є найбільшим (максимізується прибуток). Цим числом відмічається вершина 4, а стрілка співпадає з напрямком (рис. 3.6.3).

Рисунок 3.6.3– Вибір напрямку руху з вершини 4

Далі переходимо до вершини 1 (рис.3.6.4). Основний висновок полягає в тому, що за критерієм математичного сподівання доцільно з вершини 1 йти в напрямку , тобто купувати велику партію товару. При цьому прибуток, що очікується, дорівнює 980 у.о. в рік.

Рисунок 3.6.4–Обчислення прибутку, що очікується, для

вершини 1

При обробленні вершини 4 формується матриця рішень (табл. 3.6.2), де: 600=180*8-840; -520=40*8-840; 400=50*8; 320=40*8. Сама матриця рішень є матрицею платежів (у ній представлено сумарний прибуток за останні вісім місяців).

Таблица 3.6.2 – Матриця рішень для вершини 4

У вершині 1 маємо матрицю рішень (платежів), представлену у вигляді табл. 3.7.3, де: 380 = 50 * 4 + 380 - 200;

280 = 40*12-200; 1400 = 200*2-1000; -280 = 60*12-1000.

Таблиця 3.6.3– Матриця рішень для вершини 1

Розв’яжемо тепер ту саму задачу, використовуючи принцип гарантованого результату. У вершині 4 так само маємо матрицю виграшів, пред­ставлену в табл. 3.6.2. За критерієм максиміну підсумовуємо, що оптимальним є рішення , оскільки найгірший можливий результат при цьому дорівнює 320 у. о. прибутку, а при виборі можемо отримати збитки в розмірі 520 у. о. З вершиною 4 тепер асоціюється число 320, а стрілка піде в напрямку . Далі переходимо до вершини 1 з матрицею із табл. 3.6.4, яка вже відрізняється від матриці із табл. 3.6.3, оскільки тут: 320 = 50 * 4 + 320 - 200.

Таблиця 3.6.4 –Матриця рішень для вершини 1 у випадку

гарантованого результату

За критерієм гарантованого результату кращей виявляється альтернатива з гарантованим прибутком в 280 у.о. в рік, тобто спочатку рекомендуеться закуплять малу партію товару. Якщо на початку року встановиться високий попит на товар (і продовжиться чотирі місяці), то ми опинимось в розвязуючій вершині 4 и отримаємо прибуток в 50*4+320-200=320 у. о. за рік. При цьому через чотирі місяці згідно з принципом гарантованого результату рекомендуеться не робити додаткових закупок товару (рішення є оптимальним у вершині 4).

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

3.7. Марківські моделі прийняття рішень

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

Елемент матриці означає ймовірність переходу системи із стану в стан . Таким чином, строки матриці відповідають "старим", а стовпчики – "новим" станам системи. Зрозуміло, що сума елементів будь-якої строки матриці дорівнює 1. Такий процес поведінки системи називаеться марківським.

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

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

Приклад 3.7.1[15].Деяка фірма займається розробкою програмного забезпечення для комп’ютерних систем. На початку кожного року вона розв’язує задачу заміни обладнання з метою забезпечення необхідного технологічного середовища розробки. Залежно від результатів експертної оцінки обладнення стан фірми (система S) характеризується як "добрий" (1), "задовільний" (2) і "поганий" (3), тобто система може знаходитися в одному із трьох указаних станів. Тоді матриця перехідних ймовірностей може мати вигляд:

Якщо матриця перехідних ймовірностей не змінюється, то достатньо проаналізувати весь життєвий цикл системи S. Допустимо, що залежно від станів, в яких послідовно знаходиться система, може бути обчислено прибуток фирми. Логічно допустити, що прибуток за період в значній мірі корелює з тим станом, в якому знаходилась фірма на початку періода, що розглядається, і в його кінці. Якщо, наприклад, у момент часу система знаходилась в "доброму" стані і в момент цей стан зберігся, то прибуток буде максимальним. Для моделювання цієї ситуації можна матриці перехідніх імовірностей поставити у відповідність матрицю прибутків .

Елемент цієї матриці означає прибуток, отриманий за период при переході системи із стану в стан . Так, число 5 означає прибуток, виражений в деяких умовних одиницях, при збереженні сис­темой "задовільного " стану. Від’ємні значення характеризують втрати.

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

Тут в матриці прибутків враховано витрати на реорганізацію та модифікацію. Наприклад, елемент матриці став менше відповідного елемента матриці R¹. Таким чином, на кожному етапі виникає проблема вибору рішень з метою максимізації прибутку, що очікується.

Для прикладу, що розглядається, розглянемо основні моменти вибору оптимального рішення. Допустимо, що планування стратегії поведінки фірми здійснюється на кінцевий період часу. Покажемо, що рішення може бути отримано за вже відомим методом динамічного програмування (метод Беллмана) у відповідності із загальною концепцією аналіза й оптимізації багатокрокових задач. Нехай період відповідає одному року, а планування здійснюється на трирічний період. Для наочності відповідне дерево рішень можна подати у вигляді графа, показаного на рис. 3.7.1. Тут кожний квадрат позначає розв’язуючу вершину і відповідає конкретному стану системи у визначений момент часу. Знак в середені квадрата означає, що в момент часу j, у'=1,2,3 (номер кроку) система знаходиться в стані 1', i = 1, 2, 3 (відповідно "добрий", "задовільний" або "поганий" стан). Дві стрілки, що виходять із кожної розв’язуючої вершины, відповідають двум альтернативам на кожному кроці: – проводити модернізацію (це верхня стрілка, яка визначає напрямок 1), або – не проводити (це нижня стрілка, яка визначає напрямок 2). Кружочки означають "випадкові" вершини, перехід із яких здійснюється у відповідності з вибраною матрицею перехідних імовірностей.