Тема 1. 4. Оптимізація за багатьма функціями мети

1.4.1. Знаходження компромісного розв’язку

 

Якщо лінійна задача містить декілька критеріїв оптимізації, то методи лінійного програмування не дають можливості визначити оптимум за багатьма функціями мети. В такому разі доцільно перейти до знаходження компромісного розв’язку, не оптимального ні за жодною з ФМ, але цілком задовільного з точки зору їх сукупності. Умова ефективності компромісного розв’язку формулюється аналогічно до критерія Парето - кожний розв’язок, що не погіршує значень заданих ФМ і призводить до покращення принаймні однієї з них, є ефективним.

До найбільш опрацьованих схем компромісу належать умовна підоптимізація і скаляризація.

Розглянемо схему умовної підоптимізації. Сукупність ФМ впорядкуємо за спаданням їх вагомості і виберемо f₁(x) в якості основної ФМ, а всі інші переведемо в обмеження. В такому разі отримаємо задачу:

f₁(x) = (1.75)

(1.76)

f_r(x) = (1.77)

x_j ³ 0, , (1.78)

де r - індекс ФМ; - емпірично встановлене значення r-ої ФМ.

Якщо встановлення значень викликає труднощі, то можна скористатися схемою послідовних поступок. За цим методом початково визначаються максимальні значення f_r^* в заданій області допустимих розв’язків шляхом m-кратного розв’язування задачі (по кожній з ФМ). Далі емпірично встановлюється розмір допустимого погіршення оптимальних значень f_r^* і знаходиться компромісне рішення як оптимальний розв’язок такої задачі:

f₁(x) = (1.79)

(1.80)

(1.81)

x_j ³ 0, , (1.82)

де br - допустиме відносне погіршення оптимального значення r-ої ФМ (0<br<1).

Процес знаходження компромісного розв’язку за методом поступок є багатокроковим з коригуванням на кожному кроці значень br, аж до моменту знаходження задовільного розв"язку.

Основними питаннями, що виникають при скаляризації (згортанні векторної функції мети до скалярного виду) є врахування пріоритетів заданих ФМ, знаходження розумного компромісу між ними і знаходження спільної міри різновимірних величин.

Скаляризація на основі принципу "справедливого компромісу" полягає у переході від задачі з векторною функцією мети:

 

, (1.83)

, (1.84)

 

(1.85)

до задачі з скалярною функцією мети:

(1.86)

 

(1.87)

 

(1.88)

 

(1.89)

де l_r - коефіцієнт вагомості ФМ;

g_r - коефіцієнти переводу величин до одного виміру;

f_r, F _r - допустимі межі зміни значення r-ої функції мети.

Скаляризація на основі принципу рівномірної оптимізації (справедливого компромісу) полягає у знаходженні такого розв’язку, при якому відносні відхилення значень ФМ від своїх екстремальних значень будуть мінімальними і однаковими. З цією метою будується доповнена задача:

 

(1.90)

 

(1.91)

 

(1.92)

 

(1.93)

 

розв’язок якої буде шуканим компромісним.

З врахуванням таких змін:

,

доповнена задача зводиться до лінійного виду:

(1.94)

 

(1.95)

 

(1.96)

 

(1.97)

де Z - максимальне відносне погіршення значень функцій мети;

f_r* - максимальне значення r-ої функції мети для основної задачі.

 

1.4.2. Зведення задачі дробово-лінійного програмування до лінійного виду

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

Початкова задача має такий вигляд:

(1.98)

 

(1.99)

 

(1.100)

 

Припустимо, що і здійснимо таку заміну змінних:

(1.101)

 

(1.102)

 

Після підстановки нових змінних y₀, у_j в початкову задачу прийдемо до такої лінійної задачі:

(1.103)

 

(1.104)

 

(1.105)

 

(1.106)

Знайшовши оптимальний розв’язок лінійної задачі у₀*,у_j* з очевидністю отримаємо оптимальний розв’язок початкової задачі:

 

х_j*=у_j*у₀*.