Багатокритерійні задачі ДО та основні підходи до їх розв’язування
В реальних задачах вибору найбільш пріоритетного рішення, що виникають на практиці, як правило, присутні кілька критеріїв оптимальності. Під багатокритеріальною задачею найчастіше розуміють не власне вербальний опис задачі, а її модель, а саме: багатокритеріальна задача – це математична модель прийняття оптимального рішення за декількома критеріями. Ці критерії можуть відображати оцінки різних якостей об'єкта або процесу, з приводу яких приймається рішення. Оскільки, окремі критерії можуть суперечити один одному, інші діють в одному напрямку, треті - індиферентні, байдужі один до одного, то процес вирішення багатокритеріальних завдань неминуче пов'язаний з експертними оцінками як самих критеріїв, так і взаємин між ними.
Формально багатокритеріальна задача як модель задається у вигляді:
(1)де D – множина допустимих рішень; F(x) – векторна функція аргументу x, яку можна представити у такому вигляді:
F(x) = {f1 (x), f2 (x), ..., fk (x)}, (2)
де f1 (x), f2 (x), ..., fk (x) – скалярні функції векторного аргументу x, кожна з яких є математичним виразом одного критерію оптимальності. Так як в даній моделі використовується векторна цільова функція, її часто називають задачею векторної оптимізації. Очевидно, що задача (1) не належить до класу задач математичного програмування, тому що моделі цього класу задач завжди містять тільки одну цільову функцію векторного аргументу.
Інакше задачу (1) можна переписати у вигляді:
(3)де
.Тут розглядається комплексний векторний критерій, за допомогою якого можна досягти максимального ефекту, при цьому необов'язково досягнення екстремуму у всіх функціях. Існування рішення, яке буквально максимізує всі цільові функції, є рідкісним винятком. Задача векторної оптимізації в загальному випадку не має чіткого математичного рішення. Для отримання того чи іншого її вирішення необхідно використовувати додаткову суб'єктивну інформацію фахівця в даній предметній області, якого прийнято називати особою, що приймає рішення (англ. decisionmaker). Це означає, що при вирішенні задачі різними фахівцями із залученням різних джерел інформації, скоріше всього будуть отримані різні відповіді.
Основною особливістю задач векторної оптимізації є наявність невизначеності. Ця невизначеність не може бути виключена за допомогою різних прийомів моделювання та об'єктивних розрахунків. В багатокритеріальних задачах невизначеність полягає в тому, що невідомо, яким критерієм віддати перевагу і в якій мірі. Для усунення цієї невизначеності необхідно, по-перше: сформулювати спеціальний принцип оптимальності, по-друге: залучити додаткову суб'єктивну інформацію особи, що приймає рішення, засновану на її досвіді та інтуїції. Нехай х1 та х2 допустимі розв'язки задачі (3). Кажуть, що х1 краще рішення в порівнянні з х2, якщо
, 
, при чому існує i0такий, що 
. Іншими словами, будемо вважати, що рішення х1 краще в порівнянні з рішенням х2, якщо воно не гірше х2 по всіх розглянутих критеріях, причому серед всіх критеріїв є хоча б один критерій з номером i0 , для якого рішення х1 краще, ніж х2. Отже, деякий розв'язок x* задачі (3) називається ефективним рішенням даної задачі, якщо для нього не існує більш кращих розв'язків. Інакше можна сказати, що ефективним рішенням називається таке рішення x*, яке не можна поліпшити по якомусь із критеріїв, не погіршивши при цьому значення інших критеріїв. Множина ефективних рішень називається множиною Парето і позначається P(D). Очевидно, множина Парето є підмножиною множини допустимих рішень D, яка, в свою чергу, належить n-вимірному векторному простору E, тобто 
.Вектор значень критеріїв, обчислених для ефективного розв'язку F(x*), називається ефективної оцінкою. Сукупність усіх ефективних оцінок, тобто образ множини Парето в просторі критеріїв, називається множиною ефективних оцінок і, як правило, позначається як F(P). Множина ефективних оцінок є підмножиною множини допустимих рішень в просторі критеріїв F(D), яка, в свою чергу, є підмножиною k- вимірного векторного простору, тобто
. Тобто можна сказати, що множині Парето P, яка належить множині допустимих рішень D, за допомогою векторної функції F можна зіставити множину ефективних оцінок F(P). Сенс введеного поняття ефективного рішення полягає в тому, що оптимальне рішення слід шукати лише серед елементів множини Парето – множини P(D). В іншому випадку завжди знайдеться точка x, що виявляється кращою, незалежно від розстановки пріоритетів важливості окремих критеріїв. У множині Парето існує поняття узгодженого оптимуму, при якому при якому жодний з можливих розв'язків неможна покращити за якимось критерієм, не погіршивши при цьому інший. Множина розв'язків за Парето дозволяє звузити клас можливих претендентів на остаточне рішення і виключити з розгляду завідомо неконкурентоспроможні варіанти. А остаточний вибір здійснюється на основі додаткової інформації про перевагу особи, що приймає рішення. Недолік принципу Парето в тому, що він пропонує в якості розв'язку множину рішень, що не завжди прийнятно. Для того, щоб вибрати з цієї множини єдине рішення потрібна якась додаткова інформація, припущення, домовленість про те, що ж вважати найкращим рішенням. Тому потрібні якісь додаткові процедури для відшукання якогось єдиного представника з множини Парето. Специфіка розв'язку таких завдань полягає в тому, що сам вибір такої процедури, методу знаходження остаточного рішення в якійсь мірі заснований на припущеннях особи, що приймає рішення, тобто на суб'єктивній інформації. Методи вирішення задач багатокритеріальної оптимізації можна поділити на чотири групи:
– методи, засновані на згортанні критеріїв;
– методи, які використовують обмеження на критерії;
– методи цільового програмування;
– методи, засновані на знаходженні компромісного рішення.
Замість вихідної багатокритеріальної задачі відповідно до обраного методу, формується задача що її заміщає. До складу такої задачі входить один критерій, а до вихідної системи обмежень додається одне або декілька додаткових обмежень. Розв'язок такої задачі називається субоптимальним.
ВИЗНАЧЕННЯ НАЙКРАЩИХ АЛЬТЕРНАТИВ ЗА ПАРЕТО ТА ЗА СЛЕЙТЕРОМ
Рішення x*
X називається оптимальним по Парето (парето-оптимальним), якщо не існує такого можливого рішення x X , для якого має місце нерівність f (x) ≥ f (x*). Всі парето-оптимальні рішення утворюють множину Парето, що позначається Pf(X).Рішення x*
X називається оптимальним по Слейтеру, якщо не існує такого можливого рішення x X , для якого має місце нерівність f (x) > f (x*). Всі оптимальні рішення по Слейтеру утворюють множину Слейтера, що позначається S f(X).Запис
(або 
) означає виконання покомпонентних нерівностей 
(або
) для всіх j=1(1)m, причому
. Тобто компоненти першого вектора f(x′) не менші за відповідні компоненти другого вектора f(x′′) , і принаймі одна компонента першого вектора строго більша за відповідну компоненту другого (або всі компоненти першого вектора f (x′) строго більші за відповідні компоненти другого).Домінування альтернативи Ai над Aj по Парето та Слейтеру позначаються як
та 
відповідно.Приклад.
Визначити найкращі альтернативи за Парето та за Слейтером:
| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
Парето-оптимальні альтернатививизначаємо,порівнюючи біжучу альтернативу зі всіма наступними. Якщо зустрічається альтернатива, що домінується біжучою, то вона виключається з подальшого розляду. Якщож така альтернатива домінує біжучу,то біжуча виключається з розгляду,здійснюється перехід до альтернативи, наступної за біжучою і не виключеної з розгляду. Процес повторюється до моменту,поки біжучу альтернативу не буде з чим порівнювати.
Визначимо альтернативи, що домінуються, для вилучення їх з множини Парето:
A3
PA1, A3 PA4 , A3 PA5 , A3 PA7 , A3 PA8, A6 PA2 .| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
| Альтернатива, що домінує | A3 | A6 | | A3 | A3 | | A3 | A3 |
До множини найкращих альтернатив за Парето входять: A3 та A6.
Визначимо альтернативи, що домінуються, для вилучення їх з множини Слейтера:
A3
SA1, A3 SA4 , A3 SA7 , A3 SA8 , A6 SA2 .| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
| Альтернатива, що домінує | A3 | A6 | | A3 | | | A3 | A3 |
До множини найкращих альтернатив за Слейтером входять: A3, А5 та A6.
Відповідь: множина Парето {A3, A6}, множина Слейтера {A3,А5,A6}.
МЕТОД ЛІНІЙНОЇ ЗГОРТКИ
Лінійна згортка зводить задачу відшукання найкращих альтернатив за декількома критеріями до задачі відшукання найкращої альтернативи за глобальним критерієм:
де N – кількість критеріїв, M – номер альтернативи, wi – вага і-го критерію.
До недоліків методу можна віднести такі:
1) малому приросту коефіцієнтів відповідає великий приріст функції, тобто рішення задачі не є стійким;
2) необхідність визначення вагових коефіцієнтів і ступеню їх значимості (нормування кри- теріїв).
Приклад.
Визначити найкращу альтернативу за допомогою методу лінійної згортки (p1=0.2, p2=0.3, p3=0.5) для значень альтернатив в області критеріїв:
| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
Обрахуємо значення кожної альтернативи за наданих ваг критеріїв:
| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
 | 4.4 | 2.3 | 6.6 | 2.7 | 2.6 | 5.1 | 2.2 | 4.7 |
