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

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

Т е о р е м а 3.5. Для того, щоб альтернатива x^*  X така, що w_i(x^*) > 0, , була ефективною при заданому при заданому векторі переваг р  Р⁺, достатньо, щоб x^* була єдиним вирішенням системи нерівностей:

p_iw_i(х^*)  k₀, iI, (3.18)

для мінімального значення параметра k₀*, для якого ця система сумісна.

Доведення

Припустимо протилежне. Тобто, що єдине вирішення системи (3.18) x^* при значенні параметра k₀ = k₀^* не є ефективним. Тоді існує альтернатива така, що w_i()  w_i(x*), iI, і хоч би одна нерівність строга. Помноживши ці нерівності на p_i > 0, i  I отримаємо, що p_iw_i()  p_iw_i(x^*)  k₀* і хоч би одна нерівність строга. Тобто отримуємо суперечність. Альтернатива задовольняє системі (3.18) із значенням параметра k₀ не більшим за k₀^*. Тим самим теорему доведено.

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

У просторі рішень компромісній альтернативі відповідає точка перетину променя, направляючі косинуси якого визначаються заданим вектором переваг р  Р⁺ за формулами (3.17), з областю ефективних альтернатив.

Із існування точок перетину виходить наявність компромісного рішення, для якого мінімально можливі зважені втрати по всіх критеріях однакові ( p_iw_i(х) = k_0(min), iI ). Якщо такої точки не існує, то для компромісної альтернативи виконуватиметься система нерівностей і цій альтернативі відповідатиме точка, найближча до заданого променя.

Для знаходження компромісного рішення побудуємо ітераційний процес з параметром k₀  ( 0; 1/М) на кожному кроці якого перевіряється сумісність системи нерівностей (3.15) для x  X і заданого вектора р.

Параметр k₀  (0; 1/М) обмежує відносні втрати w_i(х) = w_i(f_і(х)), iI. При k₀  0 відносні втрати прямують до 0, тобто функції цілі f_і(х) збігаються до своїх оптимальних значень, а при k₀  1/М нерівності (3.18) задовольняються на всій множині допустимих альтернатив Х.

Зменшуючи параметр k₀ і тим самим зменшуючи зважені втрати по всіх функціях цілі, ми наближуємося до альтернативи, що забезпечує мінімальні втрати по всіх критеріях f_і(х), тобто до компромісної альтернативи.

Ітераційний процес зупиняється, коли найменше k₀(l) (l – номер кроку), при якому система нерівностей (3.18) на множині допустимих альтернатив ще сумісна, відрізняється від найближчого значення k₀(l + 1), для якого система вже не сумісна, не більше ніж на   0. Величина  задається наперед із міркувань прийнятного часу рішення задачі. При цьому, якщо рішення системи нерівностей єдине, то це і є шукана компромісна альтернатива. Якщо ж рішення не єдине, то для отриманих альтернатив відносні втрати еквівалентні з точністю . Єдину компромісну альтернативу можна отримати оптимізуючи на цій множині еквівалентних із точністю до  альтернатив який-небудь узагальнений критерій. Наприклад:

, (3.19)

і мінімізувати його на множині

(3.20)

Такий узагальнений критерій завжди дає ефективні рішення.

Розглянемо геометричну ілюстрацію цього методу.

Рис. 3.16. Ітераційний процес пошуку компромісної альтернативи

П р и к л а д  3.14. Нехай дані рівноцінні критерії, множина допустимих альтернатив лінійна.

G – область значень перетворених критеріїв w₁ і w₂ на множині обмежень.

Г – межа цієї множини,

критерії w₁ і w₂ визначаються співвідношеннями (3.10) (тобто вони приведені до безрозмірного виду і мінімізуються),

– частина області значень w₁ і w₂ в якій ці критерії набувають значень не перевершуючі (рис. 3.16).

Оскільки критерії рівноцінні p₁ = p₂ = 1/2, то cos(β₁) = cos(β₂) = , і напрям R – бісектриса координатного кута w₁0w₂. Рішення, що дають мінімальні відносні відхилення, від оптимальних значень, знаходяться в області G на промені, що виходить із початку координат у напрямку R.

Компромісне рішення, що забезпечує мінімум відхиленням буде в точці С^* (пересічення променя із областю ефективних точок). Щоб знайти цю точку визначимо послідовно таке найменше , при якому ще не пустий переріз та G.

Якщо вектор, визначений відповідно до формули (3.16), не перетинається із областю ефективних точок, то в область , відповідну мінімальному k₀, при якому система (3.18) ще сумісна обов'язково попаде деяка множина точок, серед яких обов'язково є ефективна, якнайкраще відповідна перевазі, що задається ваговим вектором, тобто найближча до променя R.

Проаналізуємо з цих позицій деякі узагальнені критерії.

, (3.21)

де w_i(х) описується співвідношенням (3.10).

Цей метод дозволяє знайти таку альтернативу для якої або виконується система рівності р_i w_i(х*) = k₀ , для всіх iI і мінімального значення параметра k₀, або для деяких параметрів рівності не виконуються і р_i w_i(х*) < k_0(min).

Якщо така альтернатива єдина – то це є шукане компромісне рішення, інакше необхідно застосовувати додатковий критерій (3.19).

Таким чином, запропонований метод, заснований на пошуку додаткових альтернатив системи нерівностей (3.18) при мінімальному k₀, можна розглядати як спосіб розв’язування задачі (3.21).

Метод мінімізації критеріїв виду (3.19) за x  X, не дозволяє добитися вказаного вище розв’язку оскільки:

• він істотно залежить від вибору виду перетворення w_i(х), оскільки різний порядок величин w_i(х) приводить до зміни переваг, тому що доданки можуть ставати порівнянними за величиною при малих р_i;

• якщо порядок w_i(х) однаковий, переваги можуть змінюватися за рахунок несиметричної поведінки функцій f_i(х);

• якщо f_i(х) лінійні і допустима множина є багатогранником, то рішення за критерієм (3.19) лежатиме у вершині багатогранника, тоді як деяке компромісне рішення лежить на ребрі.

Якщо в якості можливого перетворення вибрати (3.10), то задачу (3.19), (3.20) знаходження єдиної альтернативи можна сформулювати таким чином.

Знайти рішення задачі параметричного програмування відносно параметра k₀ при заданому векторі переваг р:

, (3.22)

з урахуванням обмежень:

(3.23)

Рішення задачі (3.22), (3.23) при мінімально можливому k₀  (0; 1/М) і визначає шукану компромісну альтернативу.

Цей метод називається методом обмежень.

Опишемо алгоритм методу.

Алгоритм методу.

1. Відшукується мінімально можливе значення параметра k₀ при якому система обмежень (3.23) сумісна.

2. Якщо рішення системи єдине, то це і буде шуканим рішенням задачі багатокритеріальної оптимізації.

3. Якщо рішення цієї системи нерівностей не єдине, то вибір здійснюється за допомогою критерію (3.20).

Зауважимо, що цей метод не залежить від виду функцій f_i(х) і множини допустимих альтернатив Х. Необхідно лише мати ефективні способи перевірки системи нерівностей (3.23) на сумісність.