Оптимальність за Парето та Слейтером
На практиці задачі без невизначеностей – скоріше виняток, аніж правило. Розглядатимемо методи прийняття рішень у детермінованих ситуаціях із невизначеністю мети, що формально відображається за допомогою множини критеріїв. Отже, виникає детермінована багатокритерійна задача прийняття рішень, загальний вигляд якої є наступний:
 .
Надалі в разі потреби записуватимемо умову цієї задачі в скороченому вигляді  . Знайти розв’язок, який був би найкращим водночас за всіма критеріями, неможливо, тому що в загальному випадку поліпшення значення одного з критеріїв призводить до погіршення значення іншого. Для ілюстрації цього положення наведемо декілька прикладів умов багатокритерійних задач.
Приклад 4.1. Необхідно придбати автомобіль, узявши до уваги кілька аспектів, що відображаються критеріями якості. Важливими критеріями в цьому разі є питомі витрати пального, максимальна швидкість, комфортність, прохідність, зовнішній вигляд, вартість, гарантійний термін, наявність сервісного обслуговування, ціна. Звичайно, придбати авто, яке б витрачало найменше пального та водночас було б при цьому найдешевшим, найкомфортнішим і найшвидшим, неможливо.
Приклад 4.2. Мандрівники мають обрати місце для зупинки в горах. Важливими критеріями є наявність джерела чи річки, палива, можливість купання, відсутність комарів, хижих звірів, близькість до населених пунктів. Зрозуміло, що знайти таке місце, яке відповідало б всім цим вимогам водночас, дуже важко.
Проілюструємо геометрично задачу оптимізації за двома критеріями. При цьому вважатимемо, що критерії якості максимізуються (це припущення не обмежує загальності викладу, оскільки вираз Q(x) Min еквівалентний –Q(x) Max).
Розглянемо загальну задачу оптимізації за двома критеріями з двома змінними:
 .
