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

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

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

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

Теорема 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) = g ₁ x ₁ + g ₂ x₂ на множині Х при " g₁, g₂ > 0 буде знайдено не більше двох ефективних альтернатив.

x 1

x 2

- grad F

f 1

f 2

A

B

Рис. 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	w 1(x)	w 2(x)
x 1
x 2
x 3
x 4
x 5

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

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

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

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

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

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

С

А

В

(250,750)

х2

х1

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

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

, та ,

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

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

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

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

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

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

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

,

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

, (3.8)

та

. (3.9)

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

При g ₁ = 2/3, g ₂ = 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)} – найбільші значення функцій цілі, якщо вони мінімізуються.

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

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