Метод бажаної точки при прийнятті рішень в умовах визначеності та його програмна реалізація

Якщо наслідки оцінюються тільки за одним показником – критерієм (тобто функція f є скалярною), то відбувається перехід до "звичайної" задачі оптимізації. Для такої задачі існує єдина концепція оптимальності – альтернатива, яка забезпечує цільовій функції мінімальне чи максимальне значення є оптимальною альтернативою [2]. Нехай маємо таку ЗПР, наслідки якої оцінюються за двома показниками , а не за одним, а ціль полягає в максимізації цієї пари показників (критеріїв) одночасно, тобто за вектором .

Очевидно, що точки максимумів цих  функцій можуть збігтися тільки у виключних випадках. Такі задачі є некоректними (тобто не мають розв'язку у звичайному сенсі). Для початку необхідно визначити принцип оптимальності.

2.2 Загальні відомості  про задачі багатокритеріальної оптимізації

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

Застосування математичних методів  при прийнятті рішень дає змогу  побудувати математичну модель, що представляє ситуацію вибору рішення, тобто проблемну ситуацію. Компонентами такої моделі для задач прийняття  рішень в умовах визначеності, коли випадкові і невизначені фактори  відсутні, є: множина Х альтернатив (рішень), з якої і слід зробити вибір однієї найкращої альтернативи (оптимального розв'язку), і опис переваг ОПР. Множина альтернатив Х повинна містити не менш двох елементів для того, щоб була забезпечена можливість (воля) вибору [4].

При наявності числових оцінок наслідків  порівняння альтернатив за перевагою  ОПР здійснюється а за допомогою  заданих на Х числових функцій , які називаються критеріями (показниками корисності чи ефективності, критеріальними функціями, цільовими функціями і т.п.), а не безпосередньо. Передбачається, що (при задача оптимізації називається однокритеріальною ).

Шкала критерію. Для кожного критерію на числовій прямій вказується підмножина , на якій він приймає свої значення. На практиці множину (яку часто називають шкалою критерію ) визначають відповідно до предметного змісту цього критерію. Наприклад, якщо відомо, що значення критерію є додатнім чи невід'ємним (критерій характеризує масу, вартість тощо), то можна прийняти чи відповідно . (наприклад, якщо – деяка частка запасу ресурсів, то ), якщо значення обмежені знизу й зверху деякими природними межами а і b. то , якщо значеннями можуть слугувати лише нуль і натуральні числа (скажімо, коли визначається в результаті підрахунку кількості деяких об'єктів). то , якщо на значення немає жодних змістовних обмежень тощо.

Кількісні і якісні критерії. Для вираження «інтенсивності» істотних властивостей (ознак) рішень у задачах прийняття індивідуальних рішень слугують критерії. Наприклад, при порівнянні деяких виробів можуть використовуватися такі критерії, як маса, вартість, дата випуску, зовнішній (товарний) вид тощо. У задачах прийняття групових рішень критерій характеризує "якість" (чи перевагу) рішень із погляду індивіда i, що входить у скінченну множину М= . Наприклад, якщо множина альтернатив є скінченною та індивід і їх проранжував (упорядкував за перевагою), то можна прийняти для найбільш переважної альтернативи , для наступної за перевагою тощо.

Кількісними та якісними бувають критерії за своїм характером. Критерій є кількісним, коли його значення має сенс порівнювати, вказуючи, на скільки чи в скільки разів його значення є більшим за інший, і якісним, коли ці порівняння безглузді. Прикладом кількісного критерію є маса. Якщо фіксована одиниця виміру маси, то можна говорити про те, у скільки разів (чи на скільки) один виріб важче за інший [4]. Відношення ваги виробів не змінюється після переходу до іншої одиниці виміру, тобто після перетворень у , де k > 0. Зрозуміло, що будь-яке інше перетворення (яке не є множенням на додатне число) може привести до зміни вихідного співвідношення значень .

Всі додатні лінійні перетворення  є допустимими перетвореннями критерію у розглянутому прикладі. У загальному випадку допустимим перетворенням критерію називають функцію , якщо функція знову являється критерієм, що вимірює (характеризує) ту ж саму властивість. При заміні на множина змінюється на .

Таким чином, із кожним критерієм зв'язують множину допустимих перетворень Ф і кажуть, що цей критерій має шкалу типу Ф чи що вимірювання виконуються за шкалою типу Ф. Множина Ф вводиться разом із завданням критерію, але іноді визначення типу шкали виявляється самостійною і досить складною задачею.

У вищенаведеному прикладі . Шкала такого типу називається шкалою відношень тому, що зберігаються відношення величин = const. Розповсюдженим є випадок виміру в шкалі типу . Тут допустимими перетвореннями є множення на додатне число k і додавання довільного числа l. Така шкала називається шкалою інтервалів. Ця назва пояснюється властивістю збереження відношень інтервалів: , С = const.

Чим вужча множина Ф допустимих перетворень,  тим більш досконалою є шкала. Критерії, що мають шкалу не менш досконалу, ніж інтервальна, називаються кількісними. У більшості випадків кількісні критерії відповідають вимірам об'єктивних (фізичних) властивостей. Однак дуже поширені й критерії з менш досконалими шкалами, ніж шкала інтервалів. Порядкова шкала є найменш досконалою шкалою критеріїв, що зустрічається у задачах оптимізації. Для неї множина допустимих перетворень складається з усіх монотонно зростаючих функцій: [5].

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

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

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

Наприклад, широко відомим  є метод розв'язку багатокритеріальних  задач, заснований на "згортанні" векторного критерію в одну функцію  – узагальнений (чи агрегований) критерій . Неважко переконатися в тім, що цей метод не придатний для розв'язку задач із якісними критеріями. Візьмемо найбільш розповсюджений узагальнений критерій – лінійну "згортку" , де - деякі додатні числа, що характеризують відносну важливість критеріїв (коефіцієнти важливості). Нехай, наприклад, . Тоді вказує, що краще за тому, що 2 + 8 < 1 + 27. Однак, якщо до першого критерію застосувати допустиме перетворення , а до другого (тобто замінити на , а на ), то висновок виявиться протилежним тому, що 82 + 2 > 1 +3.

Множина досяжності. Окремі (локальні) критерії , утворюють векторний критерій , де називають множиною індексів критеріїв. Вважається, що кожна альтернатива x цілком характеризується відповідною (векторною) оцінкою, тобто вектором . Тому вибір оптимальної альтернативи з множини всіх альтернатив Х зводиться до вибору оптимальної оцінки з множини досяжних оцінок , де -вимірний числовий простір, який називається простором оцінок (критеріїв). При необхідності цей простір буде вважатися евклідовим, тобто з метрикою , інколи використовуються інші простори, наприклад, із метриками чи . Часто буває, що у реальних задачах множину Y будувати дуже складно, а то й неможливо [2]. Тому розглядається деяка більш широка множина , векторам із якої можна надати певного змісту. Найчастіше – ця множина досяжних оцінок є гіперпаралелепіпедом . Іноді Y отримують із за допомогою тих чи інших обмежень, спрямованих на виключення позбавлених чи змісту, чи заздалегідь недосяжних векторів. Введення в розгляд множини дає ряд переваг. Наприклад, виникає можливість дослідження не однієї, а відразу цілої родини задач, для кожної з яких множина досяжних оцінок входить в . Зокрема, стає можливим вивчати характерні залежності оптимального розв'язку від тих чи інших параметрів задачі.

Далі альтернативи завжди будуть позначатися літерою х із різними індексами, а відповідні їм оцінки – літерою y із тими ж індексами, наприклад: і т.п. Якщо деяка векторна оцінка є досяжною і їй відповідає кілька альтернатив, то під буде розумітися (якщо немає спеціальних застережень) довільна з цих альтернатив (тобто будь-яка альтернатива, що задовольняє рівності ).

Незалежність критеріїв  за перевагою. У багатокритеріальній задачі кожний розв'язок цілком характеризується своєю оцінкою y=f(x) і тому вибір оптимального розв'язку зводиться до вибору оптимальної оцінки з множини Y всіх досяжних оцінок.

Природно, що найбільш просто порівнювати  за перевагою ті векторні оцінки, що відрізняються одна від одної  лише однією компонентою. У загальному випадку, значення критерію можуть по-різному співвідноситися за перевагою ОПР у залежності від того, які значення всіх інших критеріїв. Інакше кажучи, для чисел s і t з Y може виявитися, наприклад, що оцінка є переважнішою за , однак менш краща у порівнянні з . І тоді сказати, яке із значень критерію s чи t – переважніше, не вказуючи значень інших критеріїв, неможливо.

Критерій  , для якого має місце зазначене твердження, називається залежним за перевагою від інших. Наприклад, якщо відповідно – довжина й ширина кімнати, а висота стелі, то з погляду мешканця залежить за перевагою від ( ) [6]. Ще приклад: кожний з критеріїв (температура повітря) і (його вологість) залежать за перевагою один від одного (мається на увазі комфортність для людини).

Однак, набагато частіше зустрічаються  критерії, для яких можна впорядкувати за перевагою всі їх значення без  розгляду значень інших критеріїв. Прикладами є вже згадувані критерії доходу, витрат і т.п. Такі критерії називаються незалежними за перевагою  від інших [6]. Більш точно, критерій є незалежним за перевагою від інших m-1 критеріїв, якщо для будь-яких чотирьох оцінок виду:

, ,

,

із співвідношення R завжди випливає R .

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

Задачі, в яких усі критерії незалежні  за перевагою, тобто кожен критерій незалежний за перевагою від сукупності всіх інших, а відношення нестрогої  переваги на множині значень кожного  критерію є відношення " " ("не менше"), називаються багатокритеріальними задачами максимізації. В таких задачах кожному критерію бажано мати можливо більше значення, чи, як говорять, кожен критерій бажано максимізувати. Якщо ж у задачі кожен критерій бажано мінімізувати, то вона називається багатокритеріальною задачею мінімізації.

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

2.3 Постановка задачі  багатокритеріальної оптимізації

Будемо розглядати скінченновимірні задачі багатокритеріальної максимізації:

де Х – множина альтернатив, яка є множиною з простору ; – вектор критеріїв, який задається відображенням ; - множина індексів критеріїв, m – кількість критеріїв. У таких задачах множина альтернатив Х, як правило, виділяється з якоїсь більш широкої множини за допомогою обмежень, що найчастіше представляються у виді нерівностей:

,

де  – числові функції, які визначені на D. При цьому вважається, що і вектор критеріїв також визначений на D.

У ролі множини D, як правило, виступає або весь простір , або деяка його специфічна підмножина, наприклад, невід'ємний ортант , утворений усіма векторами з невід'ємними компонентами: .

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

Класи задач багатокритеріальної  оптимізації. В залежності від структури множини Х (чи D) і властивостей функцій (а також ) для зручності досліджень виділяють різні класи багатокритеріальних задач. Так, якщо множина Х (чи D) містить скінченну кількість елементів, то задача називається скінченною, а якщо Х (чи D) є зліченною множиною, то – дискретною.

Зокрема, якщо в кожного вектора  з Х (чи D) компоненти – цілі числа, то задача називається цілочисельною. А якщо вектори, які утворюють Х  (чи D) є бульовими (тобто складаються з нулів та одиниць), то і сама задача називається бульовою.

Якщо Х (чи D) опукла множина, а усі - угнуті функції, то задача називається угнутою. Зокрема, якщо Х – поліедральна множина (тобто "вирізана" з скінченною системою лінійних нерівностей і рівностей), а усі - лінійні, то багатокритеріальна задача називається лінійною [2].

Ефективні й слабко-ефективні  оцінки й альтернативи. В багатокритеріальній задачі максимізації із двох векторних оцінок, що відрізняються лише однією компонентою, переважнішою буде та, у якої ця компонента більша. А що можна сказати про векторні оцінки , для яких виконуються нерівності:

              (2.1)

Для цього згадаємо, як описуються переваги.

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