4.1 Задачи векторной оптимизации
В жизни целенаправленная деятельность человека устроена так, что приходится учитывать не одну, а сразу несколько целей.
Так, при транспортировке грузов возникают желания организо- вать перевозку быстро, дешево, надежно. Три сформулирован- ные целевые установки приводят по отдельности к различным трем решениям, а так как цели сами по себе противоречивы, то возникают определенные трудности сравнения этих решений, выбора наилучшего в определенном смысле или какого-то ком- промиссного. В данном разделе рассмотрим подходы количест- венного обоснования решения многокритериальных задач опти- мизации.
Вернемся к задаче определения плана выпуска продукции, рассмотренной [46]. Напомним постановку задачи.
Пусть мебельная фабрика изготавливает два вида продук- тов: столы и шкафы. Для их производства используется три вида ресурсов (пиломатериал, шурупы, краска). Будем считать, что месячные запасы ресурсов ограничены: пиломатериал — вели- чиной
1
b (
3
ì ), шурупы —
2
b (кг), краска —
3
b (кг). Расходы соответствующих ресурсов на изготовление одной единицы со- ответствующих продуктов известны и задаются таблицей (мат- рицей)
Α . Прибыль (доход) от выпуска единицы соответствую- щей продукции задана: для стола она равна
1
C (руб./шт.), для шкафа —
2
C (руб./шт.). Требуется определить план выпуска продукции каждого вида, максимизирующий доход фабрики.
Кроме этой цели, добавим еще одну. Допустим, что нам нужно максимизировать выпуск продукта первого типа — сто- лов, которые идут не на продажу, а для своих нужд. Таким обра- зом, теперь модель задачи будет выглядить так:
2 1
1
max
j j
j
y
C x
=
=
∑
— критерий первого вида; (4.1)
65 2
1
max y
x
= — критерий второго вида; (4.2) при ограничениях:
2 1
,
1,2,3
ij j
i
j
a x
b
i
=
≤
=
∑
, (4.3)
0,
1,2,
j
x
j
≥
=
(4.4) где
j
x — количество производимых продуктов j-го типа (соот- ветственно столов и шкафов), j = 1,2;
ij
a — нормативная матрица затрат i-го вида сырья на 1 еди- ницу j-го типа продукта;
i
b — ограничение на i-й вид сырья (пиломатериал, шуру- пы, краска), j = 1,2,3.
Вернемся к графическому способу решения задачи в от- дельности по каждому из критериев (рис. 4.1).
2
x′
2
x
1
x
X ′
1
y
2
y
X ′′
1
x ′′
1
x′
Рис. 4.1 — Графическое решение задачи
Если решать задачу только с учетом критерия первого вида
1
y , то решение получим в точке
1 2
( , )
X
x x
′
′ ′
=
=(517,156), а значе- ние критерия
1 517 500 156 750 375500
y
=
⋅
+
⋅
=
рублей. Если ре- шать задачу без учета критерия первого вида, а только с учетом критерия второго вида, то получим решение в точке
1
( ,0) (700,0)
X
x
′′
′′
=
=
, а значение критерия
2 1
y
x′′
=
= 700 столов.
66
Одновременный учет двух критериев приведет к решению, которое лежит на отрезке между точками (решениями)
X ′ и
X ′′ .
Множество решений на отрезке между
X ′ и
X ′′ называют множеством решений, оптимальных по Парето (оно же компро- миссное множество, недоминируемое, эффективное). Множество компромиссных решений обладает свойством противоречивости: улучшение качества решений по одним критериям вызывает ухудшение качества других (рис. 4.2).
1
∆
2
∆
1
x′
1
x ′′
Множество
Парето
2
y(столы)
1
y(доход)
)
0
,
(
1 1
xy′′
)
,
(
2 1
1
xxy′
′
Рис. 4.2 — Компромиссное множество решений
Вообще говоря, в многокритериальных задачах принятия решений понятие оптимальности плана теряется, так как не существует такого плана, который доставлял бы одновременно экстремальное значение отдельным критериям. Это обстоя- тельство и является причиной того, что методы решения много- критериальных задач предусматривают в том или ином виде учет мнения лица, принимающего решение. Чтобы выбрать из области Парето лучшие решения, ЛПР обязан ввести соответ- ствующие
принципы выбора компромиссного решения, приво- дящие к тому или иному методу решения задачи (рис. 1.4). Рас- смотрим наиболее часто употребляемые методы решения мно- гокритериальных задач.
Сведение многокритериальной задачи к однокритериальной Идея метода состоит в том, чтобы два и более критериев представить в виде единого суперкритерия, т.е. скалярной функ- ции, зависящей от локальных критериев:
67 0
0 1
2
( ,
, ..., )
n
y
y y y
y
=
Вид функции
0
y определяется тем, как ЛПР представляет вклад каждого критерия
i
y в суперкритерий. В силу того, что критерии
i
y могут измеряться в различных единицах измерения и иметь различные несоизмеримые масштабы, сравнивать реше- ния в таких условиях зачастую невозможно. Возникает пробле- ма приведения их масштабов к единому, обычно безразмерному масштабу измерения (проблема нормализации). А так как обыч- но локальные критерии имеют относительно друг друга различ- ную важность, относительный вклад в суперкритерий, то это следует учитывать при выборе лучшего решения (проблема уче- та приоритета критериев).
Наибольшее распространение получил подход определения глобального критерия (суперкритерия) в виде взвешенной сум- мы критериев
í
0 1
n
i i
i
y
y
=
=
α
∑
, где
í
i
y — отнормированное значение i-го критерия;
i
α — коэффициент относительной важности i-го критерия
(весовой коэффициент);
1 0
1,
1, ;
1
n
i
i
i
i
n
=
≤ α ≤
=
α =
∑
Весовой коэффициент определяется экспертными методами.
Значение
i
y для каждого из критериев, как правило, есть безраз- мерная величина и находится в интервале
0 1(10, 100).
i
y
≤
≤
Наи- более простым способом нормализации [7] является получение оценок по формуле
í
u
/
i
i
i
y
y y
=
, где
u
i
y — идеальное (возможно максимальное) значение i-го критерия.
Для решения нашей двухкритериальной задачи ЛПР дол- жен установить значения весовых коэффициентов
1
α и
2
α , что- бы
1 2
1
α + α = , а также учесть нормализацию критериев
1
y и
2
y , а затем построить единую целевую функцию и решить зада-
68
чу:
2 0
1 2 1 1
max
(
) / 375500
/ 700
jjjYC xx=
= α
+ α
∑
, при ограничениях
2 1
,
1, 2,3
ij jija xbi=
≤
=
∑
;
0,
1,2
jxj≥
=
Если
1 1
α = , то получим
решение с учетом первого крите- рия, если
1 0
α = — решение с учетом второго критерия. Глубо- кое знание реальной проблемы, накопленный опыт могут позво- лить ЛПР выбрать
0 1
i< α < , чтобы, решив оптимизационную задачу с единственной целевой функцией
0
Y , он получил бы удовлетворяющее его решение исходной задачи с двумя целе- выми функциями.
Выделение главного критерия Допустим, что среди критериев
1
y и
2
y ЛПР удается вы- брать основной. Пусть это будет критерий
2
y Допустим, что
ЛПР желает получить доход от реализации продукции не ниже определенной им величины
0 0
(
375500)
C C<
. Тогда можно ре- шать задачу вида:
2 1
max
yx= , при ограничениях:
2 1
,
1,3
ij jijxbi=
α
≤
=
∑
;
2 0
1
jjjC xC=
≥
∑
— ограничение по критерию
1
y;
0,
1,2
jxj≥
=
Метод последовательных уступок Предположим, что частные критерии упорядочены в поряд- ке убывания их важности
1 2
nyyyf f
f
. Решая задачу по критерию
2 1
1 1
1
: max ( )
375500
jjxjyy XC xy=
=
=
=
∑
, найдем реше- ние
X ′ . Если ЛПР может сделать некоторую уступку по перво-
69
му критерию
1
y в объеме
1
∆ (пусть
1
∆ =5500), чтобы улучшить решение по следующему критерию
2
y (рис. 4.2), то это приво- дит к задаче поиска решения по второму критерию с уступкой по первому:
2 1
max
;
y
x
=
при ограничениях:
2 1
,
1,3
ij
j
i
j
a x
b
i
=
≤
=
∑
;
2 1
370000
j
j
j
C x
=
≥
∑
— уступка по первому критерию;
0,
1,2
j
x
j
≥
=
И так далее для других критериев. На последнем шаге ре- шается задача поиска решения по n-му критерию с учетом усту- пок по
(
1)
n
− наиболее важным критериям, и решение этой за- дачи принимается в качестве решения первоначальной.
Метод целевой точки
Метод целевой точки (опорной, идеальной) базируется на задании по каждому критерию так называемых уровней притя- заний [3, 4,7] в виде желаемых значений критериев ˆ
i
y . Поскольку оценки ˆ
i
y задаются без точного знания структуры множества до- пустимых решений, то целевая точка может оказаться как внутри, так и вне области допустимых решений. Наиболее близкая точка решения к целевой будет определять наилучшее решение. В каче- стве меры близости между решением и целевой точкой, т.е. между векторами
1 2
1 2
ˆ
ˆ ˆ
ˆ
( ) ( ( ), ( ), ..., ( )),
( ,
, ..., )
n
n
y X
y X
y X
y X
y
y y
y
=
=
предлагается использовать различные расстояния [4], в том чис- ле расстояние типа
1/ 2 2
1
ˆ
( )
ˆ
( , )
ˆ
n
i
i
i
i
i
y X
y
d y y
y
=
−
=
α
∑
, где
i
α — коэффициент относительной важности критерия .i
70
Тогда модель поиска компромиссного решения для рас- сматриваемой задачи методом целевой точки будет иметь вид
1/ 2 2
2 1
2 1
1 2
1 2
1 2
ˆ
ˆ
min
ˆ
ˆ
j j
j
C x
y
x
y
d
y
y
=
−
−
= α
+ α
∑
, при ограничениях (3.52) и (3.53).
На базе рассмотренных методов поиска решения многокри- териальных задач созданы различные человеко-машинные эври- стические процедуры [28], суть которых заключается в распре- делении ролей между ЛПР и ЭВМ. ЛПР готовит информацию, необходимую для моделирования, ЭВМ осуществляет расчет и выдает решение ЛПР для его анализа. При необходимости ЛПР сообщает сведения для корректировки решения в виде оценок относительной важности критериев, уступок по критериям, ко- эффициентов нормализации и другие.
4.2 Аксиоматический подход в задачах принятия
решений
4.2.1 Функции полезности
Понятие функции полезности возникло в теории потреби- тельского спроса при сравнении различных наборов товаров
[22]. Полезность потребления продукта, например, для потреби- теля может быть выражена в виде функции, отражающей полез- ность в зависимости от количества потребления этого продукта.
В определенных пределах полезность может увеличиваться, уменьшаться либо оставаться без изменения при увеличении потребления продукта. Функция полезности может быть по- строена и для определенного набора продуктов. При этом в за- висимости от того, являются ли продукты взаимозаменяемыми или нет, интегральная функция полезности набора потребляе- мых продуктов определяется с учетом независимости или с уче- том взаимного их влияния на общую полезность потребления.
71
В задачах принятия решений значение функции полезности выражает предпочтение, полезность альтернатив. Она может быть оценена на множестве альтернатив и на множестве крите- риев, при этом критерии могут быть взаимно независимыми ли- бо зависимыми.
Аксиоматический подход к ЗПР базируется на проверке ря- да аксиом для построения функции полезности альтернатив. Ак- сиомы делятся на две группы: аксиомы существования функции полезности и аксиомы независимости критериев.
Аксиомы существования функции полезности сформулиро- ваны на множестве альтернатив и множестве критериев. В слу- чае независимости альтернатив
,
1,
i
x
X i
n
∈
=
и существования линейного порядка их предпочтения
1 2
n
x
x
x
f f
f
( f — знак отношения строгого предпочтения) в работе [22] показано, что можно на этом множестве альтернатив построить функцию полезности
( )
i
i
u x , такую, что
1 1
2 2
( )
( ) ... ( ).
n
n
u x
u x
u x
>
>
>
При наличии информации (количественной либо качест- венной) на множестве критериев
,
1, ,
j
k
K j
m
∈
=
характери- зующей соответствующие альтернативы, в [19, 22] показано, что для них могут быть построены функции полезности как по каж- дому критерию
( ),
j
j
v
k
так и по совокупности критериев.
В случае выполнения аксиом взаимной независимости крите- риев доказано существование аддитивной функции полезности
1
( )
( ),
m
j
j
j
j
U K
v
k
=
=
λ
∑
где
( )
U K — функция полезности альтернативы на множестве критериев К,
0
( ) 1;
U K
≤
≤
( )
j
j
v
k — функция полезности альтернативы по критерию
, 0
( ) 1,
1, ;
j
j
j
k
v
k
j
m
≤
≤
=
j
λ — вес j-го критерия,
1 1,
0.
m
j
j
j
=
λ =
λ >
∑
72
В случае невыполнения аксиом независимости критериев строятся кривые безразличия с целью оценки полезности аль- тернатив. Для кривой безразличия характерно то, что полез- ность любых двух альтернатив
х и
y, лежащих на одной такой кривой, одинакова:( )
( )
u xu yconst=
=
(рис. 4.3). При этом счи- тают, что известна сравнительная полезность любых двух аль- тернатив
x и
y, отличающихся не более чем по двум критериям.
На рис. 4.3 показано, что полезность альтернатив
x′ и
y′ выше, чем полезность альтернатив
x и
y : ( )
( );
( )
( ).
U xU xU yU x′
′
>
>
0 2
k1
kyxx′
y′
… … … … )
(
)
(
yUxU′
=
′
)
(
)
(
yUxU=
Рис. 4.3 — Кривые безразличия
С ростом числа зависимых критериев
усложняется проце- дура решения задачи выбора, так как увеличивается число кри- вых безразличия и соответственно число компромиссных вари- антов решения задачи. Для решения подобных задач предложе- ны методы компенсации [19, 20, 22, 35].
4.2.2 Построение аддитивной функции полезности Рассмотрим следующую задачу. Перед выпускником учеб- ного заведения стоит проблема выбора места дальнейшей рабо- ты. Выбор определяется значением критериев:
73 1
k — величина заработной платы;
2
k — процент творческой работы;
3
k — время, за которое можно добраться до места работы.
Выпускник может производить выбор из пяти предлагае- мых мест работы со следующими оценками (табл. 4.1).
Таблица 4.1 — Исходные данные
Предприятие
Критерии
1
k
2
k
3
k
1
x
100 50 30 2
x
140 30 50 3
x
170 25 45 4
x
130 15 10 5
x
140 40 40
Прежде чем начать строить функцию полезности для выпу- скника по каждому предприятию в виде аддитивной функции, следует убедиться во взаимной независимости критериев. Кри- терии будут считаться независимыми, если каждая пара крите- риев не зависит по предпочтению от своего дополнения [22].
Иными словами, если две альтернативы отличаются только по двум критериям (остальные, дополняющие, критерии у этих альтернатив имеют равные значения) и их предпочтения не бу- дут изменяться при одинаковом изменении значения у допол- няющих критериев, то эти критерии будут считаться независи- мыми от дополняющих критериев. Если такая независимость будет наблюдаться для любой пары критериев, то все критерии будут взаимно независимыми. Если ЛПР установит, что это так, то переходим к построению функций полезности по каждому критерию
( ),
j
j
v
k
,
3
,
1
=
j
0
( ) 1.
j
j
v
k
≤
≤
Введем обозначения:
j
k
∗
— лучшее значение по критерию
1 2
3
(
170,
50,
10);
j k
k
k
∗
∗
∗
=
=
=
74
j
k
o
— худшее значение по критерию
1 2
3
(
100,
15,
50).
j k
k
k
=
=
=
o o
o
Далее для удобства работы с ЛПР все критерии удобно представить с позиции их максимилизации (либо минимизации).
Поэтому новое значение критерия
í
3
k лучше представить как разность
í
3 3 max
3
,
i
i
k
k
k
=
−
где
3 i
k — значение критерия 3 для
i-й альтернативы,
3 max
k
— максимальное значение критерия 3
(
3 max
k
= 50).
Тогда для третьего критерия будем иметь:
3
k
∗
= max (50-30; 50-50; 50-45; 50-10; 50-40)=40;
3
k
o
= 0, т.е.
3 0
40
k
≤
≤
В большинстве практических задач для построения функ- ции полезности достаточно пяти точек (две точки с координата- ми
,
j
k
o
( ) 0
j
j
v
k
=
o и
j
k
∗
,
( ) 1
j
j
v
k
∗
= известны по определению).
Остальные три определяются опросом ЛПР. ЛПР должно ука- зать последовательно значения критерия
j
k , для которых зна- чения полезности соответственно будут равны 0,5; 0,25 и 0,75.
Допустим, в результате диалога ЛПР — аналитик получили сле- дующую картину (рис. 4.4).
Для определения коэффициентов
j
λ предлагается следую- щий подход [22].
Пусть даны две альтернативы
1 2
3
( , , )
k
k
k
∗
o и
1 2
3
(
?, , ),
k
k
k
−
o где
0
,
j
j
k
k
∗
— худшее и лучшее значение критерия j,
3
k — значе- ние 3-го критерия (для нас безразлично значение дополняющего критерия, т.к. все критерии взаимно независимые). Спрашиваем у
ЛПР: каково должно быть значение критерия
1
k у второй альтер- нативы, чтобы эти альтернативы были эквивалентными, т.е. функ- ции полезности у них были одинаковыми. Для нашей задачи срав- ниваем альтернативы (100, 50,
3
k ) (
1 3
?, 15, ).
k
k
−
Выясняем у ЛПР: какова должна быть заработная плата на предприятии,
75
Рис. 4.4 — Функции полезности
0 0,25 0,5 0,75 1
15 20 25 30 35 40 45 50
k
2
v
2 0
0,25 0,5 0,75 1
100 110 120 130 140 150 160 170
Скачать 1.57 Mb.