3.4. Властивості ефективних альтернатив і способи їх знаходження.

Нехай є задача багатокритеріальної оптимізації:

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

при цьому все і приведені до безрозмірного виду.

Теорема 3.1. Якщо множина допустимих альтернатив X випукла, а функції цілі увігнуті на допустимій множині Х, то для будь-якої ефективної альтернативи x* існує числовий вектор

,

такий, що лінійний критерій

, (3.2)

досягає мінімуму на Х при х = х*.

Теорема 3.2. Нехай х* – ефективна альтернатива множини функцій цілі , , . Тоді існує вектор c: , , , такий, що критерій

(3.3)

досягає мінімуму на множині допустимих альтернатив X, якщо x = x*.

За компонент c_i можна узяти числа , де , .

Теорема 3.3. Якщо х* - ефективна альтернатива множини функцій цілі f, то для будь-якого lI₁

або для будь-якого lI₂

Згідно приведеним властивостям можна побудувати три способи знаходження ефективних альтернатив.

Розглянемо ці способи.

Перший спосіб (заснований на теоремі 3.1)

Пошук всієї множини Х* зводиться до рішення такої задачі параметричного програмування

(3.4)

(3.5)

де для всіх iI функції W_i(х) є увігнутими безперервними функціями, а область допустимих альтернатив X є випуклою, замкненою множиною.

У тому випадку, коли функції не є увігнутими або множина допустимих альтернатив не випукла, задача (3.4), (3.5) не дозволяє відшукати всієї множини альтернатив.

П р и к л а д  3.6. Нехай область допустимих альтернатив задана обмеженнями вигляду , функції цілі :

x₁  min,

х₂  max,

Тут множиною ефективних альтернатив є дуга АВ ( див. рис. 3.5). Проте, оскільки область не випукла, в результаті мінімізації критерію F(x) = ₁x₁ + ₂x₂ на множині Х при  ₁, ₂ > 0 буде знайдено не більше двох ефективних альтернатив.

Рис. 3.5. Відшукування ефективних альтернатив за теоремою 1(до прикладу 3.6)

Другий спосіб (заснований на теоремі 3.2)

Пошук всієї множини Х* зводиться до рішення такої задачі параметричного програмування:

(3.6)

(3.7)

де W_i(х) – монотонні перетворення функції цілі f_i(х).

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

П р и к л а д 3.7. Нехай множина допустимих альтернатив задана дискретною множиною , із значеннями функцій w₁(x), w₂(x), приведеними в табл. 3.2. Обидві функції мінімізуються.

Таблиця 3.2

wixj	w1(x)	w2(x)
x1	2	5
x2	4	3
x3	4	2
x4	5	2
x5	6	1

При ₁ = ₂ = 0,5 мінімум критерію (3.6) досягається на x₂, х₃, тобто рішення не єдине.

Та, очевидно, що х₃ > x₂, оскільки х₃ має краще значення другої функції, тобто ефективним є лише варіант х₃.

В порівнянні з першим способом цей метод є більш загальним (менші вимоги до функції), проте в разі неєдиного рішення задачі (3.6), (3.7) може бути потрібний додатковий аналіз.

Помітимо, що для різних монотонних перетворень W_i при одних і тих самих значеннях параметрів знаходитимуться різні ефективні альтернативи. Проте, якщо перебрати всі значення параметрів _i  Г⁺ , отримані множини ефективних альтернатив співпадуть.

П р и к л а д  3.8. Нехай задана множина допустимих альтернатив ( її зображено на рис. 3.6) та функції цілі:

Визначимо множину ефективних альтернатив, використовуючи різні перетворення цільових функцій.

Рис. 3.6. Ілюстрація до прикладу 3.8.

Розглянемо два перетворення:

, та ,

де максимальні і мінімальні значення функцій відповідно.

Знайдемо максимальні і мінімальні значення функцій f₁ і f₂ на множині обмежень.

досягається в точці (1000,0) , =37500,

досягається в точці (700,0) , =26250,

у точці (1000,0), =50000,

у точці (250, 750) , =31250.

Побудуємо функції цілі відповідно до перетворень w¹ і w².

,

і розглянемо задачі параметричного програмування:

, (3.8)

та

. (3.9)

При ₁ = 0,8, ₂ = 0,2 мінімум критерію w¹ (задача 3.8) досягається в точці С, мінімум критерію w ² (задача 3.9) – в усіх точках ребра ВС (рис. 3.6).

При ₁ = 2/3, ₂ = 1/3 мінімум критерію w¹ (задача 3.9) всі точки ребра ВС, мінімум критерію w²(задача 3.6) – в точці В (рис. 3.6).

Третій спосіб (заснований на теоремі 3.3)

Множина ефективних альтернатив для функцій цілі f може бути знайдена при розв’язанні такої задачі параметричного програмування відносно параметрів zZ^M–1:

де Z^M – паралелепіпед ,

– означає оптимальні значення функцій цілі, f_i(min) – найменше значення функцій цілі, якщо вони максимізовувалися, і f_i(max) – найбільші значення функцій цілі, якщо вони мінімізуються.

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

Як і в другому випадку не всі альтернативи, що знайдені цим можуть бути ефективними, і потрібний додатковий аналіз.