Зобразимо область допустимих розв’язків у просторі змінних (х1, х2). Значення критеріїв Q1 та Q2 відображатимемо в просторі критеріїв (Q1, Q2). Кожній конкретній точці множини допустимих рішень  відповідає одне і лише одне значення кожного з критеріїв  , тобто точка в просторі критеріїв; обернене ж твердження неправильне. Це пояснюється тим, що можуть існувати різні альтернативи, які еквівалентні чи рівноцінні щодо значень критеріїв якості, тобто відповідне відображення – гомоморфне. Виконавши таку операцію для всіх точок допустимої області в просторі змінних, отримаємо її образ у просторі критеріїв.
Рис. 4.5. Відображення дискретної множини альтернатив у простір критеріїв
На рис. 4.5 наведено шість можливих альтернатив, які відображено з двовимірного простору змінних у двовимірний простір критеріїв. Точка і в просторі змінних має координати  , а її образ у просторі критеріїв –  . Альтернативи 4 та 5 відображаються в одну й ту саму точку в просторі критеріїв, тобто вони еквівалентні з погляду їх якості. Крім того, вони гірші, ніж альтернатива 2, у якої значення кожного з критеріїв більші, ніж для альтернатив 4 та 5. Альтернатива 6 гірша за альтернативи 1 і 2 з тих самих причин. Розв’язки 1, 2, та 3 непорівняльні, тобто без додаткової інформації неможливо визначити, який із них кращий, тому що значення одного критерію в них більші, а іншого – менші. Отже, виходячи з природних міркувань, ми відкинули неперспективні альтернативи.
Розглянемо тепер неперервну множину альтернатив (рис. 4.6).
Рис. 4.6. Відображення неперервної множини альтернатив із простору змінних у простір критеріїв
Кожну точку допустимої області x X відображаємо в точку області критеріїв; одержуючи таким чином образ множини допустимих альтернатив у просторі критеріїв. Проаналізувавши альтернативи за якістю так само, як у попередньому випадку, виявимо, що для неперервної області доцільно розглядати альтернативи, розташовані на фрагменті кривої А – В, включаючи точки А та В, та на фрагменті С – D виключаючи точку С, тому що альтернативи, які відповідають відрізку прямої С – В (з точкою С та без точки В), гірші, аніж альтернатива, що відповідає точці В.
Така множина включає лише недоміновані альтернативи – тобто такі, для яких немає жодної альтернативи з допустимих, яка була б ліпшою. Принцип відбору для подальшого розгляду недомінованих альтернатив називають принципом Еджворта – Парето за прізвищами вчених, які вперше застосували цей підхід до аналізу економічних проблем.
|
|
Рис. 4.7. Френсіс Ісідор Еджворт (1845 - 1926) – англійський економіст, прибічник ідеї прогресивного оподаткування
|
Рис. 4.8. Парето, Вільфредо (1848 - 1923) – італійський інженер, економіст і соціолог, один з основоположників теорії еліт. Розробив теорії, названі згодом його ім'ям: статистичне Парето-розподіл і Парето-оптимум
|
Згідно з принципом Еджворта – Парето відношення домінування на множині допустимих альтернатив формально визначають так. Розглянемо відношення «>» в просторі критеріїв. Будемо вважати, що  і  – векторні оцінки відповідно альтернатив х та у. Також уважатимемо, що Q(x) Q(y), якщо виконано умову
тобто значення всіх критеріїв для альтернативи х не гірші, ніж для альтернативи у, і, крім того, знайдеться хоча б один критерій, за яким альтернатива х виявиться кращою за альтернативу у. У цьому випадку альтернатива х домінує альтернативу у за Парето,
Множину оптимальних за Парето (чи ефективних) рішень eff(X) визначимо як
тобто альтернатива у належить до множини Парето-оптимальних, якщо серед усіх допустимих альтернатив не знайдеться жодної, яка б домінувала її в сенсі відношення «>» в просторі критеріїв.
Розглянемо відношення «>» в просторі критеріїв. Вважатимемо, що Q(x) > Q(y), якщо виконано умову
тобто за всіма критеріями альтернатива х ліпша за альтернативу у. У цьому випадку альтернатива х домінує альтернативу у за Слейтером,
Означимо множину слабо ефективних (оптимальних за Слейтером) рішень як
Так, для відображення, наведеного на рис. 4.6 до множини слабоефективних рішень належать точки, що розташовані на лінії А – В – С – D. Для відображення, проілюстрованого на рис. 4.5, множина Парето-оптимальних рішень збігається з множиною рішень, оптимальних за Слейтером.
Приклад 4.3. Задано образ множини з семи альтернатив у просторі двох критеріїв: Q(1) = (8, 2), Q(2) = (6, 2), Q(3) = (7, 1), Q(4) = (5, 5), Q(5) = (1, 8), Q(6) = (1, 7), Q(7) = (4, 3). Потрібно визначити множину альтернатив, оптимальних за Парето та Слейтером.
Подамо образ альтернатив у просторі критеріїв графічно (рис. 4.9).
Рис. 4.9. Представлення альтернатив в просторі критеріїв
Альтернатива 3 строго домінується альтернативою 1, а альтернатива 7 – альтернативою 4. Отже, альтернативи 1, 2, 4 – 6 – оптимальні за Слейтером (слабоефективні). В сенсі відношення «» альтернатива 1 домінує альтернативу 2, а альтернатива 5 – альтернативу 6. Тому множину ефективних альтернатив (оптимальних за Парето) утворюють альтернативи 1,4, 5.
Таким чином, між множинами допустимих альтернатив X, слабоефективних S(X) і ефективних альтернатив Р(Х) існує очевидне співвідношення
Р(Х) S(Х) X.
Звичайно, головне завдання в ході дослідження та розв’язання багатокритерійних задач – побудувати множину оптимальних за Парето розв’язків. Безпосередньо зробити це вдається лише для найпростіших задач, а тому зазвичай прагнуть знайти розв’язок, що належить до множини оптимальних за Парето та найбільше відповідає системі переваг децидента.
Запровадження поняття слабоефективних розв’язків пояснюється тим, що не завжди вдається отримати розв’язки, що належать до множини Парето-оптимальних, і хоча розв’язки, оптимальні за Слейтером, не такі цікаві, доводиться досліджувати випадки, коли внаслідок оптимізації за кількома критеріями одержані розв’язки, які можуть належати до множини слабоефективних.
Необхідні та достатні умови оптимальності за Парето
Множину оцінок векторного критерію в задачі багатокритерійної оптимізації часто використовують для геометричної інтерпретації поняття оптимальності за Парето. Нехай множина значень векторного критерію, який складається з двох критеріїв, має вигляд, зображений на рис. 4.10, а. Зауважимо, що множина значень векторного критерію, яка домінує за Парето значення Q(x), збігається з невід’ємним ортантом С(х), вершину якого перенесено до точки Q(x).
Рис. 4.7. Геометрична інтерпретація оптимальності за Парето
Справді, для довільної точки а С(х) цього ортанту виконуються нерівності аi Qi(x), і = 1, …, n, причому якщо а Q(x), то хоча б одна з нерівностей строга, тобто довільна точка множини С(х) Q, крім точки Q(x), домінує Q(x) за Парето. Тому на рис. 4.10, а значення векторного критерію Q(x) (тобто альтернатива х) не належить до множини оптимальних за Парето, а альтернатива х* оптимальна за Парето, оскільки виконано умову С(х) Q = {Q(x*)}, тобто перетин утворює одна точка – Q(x).
Аналіз геометричних властивостей множини оцінок векторного критерію надзвичайно корисний для виведення необхідних і достатніх умов Парето-оптимальності. Найпростіший тип умов оптимальності за Парето пов’язаний із ситуацією, коли через будь-яку оцінку векторного критерію в n-вимірному просторі можна провести опорну гіперплощину F.
Нагадаємо, що опорною гіперплощиною до опуклої множини називається така гіпер- площина, яка має щонайменше одну точку цієї множини, і всі точки цієї множини знаходяться в одному з півпросторів цієї гіперплощини. Строго опуклою множиною називають множину, до якої належать усі точки відрізка, що сполучає дві довільні точки цієї множини. Отже, якщо множина значень векторного критерію строго опукла, то наступна теорема, яку довів С.Карлін, дає умови оптимальності за Парето (рис. 4.10, б) [36].
ТЕОРЕМА 4.1. Нехай множина значень векторного критерію Q є строго опуклою, обмеженою та замкненою. Для того, щоб альтернатива х* X була оптимальною за Парето, необхідно та достатньо, щоб існували невід’ємні коефіцієнти,
що
для будь-якої іншої альтернативи x X.
Обмеженість і замкненість множини значень векторного критерію потрібні для того, щоб можна було гарантувати існування альтернатив, оптимальних за Парето.
Умову  додано для того, щоб уникнути тривіального випадку
Доведення. Необхідність. Нехай альтернатива х* оптимальна за Парето. В цьому випадку перетин конуса С(х*) з множиною векторних оцінок Q є одноелементною множиною, елементом якої є Q(x*). Із теореми про віддільність опуклих множин (Дж.Рокафеллер) випливає, що існує така гіперплощина
в просторі векторних оцінок Rn, що множина Q цілком належить одному з породжених півпросторів, а конус С(х*) – іншому. При цьому гіперплощина G має точку Q(х*), а тому  . Оскільки множина Q цілком лежить у півпросторі  , то для будь-якої точки Q(x) Q виконується нерівність  , тобто в точці х* лінійна функція від окремих критеріїв  справді досягає максимуму. Залишилося перевірити невід'ємність коефіцієнтів  . Оскільки конус С(х*) цілком міститься в півпросторі , то для будь-якої його точки справджується нерівність  , або 
Узявши  де > 0, для деякого індексу і* маємо  , звідки внаслідок довільності обрання значення індексу і* випливає невід’ємність значень  , тобто необхідність твердження теореми.
Достатність. Нехай твердження теореми виконується в точці х* для додатних значень . Якщо припустити, що х* не є оптимальною за Парето альтернативою, то існує альтернатива х', що домінує альтернативу х* в сенсі Парето, тобто  , і серед нерівностей хоча б одна строга. Однак тоді  , що призводить до суперечності.
Припустімо тепер, що  . При цьому значення деякого коефіцієнта, наприклад  дорівнює 0. Якщо альтернатива х* не оптимальна за Парето, то знайдеться хоча б одна альтернатива х', для котрої , і хоча б одна нерівність є строгою. Проте в такому разі легко переконатися, що насправді  . Справді, якщо це не так, то , що суперечить первісному припущенню. Тому  .
Розглянемо значення векторного критерію Q(x), що знаходиться на відрізку, який з’єднує точки  і  ,
 .
З одного боку,  . Однак із припущення про строгу опуклість множини значень векторного критерію Q випливає, що Q(x) – внутрішня точка множини Q, а жодна внутрішня точка опуклої замкненої множини не може бути максимумом лінійної функції. Це й доводить достатність умов теореми.
Існування опорної до множини значень векторного критерію Q площини в кожній точці, оптимальній за Парето, гарантоване і в тому випадку, коли множина альтернатив X опукла, а всі складові векторного критерію  , – строго ввігнуті функції.
Ці результати дають відповідь на питання про умови, які повинні виконуватись для векторного критерію та альтернатив, оптимальних за Парето в опуклих задачах. Однак для неопуклих множин використати лінійну функцію складових векторного критерію якості не вдасться, тому що в доведенні теореми 4.1 суттєво використано теорему про опорну гіперплощину, яка в цьому разі не виконується.
Щоб проілюструвати це, розглянемо рис. 4.11. Альтернатива х* оптимальна за Парето, оскільки ортант С(х*) перетинається з множиною Q лише в точці Q(x*).
|