Головна |
Ідеальною або точкою абсолютного максимуму називають точку в критеріальною просторі, в якій всі критерії досягають своїх максимальних значень: .
Якщо ця точка належить досяжному безлічі G, То все ефективне (паретовское) безліч складається з цієї єдиної точки (рис. 10.10) і проблеми як такої в цьому випадку немає. Однак ідеальна точка зазвичай лежить поза безлічі G і тому не реалізовується. У зв'язку з цим її іноді називають також утопічною. Ідея методу полягає в тому, щоб на безлічі G знайти точку, найбільш близьку до ідеальної. Мірою близькості виступає деяка функція відстані , В якості якої використовують в загальному випадку зважені Lp-метрікі
,
де р може бути будь-яким цілим позитивним числом і . Так як зведення в ступінь є монотонним перетворенням, то на положення екстремуму воно не впливає. Таким чином, багатокритеріальна задача зводиться до мінімізації функції
(10.20)
де - Ваги відхилень, що задаються ОПР ( = 1, > 0). На практиці частіше використовують значення р= 2. Відповідно до теореми 5 мінімізація такої функції призводить до ефективного вирішення.
Як і раніше, доцільно використовувати відхилення в відносних одиницях, для чого вираз в квадратних дужках в (10.20) можна розділити на .
приклад 10.3. Знайдемо рішення для моделі з прикладу 10.1 при однакових и р= 2. Так як = 12, = 24 і = 10, узагальнений критерій запишеться відповідно до (10.20) у вигляді
.
Після відкидання загального множника (1/3), вільного члена (820) і простих перетворень приходимо до виразу
.
Використовуючи метод квадратичного програмування, отримуємо: х = 2,97, х = 1, 52 (точка M на ріс.10.9). У цій точці f1= -5.87, f2= 16.44, f3= -1.66.
метрика з р= дає вже розглянутий раніше підхід: критеріальна функція визначається як максимальне відхилення
, (10.21)
яке слід мінімізувати по X D
приклад 10.4. Якщо скористатися сверткой (10.21) для моделі з прикладу 10.1, то отримаємо рішення: х = 1,52, х = 1,37 (точка N на рис. 10.9), в якому f1= -1,82, f2= 10,19, f3= -3,81.
приклад 10.5. Нехай потрібно максимізувати два критерії
f1(X) = -2x1+ x2,,
f2(X) = 4x1- x2
при умовах
x1+ x2 8,
-x1+ x2 2,
0 x1 6, 0 x2 4.
|
Рішення цього завдання, отримані при різних способах згортки, зведені в наступну таблицю.
№ | узагальнений критерій | Рішення | ||||
Мал. 10.11 | Х1 | Х2 | Y1 | Y2 | ||
A | -2 | |||||
K | -12 | |||||
[K, E] | [0,2] | [-12, -10] | [24,22] | |||
L | ||||||
P | 1,176 | 3,176 | 0,824 | 1,53 | ||
M | -7,7 | 18,2 | ||||
N | 4,75 | 3,25 | -6,25 | 15,75 | ||
R | 4,08 | 3,92 | -4,24 | 12,4 |
Тут квадратними дужками позначені інтервали, відповідне безлічі рішень, оптимальних у даній узагальненому критерію. Як видно з таблиці, лінійна згортка з рівними ваговими коефіцієнтами (рядок 3) дає досить однобокий результат: значення другого критерію лежать в області максимуму, а першого - в області мінімуму. Максиміна згортка дала рівні абсолютні значення критеріїв, але другий критерій сильніше, ніж перший, відрізняється від свого максимально можливого значення (рядок 4). Очевидно, якщо використовувати в цій згортку відносні величини критеріїв, взявши за базу, наприклад, різницю (maxfi-minfi ), То можна очікувати більш "справедливого" співвідношення значень критеріїв в оптимальному рішенні. Дійсно, максимізація мінімального відносної величини критерію з ваговим коефіцієнтом призводить до збільшення f2 і зменшення f1 (Рядок 5). Наступні два рішення, представлені в 6 і 7 рядках таблиці, мінімізують відхилення від ідеальної точки I. Результат, відповідний мінімуму суми квадратів відхилень. можна отримати геометрично. Так при однакових значеннях , Як в нашому випадку, лінії рівного рівня узагальненого критерію є окружності з центром в ідеальній точці. Точка мінімуму є точка дотику лінії рівного рівня і межі області досяжності G, А так як у нас лінії - окружності, то це буде підстава перпендикуляра, опущеного з ідеальної точки на найближчу кордон G (Точка M). Використання минимаксного відхилення призводить до вирівнювання відхилень критеріїв: якщо в точці M відхилення становлять 9,7 і 5,8, то в точці N - 8,25 для обох критеріїв. Рішення по максимальному відносному відхиленню представлено в рядку 8 таблиці і точкою R на рис 10.11.
Таким чином, всі способи згортки дають рішення, що належать паретовскому безлічі, яке лежить на ламаній КЕСВА (ріс.10.11).
10.2.1.7. Цільове програмування (ЦП)
Цільове програмування застосовується в основному для вирішення лінійних багатокритеріальних задач, але може бути використано і в нелінійних задачах.
Принципова відмінність ЦП від вищерозглянутих підходів - в зміні концепції мети. Замість максимізації (мінімізації) критеріїв ставиться завдання оптимального наближення до бажаних значень критеріїв, які називають також рівнями домагань ЛПР. Таким чином, ці значення, що позначаються далі як , І являють собою мету, до якої слід прагнути. Якщо в методі головного критерію обмеження на критерії (10.16) можуть призводити до нерозв'язності завдання, то в ЦП, як буде показано далі, потрібні значення , Якими б вони не були, не можуть стати причиною нерозв'язності.
Домагання ЛПР можуть бути виражені по-різному в залежності від сенсу критерію:
1) не менш ;
2) не більше ;
3) одно ;
4) належати діапазону [ ].
Відповідно по-різному ці вимоги враховуються в математичної моделі задачі.
Як правило, безліч рішень, на якому досягаються одночасно всі рівні домагань, не перетинається з допустимим безліччю. У таких випадках воно називається утопічним. Зауважимо, що утопічне безліч рішень не обов'язково має бути непустою. У той же час утопічне безліч в критеріальною просторі порожнім бути не може. Наведемо пояснюють приклади. На ріс.10.12 показані утопічні безлічі для випадку, коли домагання ЛПР задані у вигляді
| |||||
На ріс.10.13 представлений випадок, коли ЛПР має на меті у вигляді: , i =1,2,3. При цьому утопічне безліч рішень виявляється порожнім, так як немає точок, в яких одночасно всі критерії досягають рівнів домагань. Однак цілком очевидно, що в просторі критеріїв утопічне безліч не порожньо: воно складається з однієї точки з координатами ( ).
При цільовому програмуванні змінюється модель задачі:
- До вихідних умов завдання додаються так звані цільові обмеження, що відображають рівні домагань;
- З цільовими обмеженнями в модель вводяться нові змінні, що мають сенс відхилень від бажаних значень вихідних критеріїв;
- Критерій в моделі ЦП будується як функція нових змінних.
Нехай, наприклад, вихідна задача містить 4 критерії та ЛПР висуває по ним різні варіанти домагань:
,
,
,
.
Тоді цільові обмеження матимуть вигляд:
,
,
,
,
,
.
де - Змінні-відхилення, що характеризують недосягнення , - Змінні-відхилення, які означають перевищення . Всі ці відхилення небажані. Тому в моделі ЦП мета виражається мінімізацією змінних-відхилень. Так як число цих змінних більше одиниці, ми знову маємо многокритериальную завдання, в якій роль критеріїв грають змінні . Очевидно, що для її вирішення можуть бути застосовані способи, описані вище:
- Лексикографическое впорядкування ;
- Лінійна згортка
- Мінімаксна згортка
- Квадратична згортка (аналог (10.20))
Якщо вихідна модель задачі лінійна, то і моделі ЦП у всіх випадках, крім останнього, також лінійні.
Принциповою особливістю цільових Обмежень є те, що вони не звужують вихідну областю, а навпаки, розширюють, переводячи її в простір рішень більшої розмірності (за рахунок змінних di). Тому вони не можуть бути причиною нерозв'язності завдання. Остання властивість випливає також з того, що на змінні-відхилень не накладається вимога рівності нулю, а значить, завжди знайдуться такі невід'ємні di, Які забезпечать виконання цільових обмежень.
Максиміна згортка | Інтерактивні методи
Основи багатокритеріальної оптимізації | Багатокритеріальна задача математичного | Де шукати оптимальне рішення | визначення | умови оптимальності | Методи багатокритеріальної оптимізації | функція корисності | Рішення на основі лексикографічного впорядкування критеріїв | Метод головного критерію | лінійна згортка |