Головна

Метод ідеальної точки

  1. Стандартний алгоритм симплекс-методу
  2. DFD - методологія в проектуванні ІС
  3. I.3.3. Методи виносу в натуру проектних точок.
  4. I.3.4. Методи підготовки даних для перенесення проекту на місцевість.
  5. III. Опис експериментальної установки та методу вимірювання
  6. III. Опис експериментальної установки та методу вимірювання
  7. III. Опис експериментальної установки та методу вимірювання

Ідеальною або точкою абсолютного максимуму називають точку в критеріальною просторі, в якій всі критерії досягають своїх максимальних значень: .

 Якщо ця точка належить досяжному безлічі 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.

R
 Так як завдання містить дві змінні і два критерії, безлічі D и G представимо на площині, що дозволяє наочно порівняти результати розглянутих підходів (ріс.10.11).

Рішення цього завдання, отримані при різних способах згортки, зведені в наступну таблицю.

 №  узагальнений критерій  Рішення
 Мал. 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 показані утопічні безлічі для випадку, коли домагання ЛПР задані у вигляді

 
 

           
   
 
   
 
D
 

 На ріс.10.13 представлений випадок, коли ЛПР має на меті у вигляді: , i =1,2,3. При цьому утопічне безліч рішень виявляється порожнім, так як немає точок, в яких одночасно всі критерії досягають рівнів домагань. Однак цілком очевидно, що в просторі критеріїв утопічне безліч не порожньо: воно складається з однієї точки з координатами (  ).

При цільовому програмуванні змінюється модель задачі:

- До вихідних умов завдання додаються так звані цільові обмеження, що відображають рівні домагань;

- З цільовими обмеженнями в модель вводяться нові змінні, що мають сенс відхилень від бажаних значень вихідних критеріїв;

- Критерій в моделі ЦП будується як функція нових змінних.

Нехай, наприклад, вихідна задача містить 4 критерії та ЛПР висуває по ним різні варіанти домагань:

,

,

,

.

Тоді цільові обмеження матимуть вигляд:

,

,

,

,

,

.

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

- Лексикографическое впорядкування ;

- Лінійна згортка

- Мінімаксна згортка

- Квадратична згортка (аналог (10.20))

Якщо вихідна модель задачі лінійна, то і моделі ЦП у всіх випадках, крім останнього, також лінійні.

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

Максиміна згортка | Інтерактивні методи


Основи багатокритеріальної оптимізації | Багатокритеріальна задача математичного | Де шукати оптимальне рішення | визначення | умови оптимальності | Методи багатокритеріальної оптимізації | функція корисності | Рішення на основі лексикографічного впорядкування критеріїв | Метод головного критерію | лінійна згортка |

© 2016-2022  um.co.ua - учбові матеріали та реферати