Методи розв'язку задач багатокритеріальної оптимізації

Постановка задачі багатокритеріальної оптимізації

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

$\min _{\vec {x}}\{f_{1}({\vec {x}}),f_{2}({\vec {x}}),\dots ,f_{k}({\vec {x}})\},$

${\vec {x}}\in S$

де $f_{i}:R^{n}\to R$ це $k$ ($k\geq 2$) цільових функцій. Вектори розв'язків ${\vec {x}}=(x_{1},x_{2},\dots ,x_{n})^{T}$ належать до не порожньої області визначення $S$.

Задача багатокритеріальної оптимізації полягає у пошуку вектора цільових змінних, який задовільняє накладеним обмеженням та оптимізує векторну функцію, елементи якої відповідають цільовим функціям. Ці функції утворюють математичне описання критерію задовільності та, зазвичай, взаємно конфліктують. Звідси, «оптимізувати» означає знайти такий розв'язок, за якого значення цільових функцій були б прийнятними для постановника задачі.

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

Метод використовує множину Парето, яка у даному випадку складається з допустимих точок завдання, які не можуть бути «зрушені» в межах допустимої множини з поліпшенням відразу за обома критеріями.

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

Ідеальна точка визначається як вектор $y^{I}=(y_{1}^{I},\dots ,y_{p}^{I})$, кожна з координат якого має оптимальне значення відповідної складової цільової функції:

$y_{k}^{I}=\min _{x\in X}f_{k}(x)=\min _{y\in Y}y_{k}.$

Утопічну точку $y^{U}$ обчислюють на основі ідеальної:

$y^{U}=y^{I}-\epsilon U,$

де $\epsilon >0$, $U$ — одиничний вектор.

Приклад

Нехай на множині $\omega$ площині (x, y), яка визначається системою нерівностей:

${\begin{cases}0\leq x\leq 4,\\0\leq y\leq 2,\\x+2y\leq 6,\end{cases}}$

задані дві лінійні функції:

$U=x+y+2\qquad (1)$

$V=x-y+6$

Потрібно знайти рішення задачі:

$U\rightarrow max,V\rightarrow max$

Рішення

Рис.2

Рис.1

Розглянемо рішення цієї задачі методом ідеальної точки.

Множина $\omega$ являє собою п'ятикутник (рис. 1), вершини якого мають наступні координати: A (0; 0), B (0, 2), C (2, 2), D (4; 1), E (4; 0).

У силу лінійності критеріїв U і V п'ятикутник ABCDE переходить в п'ятикутник A* B* C* D* E* (рис. 2), координати вершин якого обчислюються за формулами (1): A* (2, 6), B* (4, 4), C* (6; 6), D* (7; 9), E* (6; 10).

Знаходимо кордон Парето. Це відрізок ^ D* E*. Точка утопії M* (7; 10) вважається заданою (її координати суть найбільше значення U і V).

Потрібно знайти на множині Парето точку, найближчу до точки утопії ^ M*. З малюнка видно, що шукана точка повинна лежати на відрізку D*E*. Проведемо через точки D* і E* пряму. Нехай

α U + β V = γ

— Її рівняння. Щоб відшукати конкретні значення параметрів α, β і γ, підставимо в нього координати обох точок D* і E*. Отримаємо

6α +10 β = γ,

7α +9 β = γ.

Віднімаючи з першої рівності другу, після простих перетворень прийдемо до співвідношення

— Α + β = 0,

звідки

α = β.

Покладемо α = β = 1. Тоді γ = 16 і

U + V = 16

— Шукане рівняння прямої.

За умовою задачі нам потрібно визначити на прямий

U + V = 16

точку$M_{0}(U_{0},V_{0})$, відстань якої від точки $M^{*}(7;10)$мінімально, тобто вирішити екстремальну задачу:

$z=(U-7)^{2}+(V-10)^{2}\rightarrow min.$

Так як U = 16 — V, то останнє співвідношення можна переписати у вигляді

$z=(9-V)^{2}+(V-10)^{2}\rightarrow min..$

Звівши у квадрат і приводячи подібні, отримуємо, що

$z=2V_{2}-38V+181\rightarrow min..$

Це рівняння описує параболу з вершиною $V_{0}={\frac {19}{2}}=9.5;z_{0}={\frac {1}{2}}=0.5$

Тоді

$V_{0}=16-V_{0}=16-9.5=6.5$

Ідеальна точка

$M_{0}(6,5;9,5)$

Відповідні значення x і y легко знаходяться із системи лінійних рівнянь

$6,5=x+y+2$

$9,5=x-y+6$

Маємо

$x=4,y=0,5.$

Зауваження. Ми розглянули задачу, в якій

Ф (x, y) → max, Ψ (x, y) → max.

На практиці часто зустрічаються випадки, коли вимоги виглядають по-іншому -

Ф (x, y) → max, Ψ (x, y) → min, Ф (x, y) → min, Ψ (x, y) → min, Функція

Θ =-Ψ

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

Ψ (x, y) → min і Θ (x, y) → max

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

Метод послідовних поступок

Суть методу

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

Див. також

• Оптимум Парето,
• Задача оптимізації.

Посилання

• А. Г. Трифонов. Многокритериальная оптимизация (рос.)
• Вільний розв'язувач interalg з українського ПЗ OpenOpt^{[недоступне посилання з квітня 2019]} для розв'язування багатокритеріальних задач з гарантованою точністю за допомогою інтервального аналізу

Джерела

• Matthias Ehrgott (2005). Multicriteria Optimization. Springer. ISBN 3-540-21398-8.
• M. Ehrgott and X. Gandibleux. Approximative Solution Methods for Multiobjective Combinatorial Optimization // TOP. — Sociedad de Estadística e Investigación Operativa, 2004. — Т. 12, вип. 1.