Лабораторна робота №9, Вибір рішень за допомогою дерева рішень (позиційні ігри)

« Назад

Мета: навчитися аналізувати задачі за допомогою дерева рішень та вирішувати їх у середовищі електронних таблиць

Хід роботи

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

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

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

Етап 1 Формулювання задачі. Насамперед необхідно відкинути фактори, що не стосуються проблеми, а серед множини, що залишилася, виділити істотні і несуттєві. Це дозволить привести опис задачі ухвалення рішення до форми, що піддається аналізу. Повинні бути виконані такі основні процедури:

а) визначення можливостей збору інформації для експериментування і реальних дій;

б) складання переліку подій, що з визначеною ймовірністю можуть відбутися;

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

Етап 2 Побудова дерева рішень.

Етап 3 Оцінка імовірностей станів середовища, тобто порівняння шансів виникнення кожної конкретної події. Слід зазначити, що ймовірності визначаються або на підставі наявної статистики, або експертним шляхом.

Етап 4 Встановлення виграшів (або програшів як виграшів зі знаком мінус) для кожної можливої комбінації альтернатив (дій) і станів середовища.

Етап 5 Рішення задачі.

Введемо ряд визначень.

Безумовним грошовим еквівалентом (БГЕ) гри називається максимальна сума грошей, яку ОПР готовий заплатити за участь у грі (лотереї), або, що те ж саме, та мінімальна сума грошей, за якої він готовий відмовитися від гри. Кожен індивід має свій БГЕ. Індивіда, для якого БГЕ збігається з очікуваною грошовою оцінкою (ОГО) гри, тобто із середнім виграшем у грі (лотереї), умовно називають об'єктивістом; індивіда, для якого БГЕ не дорівнює ОГО, – суб'єктивістом.

Очікувана грошова оцінка розраховується як сума добутків розмірів виграшів на імовірності цих виграшів. Наприклад, для нашої лотереї ОГО = 0,5*0 + 0,5*100 = 50 грн. Якщо суб'єктивіст схильний до ризику, то його БГЕ > ОГО. Якщо не схильний, то БГЕ < ОГО.

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

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

Таблиця 1 – Виграш компанії за різних станів середовища

Номер стратегії	Дії компанії	Виграш (грн.) при стані економічного середовища*
		сприятливий	несприятливий
1	Будівництво крупного підприємства (а1)	200000	– 180000
2	Будівництво малого підприємства (а2)	100000	– 20000
3	Продаж патенту (а3)	10000	10000
*Ймовірність настання сприятливого або несприятливого стану економічного середовища дорівнює 0,5

Розв’язання. На основі даної таблиці виграшів (утрат) можна побудувати дерево рішень (рис. 1).

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

Рис. 1. Дерево рішень без додаткового обстеження кон'юнктури ринку

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

 – рішення (рішення, що приймає гравець);

 – випадок (рішення, що «приймає» випадок);

// – відкинуте рішення.

Визначимо середній очікуваний виграш:

для вершини 1 ОГО₁ = 0,5*200 000 + 0,5*(–180 000) = 10 000 грн.;

для вершини 2 ОГО₂ = 0,5*100 000 + 0,5*(–20 000) = 40 000 грн.;

для вершини 3 ОГО₃ = 10 000 грн.

Висновок. Найбільш доцільно вибрати стратегію а₂, тобто будувати мале підприємство, а гілки (стратегії) а₁ та а₃ дерева рішень можна відкинути. ОГО найкращого рішення дорівнює 40 000 грн. Слід зазначити, що наявність стану з ймовірностями 50 % невдачі та 50 % удачі на практиці часто означає, що реальні ймовірності гравцю, швидше за все, невідомі і він усього лише приймає таку гіпотезу (так зване припущення «fіfty – fіfty» – п’ятдесят на п’ятдесят).

Розв’язання прикладу у середовищі електронних таблиць

Заповнення області вводу. Формування області вводу в даному випадку полягає у перенесенні даних таблиці 5.1. у діапазон A2:D6. При цьому зверніть увагу, що числові значення виграшів повинні міститися у відповідних клітинках діапазону C4:D6, а значення ймовірності настання сприятливого або несприятливого стану у клітинці F7 (див рис. 5.1) – це дозволить уникнути плутанини при використанні посилань у формулах області розрахунків.

Рисунок. 2. – Прийняття багатоетапних рішень в умовах ризику

Заповнення області розрахунків. Перший крок автоматизації розв’язання полягає у визначенні ОГО для кожної стратегії.

Значення ОГО зведемо у стовпчик С11:С13, а ліворуч у діапазоні В11:В13 введемо текст, що пояснює ці значення. Під час формування значень у стовпчику С11:С13 використовуємо прийом заповнення діапазону. Формула, для визначення ОГО має наступний вигляд: C4*$F$7+D4*$F$7.

Наступний крок полягає у визначенні максимального значення ОГО (клітинка Е12). Для цього використовуємо вже відому нам функцію МАХ(), аргументом якої в даному випадку буде діапазон С11:С13.

Останній крок полягає у формуванні остаточної відповіді у вигляді зручному для користувача, тобто у текстовому повідомленні – яка саме стратегія є оптимальною. Зробимо це аналогічно визначенню найкращої стратегії за критеріями прийняття рішень в умовах ризику та невизначеності. За допомогою кількох функцій IF() вкладених одна в одну порівняємо максимальне значення ОГО із значеннями ОГО для стратегій та обираємо ту, в якої це значення дорівнює максимальному, відповідь вносимо у клітинку D15.

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

Висновки

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

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

 

Ускладнимо задачу, розглянуту у прикладі 1.

