Метод переведення критеріїв у обмеження
Метод переведення критеріїв у обмеження – один із найзрозуміліших. Він полягає у виділенні головного критерію Q1(x), за яким виконується оптимізація, заданні нормативні значення  для кожного з критеріїв, що залишилися (значення критерію не може бути меншим за нормативне), і розв’язуванні отриманої у такий спосіб однокритерійної задачі оптимізації
Головними проблемами в застосуванні цього методу є складнощі з визначенням основного критерію та нормативних значень для інших критеріїв. Якщо ці значення недостатньо великі, то не всі резерви поліпшення значень критеріїв буде використано. Коли ж ці значення завеликі, то задача взагалі не має розв’язків, оскільки множина допустимих рішень порожня.
Приклад 4.7. Потрібно визначити найкращий розв’язок, оцінивши шість можливих альтернатив (A1 – A6) за трьома критеріями методом переведення критеріїв у обмеження за умови пошуку максимального значення критерію Q1, для таких випадків:
а) Q2 5, Q3 4;
б) Q2 7, Q3 9.
Образи альтернатив у просторі критеріїв задано в таб. 4.5.
Таблиця 4.5. Характеристики альтернатив в просторі критеріїв
Критерій
|
A1
|
A2
|
A3
|
A4
|
A5
|
A6
|
Q1
|
2
|
4
|
7
|
5
|
8
|
3
|
Q2
|
4
|
3
|
8
|
6
|
4
|
6
|
Q3
|
8
|
14
|
2
|
6
|
4
|
12
|
Відкинемо альтернативи, для яких не виконано обмеження, і серед тих, що залишилися, визначимо найкращі. Так, Q2 5 для альтернатив A3, A4, A6, а Q3 4 – для альтернатив A1, A2, A4, тобто водночас ці обмеження виконано для альтернатив А4 й А6. Для них максимальне значення критерію  , тобто вибираємо альтернативу А4. Якщо ж узяте обмеження Q2 7, Q3 9, то, хоча ці значення менші, ніж найбільші значення критеріїв (для Q2 це 8, а для Q3 – 14), не існує жодної допустимої альтернативи, для якої водночас було б виконано ці два обмеження.
Для розв’язання багатокритерійної задачі в багатьох методах пропонується спочатку впорядкувати критерії за важливістю в порядку спадання. Найжорсткіший у такому розумінні метод лексикографічної оптимізації, згідно з яким критерії спочатку впорядковують за спаданням важливості  , а потім розв’язують послідовність оптимізаційних задач за кожним із критеріїв, починаючи з Q1. Якщо при оптимальному значенні першого критерію  можна поліпшити значення наступного, то це виконують, а у протилежному випадку переходять до наступного. Процес припиняється, коли переглянуто всі критерії. Отже, на і-му кроці розв’язують задачу однокритерійної оптимізації
з додатковими обмеженнями у вигляді рівностей на оптимальні значення попередніх критеріїв. Вада цього методу – надмірна жорсткість: покращення значень наступних в лексикографічному порядку критеріїв в багатьох випадках є неможливим. Якщо децидент згідний на певне погіршення значення поточного критерію за умови, що покращаться значення наступних критеріїв, – то метод не передбачає такої процедури. Ці хиби усунуто в методі послідовних поступок.
Метод послідовних поступок
Метод послідовних поступок є одним із найобґрунтованіших змістовно, і він може дати непоганий результат, якщо суперечності у перевагах децидента відсутні. Насамперед децидент упорядковує критерії за важливістю в порядку її спадання – , як у методі лексикографічної оптимізації. Однак це відношення переваги не абсолютне, тому що децидент на кожному кроці може поступитися значенням поточного критерію відносно його оптимального значення. Це дає змогу побудувати значно гнучкішу процедуру, ніж лексикографічна оптимізація [35].
Після цього на кожному і-му кроці алгоритму розв’язують задачу оптимізації за критерієм Qi та призначають поступку Qi > 0, на яку ми готові зменшити отримане оптимальне значення критерію  , щоб поліпшити значення інших критеріїв, не таких важливих, як Qi. Значення цих критеріїв обчислюють за відомими координатами оптимуму х*. Призначення поступки означає введення на кожному кроці ще одного додаткового обмеження  , тому на (і + 1)-му кроці розв’язують задачу
Процес розв’язування закінчується тоді, коли досягнуто останнього критерію або ж призначати поступку недоцільно. У разі потреби процес повторюють, проаналізувавши попередні результати. Отже, метод послідовних поступок достатньо гнучкий та дає змогу уникнути багатьох проблем, властивих іншим методам. Для його реалізації достатньо мати ефективний метод розв’язування однокритерійної задачі певного типу.
Приклад 4.8. Задано образи альтернатив у просторі критеріїв (табл. 4.6). Необхідно знайти оптимальну альтернативу методами лексикографічної оптимізації та послідовних поступок. За допомогою методу лексикографічної оптимізації потрібно визначити найкращу альтернативу в трьох випадках із різними впорядкуваннями критеріїв за важливістю, а саме:
 .
 .
 .
