8556
.pdfНаконец получаем: x* 3,629 .
Получили одну из эффективных точек для оптимизационной задачи.
Прием 2.
Может применяться при условии fi 0 . Вводятся в рассмотрение вспомогательные функции:
i ( x ) f i ( xf)* f i* ,
i
которые можно рассматривать как относительное отклонение частного критерия от его наименьшего значения.
Важность i -го критерия определяется через неравенство:
i ( x ) i 0 , где i задает постановщик задачи:
чем важнее критерий, тем меньше i . Затем для каждого критерия вычисляется ра-
диус шара R*i , имеющего центром x*i , являющуюся решением задачи:
fi ( x ) min, |
|
x D , внутри которого выполняются условия: i ( x ) i , |
x D . |
||
Далее i |
вычисляются по формуле: |
|
|||
i |
1 / R*i |
|
. |
|
|
|
* |
|
|||
|
( 1 / Ri |
) |
|
|
При таком подходе важность критерия определяется двумя факторами:
выбором величины i ;
видом функции fi ( x ) .
Это является бесспорным достоинством метода. Проиллюстрируем на нашем при-
мере 1:
f1* 1, |
x*1 = 3 |
f2* 2, |
x*2 = 5 |
Назначим 1 2 0,1 .
На этом этапе мы не даем ни одному из двух критериев никакого предпочтения.
( x ) 2* ( x 3 )2 0,1 |
|
1 |
|
R* = 0,224; R* = 0,316 |
|
1 |
2 |
1 0,585 |
2= 0,415 . |
21
В результате получили, что 1-й критерий оказался важнее 2-го.
Замечание.
Приемы 1, 2 имеют довольно ограниченное применение, так как в силу необходимо-
сти решения целой серии однокритериальных задач, кроме того определяющим яв-
ляется вид функции f1 ( x ), ..., fk ( x ) .
Прием 3. Использование попарных приоритетов.
В продолжение последнего замечания следует отметить, что часто не вид функции f1 ( x ), ..., fk ( x ) является решающим в определении важности критериев, а
сама сущность проблемы, то есть степень важности одного критерия по сравнению с другим определяется не из математической постановки задачи, а путем привлечения
дополнительной информации.
Наиболее приемлемым подходом является попарное сравнение критериев по
важности в количественном выражении.
Попарное сравнивание критериев по предпочтению между собой должно быть выражено числовыми оценками mi j в виде обыкновенной дроби. Например, m23 75
означает, что второй критерий «важнее» третьего в |
7 |
раза , а третий критерий «ме- |
||
|
5 |
|||
|
|
нее важен» второго тоже в 7 раза . |
|
|
5 |
|
По имеющейся информации о степени предпочтения, по важности каждой па- |
ры частных критериев составляется матрица S размерности ( k, k + 1) , где |
|
Si j |
равно числителю mi j , i < j |
S ji |
равно знаменателю mi j , i > j |
Si j 1, i, j 1,k
k
Si, k + 1 Si, j j 1
Например, имеем трехкритериальную задачу, причем выяснили, что первый критерий важнее второго, третий критерий важнее второго, первый важнее третьего.
22
В нашем случае первый критерий важнее третьего и второго, то есть следует ожи-
дать, что наибольшим будет a1 .
Зададимся конкретными данными:
m12 |
3 |
, m32 |
= |
7 |
, m13 |
= |
2 |
. |
|
|
|||||
2 |
|
1 |
1 |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||
|
3 |
2 |
|
6 |
|
|
|
|
|
|
|
|
|
||
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
S |
2 |
1 |
1 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
1 |
7 |
1 |
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
6 |
, 2 = |
4 |
|
, 3 |
9 |
. |
||||
|
|
19 |
19 |
|
19 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Вопреки ожиданиям, наибольшим получили 3 .
Дело в том, что здесь сыграли роль именно количественные показатели: тре-
тий критерий важнее второго в 7 раз. При определении mi j надо быть очень внима-
тельным. Например, для k 3 , если мы четко знаем, что самым важным является первый критерий, затем второй, и, наконец, третий, то для определения i данным приемом можно воспользоваться, но mi j должны в этом случае удовлетворять усло-
виям: m12 1; m2 3 > 1; m1 3 > max{ m1 2 , m2 3 } .
Прием 4. Использование интервальной информации.
Одним из подходов, наиболее отвечающим практике, является интервальное задание весовых коэффициентов i , то есть задание i ' , i '' , i 1,k , где i ' , i '' - со-
ответственно нижняя и верхняя граница для i : i' i i'' .
С постановочной точки зрения этот подход предпочтительнее предыдущих.
Математически он приводит к решению следующей однокритериальной зада-
чи с ( n + k) переменными:
k
i * fi ( x ) min i 1
k
i 0, i = 1, G(x) 0
i 1
i' i i''
Вкачестве примера снова рассмотрим задачу Ошибка! Источник ссылки не найден. при условиях:
23
0,1 < 1 0,4
0,8 < 2 0,9
Для этого необходимо решить такую задачу:
1 * [ 2* ( x 3 )2 1] 2 * [( x 5 )2 2 ] min
1 x 7
0,1 |
1 |
0,4 |
|
|
0,8 |
< |
2 |
0,9 |
|
1 |
2 |
1 |
|
|
Такую задачу пришлось решать численно и получено: x* 4,333 , 1 0,1; |
2 = 0,9 |
Замечание. Как и в предыдущих приемах , в общем случае, гарантий того, что полу-
чено эффективное решение, нет.
Прием 5. Определение весовых коэффициентов по разности максимального и мини-
мального элемента матрицы предпочтений :
|
f 1* |
f 2* |
. . |
|
f k* |
|
|
||
x*1 |
|
|
|
c1 2 |
. . c1 k |
|
|||
0 |
|
|
|||||||
x*2 |
c2 1 |
0 . . . |
|
|
|||||
. |
. |
|
. |
0 . . |
|
|
|||
. |
. |
|
. . . . |
|
|
||||
x*k |
ck 1 |
. |
. . |
|
0 |
|
|
||
где |
|
|
|
|
|
|
|
||
cl i |
|
f i* - f i ( x*l ) |
|
|
|
|
|||
|
|
|
|
|
|||||
|
|
f i* |
|
|
|
|
|||
|
|
|
|
|
|
|
|
||
Вычисляются: |
|
|
|
||||||
d j |
max ci |
j |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
i 1,k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
--- |
|
j |
minci |
j |
j |
1,k |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
i 1,k |
|
|
|
|
|
|
Далее вычисляются: |
|||||||||
|
|
|
|
|
|
|
|
- - - |
|
j |
|
|
d j - j |
j 1,k |
Значения j таким образом вычисляют по формуле:
24
.
Вернемся к примеру 1Ошибка! Источник ссылки не найден. и применим к нему
прием 5:
f1* 1, |
x*1 = 3 |
f2* 2, |
x*2 = 5 |
Матрица C принимает вид:
0 2
8 0
d1 max ci j 8
i 1,k
d2 2
1 min ci 1 0
i 1,k
2 0
Далее:
1 8
2 2
Следовательно:
1 |
4 |
; |
2 = |
1 |
|
5 |
5 |
||||
|
|
|
Прием 6. Определение весовых коэффициентов при одинаковом приоритете част-
ных критериев.
В этом способе выбора весовых коэффициентов i определяется по формуле:
i k1
критерии равноправны.
Решение оптимизационных задач при наличии дополнительной информации о
важности частных критериев оптимальности.
Если среди частных критериев оптимальности f1 ( x ), ..., fk ( x ) можно выделить один наиболее предпочтительный из всех остальных, то в этом случае свёртывание
25
векторного критерия может быть осуществлено с помощью метода выделения глав-
ного критерия.
Метод выделения главного критерия.
Если среди частных критериев можно выделить один «главный», пусть
для определенности это будет f1 ( x ) , а остальные не столь значимы, то вместо ис-
ходной задачи можно рассмотреть следующую задачу:
f1 ( x ) min
G( x ) 0
|
--- |
fi ( x ) |
fi0 , i = 1,k |
где f i0 |
- некоторые пороговые значения соответствующих критериев. |
Это задача математического программирования, которая может быть решена
одним из существующих методов. Полученное при этом решение будет близко к
ожидаемому в том случае, если по существу дела критерий важнее всех ос-
тальных и пороговые значения f i0 соответствуют реальности. Можно, например, fi0
найти как решение соответствующей однокритериальной задачи:
fi0 max fk ( x )
G( x ) 0
но в этом случае ограничения на fi ( x ) будут слабыми и решение исходной задачи будет близко к решению задачи:
f1 ( x ) min
G( x ) 0
то есть критерии f2 ( x ), ..., fk ( x ) слабо влияют на результат.
Довольно распространенным является следующий подход . Выбирается неко-
торый относительный порог i (часто он бывает одинаков для различных критериев,
так как является безразмерной величиной) отклонения критерия fi ( x ) от своего ми-
нимума:
i |
fi0 fi |
|
fi fi |
||
где |
|
|
|
26 |
fi min fi ( x )
x D
fi max fi ( x )
x D
Как и в предыдущем случае нахождение fi , fi - , либо их оценок является от-
дельной задачей.
Вернемся к примеру 1:
f1 ( x ) 2* ( x 3 )2 1 min
f2 ( x ) ( x 5 )2 2 min, x R1
D {x : 1 x 7}
Применим метод выделения главного критерия, используя пороговые значе-
ния.
Пусть главным критерием будет f1 ( x ) , а величину порога будем задавать различной:
0,1; 0,2; 0,3 .
2 |
0,1 |
f20 f2 |
|
f20 2 |
f20 = 2,9 . |
f2 f2 |
18 2 |
Решаем геометрически однокритериальную задачу:
f1 ( x ) 2* ( x 3 )2 1 min |
|
|
|
f2 ( x ) ( x 5 )2 |
2 2,9 |
|
|
1 x 7 |
|
|
|
Получаем x* |
4,051 . |
|
|
Теперь решим задачу при 2 |
0,2 |
f20 = 5,2 : |
|
f1 ( x ) 2* ( x 3 )2 1 min |
|
|
|
f2 ( x ) ( x 5 )2 |
2 5,2 |
|
|
1 x 7 |
|
|
|
Получаем x* 3,2 . |
|
|
|
И, наконец, положим 2 0,3 |
|
f20 = 6,8 |
|
Получаем x* |
3,0 . |
|
|
Проанализируем полученные результаты и попробуем сделать выводы. Чем большее пороговое значение назначается, тем большее отклонение от своего мини-
мума по неглавному критерию допускается, в результате имеем однокритериальную
27
задачу со слабыми ограничениями на не основные критерии, решение такой задачи будет близко к точке минимума главного критерия на D .
В нашем примере, при 2 0,3 получили решение, которое совпало с решени-
ем однокритериальной задачи (ограничение на f2 ( x ) не сыграло роли).
Уменьшением пороговых значений мы ужесточаем требования по близости решения к точкам минимума не основных критериев, что может привести, как в на-
шем случае при 2 0,1 , к приближению полученного решения к точке минимума других критериев, либо может получиться решение, не являющееся эффективным,
либо можно получить несовместные условия, не позволяющие получить решения.
Метод выделения главного критерия, как и все последующие рассматривае-
мые методы, состоит в замене постановки исходной задачи некоторой другой, и в решении этой задачи. При этом возможны два подхода:
1)замена постановки производится затем, чтобы работать с этой новой постановкой,
не возвращаясь к старой;
2)замена постановки производится только для облегчения процедуры получения ре-
шения, которое анализируется с позиций исходной постановки.
В первую очередь полученное решение исследуется на эффективность. Наиболее распространенным условием проверки на эффективность служит следующая теоре-
ма:
Теорема. Решение x* является эффективной точкой тогда и только тогда, когда оно
минимизирует fi (x) на множестве S { x D | |
fi (x) fi (x* ), i = 1,k___} . |
|
Вернемся к нашему примеру и проверим, например, решение, соответствую- |
||
щее 0,1 x* = 4,051 . |
|
|
Для этого необходимо решить задачу: |
|
|
2* ( x 3 )2 |
1 ( x 5 )2 2 min |
|
2* ( x 3 )2 |
1 2* ( 4,051 3 )2 1 |
|
( x 5 )2 2 ( 4,051 5 )2 2 1 x 7
28
Такую задачу можно решить чисто геометрически и получим, что x* = 4,051 -
решение этой задачи, следовательно, методом выделения главного критерия при
0,1 мы получили эффективную точку.
Пусть каким-то образом мы получили решение x = 6 (заведомо мы знаем, что это неэффективное решение, так как оно не принадлежит области Парето).
Итак, снова решаем задачу однокритериальной оптимизации:
( x ) 2* ( x 3 )2 1 ( x 5 )2 2 min
2* ( x 3 )2 1 19
( x 5 )2 2 3
1 x 7
Нетрудно видеть, что здесь допустимой областью будет отрезок [ 4,6 ] , на этом отрезке производная ' ( x ) 0 , следовательно ( x ) возрастает на отрезке [ 4,6 ] и при-
нимает наименьшее значение на левом конце при x 4 , отсюда следует, что x 6 не является эффективной точкой.
Замечание. Метод выделения главного критерия позволяет в лучшем случае получить одно из нескольких эффективных решений.
Это замечание остается справедливым и для последующих алгоритмов. Одна-
ко для многих реальных задач этого явно недостаточно, поскольку окончательное решение желательно принимать, зная все или почти все эффективные решения.
Метод последовательной оптимизации с учетом жесткого приоритета
Этот метод применяется в случае, если для всех частных критериев оптималь-
ности задано предпочтение по важности:
f1 f2 ... fk
то есть считается, что критерий f1 ( x ) более важен , чем критерий f2 ( x )
последующие критерии fi ( x ) , критерий f2 ( x ) более важен, чем критерий f3 ( x )
далее.
В этом случае решение x1 доминирует над x2 , если:
f1 ( x1 ) f1 ( x2 )
ивсе
итак
29
или f1 ( x1 ) f1 ( x2 ) , f2 ( x1 ) f2 ( x2 )
или f1 ( x1 ) f1 ( x2 ) , ..., fk 1( x1 ) fk 1( x2 ) , fk ( x1 ) fk ( x2 )
это означает, что лучшим решением считается решение, для которого критерий
f1 ( x ) меньше; если значения критерия f1 ( x ) равны для решений x1 и x2 , то предпоч-
тение отдается тому решению, для которого критерий f2 ( x ) меньше и так далее.
Процедура решения многошаговая, причем число шагов может быть от 1 до K . 1-ый шаг.
Решается задача:
f1 ( x ) min
x Rn : G( x ) 0 (1)
Пусть D1 - множество решений этой задачи.
Если D1 - пусто, то принимается, что исходная многокритериальная задача решения не имеет. Если D1 - состоит из одного элемента, то этот элемент признает-
ся решением исходной задачи. Если D1 - содержит более одного элемента , то осу-
ществляется переход к шагу 2.
2-й шаг.
Решается задача:
f2 (x) min
x D1 |
(2) |
D2 - множество решений задачи (2).
Пошаговая процедура продолжается до тех пор, пока либо на каком-то шаге
произойдет прерывание процесса вследствие получения единственного решения,
либо до получения множества решений.
В том случае, когда подмножества D1 , D2 , ..., Ds могут выродиться в точку, то есть будет решена задача минимизации только по наиболее важному критерию f1 ( x ) , а все остальные частные критерии будут проигнорированы.
Таким образом, этот метод не позволяет справедливо учесть интересы менее важных критериев, так как не допускает уменьшение менее важных критериев, если
30