Modele preferencji
Optymalizacja wielokryterialna
Wielokryterialny wybór wariantu
Warianty systemu oceniane w różnych aspektach (cena, bezpie-
czeństwo, szkolenie, itd) w skali od 1 do 10 (najlepsza ocena).
wariant kryt. 1 kryt. 2 kryt. 3 kryt. 4 kryt. 5
w1 1 10 10 10 10
w2 10 1 10 10 10
w3 10 10 1 10 10
w4 10 10 10 1 10
w5 10 10 10 10 1
w6 8 8 8 8 8
Optymalizacja wielokryterialna
" x " Q  decyzje dopuszczalne
wiele funkcji oceny yi = fi(x) decyzji
" Model w przestrzeni decyzji
max{(f1(x), . . . , fm(x)) : x " Q}
" Model w przestrzeni ocen
max{y = (y1, . . . , ym) : y " A}
A = {y " Y : y = f(x), x " Q}
Model w przestrzeni ocen  przyklad
max [-x1 - 2x2 + 2x3, x2]
2 d" x1 + x2 + x3 d" 3
x1 + x2 d" 2
x2 + x3 d" 2
xj e" 0, j = 1, 2, 3
Model w przestrzeni ocen  przyklad
max [10 - x2 - x2, 10 - (x1 - 2)2 - (x2 - 2)2]
1 2
0 d" x1 d" 2
0 d" x2 d" 2
max [y1, y2]
y1 d" 10 - x2 - x2
1 2
y2 d" 10 - (x1 - 2)2 - (x2 - 2)2
0 d" x1 d" 2
0 d" x2 d" 2
Model preferencji
Preferencje określone na wektorach ocen
" relacja Å›cislej preferencji: y y Ô! y jest lepszy niż y
" relacja indyferencji: y <" y Ô! y tak samo dobry jak y
=
" relacja slabej preferencji: y y Ô! y nie gorszy niż y
" istnieja nieporównywalne wektory ocen: y ?? y
y y relacja podstawowa
y y Ô! (y y i y y )
y <" y Ô! (y y i y y )
=
Racjonalne relacje preferencji
" zwrotna: y y dla y " Y
" przechodnia (tranzytywna):
(y y i y y ) Ò! y y dla y , y , y " Y
" ściśle monotoniczna po wspólrzednych:
(y1, . . . , yi-1, yi + µ, yi+1, . . . , ym) (y1, . . . , yi-1, yi, yi+1, . . . , ym)
y + µei y dla y " Y, µ > 0, i = 1, . . . , m
gdzie ei  i ty wektor jednostkowy w przestrzeni ocen Y .
Relacja dominacji
" Mówimy, że wektor ocen y " Y (racjonalnie) dominuje y "
Y , lub y jest (racjonalnie) dominowany przez y wtedy i tylko
wtedy, gdy y y dla wszystkich racjonalnych relacji preferencji.
" Jeżeli wektor ocen y jest (racjonalnie) dominowany przez y ,
to może on być wyeliminowany z poszukiwań, ponieważ wszyscy
racjonalni decydenci preferuja y w stosunku do y .
Niezdominowane wektory ocen
" Wektor ocen y " A nazywamy (racjonalnie) niezdominowanym
wtedy i tylko wtedy, gdy nie istnieje y " A taki, że y jest domi-
nowany przez y .
" Wektor ocen y0 " A jest wektorem niezdominowanym wtedy i
tylko wtedy, gdy dla każdego y " A istnieje racjonalna relacja
preferencji taka, że nie zachodzi y y0.
" Wystarczy wybierać wśród niezdominowanych wektorów ocen.
Racjonalna dominacja
y y Ô! y y " r.r.p.
r
y y Ô! (y y i y y ) Ô! y y " r.r.p.
r r r
y <"r y Ô! (y y i y y ) Ô! y <" y " r.r.p.
= =
r r
>
y y Ô! y = y Ô! yi e" yi "i = 1, . . . , m
r
> >
y y Ô! y e" y Ô! (y = y i y = y )

r
> >
y <"r y Ô! y = y Ô! (y = y i y = y )
=
Dominowane wektory ocen
y2
y
y1
Dominujace wektory ocen
y2
y
y1
Niezdominowane wektory ocen
y2
y1
Wektor ocen y0 " A jest wektorem niezdominowanym wtedy i tylko
wtedy, gdy nie istnieje y " A taki, że y e" y0
Niezdominowane wektory ocen
" Wektor ocen y0 " A jest wektorem niezdominowanym wtedy i
tylko wtedy, gdy istnieje spójna racjonalna relacja preferencji
taka, że y0 y dla wszystkich y " A.
0 0
y y Ô! min (yi - yi ) > min (yi - yi ) lub
o
i=1,...,m i=1,...,m
ëÅ‚ öÅ‚
m m
0 0
íÅ‚
min (yi - yi ) = min (yi - yi ) i yi e" yi Å‚Å‚
i=1,...,m i=1,...,m
i=1 i=1
" Dla każdego niezdominowanego wektora ocen istnieje racjonalna
relacja preferencji, przy której jest on najlepszy.
Rozwiazanie efektywne, Pareto-optymalne
" Wektor dopuszczalny x " Q nazywamy rozwiazaniem efektyw-
nym (Pareto optymalnym, sprawnym) zadania wielokryterial-
nego wtedy i tylko wtedy, gdy odpowiadajacy mu wektor ocen
y = f(x) jest wektorem niezdominowanym.
" Wektor dopuszczalny x0 " Q jest rozwiazaniem efektywnym za-
dania wielokryterialnego wtedy i tylko wtedy, gdy istnieje spójna
racjonalna relacja preferencji taka, że f(x0) f(x) dla każdego
x " Q.
" Wektor dopuszczalny x0 " Q jest rozwiazaniem efektywnym za-
dania wielokryterialnego wtedy i tylko wtedy, gdy nie istnieje
x " Q taki, że f(x) e" f(x0).
Rozwiazanie efektywne, Pareto-optymalne
" Dla dowolnej permutacji Ä zbioru {1, . . . , m}, wektor x0 " Q
jest rozwiazaniem efektywnym zadania wielokryterialnego wtedy
i tylko wtedy, gdy jest rozwiazaniem efektywnym zadania
max {(fÄ(1)(x), fÄ(2)(x), . . . , fÄ(m)(x)) : x " Q}
" Dla dowolnych ściśle rosnacych funkcji si : R R (i = 1, . . . , m),
wektor x0 " Q jest rozwiazaniem efektywnym zadania wielokry-
terialnego wtedy i tylko wtedy, gdy jest rozwiazaniem efektyw-
nym zadania
max {(s1(f1(x)), s2(f2(x)), . . . , sm(fm(x))) : x " Q}
Rozwiazanie optymalne a efektywne
" Optymalizacja jednokryterialna
max{f(x) : x " Q}
Wszystkie rozwiazania optymalne daja ten sam wynik:
y" = f(x ) = f(x ).
Wyznaczyć dowolne rozwiazanie optymalne.
" Optymalizacja wielokryterialna
max{(f1(x), . . . , fm(x)) : x " Q}
Różne rozwiazania efektywne generuja wzajemnie nie-
porównywalne wektory ocen.
Wyznaczyć wszystkie rozwiazania efektywne?
Techniki generacji rozwiazań efektywnych
" Funkcja skalaryzujaca s : Rm R
Skalaryzacja: max {s(f1(x), f2(x), . . . , fm(x)) : x " Q}
Model preferencji: y y Ô! s(y ) e" s(y )
s
relacja jest zawsze spójna, zwrotna i przechodnia.
s
" Jeżeli funkcja skalaryzujaca s jest ścisle rosnaca po
wspólrzednych, to rozwiazanie optymalne skalaryzacji jest
rozwiazaniem efektywnym zadania wielokryterialnego.
Techniki generacji rozwiazań efektywnych
" Jeżeli funkcja skalaryzujaca s jest slabo monotoniczna (niema-
lejaca) po wspólrzednych, to zbiór rozwiazań optymalnych ska-
laryzacji zawiera rozwiazanie efektywne zadania wielokryterial-
nego.
" Jeżeli funkcja skalaryzujaca s jest slabo monotoniczna (niema-
lejaca) po wspólrzednych, to jednoznaczne w przestrzeni ocen
Y rozwiazanie optymalne skalarazycji jest rozwiazaniem efektyw-
nym zadania wielokryterialnego.
" W przypadku braku jednoznaczności dane rozwiazanie skalaryza-
cji może być zdominowane przez inne alternatywne rozwiazanie
optymalne tej skalaryzacji.
Techniki generacji rozwiazań efektywnych
" Optymalizacja jednokryterialna
max {(fj(x) : x " Q}, j " I
Zbiór rozwiazań optymalnych zadania jednokryterialnego za-
wiera rozwiazanie efektywne zadania wielokryterialnego, a jed-
noznaczne w przestrzeni ocen Y rozwiazanie optymalne zadania
jednokryterialnego jest rozwiazaniem efektywnym zadania wie-
lokryterialnego.
" Suma indywidualnych funkcji oceny
m
max { fi(x) : x " Q}
i=1
Rozwiazanie optymalne zadania z suma ocen jest rozwiazaniem
efektywnym zadania wielokryterialnego.
Techniki generacji rozwiazań efektywnych
m
" Metoda ważenia ocen: max { wifi(x) : x " Q}
i=1
Dla dowolnych dodatnich wag wi (i = 1, . . . , m) rozwiazanie
optymalne zadania ważonego jest rozwiazaniem efektywnym za-
dania wielokryterialnego.
" Dla każdego x0 rozwiazania efektywnego wielokryterialnego za-
dania PL istnieja dodatnie wagi wi (i = 1, . . . , m) takie, że x0 jest
rozwiazaniem optymalnym odpowiedniego zadania ważonego.
" Powyższe nie jest prawdziwe w przypadku ogólnych zadań opty-
malizacji wielokryterialnej. W szczególności nie jest prawdziwe
w przypadku zadań dyskretnych.
Wielokryterialny wybór wariantu
Efektywny wariant w6 nieosiagalny przy maksymalizacji ważonej
sumy ocen.
wariant kryt. 1 kryt. 2 kryt. 3 kryt. 4 kryt. 5
w1 1 10 10 10 10
w2 10 1 10 10 10
w3 10 10 1 10 10
w4 10 10 10 1 10
w5 10 10 10 10 1
w6 8 8 8 8 8
Techniki generacji rozwiazań efektywnych
" Skalaryzacja maksiminowa: max { min fi(x) : x " Q}
i=1,...,m
max z
pod warunkiem, że x " Q
fi(x) e" z dla i = 1, . . . , m
" Model preferencji: y y Ô! min yi e" min yi
i=1,...,m i=1,...,m
" Zbiór rozwiazań optymalnych zadania maksyminimalizacji za-
wiera rozwiazanie efektywne zadania wielokryterialnego;
jednoznaczne w przestrzeni ocen Y rozwiazanie optymalne jest
rozwiazaniem efektywnym zadania wielokryterialnego.
Techniki generacji rozwiazań efektywnych
" Skalowana maksyminimalizacja si : R R (i = 1, . . . , m)
max { min si(fi(x)) : x " Q}
i=1,...,m
" Jeżeli dla wszystkich osiagalnych wektorów ocen y " Y praw-
dziwa jest nierówność y" > y, to dla każdego rozwiazania efek-
tywnego x0 zadania wielokryterialnego istnieja dodatnie wagi wi
(i = 1, . . . , m) takie, że x0 jest jednoznacznym w przestrzeni
ocen rozwiazaniem optymalnym zadania maksyminimalizacji z
funkcjami skalujacymi postaci
"
si(yi) = wi(yi - yi ) dla i = 1, . . . , m
"
Można przyjać wi = -1/(fi(x0) - yi ).
Techniki generacji rozwiazań efektywnych
" Rozwiazanie efektywne x0 zadania wielokryterialnego jest jedno-
znacznym w przestrzeni ocen rozwiazaniem optymalnym zadania
maksyminimalizacji z funkcjami skalujacymi postaci
si(yi) = yi - fi(x0) dla i = 1, . . . , m
" Dla każdego x0 rozwiazania efektywnego zadania wielokryte-
rialnego istnieja ściśle rosnace funkcje liniowe si : R R
(i = 1, . . . , m) takie, że x0 jest rozwiazaniem optymalnym odpo-
wiedniego zadania maksyminimalizacji.
Optymalizacja leksykograficzna
" Porzadek leksykograficzny
v >lex v Ô! istnieje r taki, że vr > vr i vk = vk dla k < r
v e"lex v Ô! v >lex v lub v = v
Relacja nierówności leksykograficznej e"lex jest zwrotna, prze-
chodnia, spójna i antysymetryczna
(y e"lex y i y e"lex y ) Ò! y = y
Definiuje ona zatem porzadek liniowy.
" Jako uogólnienie skalaryzacji bedziemy rozpatrywać skalaryzacje
leksykograficzne, czyli zadania postaci
lexmax {(s1(f(x)), s2(f(x)), . . . , sp(f(x))) : x " Q}
Optymalizacja leksykograficzna
Algorytm sekwencyjny
1. Dla k = 1, 2, . . . , p wyznaczamy zbiór Sk rozwiazań optymalnych
zadania (gdzie S0 = Q):
Pk : max {sk(f(x)) : x " Sk-1}
2. Każdy element zbioru Sp jest rozwiazaniem optymalnym zadania
leksykograficznego.
Najprostsza technika definiowania zbiorów Sk jest dodawanie wa-
Å» Å»
runków st(f(x)) = zt dla kolejnych t = 1, 2, . . . , k, gdzie zt jest
wartościa optymalna zadania Pt.
Optymalizacja leksykograficzna
" Dla dowolnej permutacji Ä zbioru I = {1, . . . , m} rozwiazanie
optymalne zadania leksykograficznego
lexmax {(fÄ(1)(x), fÄ(2)(x), . . . , fÄ(m)(x)) : x " Q}
jest rozwiazaniem efektywnym zadania wielokryterialnego.
" Dla dowolnej permutacji Ä zbioru I = {1, . . . , m} i dowolnego
1 d" p d" m, zbiór rozwiazań optymalnych zadania
lexmax {(fÄ(1)(x), fÄ(2)(x), . . . , fÄ(p)(x)) : x " Q}
zawiera rozwiazanie efektywne zadania wielokryterialnego, a jed-
noznaczne w przestrzeni ocen Y rozwiazanie optymalne zadania
leksykograficznego jest rozwiazaniem efektywnym zadania wie-
lokryterialnego.
Leksykograficzne regularyzacje skalaryzacji
" Rozwiazanie optymalne (dwupoziomowego) zadania leksykogra-
ficznego
m
lexmax {(fi0(x), fi(x)) : x " Q}, i0 " I
i=1
jest rozwiazaniem efektywnym zadania wielokryterialnego.
" Uproszczona implementacja  inżynierska
m
max {fi0(x) + µ fi(x) : x " Q}, i0 " I, µ > 0
i=1
Leksykograficzne regularyzacje skalaryzacji
" Rozwiazanie optymalne zadania leksykograficznego
m
lexmax {( min fi(x), fi(x)) : x " Q}
i=1,...,m
i=1
jest rozwiazaniem efektywnym zadania wielokryterialnego.
" Uproszczona implementacja  inżynierska
m
max { min fi(x) + µ fi(x) : x " Q}, µ > 0
i=1,...,m
i=1
Leksykograficzne regularyzacje skalaryzacji
" Dla dowolnych ściśle rosnacych funkcji si : R R (i = 1, . . . , m)
rozwiazanie optymalne (dwupoziomowego) zadania leksykogra-
ficznego
m
lexmax {( min si(fi(x)), si(fi(x))) : x " Q}
i=1,...,m
i=1
jest rozwiazaniem efektywnym zadania wielokryterialnego.
" Dla każdego rozwiazania efektywnego x0 zadania wielokryte-
rialnego istnieja ściśle rosnace funkcje liniowe si : R R
(i = 1, . . . , m) takie, że x0 jest jednoznacznym w przestrzeni
ocen Y rozwiazaniem optymalnym odpowiedniego skalowanego
zadania maksyminimalizacji.
Wspomaganie decyzji
" W celu rozstrzygniecia praktycznego problemu decyzyjnego
trzeba wybrać jedno rozwiazanie do realizacji.
" Dla dowolnej racjonalnej relacji preferencji rozwiazania do-
puszczalne generujace wektory ocen maksymalne w sensie tej
relacji należa do zbioru rozwiazań efektywnych. Co wiecej, dla
każdego rozwiazania efektywnego x istnieje racjonalna relacja
preferencji taka, że f(x) y dla wszystkich y " A. Zatem
wybór specyficznego rozwiazania efektywnego faktycznie ozna-
cza wybór relacji preferencji .
Wspomaganie decyzji
" W wielokryterialnych problemach decyzyjnych relacja preferencji
nie jest znana a priori i dlatego ostatecznego wyboru rozwiazania
może dokonać jedynie decydent.
" Ze wzgledu na liczność zbioru rozwiazań efektywnych, nawet w
przypadku wyznaczenia metodami obliczeniowymi calego zbioru
rozwiazań efektywnych decydent nie może dokonać wyboru
rozwiazania bez pomocy odpowiedniego interakcyjnego systemu
informatycznego. System taki, nazywany tu systemem wspo-
magania decyzji (SWD), umożliwia sterowany przeglad zbioru
rozwiazań efektywnych. Na podstawie podawanych przez decy-
denta wartości pewnych parametrów sterujacych system przed-
stawia różne rozwiazania efektywne do analizy.
Skalaryzacja parametryczna
max {(s(u, f(x)) : x " Q}, u " U
x
gdzie u jest wektorem parametrów sterujacych,
a s : U × Y R funkcja skalaryzujaca.
lexmax {(s(u, f(x)) : x " Q}, u " U
x
gdzie s jest wektorowa funkcja skalaryzujaca.
" Skalaryzacja spelniajaca zasade efektywności:
dla każdego wektora parametrów sterujacych u " U rozwiazanie
optymalne zadania skalaryzacji jest rozwiazaniem efektywnym
oryginalnego problemu wielokryterialnego.
" Latwość obliczeniowa zadań skalaryzacji.
Skalaryzacja parametryczna
" Zupelność parametryzacji zbioru rozwiazań efektywnych:
dla każdego x0 rozwiazania efektywnego zadania wielokryterial-
nego istnieje wektor parametrów sterujacych u0 " U taki, że x0
jest rozwiazaniem optymalnym odpowiedniego zadania skalary-
zacji.
" Parametry sterujace reprezentujace latwo rozumiane przez de-
cydenta wielkości rzeczywiste charakteryzujace jego preferencje.
" Otwartość systemu wspomagania decyzji nie narzucajacego de-
cydentowi żadnego sztywnego scenariusza analizy problemu de-
cyzyjnego i dopuszczajacego możliwość modyfikacji jego prefe-
rencji w trakcie analizy, w wyniku poznawania specyfiki problemu
decyzyjnego.
Skalaryzacja parametryczna
" Dobre parametry sterujace  punkty odniesienia w przestrzeni
ocen (wartości ocen).
" Zle parametry sterujace  wagi kompensacyjne.
Brak intuitycyjności w sterowaniu wagami. Przyklad:
2 2 2
max{(y1, y2, y3) : y1 + y2 + y3 d" 1}
2 2 2
max{w1y1 + w2y2 + w3y3 : y1 + y2 + y3 d" 1}
wagi wynik
" " "
(1, 1, 1) (1/ 3, 1/ 3, 1/ 3)
" " " " "
(10, 2, 1) (10/"105, 2/"105, 1/"105) 2/"105 < 1/"3
(10, 7, 1) (10/ 150, 7/ 150, 1/ 150) 7/ 150 < 1/ 3
Quasi-zadowalajacy model decyzji
" Zadowalajacy model decyzji:
Decydent rozwiazujac problem decyzyjny określa poziomy aspi-
racji jako pożadane wartości oszczególnych ocen.
Jeżeli wartości ocen nie osiagaja poziomów aspiracji, to decy-
dent stara sie znalez
ć lepsze rozwiazanie.
Jeżeli wartości pewnych ocen osiagnely odpowiednie poziomy
aspiracji, to decydent koncentruje uwage na poprawie wartości
tych ocen, które nie osiagnely swoich poziomów aspiracji.
" Quasi-zadowalajacy model decyzji (kontynuacja optymalizacji):
Gdy wszystkie oceny osiagna zalożone poziomy aspiracji, to de-
cydent jest zainteresowany dalsza poprawa ocen, o ile jest to
możliwe .