Рис. 4.14. Приклад діалогового розв'язання двокритерійної задачі
Візьмемо середину відрізка  – точку
і розв’яжемо задачу  . Підставивши координати оптимальної точки в просторі змінних у вирази для критеріїв, отримаємо координати середньої точки  .
Ці дії виконуються без втручання децидента. Йому надають графічне зображення (рис. 4.14) або числову інформацію з координатами трьох точок в області критеріїв, що відповідають початковому інтервалу зміни значення критерію Q1 (точок А та В), середині цього інтервалу – точку С, і ставлять запитання: у якому напрямку від середньої точки потрібно рухатися вздовж осі критерію Q1? Децидент у прикладі вирішив поліпшити значення першого критерію, погіршивши значення другого. Тому інтервал пошуку зменшено вдвічі: тепер він простягається від точки С до точки В. На наступній ітерації (рис. 4.14, б) процедура повторюється. Тепер напрямок руху визначають відносно точки D. Децидент вирішив дещо поступитися значенням першого критерію, щоб поліпшити значення другого. Інтервал пошуку зменшено; він простягається від точки С до точки D.
Отже, інтервал пошуку звужується залежно від відповіді децидента. Шукають координати середньої точки та повторюють процедуру опитування. Її припиняють тоді, коли децидент зупинить свій вибір на одній із трьох точок або довжина інтервалу пошуку дорівнюватиме заданій точності. У цьому прикладі на кожному кроці звужується область оптимальних за Парето розв'язків, і потрібна мінімальна інформація від децидента У більшості методів багатокритерійної оптимізації використано цю ідею покрокового звуження області Парето.
Доволі поширеним є алгоритм, запропонований А.Джофріоном і модифікований багатьма дослідниками, що грунтується на принципі корисності. У ньому використано ідеї добре відомого з нелінійного програмування градієнтного методу. Цей алгоритм базується на припущенні Джофріона про те, що хоча функція корисності, яка є ввігнутою, невідома, децидент може для довільного допустимого значення векторного критерію вказати граничні значення коефіцієнтів заміщення. Ці значення отримуються безпосередньо від децидента шляхом опитування – яким значенням зміни одного з критеріїв можна скомпенсувати зміну іншого критерію (зазвичай один з критеріїв обирається як базовий, і для інших значення отримують шляхом порівняння з базовим, враховуючи, звичайно ж, координати поточної точки).
Граничні коефіцієнти заміщення й визначають градієнт функції корисності в конкретній точці  простору критеріїв із точністю до додатних коефіцієнтів, тобто напрямок «найкрутішого підйому» функції корисності. Оскільки на межі, заданій множиною оптимальних за Парето розв’язків, це може дати значення критеріїв, яким не відповідають допустимі альтернативи, то за допомогою методів нелінійного програмування визначається напрямок е, для якого похідна функції корисності максимальна за умови, що це не призводить до недопустимих розв’язків.
На кожному кроці визначають новий допустимий вектор
 ,