Максимальне значення суми відповідає альтернативі A3.
Відповідь: А3.
МЕТОД ЛЕКСИКОГРАФІЧНОЇ ОПТИМІЗАЦІЇ
Метод лексикографічної оптимізації базується на послідовному відшуканні найкращих альтернатив за пріоритетами критеріїв. На кожному кроці послідовно розглядаються альтернативи лише за одним критерієм, серед яких залишають лише ті, що мають найбільше значення. Після чого (в разі потреби) крок повторюють для наступного критерію на множині альтернатив, що залишились.
Приклад. Визначити найкращу альтернативу за допомогою методу лексикографічної оптимізації (Q1
Q2 Q3) для значень альтернатив в області критеріїв:| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
Крок 1. Визначимо максимальне значення альтернатив за критерієм Q1:
де і – номери альтернатив з множини альтернатив, що залишились до розгляду (на першому кроці – всі альтернативи).
Максимальне значення max Q1(Ai) =7. В множину альтернатив, що залишаються, потрібно внести всі альтернативи, для яких значення Q1(Ai) =7. В нашому випадку це лише одна альтернатива A6, а тому наступний крок не потрібен.
Відповідь: А6.
МЕТОД ПОСЛІДОВНИХ ПОСТУПОК
Метод послідовних поступок базується на послідовному відшуканні найкращих альтернатив за пріоритетами критеріїв. На кожному кроці послідовно розглядаються альтернативи лише за одним критерієм, серед яких залишають лише ті, що мають найбільше значення або менші на розмір поступки. Після чого (в разі потреби) крок повторюють для наступного критерію на множині альтернатив, що залишились.
Приклад. Визначити найкращу альтернативу за допомогою методу послідовних поступок (
) для значень альтернатив в області критеріїв:| Критерії | Альтернативи | |||||||
| А1 | А2 | А3 | А4 | А5 | А6 | А7 | А8 | |
| Q1 | 1 | 6 | 5 | 1 | 5 | 7 | 3 | 1 |
| Q2 | 4 | 2 | 7 | 5 | 2 | 4 | 2 | 5 |
| Q3 | 5 | 1 | 7 | 2 | 2 | 5 | 2 | 6 |
Крок 1. Визначимо максимальне значення альтернатив за критерієм Q1:
де і – номери альтернатив з множини альтернатив, що залишились до розгляду (на першому кроці – всі альтернативи).
Максимальне значення maxQ1(Ai)=7. В множину альтернатив, що залишаються, з врахуванням поступки потрібно внести всі альтернативи, для яких значення Q1(Ai)≥7−1≥6. В нашому випадку це альтернативи А2 та A6.
Крок 2. Визначимо максимальне значення альтернатив за критерієм Q2 з множини альтернатив, що залишились {A2,A6}.
Максимальне значення maxQ2(Ai) = 4. В множину альтернатив, що залишаються, з врахуванням поступки потрібно внести всі альтернативи, для яких значення Q2(Ai)≥4−2≥2. В нашому випадку залишаються обидві альтернативи А2 та A6.
Крок 3. На останньому кроці обирають лише альтернативи, що мають найбільше значення серед тих, що залишились, за останнім критерієм. В нашому випадку найкраща альтернатива A6, оскільки Q3(A6)=5>Q3(A2)=1.
Відповідь: А6.
МЕТОД ІДЕАЛЬНОЇ ТОЧКИ
Цей метод базується на тому що постулюється існування “ідеальної точки” для розв’язку задачі, у якій досягається екстремум всіх критеріїв (принцип Джофріона). Оскільки ідеальна точка, звичайно ж, не знаходиться серед припустимих, виникає проблема знаходження точки, що найменш віддалена від ідеальної, і належить до множини припустимих. Все було б добре, якщо б існувало єдине об’єктивне поняття “віддалі”.
Таким чином, для розв’язання задачі за допомогою методу “ідеальної точки” необхідно насамперед визначити її координати, і надалі визначити метрику, за допомогою якої можна було б виміряти віддаль до оптимальної точки. Для визначення координат “ідеальної точки” розв’язуємо n однокритерійних задач за кожним з критеріїв оптимізації
. Сукупність оптимальних значень критеріїв кожної з однокритерійних задач 
і визначить координати ідеальної точки 
в просторі критеріїв. Якщо “ідеальна точка” належить до множини припустимих (що зустрічається вкрай рідко), то розв’язок отриманий. В іншому випадку визначаємо “віддаль” до ідеальної точки, вводячи метрику, і розв’язуємо однокритерійну задачу знаходження точки з числа припустимих, яка найменш віддалена від ідеальної. Таким чином задача матиме вигляд
Якщо обрана Евклідова метрика, то критерій буде мати вигляд 
.Приклад. Визначити найкращу альтернативу за допомогою методу ідеальної точки для значень альтернатив в області критеріїв:
| Критерії | Альтернативи | |||||
| А1 | А2 | А3 | А4 | А5 | А6 | |
| Q1 | 6 | 7 | 9 | 2 | 13 | 20 |
| Q2 | 0 | -17 | 3 | 0 | -71 | -130 |
Крок 1: Визначаємо Парето-оптимальні альтернативи
| Критерії | Альтернативи | |||||
| А1 | А2 | А3 | А4 | А5 | А6 | |
| Q1 | 6 | 7 | 9 | 2 | 13 | 20 |
| Q2 | 0 | -17 | 3 | 0 | -71 | -130 |
| Парето-оптимальні альтернативи | - | - | П | - | П | П |
Крок 2: Координати ідеальної точки в просторі критеріїв будуть (20;3). Оскільки перша координата відповідає критерію Q1, належить альтернативі 6, а друга. Що відповідає критерію Q2, належить альтернативі 3, то ідеальна точка не належить до множини припустимих розв’язків, і необхідно розрахувати віддалі від кожної з альтернатив до ідеальної точки.
Крок 3: Віддаль від альтернативи 1 до ідеальної точки становитиме
і відповідно інші віддалі
Тобто, оптимальною буде альтернатива 3.
Відповідь: А3.
Розглянуті методи рішення задач багатокритеріальної оптимізації мають свої переваги та недоліки.
1. Векторна оптимізація як частковий випадок багатокритеріальної оптимізації дозволяє знайти таку область компромісів, до якої входить підмножина допустимих ефективних розв'язків, які є незрівняними за Парето. Таку підмножину можна знайти геометрично у векторній площині. Таким чином, рішення задачі векторної оптимізації дозволяє значно скоротити число усіх можливих варіантів розв'язку та допомогти серед незрівнянних за Парето варіантів, обрати той, який влаштовує особу, що приймає рішення. Але, нажаль, така постановка не дає однозначного об'єктивного рішення.
2. Задачі багатокритеріальної оптимізації можна розв'язувати з використанням відомих методів лінійного програмування, наприклад симплекс-методу, отримуючи при цьому деяке ефективне рішення. Але таке рішення не є оптимальним за комплексним критерієм, тому потребує подальшого уточнення.
3. З використанням методу згортки критеріїв можна отримати єдине ефективне і, водночас, оптимальне рішення, яке звужує область компромісів Парето до одного єдиного розв'язку. Але слід пам'ятати, що таке рішення отримано за допомогою нормування критеріїв, тобто за допомогою суб'єктивної інформації.
4. З використанням методу послідовних поступок також можна отримати єдине ефективне рішення, але таке рішення буде результатом заздалегідь визначеної похибки.