Необхідні та достатні умови оптимальності за Парето

Множину оцінок векторного критерію в задачі багатокритерійної оптимізації часто використовують для геометричної інтерпретації поняття оптимальності за Парето. Нехай множина значень векторного критерію, який складається з двох критеріїв, має вигляд, зображений на рис. 4.10, а. Зауважимо, що множина значень векторного критерію, яка домінує за Парето значення Q(x), збігається з невід’ємним ортантом С(х), вершину якого перенесено до точки Q(x).

Рис. 4.7. Геометрична інтерпретація оптимальності за Парето

Справді, для довільної точки а  С(х) цього ортанту виконуються нерівності а_i  Q_i(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^*). Із теореми про віддільність опуклих множин (Дж.Рокафеллер) випливає, що існує така гіперплощина

в просторі векторних оцінок Rⁿ, що множина Q цілком належить одному з породжених півпросторів, а конус С(х^*) – іншому. При цьому гіперплощина G має точку Q(х^*), а тому . Оскільки множина Q цілком лежить у півпросторі , то для будь-якої точки Q(x)  Q виконується нерівність , тобто в точці х^* лінійна функція від окремих критеріїв справді досягає максимуму. Залишилося перевірити невід'ємність коефіцієнтів . Оскільки конус С(х^*) цілком міститься в півпросторі , то для будь-якої його точки справджується нерівність , або

Узявши де  > 0, для деякого індексу і^* маємо , звідки внаслідок довільності обрання значення індексу і^* випливає невід’ємність значень , тобто необхідність твердження теореми.

Достатність. Нехай твердження теореми виконується в точці х^* для додатних значень . Якщо припустити, що х^* не є оптимальною за Парето альтернативою, то існує альтернатива х', що домінує альтернативу х^* в сенсі Парето, тобто , і серед нерівностей хоча б одна строга. Однак тоді , що призводить до суперечності.

Припустімо тепер, що . При цьому значення деякого коефіцієнта, наприклад дорівнює 0. Якщо альтернатива х^* не оптимальна за Парето, то знайдеться хоча б одна альтернатива х', для котрої , і хоча б одна нерівність є строгою. Проте в такому разі легко переконатися, що насправді . Справді, якщо це не так, то , що суперечить первісному припущенню. Тому .

Розглянемо значення векторного критерію Q(x), що знаходиться на відрізку, який з’єднує точки і ,

.

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

Існування опорної до множини значень векторного критерію Q площини в кожній точці, оптимальній за Парето, гарантоване і в тому випадку, коли множина альтернатив X опукла, а всі складові векторного критерію , – строго ввігнуті функції.

Ці результати дають відповідь на питання про умови, які повинні виконуватись для векторного критерію та альтернатив, оптимальних за Парето в опуклих задачах. Однак для неопуклих множин використати лінійну функцію складових векторного критерію якості не вдасться, тому що в доведенні теореми 4.1 суттєво використано теорему про опорну гіперплощину, яка в цьому разі не виконується.

Щоб проілюструвати це, розглянемо рис. 4.11. Альтернатива х^* оптимальна за Парето, оскільки ортант С(х^*) перетинається з множиною Q лише в точці Q(x^*).

Рис. 4.11. Оптимальні за Парето розв’язки для неопуклих множин

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

Отже, бажано одержати умову оптимальності за Парето для неопуклих задач у такому вигляді: щоб альтернатива х^* була оптимальною за Парето, необхідно і достатньо, щоб деяка скалярна функція , залежна від складових векторного критерію якості Q₁, ..., Q_n, досягала максимуму в точці Q(x^*). Для того, щоб таке твердження було конструктивним, потрібно вказати вигляд цієї скалярної функції.

Вважатимемо, що множина значень векторного критерію Q обмежена, замкнена та цілком лежить усередині невід’ємного ортанту Rⁿ, тобто

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

Повернемося до розгляду рис. 4.11. Оскільки перетин ортанту С(х^*) з множиною Q містить лише одну точку Q(х^*), доцільно вважати С(х^*) множиною рівня деякої функції ,

яка досягає максимального значення критерію Q в точці Q(x^*). В цьому випадку сторони ортанта є лініями рівня цієї функції, тобто описують множину точок у  Rⁿ, таких що (у) = А. Проведемо пряму через початок координат і точку Q(x^*), що описується співвідношеннями

(4.1)

де .

У точці Q(x^*) виконуються рівності . Повертаючись до рисунка, бачимо, що під прямою (4.1) лінія рівня функції  є променем, що виходить із точки Q(x^*) та задовольняє умови . Окрім того, виконується нерівність .

Аналогічно, над прямою (4.1) маємо , а відповідна частина лінії рівня  задається як . Тому функцію  можна подати у вигляді

Отриманий результат легко узагальнити на n-вимірний випадок, тому без доведення сформулюємо наступну теорему (Ю.Гермеєр) [13].

ТЕОРЕМА 4.2. Нехай множина оптимальних за Парето значень часткових критеріїв векторного критерію оптимальності є обмеженою, замкненою та цілком знаходиться усередині невід’ємного ортанта Rⁿ. Для того, щоб альтернатива х^* була оптимальною за Парето, необхідно й достатньо, щоб існували такі строго додатні коефіцієнти

для яких виконується умова

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

Теорема 4.2 корисна для розв’язання наступної задачі, що виникає доволі часто. Нехай задано якусь альтернативу х^*. Потрібно довести, що вона оптимальна за Парето, чи знайти оптимальну за Парето альтернативу х’ яка домінує альтернативу х^*. Ця теорема застосовна для неопуклих задач, розв’язання яких пов’язане з великими складнощами. Більше того, якщо навіть усі критерії є гладкими функціями, нелінійна згортка усе одно буде недиференційовною, до того ж у «найцікавіших» точках. Однак простота й наочність цієї теореми зумовили її надзвичайну корисність для різноманітних теоретичних побудов.

Принципи прийняття раціональних рішень у багатокритерійних задачах

Умови раціональності принципів прийняття рішень

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

Щоб принцип прийняття рішень W(X, Q) для детермінованих багатокритерійних задач був раціональним, необхідно дотримання таких умов [58].

1. Розв’язок має бути допустимим і таким, що звужує початкову множину альтернатив, тобто W(X, Q)  X.

2. Дві альтернативи з однаковими векторними значеннями критеріїв або обидві належать до множини рішень, або обидві не належать до неї, тобто

3. До числа потенційно можливих розв'язків належать лише ефективні тобто оптимальні за Парето: W(X, Q)  Р(Х).

4. Для кожної задачі існує щонайменше один розв'язок, тобто W(X, Q)  . Звичайно, цю умову виконано для певного, хоча й широкого класу задач.

5. Вибір альтернатив має бути узгодженим, тобто кращі альтернативи з множини X залишаються кращими й для підмножини В  X. Нехай (X, Q) та (В, Q') – дві ситуації прийняття рішення. Тоді

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

Із цієї системи умов випливає, що раціональний принцип прийняття рішень застосовний до всіх дво- та триелементних множин, тобто на множині X існує відношення переваги, що залежить лише від множини критеріїв якості Q найкращі елементи котрого і є елементами множини розв'язків W(X, Q).

Якщо для якогось принципу прийняття рішень виконано лише умови 1 і 2, то він не якісний.

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

Множина Q(X) є опуклою та замкненою. Існують такі елементи (вектори) (де R – множина раціональних чисел,

– декартовий добуток) такі і , множина Q(X) є – це та визначена для всіх X  Rⁿ.

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