де – довжина кроку, зазначена децидентом.
У результаті такого ітеративного процесу отримують послідовність точок, у якій значення корисності зростають і яка за умови виконання сформульованих припущень збігається до оптимуму (рис. 4.15).
Рис. 4.15. Приклад переміщення в просторі критеріїв за методом Джофріона
Звичайно, визначення напрямку руху за допомогою оцінювання граничних значень коефіцієнтів заміщення, а також довжини кроку в цьому напрямку висуває високі вимоги до здатностей децидента, тому що граничні коефіцієнти заміщення можуть бути взаємно залежними, що ще більше ускладнює процедуру одержання потрібної інформації від децидента.
Методи з використанням бінарних відношень
Окрім безпосереднього відображення системи переваг децидента у вигляді множини критеріїв якості існують й інші можливості. Зокрема, апарат бінарних відношень дає змогу описувати загальні ситуації та використовувати для вибору рішень експертну інформацію про попарні порівняння варіантів рішень. Довільній ситуації прийняття рішення, поданій у вигляді багатокритерійної задачі, можна поставити у відповідність бінарне відношення на множині допустимих альтернатив.
Зв’язок між довільною парою альтернатив визначається послідовністю бінарних відношень. «Сильним» бінарним відношенням відповідають більші вимоги до переваги однієї альтернативи над іншою та, відповідно, більше непорівняльних варіантів. Найсильніша вимога – повне домінування.
й відповідає множина альтернатив, оптимальних за Слейтером. «Слабші» бінарні відношення визначають умови, за яких, попри суперечливі оцінки, одна з альтернатив є кращою, ніж інша.
У цих методах, які ще називають методами порогів непорівняльності, попарно порівнюють елементи множини допустимих альтернатив, виходячи з обраного бінарного відношення. Ті з них, що виявляються кращими, утворюють ядро, розмір якого залежить від кількості альтернатив. Якщо бінарне відношення є відношенням домінування на множині критеріїв «», то ядро утворює множина альтернатив, оптимальних за Парето, якщо ж «>» – оптимальних за Слейтером.
Альтернативи, що належать до ядра, вважають тимчасово непорівняльними. Після першого бінарного відношення визначають наступне – «слабше» – і кількість непорівняльних елементів зменшується. Цей процес триває доти, доки кількість елементів ядра не досягне заданого числа. Після цього ці елементи разом з останнім бінарним відношенням надають децидентові, який і приймає остаточне рішення. Окрім цього, у разі потреби децидент може отримати інформацію про попередні кроки. Елементи останнього ядра в певному розумінні найкращі; з іншого боку, вони найнесхожіші між собою.
Методи ELECTRE
Групу методів (ELECTRE I, ELECTRE II, ELECTRE III) розробив колектив французьких учених, очолюваний професором Б.Руа. У цих методах бінарне відношення переваги, сильніше за відношення Парето, будується наступним чином [58].
Для кожного з n критеріїв (числових) визначають вагу – число, що характеризує його важливість; воно тим більше, чим важливішим для децидента є критерій. Ці ваги можуть бути визначені ранжуванням або, наприклад, методом Т.Сааті. У найпростішому випадку і-му з n критерію відповідає ціле число рi, яке Б.Руа запропонував інтерпретувати як кількість голосів журі, поданих за нього.
Щоб з’ясувати, чи альтернатива x = (х1, ..., хm) краща за y = (y1, ..., ym), над відповідними образами в просторі критеріїв Q(x) = (Q1(x) , …, Qn(x)) і Q(y) = (Q1(y) , …, Qn(y)), виконують наступні дії.
Множину критеріїв Q розбивають на три підмножини:
Q+(x, у) – критерії, за якими альтернатива х перевершує у,
Q=(x, у) – критерії, за якими альтернативи х та у отримали однакові значення;
Q–(x, у) – критерії, за якими альтернатива у перевершує х.
Визначають також відповідні множини індексів I+(x, у), I=(x, у), I–(x, у) і відносну важливість  кожної з них.
Встановлюють певне порогове значення і вважають, що варіант х перевершує варіант у лише тоді, коли для певної функції, яка називається індексом згоди, виконано умову
|
(4.6)
|
Вигляд функції f залежить від модифікації методу ELECTRE. Нерівність (4.6) є необхідною, проте не достатньою умовою переваги альтернативи х над у.
У методах ELECTRE формулюються додаткові умови, що дають змогу враховувати не лише порядок оцінювання альтернатив х та у за критеріями, але й значення модулів різниць  . Ці умови, які називають індексом незгоди, можуть бути записати у вигляді
dxy d1,
де d1 – порогове значення індексу незгоди dxy, яке залежить від модифікації методу ELECTRE. За допомогою індексів згоди та незгоди визначається відношення переваги:
У методі ELECTRE І індекс згоди є відношенням суми ваг критеріїв підмножин Q+(x, у) та Q=(x, у) до загальної суми ваг:
де pі – вага і-го критерію.
Індекс незгоди обчислюють на множині критеріїв  . Для зручності подальших операцій значення індексів незгоди нормують (тобто виражають у частках найбільших значень критеріїв) і впорядковують за значеннями. Отже, обчислені значення індексів згоди та незгоди є нормованими, тобто  .
У методі ELECTRE І бінарне відношення переваги задано рівнями індексів згоди та незгоди c1 і d1 (для спрощення формул тут випущено індекси ітерації при значеннях c1 і d1). Якщо  , то альтернатива х краща за у. Таким чином рівні c1 і d1 дають змогу виділити ядро, до якого належать домінуючі та непорівняльні альтернативи. Коли значення індексів  і  , де
достатньо великі, а найбільший з індексів
достатньо малий, у методі ELECTRE II приймають гіпотезу про перевагу альтернативи х над у.
У цьому методі використовують два рівні відношення переваги – сильну та слабку перевагу. Крім того, на відміну від ELECTRE І задають декілька рівнів індексів згоди та незгоди, а саме 1 > c1 > c2 > c3 > 0, 1 > d2 > d1 > 0.
Відношення сильної переваги визначається умовою
а відношення слабкої переваги – умовою
На відміну від попередніх варіантів у методі ELECTRE III використано нечіткі відношення переваги. Отже, у методах цієї групи бінарне відношення визначає підмножину недомінованих альтернатив на множині допустимих альтернатив. Як перше відношення зазвичай беруть «» на множині критеріїв. Це дає змогу виділити як перше ядро множину рішень, оптимальних за Парето. Наступні бінарні відношення будуть вкладені: S1 S2 S3 … Sn. Щоб забезпечити вкладеність послідовних відношень, слід гарантувати виконання певних умов, які пов’язують граничні рівні індексів згоди та незгоди для сусідніх бінарних відношень.
Наприклад, у методі ELECTRE І для цих рівнів індексів на двох сусідніх ітераціях k та k + 1 має виконуватись умова  . Однак, на відміну від методу ELECTRE II, у разі застосування методу ELECTRE І на множині альтернатив можуть виникнути нетранзитивні відношення.
Можна звужувати ядро альтернатив й інакше, не використовуючи вагу критеріїв. На ідеї звуження ядра ґрунтується також метод В.Подіновського. Як і в методах ELECTRE, для цього використовують додаткову інформацію про важливість критеріїв. Проте основна й істотна відмінність методу В.Подіновського полягає в тому, що якісна інформація про критерії, що отримується від децидента, не перетворюється на кількісну. Авторові методу не знадобилося вводити вагові коефіцієнти важливості критеріїв, які вносять велику невизначеність у розв’язування задачі.
Інформацію про важливість критеріїв задають сукупністю таких повідомлень децидента:
критерій Qi, важливіший, ніж Qj;
критерії Qi та Qj, рівноцінні;
набір критеріїв  важливіший, ніж набір  ;
набори критеріїв (і однаково важливі.
Побудоване на підставі цієї інформації бінарне відношення переваги дає змогу істотно звузити множину Парето. Якщо в методах ELECTRE переваги слід оцінювати в шкалі порядку, що не завжди можливо, то в методі В.Подіновського набори критеріїв порівнює експерт-децидент, і це аж ніяк не легше.
Окрім того, метод В.Подіновського застосовний лише до однорідних критеріїв, значення яких належать до однієї й тієї самої множини. Прикладом однорідних критеріїв може служити, наприклад, множина тверджень компетентних експертів, які оцінюють варіанти за єдиною шкалою. Складнощі виникають тоді, коли критерії неоднорідні (на практиці так буває доволі часто). Оцінювання порівняльної важливості неоднорідних критеріїв по суті зводиться до визначення коефіцієнтів важливості, і в цьому випадку краще застосовувати методи ELECTRE.
Принципи вибору та бінарні відношення
Для розв’язання багатокритерійних задач сформульовано низку принципів вибору, що утворюють певну структуру S механізму вибору, яку найчастіше можна подати як певне бінарне відношення Р.
У моделі багатокритерійного оцінювання властивості кожної альтернативи відображаються в просторі критеріїв, і вибір виконують, порівнюючи образи альтернатив у цьому просторі. Структуру механізму вибору, породжену застосуванням того чи іншого принципу вибору, описують за допомогою певних класів бінарних відношень – координатних, модульних, координатно-модульних [5].
Таблиця 4.7. Бінарні відношення, використовувані в принципах вибору
Принцип вибору
|
Бінарне відношення
|
Парето
|
 
|
Слейтера
|
|
Джофріона
|
|
За еталоном
|
|
Згортка критеріїв
|
|
Лексикографічний
|
 
|
Послідовних поступок
|
 
|
|