Приклад 2. Нехай перш ніж приймати рішення про будівництво, керівництво компанії повинно визначити, чи замовляти додаткове дослідження стану ринку, причому ця послуга обійдеться компанії в 10 000 грн. Керівництво розуміє, що додаткове дослідження, як і раніше, не здатне дати точної інформації, але воно допоможе уточнити очікувані оцінки кон'юнктури ринку, змінивши тим самим значення імовірностей.

Щодо фірми, якій можна замовити прогноз, відомо, що вона здатна уточнити значення імовірностей сприятливого чи несприятливого результату. Можливості фірми у вигляді умовних імовірностей сприятливості й несприятливості ринку збуту представлені в табл. 2. Наприклад, коли фірма стверджує, що ринок сприятливий, то з імовірністю 0,78 цей прогноз виправдається (та з імовірністю 0,22 можуть виникнути несприятливі умови), прогноз про несприятливість ринку виправдається з імовірністю 0,73.

Таблиця 2. Результати прогнозу

Прогноз фірми	Фактично
	Сприятливий	Несприятливий
Сприятливий	0,78	0,22
Несприятливий	0,27	0,73

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

- ситуація буде сприятливою з імовірністю 0,45;

- ситуація буде несприятливою з імовірністю 0,55.

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

 

Рис. 3. Дерево рішень при додатковому обстеженні ринку (див. умовні позначки до рис. 1)

Висновки. З аналізу дерева рішень випливає: необхідно проводити додаткове дослідження кон'юнктури ринку, оскільки це дозволяє істотно уточнити прийняте Розв’язання ; якщо фірма прогнозує сприятливу ситуацію на ринку, то доцільно будувати велике підприємство (очікуваний максимальний прибуток 116 400 грн.), якщо прогноз несприятливий, – мале (очікуваний максимальний прибуток 12 400 грн.).

Завдання для самостійного розв’язання

Задача 1. Директор ліцею, навчання в якому здійснюється на платній основі, вирішує, чи варто розширювати будинок ліцею на 250 місць, на 50 місць або не проводити будівельних робіт взагалі. Якщо населення невеликого міста, у якому організований платний ліцей, буде рости, то велика реконструкція могла б принести прибуток 250 тис. грн. у рік, незначне розширення навчальних приміщень могло б приносити 90 тис. грн. прибутку. Якщо населення міста збільшуватися не буде, то велике розширення обійдеться ліцею в 120 тис. грн. збитку, а мале 45 тис. грн. Однак інформація про те, як буде змінюватися населення міста, відсутня.

Побудуйте дерево рішень і визначте кращу альтернативу, використовуючи критерій Вальда. Чому дорівнює значення ОГО для найкращої альтернативи під час відсутності необхідної інформації?

Нехай за тих же вихідних даних державна статистична служба надала інформацію про зміну чисельності населення: імовірність росту чисельності населення складає 0,7; імовірність того, що чисельність населення залишиться незмінної чи буде зменшуватися, дорівнює 0,3. Визначите найкраще Розв’язання , використовуючи критерій максимізації очікуваної грошової оцінки. Чому дорівнює значення ОГО для найкращої альтернативи при одержанні додаткової інформації?

Розв’язання задачі реалізувати за допомогою електронних таблиць.

 

Задача 2. Фірма, що виробляє обчислювальну техніку, провела аналіз ринку нового високопродуктивного персонального комп'ютера. Якщо буде випущена велика партія комп'ютерів, то при сприятливому ринку прибуток становитиме 250 тис. грн., а за несприятливих умов фірма понесе збитки в 185 тис. грн. Невелика партія техніки у випадку її успішної реалізації принесе фірмі 50 тис. грн. прибутку і 10 тис. грн. збитків – за несприятливих зовнішніх умов. Можливість сприятливого та несприятливого випадків фірма оцінює однаково. Дослідження ринку, що провів експерт, обійшлося фірмі в 15 тис. грн. Експерт вважає, що з імовірністю 0,6 ринок буде сприятливим. У той же час при позитивному висновку сприятливі умови очікуються лише з імовірністю 0,8. При негативному висновку з імовірністю 0,15 ринок також може виявитися сприятливим. Використовуйте дерево рішень, для того щоб допомогти фірмі вибрати правильну техніко-економічну стратегію. Дайте відповіді на наступні питання:

- Чи варто замовляти експерту додаткове обстеження ринку?

- Яку максимальну суму фірма може виплатити експерту за виконану роботу?

- Яка очікувана грошова оцінка найкращого розв’язку?

Розв’язання задачі реалізувати за допомогою електронних таблиць.

 

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

Таблиця 3. Відсоток браку

Відсоток браку	Ймовірність для постачальника
	А	В
1	0,7	0,4
2	0,1	0,3
3	0,09	0,15
4	0,07	0,1
5	0,04	0,05

Повні витрати, пов'язані з ремонтом одного бракованого реле, складають 5 грн.

Реле надходять партіями по 20 000 шт. Оскільки якість виробів у постачальника В гірше, він віддасть всю партію на 500 грн. дешевше. Побудуйте дерево рішень. Якого постачальника варто вибрати?

Розв’язання задачі реалізувати за допомогою електронних таблиць.

 

Перелік питань до захисту

1. Для розв’язання яких задач використовують багатоетапні (позиційні) ігри?

2. Наведіть приклади задач, що вирішуються за допомогою дерева рішень.

3. Що називається деревом рішень?

4. Перелічіть етапи розв’язання задач за допомогою дерева рішень.

5. Що називається безумовним грошовим еквівалентом?

6. Що називається очікуваною грошовою оцінкою?