Wyk. 9, 7 semestr, Optymalizacja w biznesie i logistyce
[ Pobierz całość w formacie PDF ]
Optymalizacjawielokryterialna
Problemyoptymalizacjiwielokryterialnejwystƒpuj¡np.wanalizieportfelowejiekonomii
matematycznejprzyrozwa»aniachr
ó
wnowagikonkurencyjnej.
De
nicja1.Niechdanebƒd¡f
i
:
R
n
!
R
,i=1;:::;k,gdziek 2orazS
R
n
.
Problememoptymalizacjiwielokryterialnej(MOP)(multi-criteriaoptimiza-
tionproblem)nazywamyzagadnieniepostaci
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S:
:
(MOP)
Funkcjef
i
,i=1;:::;knazywamyfunkcjamicelu(objectivefunction),awektor
f(x)=[f
1
(x);f
2
(x);:::;f
k
(x)]
T
nazywamywektoremfunkcjicelu.Zbi
ó
rSnazy-
wamyzbioremdopuszczalnym(feasibleregion),kt
ó
ryjestpodzbioremprzestrzeni
zmiennychdecyzyjnych(decisionvariablespace)
R
Uwaga1.Wzagadnieniu(MOP)niepodali–mypostacifunkcjigeneruj¡cychzbi
ó
r
dopuszczalnyS.Ka»d¡funkcjƒbuduj¡c¡Snazywamyfunkcj¡ograniczaj¡c¡(con-
straintfunction).
De
nicja2.Niechdanebƒd¡f
i
:
R
n
!
R
,i=1;:::;k,gdziek 2orazS
R
n
.
Dlazagadnienia
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S:
:
(MOP)
obrazzbiorudopuszczalnegoZ:=f(S)nazywamyzbioremdopuszczalnymrealiza-
cjicel
ó
w(feasibleobjectiveregion)ijesttopodzbi
ó
rprzestrzenikryterialnej
(przestrzeniwektor
ó
wrealizacjicel
ó
w,ang.objectivespace)
R
Uwaga2.Niechdanebƒd¡f
i
:
R
n
!
R
,i=1;:::;k,gdziek 2orazS
R
n
.
Rozwi¡za¢zagadnienie
8
<
maxff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S
:
jestr
ó
wnowa»anezrozwi¡zaniemzagadnienia
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S:
:
1
n
.Je»eliS 6=;,tom
ó
wimy,
»e(MOP)jestzgodny(consisent).Wektorx=[x
1
;x
2
;:::;x
n
]
T
2 Snazywamy
wektoremzmiennychdecyzyjnych.
k
.Wektor
z 2 Z(tzn. z=f(x),x 2 S)nazywamywektoremrealizacjicel
ó
w(objective
values,critetionvalues).
Przyk“ad1.S“owo
zminimalizowa¢
pojawiaj¡cesiƒw(MOP)oznacza,»echcemy
zminimalizowa¢wszystkiefunkcjecelujednocze–nie.Rozwi¡»myzagadnienie
<
minfx1;x
2
g
przyograniczeniach
x 2[0;1]:
a)
(1)
:
Wpowy»szymprzyk“adzieobiefunkcjeceluosi¡gaj¡swojeminimumnazbiorzedo-
puszczalnymwtymsamympunkciex=0ijesttooczywi–cierozwi¡zanie(1)iw
takichprzypadkachniepotrzebujemy»adnychspecjalnychmetodrozwi¡zywaniatego
zagadnienia.Takiesytuacjes¡trywialneiniebƒdziemysienimizajmowa¢wdal-
szychrozwa»aniach.Interesuj¡nasprzypadkiproblem
ó
w(MOP),wkt
ó
rychsk“adowe
wektorafunkcjicelus¡wczƒ–ciowymkon
ikcie,czylinp.chcemyrozwi¡za¢problem
8
<
minf1x;x
2
g
przyograniczeniach
x 2[0;1]:
b)
:
(2)
Wpowy»szymprzyk“adziejednafunkcjaceluosi¡gaswojeminimumnazbiorzedo-
puszczalnymwpunkciex=0,adrugaosi¡gaswojeminimumnazbiorzedopuszczal-
nymwpunkciex=1.
Oilewoptymalizacjijednokryterialnejnaszezainteresowaniejestzogniskowane
naprzestrzenizmiennychdecyzyjnych,towprzypadkuoptymalizacjiwielokryterialnej
zwyklebardziejjeste–myzainterowaniprzestrzeni¡kryterialn¡.Podstawow¡trudno–ci¡
wanalizieproblem
ó
w(MOP)jestfakt,»ewprzestrzeni
R
k
,k 2niemanaturalnego
liniowegoporz¡dku(jakijestw
R
),booilemo»napowiedzie¢,»ewektor[1;2]
T
jest
gorszyni»[3;3]
T
,toniemo»nanp.por
ó
wna¢wektor
ó
w[1;4]
T
i[2;3]
T
.W
R
k
jest
jedynieczƒ–ciowyporz¡dek.Przypomnijmy,»e
De
nicja3.Relacjƒ X Xnazywamyrelacj¡czƒ–ciowegoporz¡dku,gdy
spe“niaspe“niawarunki:
i)zwrotno–¢,tzn.8x 2 X xx;
ii)przechodnio–¢,tzn.8x;y;z 2 X(xy ^ yz)) xz;
iii)antysymetrczno–¢,tzn. 8x;y 2 X(xy ^yx)) x=y.
W
ó
wczasm
ó
wimy,»erelacjajestrelacj¡czƒ–ciowoporz¡dkuj¡c¡zbi
ó
rX.
Je»elirelacjaczƒ–ciowoprz¡dkuj¡cazbi
ó
rXspe“niadodatkowowarunek
iv)sp
ó
jno–¢,tzn.8x;y 2 X(xy _yx).
tom
ó
wimy,»erelacjajestrelacj¡liniowegoporz¡dkuoraz»ezbi
ó
rXjestzbiorem
liniowouporz¡dkowanymprzezrelacjƒ.
2
Uwaga3.Naturaln¡relacj¡czƒ–ciowegoporz¡dkuw
R
k
,k 2jestrelacja
k
x y ) 8i=1;:::;k x
i
y
i
:
8x;y 2
R
Zauwa»my,»e
x y , xy 2
R
:=fw 2
R
n
:w
i
0;i=1;:::;kg:
k
pewnewektoryrealizacjicel
ó
wmog¡by¢
okre–lonejakooptymalne.S¡towektoryrealizacjicel
ó
w,kt
ó
rychniemo»napoprawi¢
nawszystkichwsp
ó
“rzƒdnychjednocze–nie.Oznacza,»eje»elinastƒpujepoprawana
pewnejwsp
ó
“rzƒdnej,tomusinastapi¢pogroszenienainnej.De
nicjatazostalaw
1881zaprezentowanaprzezEdgewortha,alewektoryopowy»szejw“asno–cinazywasiƒ
wektoramioptymalnymiwsensiePareto(lubPareto-optymalnymi).VilfredoPareto
by“francusko-w“oskimekonomist¡isocjologiemibada“pojƒcieEdgeworthawpracy
z1896ip
ó
„niej.Matematyczniede
nicjƒPareto-optymlano–ciw1951sformulowa“
Koopmansimaonaposta¢
De
nicja4.Niechdanybƒdzieproblem
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S:
:
(MOP)
Wektordecyzyjnyx
?
2 Snazywamywektorem/rozwi¡zaniemoptymalnymw
sensiePareto(MOP)(Pareto-optymalnym),je»eli
9x 2 S f(x) f(x
?
)^ f(x)6=f(x
?
)
,
9x 2 S(8i 2f1;:::;kg f
i
(x) f
i
(x
?
)^ 9i
0
2f1;:::;kg f
i
0
(x)< f
i
0
(x
?
)
:
Uwaga4.Czasamizamiastokre–leniaPareto-optymlanyu»ywasiƒpojƒ¢niezdomi-
nowany,efektywny(ang.noninferiority,e
ciency,nondominance).
Przyk“ad2.Dyrekcjaog“osi“akonkursnastanowiskoasystentadyrektora/-rki.Zg“osi“o
siƒ6kandydat
ó
w.Poddanoichbadaniomtestowymnainteligencjƒ,umiejƒtno–¢pos“ugi-
waniasiƒkomputeremiznajomo–¢jƒzykaangielskiego.Skalaocenstosowaneprzy
poszczeg
ó
lnychtestachs¡nastƒpuj¡ce:
0,1,2,3-(nie-,ma“o-,przeciƒtnie,wybitnieinteligenta);
0,1,2-(s“aba,wystrczaj¡ca,bieg“aumiejno–¢pos“ugiwnaniasiƒkomputera);
0,1,2,3,4-(niedostateczna,dostateczna,dobra,bardzodobra,wybitnaznajomo–¢jƒzyka).
Kandydacizostalioznaczenienumeramiod1do6iuzyskalinastƒpuj¡cetr
ó
jkiocenz
test
ó
wwed“ugpodanejwy»ejkolejno–ciiotrzymanorezultaty:
(1,2,2),(1,1,4),(2,2,4),(2,2,3),(3,2,3),(3,1,1).Kt
ó
regozkandydat
ó
wpowininawybra¢
dyrekcja,kieruj¡csiƒjedyniewynikamitest
ó
w?Tutajmamyzadaniemaksymalizacji.
Twierdzenie1.Niechdanybƒdzieproblem
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S:
:
(MOP)
3
k
Dziƒkirealcjiczƒ–ciowegoporz¡dkuw
R
W
ó
wczasx
?
jestwektorem/rozwi¡zaniemoptymalnymwsensieParetowtedyitylko
wtedy,gdy
f(S)\(
R
k
+ff(x
?
)g)=ff(x
?
)g (Z \(
R
k
+ff(x
?
)g)=ff(x
?
)g):
Dow
ó
d.Dow
ó
dprzeprowadzonynawyk“adzie.
Przyk“ad3.Wyznaczy¢zbi
ó
rwektor
ó
woptymalnychwsensieParetozrysunk
ó
wna
R
.
jestwymiaruk >2.Abyrozwi¡zywa¢
zagadanienia(MOP)staramysiƒteproblemysprowadza¢dozada«,kt
ó
reumiemy
rozwi¡za¢,czylistosujemyskalaryzacjƒzagadnienia(MOP).Istniejewielemo»liwo–ci
skalaryzacji,myograniczymysiƒtylkodowprowadzeniajednejzmetod-metody
wagowej.
k
Niechdanybƒdziewektorw=(w
1
;:::;w
k
)2
R
k
+
,
P
k
i=1
w
i
=1orazniechdanybƒdzie
problem
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S:
:
(MOP)
Okre–lamyproblemwagowy(P(w))zwi¡zanyz(MOP)postaci
8
<
X
w
i
f
i
(x)!min
i=1
(P(w))
:
przyograniczeniach
x 2 S:
Przejd„mydoprezentacjiwarunk
ó
wdostatecznychoptymlano–ciwsensieParetozwi¡zanych
zproblememwagowym.
Twierdzenie2.Je»elix
?
w
jestrozwi¡zaniemproblemuwagowego(P(w))dlaw
i
>0,
i=1;:::;k,tox
?
w
jestrozwi¡zaniemoptymalnymwsensieParetodla(MOP).
Dow
ó
d.Dow
ó
dprzeprowadzonynawyk“adzie.
Zauwa»my,»eniemo»eby¢tojednakwarunekkonieczny.
Przyk“ad4.Rozwa»mywcze–niejrozwa»anyprzyk“ad(2),czyli
<
minf1x;x
2
g
przyograniczeniach
x 2[0;1]:
b)
:
4
2
Niezawszemo»emykorzyta¢zgeometrycznychmetod,wszczeg
ó
lno–cidotyczyto
przypadk
ó
wgdyprzestrze«kryterialna
R
k
Jakpokazali–mywcze–niejka»dywektorrealizacjicel
ó
wjestPareto-optymlany.Rozwi¡»my
problemywagowe(P(w))w=(w
1
;w
2
),gdziew
1
;w
2
>0,w
1
+w
2
=1iwtedy
w
1
=1w
2
,w
2
2(0;1)tzn.problemypostaci
8
<
(1w
2
)(1x)+w
2
x
2
!min
przyograniczeniach
x 2[0;1]:
:
P(w
MOP
b
)
Funkcjacelujestfunkcj¡kwadratow¡wpostacikanonicznej f(x)=w
2
(x
1
w
2
2w
2
)
2
(1
w
1
)(1
5w
2
)
4w
2
ist¡d
(
1
w
2
2w
2
dlaw
2
2[
1
3
;1)
1 dlaw
2
2(0;
1
3
)
cogenerujenamwektoryPareto-optymlanepostaci
x
w
2
min
=
(1y;y
2
); y 2(0;1]
inieudanamsiƒwygenerowa¢zrozwi¡za«problem
ó
w(P(w
MOP
b
))rozwi¡zania
Pareto-optymlanego(1;0).
Twierdzenie3.Je»elix
?
w
jestjedynymrozwi¡zaniemproblemuwagowego(P(w)),to
x
?
w
jestwektoremoptymalnymwsensieParetodla(MOP).
Dow
ó
d.Dow
ó
dprzeprowadzonynawyk“adzie.
Przejd„mydoprezentacjiwarunkukoniecznegooptymlano–ciwsensieParetozwi¡zanego
zproblememwagowym,kt
ó
rywymagadodatkowegoza“o»enia.
Twierdzenie4.NiechS
R
k
bƒdziezbioremwypuk“ymorazfunkcjef
i
bƒd¡funkcjami
wypuk“yminaS.Je»elix
?
jestwektoremoptymalnymwsensieParetodla
8
<
minff
1
(x);f
2
(x);:::;f
k
(x)g
przyograniczeniach
x 2 S;
:
(MOP)
toistniejew=(w
1
;:::;w
k
),w
i
0,i=1;:::;k,
P
k
i=1
w
i
=1taki,»ex
?
jest
rozwi¡zaniemproblemuwagowego(P(w)).
Przyk“ad5.Dow
ó
dpowy»szegotwierdzeniawykorzsytujetwierdzeniaopodpieraniu,
cowymagaza“o»eniaowypuk“o–ciproblemu.Zauwa»mynaprzyk“adzie,»ejestto
za“o»enieistotne.
5
[ Pobierz całość w formacie PDF ]