Ім'я файлу: Melynuk Т. P. КSМм-51.pdf
Розширення: pdf
Розмір: 1138кб.
Дата: 04.06.2021
скачати

33
Таблиця 2.1 - Способи нормалізації критеріїв
Нормалізація
Математичний вираз
Зведення до безрозмірних величин
y
x
f
y
x
f
|
|
Приведення до однієї розмірності
y
y
x
f
y
y
x
f
|
|
Зміна інгредієнту
)
|
(
y
x
f
)
|
(
1
y
x
f
Природна нормалізація
y
x
i
|
))
|
(
min(
))
|
(
max(
))
|
(
min(
))
|
(
(
y
x
f
y
x
f
y
x
f
y
x
f
Нормалізація порівняння
y
x
f
y
x
f
|
max
|
Нормалізація Савіджа
)
|
(
))
|
(
max(
y
x
f
y
x
f
Нормалізація усереднювання
Y
y
y
x
f
y
x
f
|
|
Кобба-Дугласа вигляду:
)]
|
(
)
(
[
))
(
(
),
|
(
)
(
))
(
(
)],
(
)
|
(
)
(
max[
))
(
(
)],
(
)
|
(
)
(
min[
))
(
(
),
|
(
)
(
))
(
(
)
(
Y
y
y
Y
y
Y
y
y
x
f
y
x
f
g
y
x
f
y
x
f
g
y
y
x
f
y
x
f
g
y
y
x
f
y
x
f
g
y
x
f
y
x
f
g
Проблеми отримання і обгрунтування вибору згорток складають основний напрям теорії корисності.
У завданнях вибору рішення, що формалізуються у вигляді моделі векторної оптимізації, першим природним кроком слід вважати виділення області компромісів (або рішень, оптимальних по Парето).

34
Вектор називається оптимальним по Парето рішенням, якщо не існує
X
x
такого, що виконані нерівності:
)
|
(
)
|
(
)
|
(
)
|
(
0 0
y
x
f
y
x
f
Y
y
y
x
f
y
x
f
Областю компромісів
x
називається підмножина допустимої множини рішень Х, що володіє наступною властивістю, всі рішення, що належать йому, не можуть бути покращені одночасно по всіх локальних критеріях — компонентам вектора ефективності.
Оптимальне рішення, вибране на основі багатокритерійного підходу незалежно від обраного принципу оптимальності, завжди повинне належати області компромісів. Інакше його можна буде покращити і, отже, воно не є оптимальним. Таким чином, область компромісів є область потенційно оптимальних розв’язків. Отже, при виборі рішення по векторному критерію ефективності можна обмежити пошук оптимального рішення областю компромісів
x
, яка, як правило, значно вужча всієї області можливих значень Х.
2.2 Методи та особливості побудови алгоритмів розв’язування задач багатокритеріальної оптимізації
Розглянемо основні методи розв’язання багатокритеріальних задач математичного програмування.
Принцип справедливого компромісу
Нехай всі локальні критерії, створюючі вектор ефективності, мають однакову важливість. Справедливим вважають такий компроміс, при якому відносний рівень зниження якості по одному або декільком критеріям не перевищує відносного рівня підвищення якості по решті критеріїв (менше або рівний).
Цьому принципу можна дати наступну математичну інтерпретацію. Нехай у області компромісів
x
задані два розв’язки
x
і
x
, які оцінюються критеріями
x
F
1
і
x
F
2
. Розв’язок
x
кращий ніж розв’язок
x
по критерію
1
F
, але

35 поступається йому по критерію
2
F
. Необхідно порівняти ці розв’язки і вибрати кращий на основі принципу справедливого компромісу.
Для порівняння цих розв’язків на основі принципу справедливого компромісу введемо міру відносного зниження якості розв’язкупо кожному з критеріїв – ціну поступки
x
:
x
F
x
x
F
x
1 1
1
max
,
,
x
F
x
x
F
x
2 2
2
max
,
Якщо відносне зниження критерію
1
F
більше, ніж критерію
2
F
, то слід віддати перевагу розв’язку
x
. Це слідує з порівняння ціни поступки по кожному критерію.
Алгоритм рішення задачі багатокритеріальної оптимізації, оснований на принципі справедливого компромісу, включає наступні кроки.
Крок 1. Вибираємо
x
і
x
Крок 2. Обчислюємо за формулою (2.1)
1
x
і
2
x
Крок 3. Якщо
1
x
>
2
x
, то вибираємо
x
, якщо
1
x
>
2
x
, то вибираємо
x
Кінець.
Модель визначення області компромісів, а також модель справедливого компромісу інваріантні до масштабу вимірювання критеріїв. Проте перша з них є допоміжною при виборі рішення, а інша може бути використана тільки в тих ситуаціях вибору рішення, для яких ідея справедливого компромісу може бути виправдана. Тому в більшості випадків доводиться вдаватися до інших принципів оптимальності, що мають сенс тільки у разі нормалізованого простору критеріїв, коли всі локальні критерії мають єдиний масштаб вимірювання. В більшості випадків масштаби вимірювання критеріїв неоднакові, і виникає необхідність проводити нормалізацію критеріїв, тобто штучно приводити їх до єдиної міри.
Більшість принципів нормалізації грунтуються на введенні ідеального рішення, тобто рішення, що володіє ідеальним вектором ефективності. Це

36
ідеальне рішення можна апріорно припустити виходячи з інформації про об'єкт, а можна вирішити задачу оптимізації для кожного локального критерію і відповідно цим рішенням, значення вектора ефективності прийняти за ідеальний вектор ефективності. Тоді вибір оптимального рішення стає рівнозначним найкращому наближенню до цього ідеального вектора.
В цьому випадку замість дійсного значення критеріїв розглядаються їх відхилення від ідеального значення
j
ij
j
F
F
F
,
або їх безрозмірне відносне значення
ij
j
j
F
F
F
При рішенні даної проблеми використовуються обидва способи нормалізації. Таким чином, успішне рішення проблеми нормалізації багато в чому залежить від того, наскільки точно і об'єктивно вдається визначити ідеальну якість розв’язку.
Після нормалізації критеріїв ефективності задача вибору рішення набуває чіткого математичного сенсу. У теоретико-множинному відношенні вона стає завданням впорядковування обмежених векторних множин, а з погляду теорії наближень – завданням наближення в метричному скінченному просторі. Це дає можливість проводити обгрунтований вибір принципів оптимальності і виявляти
їх логічний сенс.
Отже, для даного випадку принцип оптимальності ідентичний принципу наближення, а узагальнений скалярний критерій оптимізації – критерію наближення, що є деякою функцією відхилення від ідеальної функції.
Принцип слабкої оптимальності по Парето
Вектор
X
x
називається слабо оптимальним по
Парето розв’язку(оптимальним по Слейтеру), якщо не існує вектора
X
x
, такого, що задовольняє умові:
Y
y
y
x
F
y
x
f
)
|
(
)
|
(

37
Нехай x oj
(i=1,m) є оптимальними розв’язками для звичайних скалярних оптимізаційних задача, кожна з яких максимізувала компоненту F
i
(х) вектора
F(х):
m
j
x
F
j
,
1
),
(
max
Якщо вони є максимальними розв’язком для кожної i, то вважаємо, що
F
j
(x oj
)>F
i
(x j
) (i=1,m), де x oj
— оптимальне рішення задачі.
Припустимо, що S
oj відображає множину розв’язків, кожен з яких відповідає компоненті F
j
, і
}
)
(
)
(
|
{
j
oj
j
j
oj
a
x
F
x
F
x
S
, де a j
- відображає допустиму кількість обмежень відповідної області по відношенню до F
j
Тоді оптимальний достатній розв’язокце такий розв’язок, при якому мінімальний компонент (найгірший компонент) максимізовувався на множині, що задовольняє достатню умову
X
x
і
x
S
om
. Він може бути сформульовано так: max z х, z при
F
j
(x)>z, F
i
(x)>F
j
(x)
oj
-а j
, i=1,m ,
X
x
Задача не має розв’язку, якщо а j
не настільки велике, що перетин {S°
j
} непорожній. Величини а j
повинні бути визначені на основі значень F
j
(x oj
) або аналізу точності. Можна довести, що оптимальне рішення останньої задачі є оптимальне рішення по Парето.
Алгоритм рішення задачі має наступні етапи.
Крок 1. Вважаємо l=1 і вирішуємо задачу max z х, z при
F
j
(x)> z; F
i
(x)>F
j
(x)
oj
- a j
, i=1,m;
X
x
Знахидимо початковий розв’язокx
1
і оцінюємо цільову функцію F(x
1
).
Крок 2. Коли х l
задане, розкладаємо F(х l
) на задовільні і незадовільні компоненти. Позначимо їх відповідно через S і
S
. Якщо
S
, тоді задача вважається нерозв'язною, а якщо
S
то х
1
— оптимальний розв’зок, що відповідає вимогам. Якщо
<>
і S <>
, то для S
l визначається а lj
>0,

38 допустиме по відношенню до F
j
(x l
) а lj
=0 означає, що j-я цільова функція f j
(x) не може приймати значення, відмінне від f j
(x l
).
Крок 3. Розв’язуємо задачу max z х, z за умови F
j
(x) є z, j є l F
i
(x)>F
j
(x)
oj
- a j
, j є S
l
X
x
Викликаємо початковий розв’язок x l
+l. Якщо x l
+1=x l
, то задача буде нерозв'язною; якщо x l
+1<>x l
, то вважаємо 1 = 1+1 і повертаємося до кроку 2.
Кінець.
Принцип наближення по всіх локальних критеріях до ідеального розв’зку
В основі даного підходу покладена ідея наближення по всіх критеріях.
Нехай дано задачу багатокритерійного програмування
}
)
(
{
},
)
(
{
},
)
(
{
2 2
1 1
k
k
F
x
f
Max
F
x
f
Max
F
x
f
Max







і задані граничні умови
Серед розв’язків системи потрібно відшукати таке значення вектора х, при якому локальні критерії приймуть по можливості максимальне (мінімальне) значення одночасно.
Розглянемо кожну окрему функцію і допустимо, що для кожного фіксованого i (i=1,m) вирішене завдання максимізації. Нехай відповідні оптимальні плани характеризуються векторами:
)
,...,
,
(
2 1
on
o
o
x
x
x
xoi
На цих оптимальних планах визначимо значення критеріїв відповідно
F
oi
=(F
i
(x o1
), F
i
(x о2
), ... , F
i
(x on
))
Розглянемо вектор F(х) з компонентами F(x) і складемо квадрат Евклідової норми

39 2
)
(
)
(
o
F
x
F
x
R
де вектора F(x) - F
o
, визначеного для всіх
x
Відмітимо, що F
o буде одиничним вектором в просторі вектора F(x).
Назвемо його ідеальним значенням вектора F(x). Поставлене завдання тепер формулюватиметься так: дана система цільових функцій і дані умови задачі, потрібно визначити точку
x
, у якій функція R(x) досягає мінімуму. Таким чином, пошук векторно-оптимального плану
x
у даній задачі зведено до оптимізації виразу
2
)
(
)
(
o
F
x
F
x
R
на розв’язках системи лінійних нерівностей умови. Оскільки даний вираз є квадратичною функцією змінних х
1
,х
2
, … , х n
то задача пошуку векторно-оптимального плану звелася до задачі квадратичного програмування:
Задана квадратична функція R(x), визначена на множині
x
. Потрібно відшукати точку
x
, що забезпечує виконання умови
)
(
min
*)
(
x
R
x
R
Метод квазіоптимізації локальних критеріїв (метод послідовних поступок)
В методі послідовних поступок здійснюється пошук не єдиного точного оптимуму, а деякої області розв’язків, близьких до оптимального, – квазіоптимальної множини. При цьому рівень допустимого відхилення від точного оптимуму визначається з урахуванням точності постановки завдання
(наприклад, залежно від точності обчислення величини критеріїв), а також деяких практичних міркувань (наприклад, вимог точності рішення задачі).
Спочатку проводиться якісний аналіз відносної важливості критеріїв; на підставі такого аналізу критерії розташовуються і нумеруються в порядку зменшення важливості, так що головним вважається критерій
1
F
, менш важливий
2
F
, потім слідує решта локальних критеріїв
3
F
,
4
F
, ... ,
m
F
. Максимізовується перший по важливості критерій
1
F
і визначається його найбільше значення
1
M
Потім призначається допустиме зниження (поступка)
0 1
d
критерію
1
F
Визначимо нову допустиму область X(1), як підобласть X виду
1 1
1
|
)
1
(
d
M
x
F
x
X
X
n

40
Такий підхід дозволяє значно звузити первинну допустиму область X, коли переходимо до наступного по важливості критерію.
Після цього знаходимо найбільше значення
2
M
другого критерію
2
F
на множині X(1), тобто за умови, що значення першого критерію повинне бути не менше, ніж
1 1
d
M
. Знову призначається значення поступки
0 2
d
, але вже по другому критерію, яке разом з першим використовується при знаходженні умовного максимуму третього критерію, і т.д. Нарешті, максимізовувався останній по важливості критерій
m
F
за умови, що значення кожного критерію
r
F
з m—1 попередніх повинне бути не менше відповідної величини
r
r
d
M
одержувані стратегії вважаються оптимальними.
Таким чином, оптимальною вважається стратегія, що є розв’язком останньої задачі.
Якщо критерій
m
F
на множині стратегій (що задовольняють обмеженням задачі m) не досягає свого найбільшого значення
m
M
, то рішенням багатокритерійної задачі вважають максимізуючу послідовність
k
x
, з послідовності множин:
X
X
X
X
m
m
1 2
1

Практично подібні послідовності, що максимізувалися, має сенс розглядати
і для того випадку, коли верхня границя в задачі m не досягається, оскільки для вирішення екстремальних задач широко застосовуються ітеративні методи.
Алгоритм рішення задачі векторної оптимізації включає наступні кроки:
Крок 1. Нехай
0
x
— розв’зок задачі
X
x
F
)
(
max
0 1
Крок 2. Нехай
k
x
- розв’зок задачі
1
)
(
max
k
k
X
x
F
, де
k
x
визначається після призначення поступки.

1   2   3   4   5   6

скачати