У методі послідовних поступок упорядкування критеріїв за важливістю наступне: . Децидент на першому кроці призначив поступку 2, на другому – 3, на третьому – 4. Потрібно визначити, яку альтернативу вибрав децидент.
Таблиця 4.6. Характеристики альтернатив для методів послідовних поступок і лексикографічної оптимізації
Критерій
|
A1
|
A2
|
A3
|
A4
|
A5
|
A6
|
A7
|
Q1
|
6
|
8
|
7
|
8
|
8
|
3
|
2
|
Q2
|
10
|
5
|
8
|
5
|
4
|
10
|
10
|
Q3
|
8
|
6
|
12
|
3
|
4
|
12
|
4
|
Q4
|
10
|
7
|
8
|
4
|
9
|
8
|
11
|
Спочатку визначимо оптимальні альтернативи, користуючись методом лексикографічної оптимізації.
У першому випадку на першому кроці децидент обере альтернативи A2, A4, A5, тому що вони мають найліпше значення першого критерію. На другому кроці вибір буде обмежений альтернативами, обраними на першому кроці, тобто за другим критерієм порівняємо альтернативи A2, A4, A5 і обираємо альтернативи A2, A4, для яких значення другого критерію становить 5 (альтернатива A5 має значення 4). Урешті-решт, порівнявши за третім критерієм альтернативи A2 та A4, обираємо альтернативу A2 як оптимальну.
Для другого випадку на першому кроці виберемо альтернативи A1, A6, A7, для яких значення другого критерію найбільше й дорівнює 10. На наступному кроці порівняємо ці альтернативи за першим критерієм і оберемо як оптимальну альтернативу A1.
І нарешті, в останньому випадку, порівнявши альтернативи за четвертим критерієм, відразу ж оберемо як оптимальну альтернативу A7, що має найбільше значення четвертого критерія – 11.
Визначимо оптимальну альтернативу методом послідовних поступок, виходячи з наявної інформації про значення поступок і впорядкування критеріїв за важливістю. За першим критерієм децидент обере альтернативи A2, A4, A5. Оскільки для цього критерію він зробив поступку 2, то до альтернатив, що розглядаються на наступному кроці, буде додано A1 і A3.
На другому кроці з множини альтернатив {A1, A2, A3, A4, A5} потрібно обрати кращі за другим критерієм. Такою є альтернатива A1, що має найбільше значення другого критерію – 10. Зробивши поступку 3 для цього критерію, до альтернативи A1, додамо A3 (альтернативи A6 і A7 із таким самим значенням другого критерію, як і альтернатива A1, – 10, ми вже не розглядатимемо, тому що для них порушено обмеження на перший критерій). На третьому кроці оби- ремо альтернативу A3, та зробивши поступку 4 за третім критерієм, знову повернемо альтернативу A1, для якої значення третього критерію 8 = 12 – 4. Урешті-решт, на останньому кроці, порівнявши альтернативи A1 та A3 за четвертим критерієм, оберемо як оптимальну альтернативу A1.
Метод послідовних поступок є достатньо гнучким. Крім того, децидент може застосовувати його кілька разів, щоб вивчити ті фрагменти області оптимальних за Парето рішень, які найбільше його цікавлять. На кожному кроці методу потрібна інформація про значення поступки за тим чи іншим критерієм, яку надає децидент. Отже, це фактично метод діалогового типу, тому у процесі його застосування необхідно забезпечити інтерактивну взаємодію програмного забезпечення та децидента.
Діалогові методи
Діалогові методи належать до групи найгнучкіших методів пошуку розв’язків багатокритерійних задач. Характерна їх риса – участь децидента в процесі розв’язування, що дає змогу скорегувати перебіг процесу розв’язування та врахувати деякі неформальні аспекти.
Розглянемо ілюстративний приклад використання додаткової інформації від децидента для знаходження оптимального розв’язку двокритерійної задачі.
Приклад 4.9. Потрібно знайти оптимальний розв'язок наступної двокритерійної задачі:
Спочатку визначимо межі зміни значень критеріїв у критерійному просторі. Для цього розв’яжемо дві однокритерійні задачі оптимізації за кожним із критеріїв окремо та, підставивши відповідні оптимальні значення змінних, визначимо іншу координату в просторі критеріїв. Спочатку розглянемо першу задачу
Отримаємо результат
тобто координати оптимальної точки  і оптимальне значення критерію  . Підставимо координати у вираз для другого критерію і одержимо значення  .
Потім розв’яжемо задачу оптимізації за другим критерієм:
Отримаємо результат
координати оптимальної точки  та оптимальне значення критерію  , а також значення  .
Отже, одержано дві граничні точки множини Парето-оптимальних розв’язків у просторі критеріїв –  та  (рис. 4.14, а).
|