Diplomová práce
Heuristické metody pro vícekriteriální analýzu vypracoval: Jaroslav Smrž vedoucí práce: doc. RNDr. Jindřich Klapka, CSc. obor: Inženýrská informatika a automatizace specializace: Informatika 2006
Strana 3
ZADÁNÍ ZÁVĚREČNÉ PRÁCE (na místo tohoto listu vložte originál a nebo kopii zadání Vaš práce)
Strana 5
ANOTACE Tato diplomová práce se zabývá metodami vícekriteriální analýzy a optimalizace. Metody vícekriteriální analýzy jsou jednou z oblastí rozsáhlého výzkumu v optimalizaci za posledních 20 let. Nejprve si představíme obecně vícekriteriální analýzu, její teorii a vybrané metody. Dále presentujeme metodu pro vícekriteriální výběr projektů J. Klapky, P. Piňose a její speciální případ metodu T. J. Stewarta. Tento algoritmus potom otestujeme a srovnáme s alternativními způsoby výpočtu.
ANNOTATION This thesis deals with the implementation of Multicriteria Decision Support. Multicriteria Decision Support has been one of the most active research areas in optimization for the past 20 years. At first we introduce Multicriteria Decision Support in general, theory and selection of methods. We also present original implementation of method for multicriteria selection of projects by J. Klapka, P. Piňos and special case of this method - method by T. J. Stewart. We test the algorithm and confront it with alternative ways of computation.
Strana 7
PODĚKOVÁNÍ Děkuji vedoucímu práce, doc. RNDr. Jindřichu Klapkovi, CSc., za cenné rady a připomínky, kterými přispěl k její realizaci.
Strana 9
Obsah: Zadání závěrečné práce...................................................................................................3 Anotace.............................................................................................................................5 Poděkování.......................................................................................................................7 1 Úvod.............................................................................................................................11 1.1 Základy vícekriteriálního rozhodování....................................................................11 1.2 Podstata úloh vícekriteriálního rozhodování...........................................................11 1.3 Prvky vícekriteriálního rozhodovacího procesu......................................................11 1.4 Klasifikace rozhodovacích procesů.........................................................................12 1.5 Kritéria....................................................................................................................12 1.6 Typy škál ................................................................................................................13 2 Metody modelování preferencí mezi kritérii a variantami ...................................17 2.1 Členění metod podle informací o kritériích ...........................................................17 2.2 Metody s nominální informací o kritériích.............................................................17 2.2.1 Metoda stejné důležitosti...............................................................................................17 2.2.2 Metoda aspirační úrovně ...............................................................................................18
2.3 Metody s ordinální informací o kritériích...............................................................18 2.3.1 Lexikografická metoda...................................................................................................18
2.4 Metody skalarizace ordinální informace o kritériích..............................................18 2.4.1 Metoda pořadí a bodovací metoda.................................................................................19 2.4.2 Metody párového porovnání.........................................................................................19 2.4.3 Metoda Fullerova trojúhelníku.......................................................................................19 2.4.4 Saatyho metoda párového porovnání............................................................................21 2.4.4.1 Metoda nejmenších čtverců stanovení vah..................................................................21 2.4.4.2 Metoda logaritmických NČ (Metoda geometrického průmeru)..................................22
2.5 Metody s kardinální informací o kritériích.............................................................23 2.5.1 Úvod do metod s kardinální informací o kritériích........................................................23 2.5.2 Standardizace a normalizace..........................................................................................23 2.5.3 Metody založené na funkci užitku..................................................................................25 2.5.4 Metody založené na párovém porovnání variant...........................................................25 2.5.5 Metody vzdálenosti........................................................................................................26
3 Vícekriteriální programování...................................................................................29 3.1 Metody s informací á posteriori..............................................................................29 3.2 Interaktivní metody.................................................................................................30 3.2.1 Metoda GDF...................................................................................................................31 3.2.2 Ziontsova – Walleniusova metoda..................................................................................32 3.2.3 Metoda STEM................................................................................................................33 3.2.4 Steuerova metoda...........................................................................................................34
3.3 Kombinované metody.............................................................................................35 4 Vícekriteriální výběr projektů ..................................................................................39 4.1 Formulace problému...............................................................................................39 4.2 Úprava zadání..........................................................................................................40 4.3 Implementace hierarchických závislostí do programového systému......................41 4.4 Optimalizace a dialog..............................................................................................41 4.5 Numerický příklad ..................................................................................................43 5 Vliv zdrojových omezení na výběr projektů ...........................................................47 5.1 Algoritmus výpočtu.................................................................................................47 5.1.1 Metoda efektivního gradientu........................................................................................47 5.1.2 Uvažování zdrojových omezení.....................................................................................48
Strana 10
Poděkování
5.1 Numerický příklad...................................................................................................49 5.2 Experiment .............................................................................................................56 6 Závěr............................................................................................................................59 Seznam použité literatury.............................................................................................61
Strana 11
1
ÚVOD
Rozvoj výpočetní techniky a zejména rozšíření osobních počítačů, které jsou dnes přístupné prakticky každému, vytváří zcela novou situaci ve využití formalizovaných přístupů v rozhodovacích situacích manažerů malých a středních podniků, běžných zákazníků a vlastně i obyčejných občanů v běžném životě, např. v domácnosti. Osobní počítač vybavený vhodným programem, dovoluje smysluplné využití v oblasti, která byla dříve doménou ústavů a velkých podniků, totiž v oblasti počítačové podpory rozhodování. Aplikační sféra se takto rozšiřuje z rozhodovacích problémů celospolečenského významu na individuální problémy menších rozměrů malých firem i jednotlivců, např. výběr nejvhodnějšího osobního automobilu nebo jiného nákladnějšího přístroje pro firmu i pro domácnost, výběr vhodné rodinné dovolené, školy ke studiu, způsobu uložení peněz apod. Rozhodovací úlohy, v nichž se důsledky rozhodnutí posuzují podle více kritérií, se nazývají úlohami vícekriteriálního rozhodování, někdy se překládá výraz vícekriteriální jako multikriteriální z anglického multicriterion. Vícekriteriální rozhodování je obor lidské činnosti analyzující rozhodování lidí a to v nejrůznějších oblastech lidské činnosti.
1.1
Základy vícekriteriálního rozhodování
Vícekriteriálnost představuje podstatný rys rozhodování jak ve sféře ekonomické, tak sociální, politické, vojenské apod. Rozhodovacími procesy se nejčastěji rozumí řešení problémů s více než jednou možností řešení. Řešením vícekriteriální rozhodovací úlohy se rozumí postup, který vede k nalezení „optimálního“ stavu systému vzhledem k více než jednomu uvažovanému kritériu. Takový postup se nazývá rovněž vícekriteriální optimalizace. Vzájemně provázané činnosti tvořící náplň rozhodovacích procesů lze charakterizovat jednotlivými složkami (prvky, fázemi, etapami apod.).
1.2
Podstata úloh vícekriteriálního rozhodování
Rozhodnutím zde rozumíme vybrání jedné varianty ze seznamu v dané situaci potenciálně realizovatelných variant na základě většího množství kritérií. Vedle seznamu kritérií nepřímo formulujících cíl rozhodovací analýzy je nutné mít k dispozici i seznam (množinu) variant, z nichž rozhodnutí vybíráme. Případy, kdy je k dispozici jednoznačně definovaný seznam potenciálních variant jsou spíše výjimkou než pravidlem. Tento seznam může být zadán explicitně, jako výčet konečného počtu možností, nebo implicitně specifikací podmínek, které musí rozhodovací varianta splňovat, aby mohla být považována za přípustnou. Ani v této etapě rozhodovacího postupu se zpravidla nelze vyhnout subjektivním vlivům případně i zjišťování mínění expertů či zadavatele úlohy. Je-li k dispozici seznam kritérií i seznam rozhodovacích variant, je nutné podrobněji uvážit, jaku formu by konečné rozhodnutí mělo mít. Trváme-li na tom, že je skutečně nutné vybrat jedinou „optimální“ variantu určenou k realizaci, měli bychom si připustit, že v typických případech chceme z nespolehlivých a nedostatečných informací vytěžit něco, co v nich téměř jistě není obsaženo. Speciálním případem takto formulované úlohy je požadavek, abychom seřadili rozhodovací varianty podle pořadí v souladu s tím, jak se přibližují k představě varianty optimální.
1.3
Prvky vícekriteriálního rozhodovacího procesu Prvky vícekriteriální rozhodovací soustavy jsou zejména : ● ● ● ● ●
cíl rozhodování, subjekt a objekt rozhodování, kritéria, varianty, stavy světa.
Cílem rozhodování rozumíme určitý budoucí stav systému vyplývající z nutnosti uspokojit
Strana 12
1Úvod
určité potřeby nebo plnit jisté funkce. Cíle se má dosáhnout realizací některé z variant rozhodování. Cíl rozhodování se obvykle hierarchicky rozkládá do dílčích cílů, které se transformují do podoby rozhodovacích kritérií. Rozhodovací kritéria mohou mít různou podobu od fyzikálních, technických nebo technologických měřitelných vlastností, přes ekonomická kritéria vyjadřovaná peněžitými jednotkami až k neměřitelným subjektivním kritériím typu krása, vůně, morálka aj. Někdy u kritérií dále rozlišujeme, zda existují nezávisle na naší vůli – v tom případě se jedná o charakteristiky, eventuálně vlastnosti, jindy kritéria úmyslně vytváříme – pak hovoříme o atributech. V této kapitole se nebudu podrobnějšímu členění kritérií věnovat, k tomuto tématu se vrátím v pozdějších kapitolách. Prozatím vystačíme s obecným pojmem kritérium, které můžeme interpretovat jako určité hodnotící hledisko, jež bereme v úvahu při rozhodování. Základem pro stanovení souboru kritérií je soubor dílčích cílů řešení rozhodovacího problému. Některé dílčí cíle se však netransformují do podoby kritérií, nýbrž do omezujících podmínek k redukci souboru rozhodovacích variant. Variantami mohou být nejrůznější prvky, které má smysl vzájemně porovnávat, nebo, v užším kontextu, přicházejí v úvahu pro výběr v určitém procesu rozhodování. Například zákazník se rozhoduje při koupi mezi výrobky určitého typu (automobily, počítače aj.), ředitel podniku rozhoduje mezi různými perspektivními výrobními programy, různými variantami marketingových strategií, různými kandidáty na řídicí funkce v podniku apod. Subjektem rozhodování může být jednotlivec nebo skupina jednotlivců (podnik, instituce apod.), která rozhoduje. Protipólem subjektu rozhodování je objekt rozhodování, který představuje systém, v němž je formulován rozhodovací problém, cíl, kritéria i varianty rozhodování. Důsledky variant vyjádřené jako hodnoty kritérií jsou jednoznačné, nebo závisejí na stavech světa. Ty jsou chápány jako vzájemně se vylučující stavy té části okolí rozhodovacího systému, která je mimo kontrolu rozhodovatele. Náhodné faktory okolí se obvykle považují za náhodné veličiny určující stavy světa. Problémem vícekriteriálního rozhodování (za jistoty) zde rozumíme úlohu nalezení „optimální“ varianty, která by v „co možná největší míře“ zohledňovala uvažovaná kritéria (dílčí cíle). Pojmy uvedené v uvozovkách prozatím chápeme intuitivně, jejich význam bude upřesněn na příslušném místě později. Obecný postup při řešení problému vícekriteriálního rozhodování rozdělíme do 4 kroků : 1. Stanovení cíle rozhodování. 2. Vyčlenění množiny variant A={a1 , a 2 , , a n } a vyčlenění množiny kritérií C={ f 1 , f 2 , , f m }. 3. Dílčí vyhodnocení všech variant podle jednotlivých kritérií. 4. Agregace dílčích hodnocení do výsledného celkového hodnocení a výběr „optimální“ varianty.
1.4
Klasifikace rozhodovacích procesů
Jedno z nejdůležitějších hledisek při klasifikaci rozhodovacích procesů představuje informace o stavech světa a důsledcích variant vzhledem k jednotlivým kritériím. Tato informace může být buď úplná (deterministická) vzhledem k jednoznačnosti stavů světa a hodnot kritérií jednotlivých variant, nebo neúplná, náhodná (stochastická). V prvním případě hovoříme o rozhodování za jistoty, ve druhém případě o rozhodování za rizika, nebo rozhodování za nejistoty. Přitom rozhodování za rizika odlišujeme od rozhodování za nejistoty podle toho, zda známé příslušné pravděpodobnostní rozdělení, nebo jej alespoň v principu můžeme zjistit. Pokud rozdělení pravděpodobnosti neznáme a nelze jej ani zjistit, jedná se o rozhodování za nejistoty.
1.5
Kritéria
Každé vybrané kritérium slouží v rozhodovací úloze k tomu, abychom dané varianty podle něj vyhodnocovali, eventuálně porovnávali či uspořádali. Jakým způsobem budeme toto porovnávání uskutečňovat závisí na povaze každého kritéria. Z čistě formálního hlediska můžeme každé kritérium v našem rozhodovacím problému ztotožnit s určitým zobrazením f množiny variant A do jiné
1Úvod
Strana 13
množiny S nazývané stupnice (škála), zapsáno matematicky : f : A S. Ohodnocení varianty a ∈ A podle kritéria f je obraz varianty a při zobrazení f, označujeme jej symbolem f a , přičemž f a ∈ S. Důležitý je v této souvislosti fakt, že jednotlivá ohodnocení různých variant lze mezi sebou porovnávat, což jinak řečeno znamená, že škála S má některé vlastnosti uspořádané množiny. V závislosti na těchto vlastnostech uspořádání rozlišujeme několik typů škál (stupnic). K vysvětlení této problematiky budeme potřebovat si ujasnit, co rozumíme pod pojmem uspořádaná množina, kterýžto pojem je dále založen na pojmu relace. Nechť S je množina, S ×S je kartézský součin, tj. množina všech dvojic u , v , u∈ S , v ∈S. Podmnožina R⊆S ×S se nazývá relace na S. Jsou-li dva prvky u , v∈ S spolu v relaci R , označujeme to takto: u , v ∈R nebo uRv . Relace R na množině S se nazývá : ● ● ● ● ●
reflexivní, jestliže platí: uRu pro každé u ∈S, symetrická, jestliže platí: u ∈S , v ∈S , uRv potom vRu, antisymetrická, jestliže platí: u ∈S , v ∈S , uRv , vRu potom u=v, tranzitivní, jestliže platí: u ∈S , v ∈S , w ∈S , uRv , vRw potom uRw , úplná, jestliže platí: u ∈S , v ∈S potom uRv anebo vRu.
Relace R na množině S se nazývá částečné uspořádání, jestliže je reflexivní, antisymetrická a tranzitivní. Relace R na množině S se nazývá uspořádání, jestliže je reflexivní, antisymetrická, tranzitivní a úplná. Relace R na množině S se nazývá částečné kvaziuspořádání, jestliže je reflexivní a tranzitivní. Relace R na množině S se nazývá kvaziuspořádání, jestliže je reflexivní, tranzitivní a úplná. Nechť R je relace na S. Preferenční relaci P na S k relaci R definujeme takto: uPv právě když u R v ∧v R u. Indiferenční relaci I na S k relaci R definujeme takto: uIv právě když u R v∨v R u. Relaci R lze vyjádřit pomocí preferenční a indiferenční relace: Mějme u ∈S , v ∈S , potom u R v právě když u P v nebo u I v . Tento fakt vyjadřujeme zkráceně zápisem R= P , I . Mějme kritérium f , tj. zobrazení množiny variant A do množiny S , f : A S , a nechť R je relace na S . Relace ⊂ na A indukovaná kritériem f je definováno takto: Nechť a ,b∈ A , potom a⊂b právě když f a R f b . Nechť R je relace na S , f : A S . Jestliže R je (částečné) uspořádání na S , potom relace ⊂ indukovaná kritériem f je (částečné) kvaziuspořádání na A . Kritérium f a relace uspořádání na škále S umožňují definovat (indukovat) příslušné (částečné) kvaziuspořádání také na množině variant A . Přitom některé varianty mohou být ohodnoceny stejně, a proto pro relaci ⊂ neplatí podmínka antisymetrie. Jinak řečeno, pomocí kritéria f můžeme varianty z množiny A vyhodnocovat, tj. uspořádat (seřadit), tak jak nám to dovoluje relace na škále S . Provedeme-li rozklad relace ⊂ na relaci preference ⊂ P a indiference ⊂ I , pak různě hodnocené varianty z A jsou v relaci ⊂ P , zatímco stejně ohodnocené varianty jsou společně v relaci ⊂ I .
1.6
Typy škál
Nominální škála S nemá vlastnost uspořádání, tj. není na ní definována žádná relace. Ohodnocení varianty a ∈ A podle kritéria f označuje variantu a pouze jejím jednoznačným jménem f a ∈ S , což znamená, že zobrazení f musí být prosté (jednoznačné). Kritérium f : A S nazýváme nominální, jestliže f je prosté a S je nominální škála.
Strana 14
1Úvod
Ordinální škála S je uspořádanou množinou, tj. je na na ní dána relace R , která je relací uspořádání na S . Ohodnocení všech variant f a j ∈S , j=1,2 , , n dovoluje varianty a j úplně uspořádat „od nejhorší k nejlepší“ a toto uspořádání je invariantní vůči rostoucímu monotónnímu zobrazení : S S, tj. složené zobrazení ° f poskytuje stejné uspořádání variant, jako kritérium f. Jestliže tedy f a 1 ∈S , f a 2∈S , f a 1 R f a 2, potom platí: f a 1 R f a 2 . Kritérium f : A S nazýváme nominální, jestliže f je prosté a S je nominální škála. Kardinální škála S je podmnožinou množiny reálných čísel, tj. S ⊆R, včetně jejího přirozeného uspořádaní „menší rovno“, tj. ≤. Kritérium f : A S nazýváme kardinální, jestliže S je kardinální škála a f je invariantní vůči lineární transformaci x=axb , a0. Častým příkladem kardinální škály je jednotkový číselný interval [0,1]⊆R . Kritérium f : A[0,1] nazýváme váhové kritérium, jestliže pro vi = f a i ∈[0,1] platí: m
∑ v i=1. i =1
Čísla vi pak nazýváme váhy. Váhy vi můžeme interpretovat jako relativní důležitosti (významnosti) jednotlivých variant a i ∈ A vzhledem ke kritériu f. Součet vah je roven 1, proto hodnoty 100⋅v i lze také interpretovat jako procentuální významnost varianty a i z celkové významnosti všech variant vzhledem ke kritériu f. Uvažujme problém stanovení „optimálního“ rozhodnutí, neboli výběru „optimální“ varianty na základě uvažovaných kritérií. Máme množinu variant A={a1 , a 2 , , a n } a množinu kritérií C={ f 1 , f 2 , , f m} , každé kritérium je reprezentováno zobrazením f i : A S i, přitom S i je ordinální nebo kardinální škála s relací ≤i, která je uspořádáním, potom je relace ⊂i indukovaná kritériem f i, kvaziuspořádáním, i=1,2 , , m . Jestliže pro kritérium f i a dvě varianty a , b∈ A platí a ⊂i b, nebo f i a≤i f i b, potom říkáme, že podle i -tého kritéria je varianta a „je dominována“ variantou b , nebo, že varianta b „dominuje“ a podle i -tého kritéria. Varianta, která podle i -tého kritéria dominuje všechny ostatní varianty, se nazývá nejlepší variantou podle i -tého kritéria. Varianta, která je dominována všemi ostatními variantami se nazývá nejhorší varianta. V naší terminologii je pojmenování relací „je dominována“ a „dominuje“ podle i -tého kritéria potřeba brát spíše ve formálním než významovém slova smyslu. Asi by bylo přijatelnější na místo „dominuje“ použít „je stejně důležitá, nebo dominuje“, neboť podle naší terminologie varianta a „dominuje“ b (reflexivita), což sémanticky nevypadá dobře. Protože jsme pro název naší preferenční relace nenašli vhodnější krátké označení, tak výroku: varianta a „dominuje“ variantu b rozumíme ve významu: varianta a „je stejně důležitá, nebo dominuje“ variantu b . Analogický významový posun lze uplatnit pro termín „je dominována“ podle i -tého kritéria. Následující tvrzení říká, že nejlepší varianta podle jediného kritéria vždy existuje, což je snadným důsledkem toho, že příslušná škála je uspořádanou množinou a také faktu, že množina ohodnocení variant je její konečnou podmnožinou. Nechť A={a1 , a 2 , , a n } je množina variant, a nechť kritérium f je reprezentováno zobrazením f : A S, kde S je ordinální nebo kardinální stupnice s relací ≤, která je uspořádáním, dále nechť relace ⊂ je indukována kritériem f. Potom existuje nejlepší varianta (podle kritéria f). Pro každé kritérium uvažujeme ohodnocení všech variant :
y ij = f i a j , i=1,2 , , m , j=1,2 , , n. Získáme tak kriteriální matici H ={ y i , j } typu m×n, hodnota y i , j ∈S představuje ohodnocení j -té varianty i -tým kritériem. Pokud je S i ⊆R pro všechna i=1,2 , , m , například jsou–li všechna kritéria kardinální, potom matice H je obvyklou maticí s reálnými prvky. Kriteriální matice H představuje základní vstupní informace (data) nezbytná k učinění rozhodnutí, tj. výběru „optimální“ varianty. Další postup vedoucí k výběru „optimální“ varianty pak závisí především na tom, zda máme k dispozici ještě nějaké další informace o rozhodovacím problému, například informace o významnosti jednotlivých kritérií. Doposud jsme výraz optimální uváděli v uvozovkách, neboť jsme ještě neupřesnili, v jakém smyslu máme optimalitu našeho
1Úvod
Strana 15
rozhodnutí (varianty) chápat. Nejprve budeme analyzovat situaci, kdy nemáme kromě materiální matice o rozhodovacím problému žádné další informace. Konkrétně informace o důležitosti jednotlivých kritérií pro rozhodování nejsou k dispozici, ani je nelze získat, nebo nemá smysl o nich uvažovat. Potom lze ovšem od optimálního rozhodnutí (optimální varianty) očekávat, že bude podle všech kritérií nabývat nejlepších hodnot. V reálných rozhodovacích situacích je takové očekávání značně iluzorní, neboť uvažovaná kritéria jsou obvykle protichůdná, a to znamená, že zlepšení ohodnocení jednoho kritéria způsobí zhoršení jiného. Zavádíme proto pojem dominovanosti (podle všech kritérií současně) a pojem nedominované varianty. Nechť a ´ , a´ ´ ∈ A jsou dvě varianty, pro každé kritérium f i : A S i, kde S i je ordinální nebo kardinální škála s relací ≤i, která je uspořádáním, i=1,2 , , m . Říkáme, že varianta a ´ ´ dominuje ´ ´´ variantu a ´ a píšeme a ⊂D a , jestliže platí:
f i a´ ≤i f i a ´´ pro každé i=1,2 , , m. Varianta se nazývá nedominovaná, jestliže v množině rozhodovacích variant neexistuje varianta, která ji dominuje. Symbolem AN označujeme množinu všech nedominovaných variant, AN ⊆ A. Relace ⊂D je částečným kvaziuspořádáním na množině A. Nedominované varianty, tedy prvky z množiny AN nejsou pomocí relace ⊂D porovnatelné. Varianta je nedominovaná, když neexistuje jiná varianta, která ji dominuje podle všech kritérií. Každá jiná varianta musí být dominována alespoň podle jednoho kritéria. Povšimněte si rozdílu mezi pojmy „dominovaná podle určitého kritéria“ a „dominovaná“ (rozuměj podle všech kritérií). Pojem nedominované varianty se zdá být racionálním kandidátem na „optimální“ variantu. V praxi však často nevyhovuje, a to z toho důvodu, že nedominovaných variant bývá relativně k počtu všech uvažovaných variant příliš mnoho. Z definice dominance je jasné, že dominované varianty nemají pro optimální rozhodnutí praktický význam, můžeme je proto z dalších úvah vypustit. Vskutku, je–li varianta dominována jinou variantou, pak tato jiná varianta je „lepší“ podle všech kritérií, a proto můžeme dominovanou variantu z dalších úvah vyloučit. Pro následný, nyní již zúžený výběr optimální varianty, zůstávají pouze nedominované varianty. Budeme předpokládat, že všechny uvažované varianty v Ajsou nedominované, jinými slovy, že v prvním kroku, jak byl popsán dříve, jsme vypustilivšechny dominované varianty. Abychom počet variant dále zredukovali, v ideálním případě až na jeden prvek – optimální variantu, potřebujeme doplňující informace a na ně navazující metody. Výběr konkrétní optimální varianty pak závisí na použité metodě. Někdy se namísto pojmu optimální varianta používí název kompromisní varianta. Nejlepší představitelná varianta je varianta, která podle všech kritérií nabývá nejlepšího hodnocení všech variant. Taková varianta se nazývá ideální varianta (někdy též zenit). Na druhou stranu můeme definovat variantu s nejhorším ohodnocením podle všech kritérií, takovou variantu nazýváme bazální varianta (někdy též nadir). V reálných rozhodovacích situacích, tj. v množině variant A, se s ideální, resp. bazální variantou, jako variantami, které přicházejí v úvahu pro výběr optimální varianty, prakticky nesetkáváme. Jedná se tudíž o varianty uměle vytvořené, které však mohou být užitečné při stanovení optimální varianty, například tak, že optimální varianta bude od ideální varianty nejméně vzdálena, nebo naopak nejvíce vzdálena od bazální varianty, což nemusí být vždy totéž. Ke stanovení „vzdálenosti“ dvou variant však potřebujeme nástroj, kterým bychom tuto vzdálenost měřili, tzv. metriku.
Strana 16
1Úvod
Strana 17
2
METODY MODELOVÁNÍ PREFERENCÍ MEZI KRITÉRII A VARIANTAMI Problém vícekriteriálního rozhodování vychází z těchto východisek: Je dána množina variant
A, množina kritérií C, každé kritérium je reprezentováno zobrazením f i : A S i, přitom S i i je ordinální nebo kardinální škála s relací, která je uspořádáním. Relace indukovaná kritériem f i je kvaziuspořádáním. Předpokládáme dále, že množina A obsahuje pouze nedominované varianty. Mezi těmito variantami se má vybrat optimální varianta. Vzhledem k tomu, že optimální varianta je zároveň nedominovaná, potom jestliže ji zaměníme za jinou nedominovanou variantou, pak tato nová varianta bude mít podle některých kritérií ohodnocení lepší, podle jiných kritérií bude mít ohodnocení horší, než původní varianta. Proto takovou variantu budeme nazývat kompromisní varianta. Postup při výběru kompromisní varianty pak závisí na tom, jakou další informaci máme o charakteru, resp. důležitosti jednotlivých kritérií. Intuitivně se zdá oprávněné, aby optimální varianta nabývala co možná nejlepších ohodnocení podle nejdůležitějších kritérií. V této kapitole se budete zabývat metodami vícekriteriálního rozhodování, které budou rozčleněny do 3 hlavních skupin podle typu informací, které o kritériích jsou známy. Jsou to nominální informace, kdy znáte pouze názvy kritérií, dále ordinální informace, kdy jsou kritéria vzájemně uspořádána (podle důležitosti) a konečně kardinální informace, kdy je znám i relativní podíl z celkové důležitosti každého kritéria. Tato informace je dána ve formě tzv. vah. Rozdělení metod do jednotlivých skupin není samoúčelné. Dává totiž možnost pochopit rozdílné typy rozhodovacích úloh z pohledu různé kvality informací, které jsou pro ně k dispozici a na základě ní zvolit správnou metodu na podporu rozhodnutí. Nesprávná volba metody může totiž způsobit nesprávnou interpretaci výsledného řešení a tudíž neadekvátní rozhodnutí
2.1
Členění metod podle informací o kritériích
Na množinu kritérií C={ f 1 , f 2 , , f m} budeme nyní pohlížet, jako by to byla množina variant v novém rozhodovacím problému s jediným kritériem G, jímž je hlavní cíl našeho rozhodovacího problému, tj. výběr optimální varianty z A. Další informace o kritériích budeme dále formulovat jako informace o typu kritéria G, které podobně jako dříve ztotožňujeme se zobrazením množiny C do nějaké škály S, tj. G : C S. Opět rozlišujeme 3 typy kritéria G, tj. 3 druhy informací o variantách z množiny C, jinak řečeno 3 typy informací o kritériích f 1 , f 2 , , f m, což vede k vyšetřování 3 skupin metod vícekriteriálního rozhodování: ● ● ●
metody s nominální informací o kritériích, metody s ordinální informací o kritériích, metody s kardinální informací o kritériích.
2.2
Metody s nominální informací o kritériích
2.2.1
Metoda stejné důležitosti
Nominální informace neříká o kritériích nic víc, kromě jejich jména, nemáme kromě kriteriální matice o rozhodovacím problému žádné další informace. Konkrétně nejsou k dispozici informace o důležitosti jednotlivých kritérií, ani je nelze získat, nebo nemá smysl o nich uvažovat, kritéria nelze uspořádat podle důležitosti, natož jim přidělit číselné váhy, které by vyjadřovaly jejich relativní významnost pro rozhodování. V této situaci se nejčastěji používá technika stejné důležitosti, kdy kritéria při nedostatku informace považujeme za stejně důležitá (to se týká ordinálních kritérií), eventuálně jim přiřadíme stejné váhy (u kardinálních kritérií). Další postup spočívá v použití některé metody s ordinální, resp. kardinální informací o kritériích.
Strana 18 2.2.2
2Metody modelování preferencí mezi kritérii a variantami
Metoda aspirační úrovně
Aspirační úroveň pro kritérium f je hodnota, kterou musí kritérium f pro danou variantu minimálně dosáhnout, aby ta mohla být považována za optimální. Metoda aspirační úrovně při neznalosti informací o důležitosti kritérií vyžaduje alespoň znalost aspirační úrovně i ∈S i pro každé kritérium f i ∈C. Za optimální variantu se vybere ta varianta a ∈ A, pro niž platí: i ≤i f i a pro všechna i=1,2 , , m . Pokud variant splňujících předchozí podmínku je příliš mnoho, je aspirační úroveň „nastavena“ příliš nízko, můžeme proto některé, případně všechny aspirační úrovně zvýšit a opět hledat optimální variantu, která splňuje uvedenou podmínku, tentokrát se zvýšenými hodnotami i. Na druhou stranu, pokud pro danou aspirační úroveň neexistuje žádná varianta splňující podmínku, pak je zapotřebí některé, případně všechny, aspirační úrovně snížit a opět hledat optimální variantu. Tento postup můžeme opakovat tak dlouho, dokud není dosaženo přijatelně malého počtu optimálních variant, v ideálním případě varianty jediné. Nalezení všech optimálních variant splňujících podmínku není v praxi algoritmický problém, neboť se jedná o prověření platnosti jednoduché podmínky na konečné množině variant pro konečný počet kritérií. Při použití běžného počítače řešení takové úlohy není ani numerickým problémem, pokud snad počty variant n a kritérií m nejsou astronomicky velká čísla.
2.3
Metody s ordinální informací o kritériích
Připomeňme, že na množinu kritérií C={ f 1 , f 2 , , f m} nyní pohlížíme, jako by byla množinou variant v novém rozhodovacím problému s jediným kritériem G, kterým je hlavní cíl našeho rozhodovacího problému, tj. výběr optimální varianty z A. Další informace o kritériích budeme nyní formulovat jako informace o typu kritéria G, které podobně jako dříve ztotožňujeme se zobrazením množiny C do škály S, tj. G : C S, jež je však ordinální škálou. V souladu s předchozím výkladem to znamená, že ohodnocení G f i ∈S lze seřadit podle „velikosti“ a indukovaná relace ⊂G je kvaziuspořádáním. Kritéria f i dokážeme pod relace ⊂G seřadit od nejdůležitějšího (nejvýše hodnoceného) k nejméně důležitému, přitom některá kritéria mohou být ohodnocena stejně. Samotná kritéria f i jsou typu ordinálního nebo kardinálního, f i : A S i, přitom S i je ordinální nebo kardinální škála s relací ≤i, která je uspořádáním, i=1,2 , , m . 2.3.1
Lexikografická metoda
Lexikografická metoda vychází z principu, že největší vliv na výběr optimální varianty má nejdůležitější kritérium. Teprve v případě, kdy existuje více variant, které jsou podle nejdůležitějšího kritéria ohodnocena stejně, přichází v úvahu druhé v pořadí nejdůležitější kritérium, atd. Algoritmus se zastaví buď když je v některém kroku vybraná jediná varianta, ta je potom variantou optimální, anebo se zastaví po vyčerpání všech uvažovaných kritérií. Optimální varianty jsou pak ty, které zůstaly stejně ohodnoceny po zařazení posledního kritéria. Ordinální informace o kritériích dovolují, jak bylo uvedeno výše, aby kritéria f i ∈C byla podle relace ⊂G seřazena od nejdůležitějšího (nejvýše hodnoceného) k nejméně důležitému. Přitom je možné, že některá kritéria jsou ohodnocena stejně, proto seřazení podle relace ⊂G nemusí být jednoznačné. To je určitý nedostatek lexikografické metody, která může tak poskytovat při různých seřazeních stejně ohodnocených kritérií různé výsledné optimální varianty. To je jedním z důvodů k používání jiných metod, nejčastěji metod skalarizace (někdy též kardinalizace) ordinální informace o kritériích.
2.4
Metody skalarizace ordinální informace o kritériích
Metody skalarizace patří k velmi často používaným metodám a představují různé přístupy, pomocí nichž se z ordinální informace o kritériích stane informace kardinální, umožňující nejen seřazení kritérií podle významnosti, ale i stanovení relativních významností jednotlivých kritérií podle
2Metody modelování preferencí mezi kritérii a variantami
Strana 19
vah.
Vstupem pro metodu skalarizace ordinální informace o kritériích jsou seřazená kritéria f i podle relace ⊆G, nebo-li podle relace uspořádání ≥G aplikované na ohodnocení G f i ∈S. Výstupem metody skalarizace jsou váhy vi jednotlivých kritérií f i ∈[0,1], pro něž platí ∑ v i=1. Získané váhy umožňují použití metod s kardinální informací o kritériích. Mezi metody skalarizace se zařazují metody párového porovnání, z nichž metoda vlastního vektoru známá jako Saatyho metoda je jedním ze základních stavebních kamenů metod APH. 2.4.1
Metoda pořadí a bodovací metoda
Metoda pořadí je všeobecně známý postup, kterým se nejprve podle relace ⊂G kritéria f i, i=1,2 , , m , seřadí od nejhoršího k nejlepšímu. Nejhoršímu kritériu, označme jej f ´1, se přiřadí ohodnocení w1=1, tedy pořadí daného kritéria. Druhému nejhoršímu kritériu, označíme jej f ´2, se přiřadí ohodnocení – pořadí w 2=2, atd., až nejlepšímu kritériu, označíme jej f ´m , kterému se přiřadí ohodnocení wm =m. V případě stejně hodnocených kritérií se všem stejně ohodnoceným kritériím přiřadí ohodnocení, které je aritmetickým průměrem příslušných pořadí. Součet nových ohodnocení ´ dává s=∑ wi=mm1/2. Váhu vi kritéria f i pak definujeme takto: vi =w i / s.
Snadno se lze přesvědčit, že pro váhy vi platí podmínka ∑ v i=1. Konstrukce vah pomocí vi =w i / s odpovídá intuici v tom smyslu, že důležitější kritéria mají větší váhu. Na druhou stranu metoda pořadí nepostihuje eventuální rozdílnost v intenzitě důležitosti jednotlivých kritérií. To je v definici vah vi =w i / s vyjádřeno skutečností lineárního růstu vah spolu se vzrůstající významností kritérií. Tento přístup připomíná techniku stejné důležitosti popsanou již dříve. Nemáte-li informace o intenzitě přírůstku významností kritérií, aplikujte vždy stejný přírůstek. V případě, že jste schopni kromě pořadí kritérií přinést i informaci o intenzitách významností jednotlivých kritérií, např. pomocí bodů, může výše zmíněnou vlastnost lineárně rostoucích vah zreálnit následující bodovací metoda. Bodovací metoda se v zásadě liší od metody pořadí v tom, že se seřazeným kritériím f ´i přiřazují bodová ohodnocení wi na předem zvolené stupnici – škále (např. intervalu 0 až 10). Bodová hodnocení musí splňovat podmínku 0w 1≤w 2≤≤w m. Součet všech ohodnocení označíme s ´ =∑ wi. Váhu vi kritéria f ´i potom definujeme takto: vi =w i / s´. Bodovací metoda má na rozdíl od metody pořadí určitou nevýhodu v tom, že do ní vnášíme novou informaci kardinálního typu. Tento fakt ji zařazuje spíše mezi metody s kardinální informací o kritériích. 2.4.2
Metody párového porovnání
Metody párového porovnání jsou založeny na principu využití ordinální informace uložené v párovém porovnání dvojic kritérií ke stanovení vah kritérií. Ve své klasické podobě využívají metody párového porovnání, např. metoda Fullerova trojúhelníku, pouze ordinální informaci ve tvaru, ve ´ ´ kterém pro každou dvojici kritérií f , f ´ ∈C platí f ⊆G f anebo f ⊆G f . Počet všech párových porovnání je roven číslu:
m−1 N = m =m . 2 2
Další metody párového porovnání, např. Saatyho metoda, již vnášejí do procesu dodatečnou informaci kardinální povahy, kterou vyjadřují stupeň intenzity platnosti relace ⊆G mezi porovnávanými kritérii na předem zvolené škále (např. Saatyho metoda používá škálu 1 až 9). Tím se tyto metody spíše zařazují k metodám s kardinální informací o kritériích. 2.4.3
Metoda Fullerova trojúhelníku Fullerův trojúhelník je schéma trojúhelníkového tvaru, viz níže, ve kterém jsou pod sebou ve
Strana 20
2Metody modelování preferencí mezi kritérii a variantami
dvou řádcích uvedeny postupně dvojice porovnávaných kritérií pro jednoduchost očíslovaných 1 až m. Nevyžaduje se, aby kritéria byla uspořádána podle významnosti. V prvním ze dvojice řádků je uvedeno opakovaně vždy stejné číslo kritéria, ve druhém jsou uvedena postupně všechna kritéria s vyššími čísly označení. Tímto způsobem jsou ve schématu zachyceny všechny porovnávané dvojice kritérií. V každé porovnávané dvojici f , f ´ se označí (např. rámečkem) významnější kritérium, např. f. Pro toto kritérium platí f ⊆G f ´. Konstrukce výsledných vah probíhá následovně: Pro každé kritérium f i ∈C se stanoví počet preferencí tohoto kritéria nad ostatními kritérií (tj. počet označených „ i “), tento počet označíme ni. Celkový počet porovnávaných dvojic (tedy celkový počet orámovaných kritérií) je roven N =mm−1/2. Výsledná váha vi kritéria f i je definována vztahem: vi =n i / N. Výše uvedená konstrukce vah je v souladu s intuicí: Čím je kritérium f i významnější, tím je preferováno před větším počtem jiných kritérií, a tím větší má výslednou významnost vyjádřenou vahou vi, což je plně ve shodě se vztahem vi =n i / N. Fullerův trojúhelník můžeme nahradit ekvivalentním schématem ve formě tzv. matice párových porovnání. Matice párových porovnání S je čtvercová matice typu m×m. 1
1
1
1
1
1
…
1
2
3
4
5
6
7
…
m
…
…
…
…
…
…
…
…
2
2
2
2
2
…
2
3
4
5
6
7
…
m
…
…
…
…
…
…
…
3
3
3
3
…
3
4
5
6
7
…
m
…
…
…
…
…
… m–1 m
Obr. 1 Fullerův trojúhelník Prvek s ij v i -tém řádku a j -tém sloupci je definován následujícím způsobem:
s ij =1, právě když platí f i ⊆G f j , s ij =0, jinak. Předpokládáme, že relace ⊆G je reflexivní, proto pro prvky na hlavní diagonále matice S platí
s ii =1. Fullerův trojúhelník pak odpovídá horní trojúhelníkové submatici v matici párových porovnání
nad hlavní diagonálou. Zavedeme následující označení: Symbolem S i ° označíme součet prvků i -tého řádku matice
2Metody modelování preferencí mezi kritérii a variantami
Strana 21
S, symbolem S ° j označíme součet prvků j -tého sloupce matice S. Platí tedy : S i ° =∑ s ij , S ° j =∑ s ij .
Podle konstrukce Fullerova trojúhelníku je zřejmé, že počet preferencí i -tého kritéria, který jsme označili symbolem ni splňuje následující vztah :
ni=S i ° −1, neboť mezi kritéria, která jsou preferována i -tým kritériem se samotné i -té kritérium nezahrnuje. 2.4.4
Saatyho metoda párového porovnání
Základním východiskem pro konstrukci vah uvažovaných kritérií f i ∈C je matice párových porovnání S. Prvky s ij jsou však odlišné od prvků matice párových porovnání v metodě Fullerova trojúhelníku. Podobně jako tam se prvky stanoví na základě ordinální informace z relace ⊆G, avšak dodatečná informace umožňuje zohlednit intenzitu významností v příslušném porovnávaném páru kritérií, např. f i A f j. Pokud platí f i ⊆G f j, pak prvek s ij vyjadřuje poměr významností kritéria f i k významnosti kritéria f j, tj. poměr vah vi a v j :
s ij =
vi ; i , j=1,2 , , m. vj
(2.1)
Protože však váhy vi nejsou předem známy, (naším cílem je právě váhy stanovit), využívá se k jejich stanovení dodatečná informace o číslech s ij, které jsou prvky zvolené škály 1 až 9, tj.: s ij ={1,2 ,3 ,4,5 ,6 ,7,8 ,9}, (2.2) jestliže f i ⊆G f j. V opačném případě, tj. Když f j ⊆G f i, platí : s ij =1/ s ji . (2.3) Jestliže kritérium f j je s ji -krát významnější než kritérium f i, potom významnost kritéria f i 1/ s tvoří ji -tou část významnosti kritéria f j . Jestliže pro prvky s ij platí (2.3), potom říkáme, že matice S je reciproká. Motivaci pro výběr škály (2.2) i podrobné zdůvodnění bude uvedeno později, v kapitole zabývající se Saatyho metodou konstrukce vah uvažovaných kritérií a spočívá ve výpočtu vlastního vektoru odpovídajícího maximálnímu vlastnímu číslu matice párových porovnání S. Řešením soustavy m rovnic o m neznámých x = x 1 , x 2 , , x m vyjádřené ve vektorovém tvaru : S − max I x =0, (2.4) nebo jinak vyjádřeno : Sx=max x , (2.4´) kde max je maximální vlastní číslo matice S a I je jednotková matice, získáme vlastní vektor, z něhož pak sestavíme hledané váhy takto :
vi =
xi , i=1,2 , , m. ∥x∥
(2.5)
∑
1/ 2
m
Symbol ∥x∥ označuje velikost vektoru x , tj. ∥x∥=
x
x=1
2 i
.
2.4.4.1 Metoda nejmenších čtverců stanovení vah Metoda nejmenších čtverců (MNČ) je obecně známá metoda používaná všude tam, kde chceme empirická data zatížená chybami aproximovat nějakým zvoleným modelem systému závislého na neznámých parametrech. MNČ umožňuje optimální nastavení těchto parametrů. V úloze stanovení vah kritérií úlohy vícekriteriálního rozhodování jsou těmito neznámými parametry právě hledané váhy a empirická data představují získané odhady podílů významností jednotlivých kritérií. Metoda nejmenších čtverců stanovení vah má podobná východiska a předpoklady, jako předchozí Saatyho metoda z předchozí kapitoly. V souladu s obecným postupem MNČ se hledají takové váhy vi , které minimalizují součet kvadrátů odchylek prvků matice párových porovnání od
Strana 22
2Metody modelování preferencí mezi kritérii a variantami
příslušných podílů vah jednotlivých kritérií. Neznámé váhy vi se získají řešením úlohy nelineárního programování :
∑∑ i
za podmínky :
j
2
vi s ij − j min ; v
(2.6)
m
∑ v j=1, v i ≥0,i=1,2 , , m.
(2.7)
j =1
Numerické řešení úlohy (2.6), (2.7) je poměrně náročné, avšak dnes již existuje celá řada SW produktů, které umožňují řešit podobné úlohy i na počítačích PC. Pro úlohy malých rozměrů (např. m≤20) lze úlohu řešit pomocí Řešitele v programu Excel, pro větší úlohy lze použít např. programů LINGO, XA aj. 2.4.4.2 Metoda logaritmických NČ (Metoda geometrického průmeru) Metoda logaritmických nejmenších čtverců (Metoda geometrického průměru) založena na stejných předpokladech, jako metoda nejmenších čtverců. Na rozdíl od MNČ však neměří přímo odchylky odhadnutých dat od teoretických podílů vah vi / v j, avšak měří logaritmy odchylek těchto dvou veličin. Tato změna přináší 2 výhody : ● logaritmickou transformací se rovnoměrně rozdělí odchylky podílových hodnot na obě strany od 1, ● optimální řešení úlohy nelineárního programování je možné vyjádřit v explicitním tvaru a není zapotřebí využívat speciální SW.
V souladu s obecným postupem MNČ se hledají takové váhy vi , které minimalizují součet kvadrátů logaritmů odchylek prvků matice párových porovnání od příslušných logaritmů podílů vah jednotlivých kritérií. Neznámé váhy vi se získají řešením úlohy nelineárního programování :
F v 1 , v 2 , , v m =∑ ∑ ln s ij −ln v i−ln v j min 2
i
j
(2.8)
za podmínky : k
∑ v j=1, v i ≥0,i=1,2 , , m.
(2.9)
j =1
Optimální řešení úlohy lze nalézt v explicitním tvaru: Váha i -tého kritéria se vypočte jako geometrický průměr odhadů s ij poměrů významností všech kritérií k i -tému kritériu, normovaný součtem geometrických průměrů stejně vypočtených pro všechna kritéria. Podle tohoto výsledku získala metoda své jméno. Optimální řešení úlohy (2.8), (2.9), tj. Váhy vi , které minimalizují účelovou funkci F z (2.8) mají následující tvar :
∏ ∑ ∏
1 /m
m
vi =
j =1
sij
m
m
i=1
j=1
1/ m
, i=1,2 , , m.
(2.10)
s ij
Důkaz plyne z následující úvahy: Protože s ij 0 pro všechna i , j=1,2 , , m , je také vi 0 pro i=1,2 , , m . Snadno lze ukázat, že funkce F v 1 , v 2 , , v m je ryze konvexní pro vi 0, i=1,2 , , m, a že pro vi definované vztahem (2.10) se všechny parciální derivace anulují.
2Metody modelování preferencí mezi kritérii a variantami
2.5
Strana 23
Metody s kardinální informací o kritériích
Vzhledem k tomu, že optimální varianta je zároveň nedominovaná, potom jestliže ji zaměníme za jinou nedominovanou variantou, pak tato nová varianta bude mít podle některých kritérií ohodnocení lepší, podle jiných kritérií bude mít ohodnocení horší, než původní varianta. Proto takovou variantu budeme nazývat kompromisní varianta. Postup při výběru kompromisní varianty pak závisí na tom, jakou další informaci máme o charakteru, resp. důležitosti jednotlivých kritérií. Intuitivně se zdá oprávněné, aby optimální varianta nabývala co možná nejlepších ohodnocení podle nejdůležitějších kritérií. 2.5.1
Úvod do metod s kardinální informací o kritériích
Zopakujme fakt, že na množinu kritérií C={ f 1 , f 2 , , f m} pohlížíme, jako na množinu variant v (jiném) rozhodovacím problému s jediným kritériem G, kterým je hlavní cíl našeho rozhodovacího problému – výběr optimální varianty z množiny variant A. Přitom G, podobně jako dříve, ztotožňujeme se zobrazením množiny C do škály S, tj. G : C S, jež je však nyní kardinální škálou. V souladu s předchozím výkladem to znamená, že ohodnocení G f i každého kritéria je reálné číslo, takže kritéria lze seřadit nejen podle velikosti jejich ohodnocení, tj. významnosti, přičemž indukovaná relace ⊂G je kvaziuspořádáním, ale známe i vzájemný poměr významnosti kritérií f i. Číselné ohodnocení jednotlivých kritérií můžeme normalizací, tj. vydělením každého ohodnocení součtem všech ohodnocení, získat váhy vi jednotlivých kritérií f i , pro i=1,2 , , m . Máme-li k dispozici váhy vi které interpretujeme jako relativní významnosti kritérií, potom další postup vedoucí k výběru optimální varianty z množiny variant A, závisí na typu jednotlivých kritérií, konkrétně na tom, zda jsou kritéria ordinálního nebo kardinálního typu. Vhodnými transformacemi je pak převedeme na kritéria se stejnou škálou hodnot, obvykle to je interval [0,1], a celkové ohodnocení varianty získáme jako vážený součet ohodnocení podle jednotlivých kritérií. Podívejme se na tento problém podrobněji matematicky. 2.5.2
Standardizace a normalizace
Nechť f i ∈C je kardinální kritérium, f i : A S i, přitom S i ⊆R je kardinální škála. Pro transformaci škály S i na škálu S =[0,1], totožnou pro všechna kritéria, používáme obvykle dvou postupů. Prvnímu budeme v této práci říkat standardizace, druhému normalizace. Standardizace : Pro každé i=1,2 , , m označíme : f min (2.11) 1 =min { f i a j ∣ j=1,2 , , n},
f max 1 =max{ f i a j ∣ j=1,2 , , n}.
(2.12) Dále budeme předpokládat, že všechna kritéria nabývají nezáporných hodnot, tj. f i a j ≥0 min pro všechna i=1,2 , , m , j=1,2 , , n, a že platí f max 1 f1 . Pro maximalizační kritérium, kdy větší hodnota kritéria je považována za „lepší“, definujeme transformaci i : S i [0,1] ,i=1,2 , , m, následovně : min
x− f i i x = max , x ∈S i . min fi −fi
(2.13)
Pro minimalizační kritérium, kdy menší hodnota kritéria je považována za „lepší“, definujeme transformaci i : S i [0,1] :
i x =
f max −x i max
min
fi −fi
, x∈ S i .
(2.14)
Pomocí zobrazení i definujeme nyní namísto kritéria f i nové kritérium : F i a = f i a , a∈A. (2.15) Kritérium (2.5) má tu vlastnost, že pro nejhůře hodnocenou variantu nabývá hodnoty 0 a pro
Strana 24
2Metody modelování preferencí mezi kritérii a variantami
nejlépe hodnocenou variantu nabývá hodnoty 1, pro všechna kritéria i =1,2 , , m. Normalizace : Budeme dále předpokládat, že všechna kritéria nabývají kladných hodnot, to znamená, že f i a j 0 pro všechna i=1,2 , , m , j=1,2 , , n. (Pokud by tomu tak pro některé kritérium nebylo, připočítali bychom ke všem hodnocením tohoto kritéria dostatečně velkou kladnou hodnotu, čímž bychom obdrželi kritérium s požadovanou vlastností.) Pro maximalizační kritérium, kdy větší hodnota kritéria je považována za „lepší“, definujme transformaci i : S i R , i=1,2 , , m , následovně: i x= x , x ∈S i . („identická transformace“) Pro minimalizační kritérium, kdy menší hodnota kritéria je považována za „lepší“, definujeme transformaci : S i R :
1 i x= , x ∈S i . („inverzní transformace“) x Pro každé i=1,2 , , m definujeme namísto původního kritéria f i nové kritérium G i : i f i a G i a= n , a ∈A
∑ i f i a j
,
(2.16)
j=1
kde i je buď identická nebo inverzní transformace, podle toho, zda f i je maximalizační nebo minimalizační kritérium. Kritéria (2.16) podobně jako kritéria (2.15) transformují hodnoty původních kritérií do jednotkové škály [0,1]. Pro G i platí základní vztah normalizace : n
∑ G i a j =1.
(2.17)
j =1
Základní odlišnosti obou přístupů : ●
Standardizací se u daného kritéria mění původní poměr ohodnocení dvou variant, jestliže např. původní směr ohodnocení variant a ´ , a´ ´ ∈ A je f i a´ / f i a ´ ´ , pak nový poměr po
´´ min min transformaci je f i a ´ − f min i / f i a − f i . V případě, že f i =0 , jsou oba poměry stejné. Při normalizaci zůstává poměr ohodnocených variant stejný (v případě maximalizačního kritéria), nebo je převrácený (v případě minimalizačního kritéria). ● Standardizace způsobí, že nové kritérium pro nejhůře ohodnocenou variantu nabývá hodnoty 0, pro nejlépe hodnocenou variantu nabývá hodnoty 1. Tuto vlastnost normalizace nemá, naproti tomu normalizované kritérium má vlastnost (2.17), kterou zase nemá standardizované kritérium. Jsou-li kritéria f i standardizována, tj. máme k dispozici nová kritéria F i, nebo jsou normalizována, tj. máme k dispozici nová kritéria Gi , a dále známe váhy kritérií vi, potom můžeme provést výsledné ohodnocení variant a na jeho základě vybrat optimální variantu, která dosáhla nejlepšího ohodnocení. Pro standardizovaná kritéria F i stanovíme výsledné ohodnocení jako vážený součet dílčích ohodnocení podle jednotlivých kritérií :
m
H s a j =∑ v i F i a j .
(2.18)
i=1
Pro normalizovaná kritéria G i stanovíme obdobně výsledné ohodnocení jako vážený součet dílčích ohodnocení podle jednotlivých kritérií : m
H n a j=∑ v i G i a j . i =1
(2.19)
Přirozeně je na místě otázka, kdy použít pro kardinální kritéria standardizaci a ve kterých případech normalizaci. Odpověď není jednoznačná a závisí do značné míry na věcné povaze rozhodovacího problému.
2Metody modelování preferencí mezi kritérii a variantami
Strana 25
Standardizace má blízko k teorii užitku, standardizované kritérium je vlastně lineární funkcí užitku a vzorec (2.19) představuje aditivní tvar vícekriteriální funkce užitku. Přístup normalizace s využitím (2.18) a (2.19) je použit v metodě analytického hierarchického procesu (AHP). 2.5.3
Metody založené na funkci užitku
Funkce užitku pro i -té kritérium: f i : A S i je neklesající funkce u i : S i [0,∞ , kde S i ⊆R , i=1,2 , , m . Ve vícekriteriálním rozhodování se v tomto případě hovoří o i -té dílčí funkci užitku.
Varianta a ∈ A má podle i -tého kritéria ohodnocení h= f i a a toto ohodnocení přináší užitek u i h=ui f i a. Tento užitek roste, nebo alespoň neklesá, s rostoucím ohodnocením h. Speciálním případem i -té dílčí funkce užitku je funkce : u i :[ D i , H i ] [0,1] , (2.20) kde D i je nejméně preferovaná hodnota z S i vzhledem k f i, taková, že platí u i D i =0, H i je nejvíce preferovaná hodnota vzhledem k f i, přičemž platí u i H i =1. Konkrétním příkladem uvedené funkce užitku je zobrazení (2.14) . V ekonomii více činitelů se setkáváme s agregovanou (vícekriteriální) funkcí užitku, která podle toho, zda lze celkový užitek skládat z dílčích užitků jednotlivých činitelů (kritérií), má aditivní tvar : U a =∑ i v i u i f i a , a ∈ A , (2.21)
kde vi jsou váhy, ∑i v i=1, v i≥0, nebo, pokud vzniká celkový užitek násobením dílčích užitků, má agregovaná funkce užitku multiplikativní tvar : U a =∏i ui f i a , a∈ A. (2.22) Je možné uvažovat i s jinými nelineárními tvary, které však z praktického hlediska mají jen omezený význam. Agregovaná funkce užitku indukuje na množině variant A relaci R, která je, jak známo, kvaziuspořádáním a kterou lze rozložit na relaci preference P a relaci indiference I , tj. R= P , I takto: Pro a , b∈ A je: A P b právě když U a U b , (2.23) A I b právě když U a =U b. (2.24) V podmínkách neurčitosti, resp. při neznalosti přesného tvaru funkce užitku U lze relace (2.23), (2.24) zeslabit. Pro zadané prahy citlivosti 0, 0 definujeme novou relaci R , = P , , I , takto : Pro a ,b∈ A je : a P , b právě když U a −U b , (2.25) a I , b právě když ∣U a −U b∣≤ . (2.26) V závislosti na velikosti citlivosti 0, 0 mohou být některé varianty a , b∈ A vzájemně neporovnatelné. Relace R , = P , , I , je pak relací částečného kvaziuspořádání. Tato relace definuje na množině variant A rozklad, na skupiny variant, kde jsou dvojice variant vzájemně − -indiferentní, dvojice variant patřící do různých skupin jsou − -preferovány a varianty mimo tyto skupiny jsou s jinými variantami neporovnatelné. Analýzou citlivosti prahů lze získat hlubší informaci o preferenční struktuře množiny variant. 2.5.4
Metody založené na párovém porovnání variant
Doposud jsme řešili případ kardinálních kritérií f i ∈C, nyní se obrátíme k případu, kdy jsou kritéria f i : A S i ordinální, S i jsou přitom ordinální škály s relacemi uspořádání ≤i. Navíc jsou k dispozici váhy vi vyjadřující relativní významnosti kritérií. V této situaci v souladu s předchozím výkladem to znamená, že pro dané kritérium f i lze ohodnocení variant f i a j ∈S i seřadit podle „velikosti“ a indukovaná relace ⊂i je kvaziuspořádáním. Varianty a j ∈ A můžeme podle relace ⊂i
Strana 26
2Metody modelování preferencí mezi kritérii a variantami
seřadit od nejméně důležité (nejníže hodnocené) k nejdůležitější, přitom některé varianty mohou být podle kritéria f i ohodnoceny stejně. Podobně jako pro kritéria využijeme nyní analogicky pro varianty metody skalarizace, s jejíž pomocí se z ordinální informace o variantách stane informace kardinální, umožňující nejen seřazení variant podle důležitosti, ale i stanovení relativních důležitostí jednotlivých variant vzhledem ke zvolenému kritériu, a to v podobě vah. Vstupem pro metodu skalarizace ordinální informace o variantách jsou seřazené varianty a j ∈ A podle relace uspořádání ⊂i. Výstupem metody skalarizace jsou váhy vij, které představují kardinální a normované hodnocení jednotlivých varian ta j ∈ A podle kritéria f i ∈C, neboť platí
∑i v ij =1.
Získané váhy umožňují použití metod s kardinální informací o kritériích, jimiž byly věnovány předchozí části. Principiálně lze použít všechny metody uvedené v těchto kapitolách, konkrétně metodu pořadí, bodovací metodu a metody párového porovnání, pouze s tím rozdílem, že namísto s kritérií se pracuje s variantami. Připomínáme, že mezi metody skalarizace se zařazují metody párového porovnání, z nichž metoda vlastního vektoru známá jako Saatyho metoda je jedním ze základních stavebních kamenů metod AHP. 2.5.5
Metody vzdálenosti
Předpokládáme, že všechna kritéria f i ∈C jsou kardinální, buď všechna standardizovaná nebo normalizovaná. Pro výsledné ohodnocení varianty a ∈ A existují dvě základní metody vzdálenosti : ● ●
metoda nejmenší vzdálenosti od ideální varianty, metoda největší vzdálenosti od bazální varianty.
Mějme varianty a , b∈ A, kardinální kritéria f i ∈C nechť jsou všechna maximalizační. Položme
a= F 1 a , F 2 a , , F m a ,b= F 1 b , F 2 b , , F m b , F f kde i jsou kritéria i, standardizovaná podle (2.14), tj. F i a =i f i a , a ∈A a i jsou definovány vztahem x− f min i i x = max , x∈S i . min fi −fi Potom a , b jsou vektory z R m. Pro každé dva vektory x , y ∈ Rm definujme jejich vzdálenost
pomocí funkce vzdálenosti (metriky) : Funkci d : R m×Rm R nazýváme funkcí vzdálenosti v R m (metriky v R m), splňuje-li následující 3 podmínky : („nezápornost“), d x , y ≥0 pro všechny x , y ∈ Rm , m („jednoznačnost“), d x , x =0 pro všechny x ∈R , („trojúhelníková nerovnost“). d x , y d y , z ≥d x , z pro všechny x , y , z ∈Rm , Speciálně nás bude zajímat funkce vzdálenosti, která má následující tvar : p 1/p (2.27) d x , y = ∑ ∣x i− y i∣ , kde vektory, jsou ve tvaru : x = x 1 , x 2 , , x m ∈R m , y= y1 , y 2 , , y m ∈ Rm a p0 . Pro některé hodnoty parametru p jsou funkce vzdálenosti (metriky, normy) (2.27) známy pod speciálními názvy : ●
Pro p=2 se funkce vzdálenosti nazývá Euklidovská metrika a má tvar : 1 /2
d x , y = ∑i x i− y i 2
●
.
(2.28)
Pro p 0 se funkce vzdálenosti nazývá Čebyševova metrika a má tvar :
2Metody modelování preferencí mezi kritérii a variantami
Strana 27
d x , y =maxi∣xi − y i∣.
(2.29) Pro p ∞ se funkce vzdálenosti nazývá Minkowského metrika a má tvar : d x , y =∑i ∣x i− y i∣. (2.30) (2.29) a (2.30) lze snadno dokázat výpočtem příslušných limit z výrazu (2.27), nejprve pro p 0 , potom pro p ∞. Euklidovská metrika je funkce vzdálenosti, které se v praxi používá nejvíce. Nyní, poté, co jsme zavedli potřebné pojmy, se opět vrátíme k metodám vzdálenosti vícekriteriálního rozhodování. Metoda nejmenší vzdálenosti od ideální varianty používá ke stanovení agregovaného ohodnocení varianty a ∈ A vzdálenost vektoru ohodnocení varianty a (podle standardizovaných kritérií) od vektoru ohodnocení ideální varianty podle standardizovaných kritérií, tj. D a=d a ,1 , (2.31) a= F 1 a , F 2 a , , F m a , kde d je funkce vzdálenosti (např. některá z norem (2.28) – (2.30)), přičemž F i a =i f i a a i jsou definovány vztahem : ●
min
i x =
x− f i
, i=1,2 , , m , x∈S i . (2.32) max min fi −fi Vektor l=1,1 ,,1∈R m je složen ze standardizovaných ohodnocení příslušných ideální variantě. Speciálně pro nejvíce využívanou funkci vzdálenosti (2.27) dostáváme : p 1/p
(2.33) D a= ∑i ∣F i a−1∣ . Ze vztahu (2.33) je zřejmé, že kdyby a byla ideální variantou, potom D a=0 . V opačném případě platí D a0 . Za optimální variantu položíme tu variantu a ∗ ∈ A, pro kterou platí : (2.34) D a ∗=min {Da ; a∈A}. Metoda největší vzdálenosti od bazální varianty používá ke stanovení agregovaného ohodnocení varianty a (podle standardizovaných kritérií) od vektoru ohodnocení bazální varianty podle standardizovaných kritérií, tj. D a=d a ,0 , (2.35) kde d je funkce vzdálenosti (např. některá z metrik (2.28) – (2.30)), a= F 1 a , F 2 a , , F m a , přičemž F i a =i f i a a i jsou definovány vztahem (2.32), vektor O=0,0 ,,0∈ Rm je složen ze standardizovaných ohodnocení příslušných bazální variantě. Speciálně pro nejvíce využívanou funkci vzdálenosti (2.33) dostáváme : p 1/ p
(2.36) D a=∑ i ∣F i a ∣ . Je zřejmé, že kdyby a byla bazální variantou, potom by platilo D a=0 . V opačném případě platí D a0 . Za optimální variantu položíme v tomto případě tu variantu a ∗ ∗ ∈ A, pro kterou platí: ∗∗ (2.37) D a =max {D a ; a ∈A}.
Namísto standardizovaných kritérií lze ve výše popsaných metodách použít též normalizovaná
kritéria.
Strana 29
3
VÍCEKRITERIÁLNÍ PROGRAMOVÁNÍ
Úlohy vícekriteriálního programování jsou obdobou úloh matematického programování s tím, že v nich není definováno pouze jedno kritérium (účelová funkce), ale takových kritérií je několik. Úlohu vícekriteriálního programování lze definovat následovně:
za podmínek
[ [
] ]
z 1= f 1 x 1 , x 2 , , x n z 2= f 1 x 1 , x 2 , , x n max ⋮ z n= f 1 x 1 , x 2 , , x n
(3.1)
g 1 x 1 , x 2 , , x n ≤0 g 2 x 1 , x 2 , , x n ≤0 , x i ≥0,i=1,2 , , n , ⋮ g n x 1 , x 2 , , x n ≤0
(3.2)
kde n je počet proměnných, m počet vlastních omezení a k počet kritérií. Za řešení výše uvedené úlohy lze považovat nalezení takového vektoru x= x 1 , x 2, ... , x n , který vyhovuje soustavě omezujících podmínek a současně dosahuje pokud možno co nejvyšších hodnot kritérií f 1 , f 2, ... , f k .
3.1
Metody s informací á posteriori
Cílem těchto metod je poskytnout uživateli představu o struktuře vhodných řešení bez předchozího vyjádření dodatečné preferenční informace uživatele. Výchozím hlediskem je zde princip nedominovanosti. Úplným řešením úlohy vícekriteriálního programování bez dodatečných informací je nalezení množiny všech nedominovaných řešení X N . Tato úloha je však pro řadu nelineárních modelů algoritmicky neřešitelná, proto se budeme zabývat úlohou lineárního vícekriteriálního programování C x max (3.3) při omezeních . Pro vyjádření množiny všech nedominovaných řešení jsou vyvinuty efektivní způsoby, které vycházejí ze skutečnosti, že množina X N je souvislá. Množina X N je sjednocením konvexních polyedrických množin, které je možno popsat nedominovanými krajními body. U většiny metod je možné rozlišit tři základní etapy : ● ● ●
Nalezení výchozího nedominovaného krajního bodu Určení množiny všech nedominovaných krajních bodů X KN Určení množiny všech nedominovaných řešení X N ve tvaru minimální reprezentace
Nalezení nedominovaného krajního bodu V této etapě je možné použít několika způsobů : 1) Vybereme jednu z kriteriálních funkcí úlohy vícekriteriálního programování a řešíme jednokriteriální úlohu lineárního programování (3.4) při omezeních x ∈ X . Jestliže existuje jediné optimální řešení úlohy, potom je nedominovaným krajním bodem pro úlohu LVP. Jinak optimalizujeme podle další kriteriální funkce s přidáním podmínky pro optimální hodnotu první kriteriální funkce atd.
Strana 30
3Vícekriteriální programování
2) Postup je založen na větě o nedominovanosti argmaxu sdruženého ukazatele. Určíme kladné váhy v0 kriteriálních funkcí a řešíme úlohu lineárního programování vCx max (3.5) při omezeních x ∈ X . Jestliže existuje optimální řešení úlohy, potom existuje i základní optimální řešení, které odpovídá krajnímu bodu pro úlohu LVP a získáváme tak nedominovaný krajní bod úlohy LVP. 3) Další postup je založen na řešení úlohy, která testuje nedominovanost řešení (3.6) z =eT y max T 0 0 při omezeních Cx− y=C x , Ax≤b , x≥0 , y≥0 , kde e =1,1 , ...,1 , x ∈ X je konkrétní přípustné řešení úlohy Cx max při omezeních x ∈ X ={x ∈Rn ; Ax≤b , x≥0} . Jestliže úloha má konečné optimální řešení x ° , y ° , potom x ° ∈ X N . Jestliže úloha nemá konečné optimální řešení, potom X N =0 . Určení množiny všech nedominovaných řešení V této etapě se vychází ze znalosti množiny X KN . Parametrický přístup umožňuje jednoduše určit množinu X N . Srovnáme vektorové parametry v z konečného seznamu vektorových parametrů V . Předpokládejme, že počet různých vektorových parametrů je s a označme je v i , i=1,2 , ... , s . Ty nedominované krajní body, které mají shodné vektorové parametry v generují nedominovanou stěnu K i , která je jejich konvexní kombinací. Některým nedominovaným krajním bodům je přiřazen více než jeden vektorový parametr a jsou součástí více než jedné nedominované stěny. Tímto způsobem získáme množinu nedominovaných variant X N ve tvaru minimální reprezentace.
[
3.2
1
1
1
v 1 ⇔ K 1 : x 1 , x 2 , , x v1 v 2 ⇔ K 2 : x 21 , x22 , , xv22 ⋮ s v s ⇔ K s : x 1 , x2s , , x vss
]
(3.7)
Interaktivní metody
Interaktivní metody nebo metody s průběžnou informací jsou založeny na interaktivním dialogu mezi uživatelem a analytikem (PC). V každé interakci se střídají dvě základní fáze: výpočetní fáze a rozhodovací fáze. Uživatel v dialogu s analytikem prochází množinu přípustných řešení a v každém kroku zlepšuje řešení podle svých preferencí. Analytik nabízí uživateli řešení, a pokud uživateli vyhovují dosažené hodnoty kriteriálních funkcí anebo nelze tyto hodnoty zvýšit podle jeho preferencí, potom je nalezené řešení považováno za kompromisní. Při řešení úlohy vícekriteriálního programování
[ ]
f 1 x f x F x = 2 max ⋮ f k x
(3.8)
n
při omezeních x ∈ X ={x ∈ R ; g i x ≤bi , i=1,2 ,... , m ; x j ≥0, j=1,2 , ... , n} je výpočetní fáze založena na řešení jedné ze dvou následujících úloh : 1) Maximalizace váženého součtu kriteriálních funkcí k
∑ vi f i x max i=1
(3.9)
3Vícekriteriální programování
Strana 31
při omezení x ∈ X . 2) Minimalizace vzdálenosti od ideální varianty k
p 1/ p
∑ wi z i−c x i
min
(3.10)
i=1
při omezení x ∈X =〚 x ; Ax≤b , x≥0〛 . Jestliže uživateli průběžné řešení vyhovuje, je toto řešení přijato za kompromisní řešení, v opačném případě sdělí analytikovi informace o preferencích vzhledem k dosaženému průběžnému řešení. Metody využívající různých forem informací o preferencích se dělí na dvě skupiny : a) Metody s explicitně vyjádřenou hodnotou záměny Tyto metody vyžadují od uživatele, aby určil míry substituce mezi jednotlivými kriteriálními funkcemi. Míra substituce sij mezi i -tou a j -tou kriteriální funkcí udává, jaké zhoršení i -té kriteriální funkce pro zadavatele kompenzuje zlepšení j -té kriteriální funkce o jednotku. Nejznamějšími představiteli této skupiny jsou Geoffrionova metoda a Ziontsova-Walleniusova metoda. b) Metody s implicitně vyjádřenou hodnotou záměny Tyto metody vyžadují od uživatele, aby posoudil dosažené úrovně jednotlivých kriteriálních funkcí a určil, které z nich mají akceptovatelné hodnoty a v jakých přípustných mezích se mohou hodnoty jednotlivých kriteriálních funkcí pohybovat. Nejznámějšími představiteli této skupiny jsou metoda STEM a Steuerova metoda. Mezi základní požadavky na interaktivní metody patří konvergence a univerzálnost. Při logicky konzistentním chování uživatele by měla metoda v konečném počtu iterací nalézt kompromisní řešení nebo zjistit, že nelze všechny požadavky uspokojit. Požadavek univerzálnosti vyžaduje, aby ke každému nedominovanému řešení existovala posloupnost odpovědí uživatele, která vede k tomuto nedominovanému řešení. Mezi výhody interaktivních metod patří to, že nepožadují preferenční informaci předem pro celý problém, ale je nutná pouze lokální preferenční informace. Zadavatel prochází procesem učení a poznává chování systému. Protože zadavatel je součástí procesu řešení, tak nalezené řešení má větší naději na implementaci. Mezi nevýhody interaktivních metod patří to, že řešení je závislé na přesnosti lokální informace o preferencích uživatele a metody nejsou imunní vůči subjektivnímu hodnocení uživatele. Problémem u interaktivních metod je, jak se vyrovnávají s nekonzistencí odpovědí uživatele a netranzitivností jeho preferencí. 3.2.1
Metoda GDF Metoda vychází z existence funkce užitku
u z =u f 1 x , f 2 x , , f k x ,
o které předpokládáme, že je diferencovatelná v každém bodě kriteriální množiny z ∈ Z . Dalším předpokladem je, že množina variant X je konvexní a funkce u f 1 x , f 2 x ,... , f k x vzhledem k proměnným x je funkcí konkávní. Úloha vícekriteriálního programování potom přechází v konvexní úlohu matematického programování u z =u f 1 x , f 2 x , ... , f k x max (3.11) při omezení x ∈ X . Funkce u však není explicitně známa, ale rozhodovatel může poskytnout lokální informace o směru gradientu funkce u v jednotlivých bodech kriteriální množiny z ∈Z . Směr gradientu je dán vzájemnými poměry parciálních derivací funkce u podle proměnných z i ,i=1,2 ,... , k :
sij =
∂u ∂u / , i , j=1,2 , , k. ∂ zi ∂ z j
(3.12)
Strana 32
3Vícekriteriální programování
Metoda je založena na interaktivní modifikaci Frankova-Wolfova algoritmu, což je gradientní metoda s dlouhým krokem. Řešení probíhá v iteracích q . Krok 1) Stanoví se výchozí řešení x ∈X a položí q=1 . u
Krok 2) Určí se směr gradientu funkce u , ∇ x =
∂u ∂u , , . Uživatel vyjádří hodnoty ∂ x1 ∂ xn
∂u ∂u / , i , j=1,2 , ... , k , v bode z q . Na základě hodnot sij analytik vypočte podle ∂ zi ∂ z j k ∂fj ∂u ∂u ∂ f j =∑ , i=1,2 , , n. Hodnoty pravidla o derivaci složené funkce hodnoty c i= ∂ xi x i i=1 ∂ z j ∂ x i ∂u jsou známy a hodnoty se určí z dodaných hodnot sij a na kladnou multiplikativní konstantu. ∂zj sij =
n
která neovlivní směr gradientu funkce u , ani řešení úlohy
∑ ci x i max
při omezení x ∈X .
i=1
Řešení úlohy označíme . x q Krok 3) Určí se velikost kroku. Analytik nabídne uživateli k výběru lineární kombinaci prvního x q a druhého . x q průběžného řešení x q t= x qt . x q −x q pro t∈〈 0,1〉 spolu s hodnotami kriteriálních funkcí z q t= z x q t . x q− x q pro t ∈〈 0,1〉 zadanou buď ve formě tabulky nebo ve formě grafu, kde je vyznačena závislost řešení na parametru t. Uživatel vybere hodnotu t 0 , pro níž mu nejlépe vyhovují hodnoty kriteriálních funkcí z t 0 . Analytik vezme zvolenou kombinaci za první průběžné řešení pro další iteraci q1 : x q 1=x q t 0 . x q− x q . Položí se q=q1 a přejde k druhému kroku algoritmu. Výpočet končí, jestliže x q 1=x q . Hlavní nevýhodou metody je požadavek, aby zadavatel přímo numericky specifikoval záměny hodnot kriteriálních funkcí. 3.2.2
Ziontsova – Walleniusova metoda
Metoda vychází z implicitní funkce užitku u , o které se předpokládá, že je lineární nebo obecněji konkávní funkce v proměnných x . Dále se předpokládá, že rozhodovací množina X je konexní a kriteriální funkce jsou konkávní. Omezující podmínky i kriteriální funkce se linearizují. Uživatel nemusí přímo stanovit míry substituce, ale analytik předkládá uživateli určité hodnoty měr substituce k posouzení, zda jsou pro něj výhodné. k
q Krok 1) Položíme číslo iterace q=1 a vybereme libovolné váhy v i q0 , i=1,2 , ... , k , ∑ vi =1 . i=1
q Krok 2) Určíme pomocí vah v i funkci užitku a hledáme optimální řešení úlohy
k
∑ vi q f i x max
(3.13)
i=1
q při omezení x ∈ X . Určíme množinu nezákladních proměnných J N .
Krok 3) Analytik určí úbytky hodnot
z ij jednotlivých kriteriálních funkcí f i x po zařazení
q nezákladní proměnné x j , j ∈J N , na jednotku hodnoty této proměnné.
j
zi =
f i x q − f i * x , , kde xj
*
x
je řešení, které dostaneme z řešení x q po zařazení
3Vícekriteriální programování
Strana 33
nezákladní proměnné x j . Na základě znalosti z ij můžeme z nezákladních proměnných vyčlenit tzv. efektivní proměnné, to jsou takové, jejichž zařazení do báze vede k zápornému úbytku, tj. k přírůstku hodnoty funkce užitku. Jestliže pro nějakou nezákladní proměnnou x j jsou všechny úbytky kriteriálních funkcí z ij kladné, potom proměnná x j není efektivní. V ostatních případech řešíme pro určitou q proměnnou x r , r ∈ J N , úlohu:
k
∑ z ir v i min , i=1
k
při omezeních
∑ z ij v i≥0,
q
j ∈J N , j≠r ,
i=1 k
∑ vi =1, v i≥0,
i=1,2 , , k.
i=1
Jestliže minimum hodnoty kriteriální funkce úlohy je záporná hodnota, potom proměnná x r je efektivní, v opačném případě efektivní není. Množinu indexů efektivních proměnných značíme q E . j
q
Krok 4) Analytik předloží uživateli změny hodnot z i , j ∈E , kriteriálních funkcí f i x , i=1,2 , ... , k , po zařazení jednotlivých efektivních proměnných. Podle zadavatele se rozdělí množina efektivních proměnných na akceptovatelné, množinu indexů těchto proměnných potom q q q označíme E 1 , neakceptovatelné (množina indexů E 2 ) a indiferentní (množina indexů E 3 ). q
q
q
q
E =E 1 ∪E 2 ∪E 3
q Jestliže E 1 =∅ , dostáváme kompromisní řešení, jinak přejdem ke kroku 5.
Krok 5) Na základě odpovědí uživatele v předchozím kroku sestavíme omezení pro množinu přípustných vah pro další iteraci v procesu vytváření konečné funkce užitku : k
∑ z ir v i
= − , r ∈ E 1 ,
(3.14)
∑ z ir v i
= , r ∈E2q ,
(3.15)
∑ z ir v i
= 0, r ∈E 3 ,
i=1 k i=1 k i=1
q
q
(3.16)
kde je malé kladné číslo. q1 , i=1,2 , , k , Z množiny vah, které splňují tyto podmínky, vybereme nové váhy v 1 položíme a q = q1 vrátíme se ke kroku 2. Pro dosažení jednoznačnosti výběru vah se někdy k
vybírají váhy tak, aby platilo
∑ z ir v i 0
i=1
3.2.3
q
max , r 0 ∈E 2 .
Metoda STEM
Metoda STEM neboli metodá kroků spočívá ve střídání dvou základních kroků, výpočetního a rozhodovacího. Metoda je určena pro řešení úloh LVP a je založena na minimalizaci vzdálenosti od ideální varianty. Ve výpočetním kroku analytik vypočte průběžné řešení a předloží uživateli hodnoty kriteriálních funkcí. V rozhodovacím kroku uživatel posoudí dosažené hodnoty a předá analytikovi informaci, které hodnoty mu vyhovují, a hodnotu které kriteriální funkce je ochoten snížit a o kolik. Na počátku výpočtu analytik určí dílčí optima podle jednotlivých kriteriálních funkcí a sestaví matici Z hodnot z ij , což jsou hodnoty i -té kriteriální funkce při maximalizaci j -té kriteriální
Strana 34
3Vícekriteriální programování
* funkce. Na diagonále matice Z jsou tedy ideální hodnoty z i jednotlivých kriteriálních funkcí. q
Matice Z hodnot z ij slouží uživateli při posuzování dosažených hodnot z i , i=1,2 , , k , jednotlivých kriteriálních funkcí a určení hodnoty i 0 , která udává, o kolik je uživatel ochoten snížit hodnotu i 0 -té kriteriální funkce. Krok 1) Analytik řeší úlohu lineárního programování
max wi z *i − c i x min
(3.17)
i
při omezení x ∈ X . V první iteraci q=1 se za X úlohy lineárního vícekriteriálního programování q
1
bere množina všech přípustných řešení
X 1={x ∈R n ; Ax≤b , x≥0}.
Váhy odchylek w i se berou buď jednotkové nebo se jimi normalizují odchylky, potom se
wi =
z *i − min z ij ⋅ n , * zi 2 ∑ cij j =1
kde se hodnota volí tak, aby
(3.18)
k
∑ wi=1 . Optimálním řešením úlohy je vektor
x q s hodnotami
i=1
q i q kriteriálních funkcí z i =c x ,i=1,2 , , k.
Krok 2) Uživatel posoudí hodnoty kriteriálních funkcí z i q , i=1,2 , , k , které odpovídají průběžnému řešení x q . Jestliže uživateli vyhovují všechny dosažené hodnoty kriteriálních funkcí q z q kompromisním řešením. V opačném případě, kdy uživateli i , i=1,2 , , k , potom je vektor x nevyhovuje žádná s dosažených hodnot kriteriálních funkcí, výpočet končí s tím, že není již možné zlepšit současně všechny hodnoty kriteriálních funkcí, protože průběžné řešení x q je nedominované. Jestliže některé hodnoty kriteriálních funkcí vyhovují a některé nevyhovují, určí uživatel z vyhovujících hodnot tu hodnotu z i0q , kterou je ochoten snížit o hodnotu i 0 . Analytik potom formuluje
c
i 0
novou
množinu
přípustných
řešení
x q1={ x ; Ax≤b , x≥0, c i x≥z iq ,i=i 0 ,
q x≥ z i − i 0 }. Položíme w i =0, q=q1 a vratíme se ke kroku 1. 0
0
Výhodou metody STEM je nenáročnost programového zabezpečení, které dostaneme malými úpravami programu pro řešení úloh lineárního programování. 3.2.4
Steuerova metoda
Metoda je založena na redukci kriteriálního kužele. Cílem metody je určit nedominovaný krajní bod s nejvyšším užitkem pro uživatele. Krok 1) q=1 , určení výchozích váhových vektorů q
v 1 =1,0 , ,0 , q
v 2 =0,1 , ,0 , ⋮ q v k =0,0 ,,1. Krok 2) Určení dalších k 1 váhových vektorů (s indexy k 1 až 2k1 ) na základě prvních k váhových vektorů q -té iterace podle vzorců :
3Vícekriteriální programování q
q
q
Strana 35
q
v k 1=1/ k v 1 v 2 v k , q
q
q
q
v k2=1/k v k 1 v 2 v k , q q q q v k3=1/k v 1 v k1v k , ⋮ q q q q ¿ v 2k 1=1/ k v 1 v 2 v k1 .
(3.19)
Váhový vektor s indexem k 1 je průměr prvních k váhových vektorů, další váhové vektory se počítají analogicky s tím, že se vždy jeden z prvních k vektorů postupně nahrazuje vektorem s indexem k 1. Krok 3) Pro 2k1 získaných váhových vektorů řešíme maximalizace váženého součtu kriteriálních funkcí :
v i q Cx max , i=1,2 , , 2k1, x ∈X {x∈ R n ; Ax≤b , x≥0}.
2k1 jednokriteriálních úloh (3.20)
Krok 4) Uživatel vybere z výsledků 2k1 úloh to řešení, jehož kriteriální hodnoty mu nejlépe vyhovují. Předpokládejme, že je to řešení s indexem i 0 , s hodnotami proměnných x i a kriteriálními hodnotami z i . Pokud je uživatel spokojen s dosaženými hodnotami průběžného řešení nebo bylo dosaženo stanoveného počtu iterací, potom procedura končí nalezením kompromisního řešení, v opačném případě přejdeme ke kroku 5. 0
0
Krok 5) Jsou stanoveny nové váhové vektory pro další iteraci. jestliže pro vybrané řešení platilo i 0 ∈1,2 , , k 1 , potom se váhové vektory vypočtou podle vzorců :
v q1 =1/2v q1 v i q , 1 0
q1
q
q
=1/2v 2 v i , ⋮ q1 q q v k =1/2v k v i . řešení platilo i 0 ∈ k 2, k 3, , 2k1 , v2
0
0
Jestliže
pro
vybrané
při
označení
i 0= k1 j 0 , j 0 ∈1,2 , , k , potom se váhové vektory vypočtou podle vzorců : q1 q q v 1 =1/2v 1 p i , 0
q1 2
q 2
q i0
=1/2v p , ⋮ q1 q q v k =1/2v k p i , v
0
k
kde p i =1/k −1 ∑ v i . q 0
3.3
q
i=1
Kombinované metody
Kombinované metody kombinují postupy různých metod. Dělí se na tři základní skupiny metod. Tyto metody využívají kladných stránek z různých skupin zmíněných postupů. Obecný postup řešení je možno rozdělit do následujících etap : Generování reprezentantů množiny nedominovaných řešení Pro generování reprezentantů existuje několik postupů, např. postupná maximalizace jednotlivých dílčích kriteriálních funkcí, maximalizace váženého součtu kriteriálních funkcí. Tato
Strana 36
3Vícekriteriální programování
etapa není interaktivní a nevyžaduje spolupráci s uživatelem. Postupná maximalizace jednotlivých dílčích kriteriálních funkcí Získání k reprezentantů je postupné řešení k jednokriteriálních úloh matematického programování
z =c i x max , i=1,2 , , k za podmínky x ∈ X = {x ∈ Rn ; Ax≤b , x ≥0}. Jestliže optimální řešení této úlohy je jediné, potom jsme nalezli nedominované řešení úlohy
z =Cx max za podmínky x ∈X = {x ∈R ; Ax≤b , x ≥0}, v opačném případě máme zaručenou slabou nedominovanost řešení. Výsledné hodnoty kriteriálních funkcí sestavíme do matice Z = z ij , kde z ij je hodnota i -té kriteriální funkce při maximalizaci j -té kriteriální funkce, potom ideální hodnoty z ij . Tím kriteriálních funkcí z *i = z ii , i=1,2 , , k , bazalní hodnoty kriteriálních funkcí z * i=min j n
získá uživatel představu o dosažitelných hodnotách kriteriálních funkcí. Tento postup je použit např. u metody STEM. Minimalizace vzdálenosti od ideálních hodnot kriteriálních funkcí Pro měření vzdálenosti od ideálních hodnot se často používá Čebyševova metrika s vahami w i , potom se řeší úloha :
max i=1,2 , ,k
wi z *i −c i x min
za podmínky x ∈ X = {x ∈ Rn ; Ax≤b , x ≥0}. Úlohu je možné přepsat do tvaru úlohy lineárního programování
y min za podmínek y≥w i z −c x , i=1,2 , , k , x ∈ X = {x∈R n ; Ax≤b , x≥0 }. Změnami vah w i a řešením úlohy získame reprezentanty. Pokud řešení úlohy není jediné, * i
i
nemusí být nutně nedominované, je však zaručena slabá nedominovanost. Interaktivní stanovení preferencí uživatele Na základě znalostí reprezentantů množiny nedominovaných řešení a jim odpovídajících hodnot kriteriálních funkcí zadá uživatel informaci o preferencích na množině přípustných řešení, která umožní skalarizaci úlohy. V této etapě se mohou interaktivně určit např. váhy kriteriálních funkcí nebo váhy odchylek od jejich ideálních hodnot anebo se interaktivně určí funkce užitku. K vyjádření preferencí uživatele je možno použít postupy určené k vícekriteriálnímu hodnocení variant. Mezi nejčastější způsoby vyjádření preferencí uživatele patří odhady vah kriteriálních funkcí, případně vah odchylek od jejich hodnot a konstrukce funkce užitku. Na modelování preferencí pomocí vah je založena metoda AHP. Příklad použití metody AHP pro vícekriteriální programování : * Rozpětí hodnot kriteriálních funkcí je dáno hodnotou = z i −z * i ,i=1,2 , , k , pro váhy potom platí w i=v i /i . Od uživatele požadujeme odhad hodnot v i , pro jejichž odhad je možno použít metody párového srovnání. 1) Určení matice Z , ideální hodnoty z * , bazální hodnoty z a rozpětí hodnot 2) Předložení ideální hodnoty jednotlivých kriteriálních funkcí s 10%, 30%, 50%, 70%, 90% odchylkami rozpětí hodnot ve směru k bazálním hodnotám 3) Uživatel porovnává 10% odchylky i -té a j -té kriteriální funkce, jestliže jsou ekvivalentní, potom a ij =1 . Jestliže nejsou ekvivalentní, potom např. i -tá funkce je preferována. Jestliže 10% odchylka i -té funkce je ekvivalentní s 30% odchylkou j -té funkce, potom a ij =3 . Jestliže 10% odchylka i -té funkce je ekvivalentní s 50% odchylkou j -té funkce, potom a ij =5
3Vícekriteriální programování
Strana 37
atd. včetně využívání mezistupňů 2, 4, 6, 8. Tímto způsobem získáme matici párových srovnání A . 4) Použití některé z metod na odhad vah. Nalezení konečného kompromisního řešení Na základě preferenční informace vyjádřené uživatelem je zkonstruována jednokriteriální úloha matematického programování, jejíž optimální řešení je bráno jako konečné kompromisní řešení původní úlohy. Tato etapa není interaktivní a nevyžaduje spolupráci s uživatelem. Je zformulována tzv. kompromisní úloha s lineárními omezeními úlohy (odkaz na začátek) a s lineární případně nelineární kriteriální funkcí
f x opt f x ∈ X = {x ∈ R ; Ax≤b , x ≥0}. za podmínky n
Optimální řešení této kompromisní úlohy je považováno za hledané konečné kompromisní řešení úlohy vícekriteriálního programování. Při hledání kompromisního řešení je možno volit z několika principů vypočtu s odpovdajícím modelem preference uživatele. Můžeme použít např. principu minimalizace vzdálenosti od ideálních hodnot kriteriálních funkcí. Řešíme mírně pozměněnou úlohu lineárního programování k
y∑ i z i v *−c x min i
i=1
za
podmínek
y≥wi z *i −c i x , i=1,2 , , k , x ∈ X = {x∈R n ; Ax≤b , x≥0 },
kde
1 , 2 , , k jsou malá kladná čísla. Řešením úlohy dostaváme již nedominované řešení úlohy (odkaz na začátek), které nemusí být krajním bodem.
Strana 39
4
VÍCEKRITERIÁLNÍ VÝBĚR PROJEKTŮ
Uveďme zde příklad základní myšlenky heuristické metody, která je schopna provést objektivně pomocí osobního počítače vícekriteriální výběr řádově stovek projektů při desítkách kriteriálních funkcí, včetně nelineárních, a desítkách zdrojových omezení. Je možné ji použít pro objektivizaci jakéhokoliv výběrového řízení týkajícího se například státních zakázek nebo projektů výrobních inovací ve firmách nebo jakýchkoliv projektů navrhovaných a realizovaných jakýmikoliv institucemi. I když se metoda řadí mezi interaktivní metody, má oproti nim jednu výhodu, a sice není závislá na přesnosti lokální informace o preferencích uživatele.
4.1
Formulace problému
Je řešen následující problém: vyberme několik z s projektů do portfolia, nechť i je číslo projektu i=1,2 , , s . Projekty náleží do různých kategorií (tj. z hlediska typu projektu a typu klienta). Kategorie nemusí být vzájemně disjunktní (nemusí mít neprázdné průniky). Nechť S k je množina projektů spadajících do kategorie k ,k =1,2 , , s . Cílem řešení je nalézt pro všechna i hodnoty bivalentních proměnných i , pro které i=1 , jestliže daný projekt i je vybrán do portfolia a i=0 v opačném případě. Výběr by měl být proveden tak, že všechny požadavky řešení mohou být naplněny, což zahrnuje následující : ●
splnění zdrojových omezení : s
s−1
s
∑ aij i−∑ ∑ i=1
i =1 k=i1
s−2
a ijk i k ∑
s−1
s
∑ ∑
i=1 k=i1 l= k1
a ijkl i k l ≤b j ,
(4.1)
kde b j0 je totální dostupnost (disponibilní kapacita) zdroje j , j=1,2 , , m , a ij ≥0 je množství zdroje j požadovaného projektem i , a ijk ≥0 je množství zdroje j sdíleného projekty i a k , a ijkl je množství zdroje j sdíleného projekty i , k , l . Obecně platí, že a ij ≥aijk , a kj ≥a ijk , a ijk ≥a ijkl , a ijl ≥a ijkl , a kjl ≥a ijkl pro všechna i , k , l . V případě absence synergistického efektu ve sdílení zdroje platí a ijk =0, a ijkl =0 . ●
splnění omezení vyjadřujících hierarchické závislosti :
∑ m≥∣Ai∣i pro všechny i∈H ,
m ∈ Ai
(4.2)
kde H , H ⊂{1,2 , , s} je množina všech projektů, které ke svému průběhu potřebují implementaci jiných projektů, Ai , Ai ⊂{1,2 , , s} je množina všech projektů, které jsou potřebné pro implementaci takového závislého i-tého projektu. ∣Ai∣ je počet prvků v množině Ai . ●
splnění direktivních podmínek :
i=1 pro i∈ B , B⊂{1,2 , , s } , i=0 pro i∈ D , D⊂{1,2 , , s} , kde množiny B , D jsou nařízeny v důsledku vnitřních a vnějších omezení.
(4.3)
Strana 40
4Vícekriteriální výběr projektů
splnění omezení na vzájemnou výhradnost projektu : Pro nějaké i , j ,i , j∈{1,2 , , s} může být požadováno: jestliže i=1 , pak j =0 , a jestliže j =1 , pak i=0 (tj. v případě, kdy dva projekty reprezentují alternativní způsoby řešení téhož základního problému) ●
●
získání nejvyšších možných hodnot kriteriálních funkcí výnosu (zisku) : s
s−1
z j =∑ c ij i∑
s
∑
i=1 k =i1
i=1
s −2 s −1
c ijk i k ∑
s
∑ ∑
i=1 k =i 1 l =k 1
cijkl i k l , j=1,2 , , p ,
(4.4)
kde c ij ≥0 je j -tý zisk odvozený z implementace samotného projektu i , c ijk ≥0 je přídavný j -tý zisk odvozený ze současné implementace projektů i a k a c ijkl ≥0 je přídavný j -tý zisk odvozený ze současné implementace projektů i , k , l . Pozn. I. : Stejně tak je možné formulovat účelovou funkci vztaženou k nákladům, jejichž záporná hodnota je maximalizována tím, že se blíží k nule. Pozn. II. : Speciální případ, kdy c ijk =0, c ijkl =0 , odpovídá nepřítomnosti synergického efektu zisku. Za zjednodušených předpokladů beroucích v úvahu aditivnost zisku (Jain a kolektiv, 1991), riziko množiny vybraných projektů může být vyjádřeno prvním členem v rovnici (4.4), kde c ij je nyní riziko implementace projektu i . V tomto případě minimalizujeme celkové riziko portfolia vybraných
{∑ } s
projektů maximalizací −
i=1
●
c ij i .
získání nejmenší možné odchylky Stewartovy funkce :
k =
∑
i∈ S k s
i i
∑ i i
, k =1,2 , , q ,
(4.5)
i=1
od ideální hodnoty k (viz výše uvedená definice projektových kategorií), kde i jsou náklady vztažené k projektu i (nebo například celkový počet pracovníků užitých projektem i ). To znamená, že k ∈[0 ; 1] , k ∈[0 ; 1] . Předpokládejme, že pro alespoň jedno i platí, že i .
4.2
Úprava zadání
Zaveďme asymetrickou významnost odchylky k od k , označenou ∥ k − k∥ takovým způsobem, že jeho hodnota patří do intervalu [0 ; 1] a že pro k =1∧k ≠1∨ k =0∧k ≠0 platí, že ∥k −k ∥=1 a že pro k =k platí, že ∥ k −k ∥=0 . Pro tento účel definujeme
0
∥ k − k∥=
{
k =k ,
k −k (jinak) l k −k −k
(4.6)
4Vícekriteriální výběr projektů
Strana 41
{10
x≤0 x0. To znamená, že maximální možná odchylka k na každou z obou stran od k má stejnou
kde skoková jednotková funkce l x =
důležitost. Potom je možné znovu formulovat problém následujícím způsobem :
max z j , j=1,2 , , pq . Řešíme tento problém za omezení (4.1) – (4.3), kde kriteriální funkce z j , j=1,2 , , p , jsou dány v (4.4) se znaménky jednotlivých členů, případně změněných s ohledem na Poznámky I a II. Kriteriální funkce z pk , k =1,2 , , q , je nyní definována :
0
z pk =−∥ k− k∥=
4.3
{
k =k ,
k −k (jinak) l k −k −k
k =1,2 , , q
Implementace hierarchických závislostí do programového systému
Způsob implementace zdrojových omezení (4.2) do programového systému byl nalezen v matematickém grafu. Graf sestává z ohodnocených vrcholů a orientovaných hran. Vrchol reprezentuje projekt a hodnota vrcholu reprezentuje stav projektu. Jestliže projekt náleží do portfolia, potom tato hodnota se rovná 1 , v opačném případě je rovna 0 . Hrana reprezentuje hierarchickou závislost a směr hrany indikuje závislost či nezávislost projektů. Vyřešili jsme dva druhy problému během výpočtu: projekt je vyřazen z portfolia a projekt je zařazen do portfolia. V prvním případě jsme hledali všechny závislé projekty, jež musely být vyřazeny z portfolia kvůli závislosti projektů. V druhém případě jsme hledali všechny nezávislé projekty, které musejí být zařazeny do portfolia, protože jsme tam zařadili jejich závislý projekt. Řešení výše zmíněného problému potřebujeme hledat skrze matematický graf. Pro tento účel používáme algoritmus hledání do šířky. Algoritmus nám poskytuje flexibilní manipulaci s projekty.
4.4
Optimalizace a dialog
Podle Santhanama a Kyparisise [16] je řešen problém výběru projektu pomocí kriteriálních funkcí typu (4.4), zdrojových omezení (4.1), hierarchických omezení (4.2), pro 14 projektů s=14 . Systém na podporu rozhodování J. Klapky, P. Piňose [2] rozšiřuje schopnosti Santhanamova systému [7] s možnostmi řešení problémů s větším rozsahem vstupních dat. Využívá také bilančních podílových funkcí typu (4.5) a dialogu, který umožňuje řešit také špatně definované problémy za využití předběžné realisticky hodnocené požadované úrovně individuálních kriteriálních funkcí. S ohledem na tento dialog není nutné používat přesných metod optimalizace, ale je možné použít heuristickou metodu, která umožní rozšíření šíře vstupních dat řešeného problému. Pro každou kriteriální funkci z j stanovíme horní hranici I j (ve smyslu řešení odpovídajícího jednokriteriálního maximalizačního problému s kriteriální funkcí z j ) a analogicky spodní hranici N j jeho optimální hodnoty skrze jednokriteriální minimalizační problém. Je velmi jednoduché najít tyto hranice pro každou kriteriální funkci. Přitom uživatel určuje realisticky hodnocenou požadovanou úroveň (referenční úroveň) R j pro každé z j . Požadujeme N j ≤R j≤ I j (4.7) V případě, že uživatel není schopen stanovit R j , můžeme počáteční referenční úroveň nastavit následovně:
Strana 42
4Vícekriteriální výběr projektů
R j=
I j N j . 2
Problém je nyní transformován na minimalizování skalarizující funkce pq
= ∑
j =1
I j −z j I j−R j
h
(4.8)
pro některé h0 za podmínek (4.1) – (4.4), (4.6). Pro řešení tohoto minimalizačního problému je používána metoda efektivního gradientu [7], zobecněná Klapkou pro případ synergických efektů a hierarchických vzájemných závislostí projektů. Z kompromisu mezi citlivostí metody a zaokrouhlovacími chybami vyplývá ve většině praktických problémů doporučení volby h=4 . Ve smyslu řešení jsou určovány optimální hodnoty i ,i=1,2 , , s , které definují portfolio vybraných projektů. Hlavní myšlenka metody zobecněného efektivního gradientu je následující : Na začátku procesu řešení vybereme i=1 pro všechny i=1,2 , , s . Potom dostaneme s
s−1
u j=∑ a ij i−∑ i =1
s
s−2
∑
i=1 k=i1
aijk i k ∑
s−1
s
∑ ∑
i =1 k=i1 l =k1
a ijkl i k l , j=1,2 , , m ,
což je množství j -tého zdroje požadovaného těmito projekty, které byly zahrnuty do portfolia. V případě, že zdrojové omezení není splněno, potom pro každé i , pro které i=1 , definujeme i jako přírůstek (tj. zhoršení hodnoty) funkce způsobený vyjmutím projektu i z portfolia. Pro všechna taková i vypočteme
i P i=
∑ u −b , 2
j
j
j
(4.9)
∑ Aij u j −b j j
kde
Aij =a ij −
∑
k=1,2 ,,i−1,i 1, i2,, s
a ijk k
∑
∑
k =1,2 ,, i−1,i1,, s−1 l=k 1,k2,, i−1,i1,, s
a ijkl k l
je
množství j -tého zdroje spotřebovaného implementací i -tého projektu. P i je efektivní gradient skalarizující funkce . Součty ve vztahu P i jsou realizovány pouze pro všechna u j≥b j . Projekt dávající výrazu P i minimální hodnotu bude vyjmut z portfolia. Tento krok se opakuje tak dlouho, dokud nejsou splněna všechna zdrojová omezení. Analogicky ve zpětném chodu metody dáme do portfolia maximální počet projektů, které neporušují zdrojové omezení. Potom pro každé i , pro které i=0 , definujeme i jako úbytek (tj. zlepšení hodnoty) funkce způsobený zařazením projektu i do portfolia. Pro všechna taková i vypočteme
i Di =
∑ u −b . 2
j
j
j
∑ Aij u j−b j
(4.10)
j
Do portfolia pak přidáme ten projekt, který poskytuje (4.10) maximální hodnotu. Krok opakujeme až do té doby, kdy neexistuje takový projekt, který by mohl být přidán do portfolia, aniž by
4Vícekriteriální výběr projektů
Strana 43
se narušila platnost zdrojových omezeni. Dialog mezi uživatelem systému a osobou řešící tento problém uskutečněný po vstupní optimalizaci, ovlivní také hodnotu referenčních úrovní R j a tedy také váhy komponent skalarizující funkce pro účely potenciální budoucí reoptimalizace portfolia. Jestliže, založeno na vnitřních či vnějších omezeních nebo na základě nadřízeného orgánu, je projekt * aditivně přidán nebo odebrán z optimalizovaného portfolia, pak každá kriteriální funkce z hodnot z j *
(odpovídající původní referenční hodnotě R j ) je změněna na hodnotu z j . Je předpokládáno, že také * hodnoty R j jsou změněny ve stejném poměru k vzdálenosti od ideálního stavu I j , jestliže je ovšem uživatel spokojen s hodnotami z j . Tedy program mění hodnotu R*j na hodnotu R j , pro kterou platí R j =R j j , kde j=0 v případě, že je uživatel spokojen s hodnotou z j , a j= j jestliže uživatel doporučuje zvýšení hodnoty z j , a j=− j jestliže uživatel je ochoten vzdát se části * dosažené hodnoty z j ; 0 je dáno v (4.11) a (4.12). Následující vztah pro adaptivní změnu vah se odlišuje od podobného ve Stewartovi tím, že je v něm garantována platnost podmínky N j ≤R j≤ I j a vyloučeno dělení nulou a je v něm zahrnuta adaptivní proměnná.
*
* j
R j =R
z j−z j I j− z
* j
* j
I j −R
R j =N j R j =z j
*
* j
* j
z I j∧R
z j −z j I j −z
* j
*
*
*
*
z j I j ∧R j
z j−z j I j−z
* j
I j− R j ≥N j ,
*
I j −R j N j ,
z *j=i j .
Počáteční volba j je
j=
I j−R j pro j 0 2
j=
R j−N j pro j0, 0,51 2
(4.11)
a pro další reoptimalizaci
j = I j− R j pro j 0 j = R j−N j pro j0 ,
(4.12)
jestliže změna směru kriteriální funkce požadovaná uživatelem je stejná jako změna provedená v posledním kroku dialogu. V opačném případě je použito vztahu (4.11). je adaptivní hodnota závislá na historii změny znaménka j . Volba závislosti na této historii je dána uživatelem.
4.5
Numerický příklad Tento příklad je založen na datech firmy, která užívá informační technologie při obchodních
Strana 44
4Vícekriteriální výběr projektů
operacích a zabývá se zásobovacími službami. Během fiskálního roku stanovilo její marketingové oddělení 9 projektů zabývajících se vývojem informačních systémů pro zdokonalení objednávek zákazníků, pro instalaci komunikačních systémů a instalaci terminálů. Tyto projekty by měly pomoci zlepšit sledování prodeje a zvýšení budoucích zisků firmy. Je nutné vybrat množinu projektů, které by splnily roční omezení rozpočtu. Firma je schopna připravit vstupní data pro práci na systému na podporu rozhodování popsaném v předchozích paragrafech. Pro tento účel je vybavena firma vhodným softwarem. Jestliže použijeme uvedený obecný model a zmíněná vstupní data, obdržíme následující model vícekriteriální optimalizace : Pro hodnoty i ∈{0 ; 1}, i = 1, 2, , 9 nalézt max z j , j= 1, 2, 3, 4, kde účelová funkce vztažená k zisku je typu (4.4) a má tvar :
z 1 = 1200 1 250 2 360 3 200 4 1100 5 1276 90 7 70 8 8000 9 21 3 4 2200 7 8 9 (všechny zisky a náklady v příkladu jsou v tisících dolarech), účelová funkce vztažená k riziku násobená minus jedničkou má tvar :
z 2 =−3 1 − 2 2 − 3 3 − 1 4 − 55 − 3 6 − 1 7 − 4 8 − 3 9 (rizika pro každý projekt byla subjektivně ohodnocena na stupnici 0−10 , kde 0 znamená žádné riziko a 10 znamená maximální možné riziko pro projekt), účelová funkce vztažená k nákladům (dodavatelé, poplatky na konzultace, počítačový čas atd.) násobená minus jedničkou má tvar :
z 3=−220 4 − 710 5 − 62 6 − 400 7 − 800 8 − 2000 9 . Management firmy chce využít takový poměr celkových lidských zdrojů z celkového portfolia projektů pro všechny lidské zdroje užité v projektech 1 - 4, že bude tento poměr nejblíže jedné třetině. Potom dle (4.5)
i =
∑
i ∈{1,2 ,3,4} 9
i i
∑ i i
=
250 1600 2 80 3500 4 , 250 1600 280 3500 480 5150 6 110 7270 8130 9
1
1 = , 3 kde i je celkové množství lidských zdrojů použitých i -tým projektem a platí dle (4.6)
∥ 13∥.
z 4=− i−
Tato čtyři kritéria optimalizačního problému jsou řešena za následujících podmínek : a) Omezení hardwarového rozpočtu je typu (4.1) a má tvar :
4Vícekriteriální výběr projektů
Strana 45
450 1 360 2 12500 3 200 4 3000 5 900 6 − 1000 2 4 − 90 3 4 300 2 3 4 ≤ 17360 b) Omezení softwarového rozpočtu je typu (4.1) a má tvar :
2270 1 3000 2 370 3 500 4 255 29 6 7 7 12 8 45 9 − − 200 4 5 − 180 4 6 − 170 5 6 125 4 5 6 ≤ 4500 c) Hierarchické závislosti jsou typu (4.2) a mají tvar :
1 ≥ 2 , 2 ≥ 3 , 2 ≥ 4 . Vstupní referenční úroveň je dána ve tvaru R j =
Ij Nj , j = 1,2,3 ,4 . 2
Řešení :
1 = 1, 2 = 0, 3 = 1, 4 = 0, 5 = 0, 6 = 0, 7 = 0, 8 = 0, 9 = 0, účelová funkce vztažená k zisku
z 1 = 1560,
účelová funkce vztažená k riziku
−z 2 = 6,
účelová funkce vztažená k nákladům
−z 3 = 0,
kvocient lidských zdrojů
1 = 1.
Po vyhodnocení tohoto řešení management firmy na základě dodatečné informace usoudil, že by bylo smysluplné zvýšit ještě více zisk. Dialog byl uskutečněn podle [2] pro 1 = 1 , 2 = 0, 3 = −3 , 4 = 4 , skrze které se referenční úroveň R1 přiblížila horní hranici o polovinu své vzdálenosti. S vahou změněnou tímto způsobem byla provedena nová optimalizace portfolia projektů a bylo obdrženo nové řešení :
1 = 1, 2 = 0, 3 = 0, 4 = 0, 5 = 1, 6 = 1, 7 = 1, 8 = 1, 9 = 1, účelová funkce vztažená k zisku
z 1 = 12787,
účelová funkce vztažená k riziku
−z 2 = 19,
účelová funkce vztažená k nákladům
−z 3 = 3972,
kvocient lidských zdrojů
1 = 0,252.
Další kroky dialogu následují obdobným způsobem.
Strana 47
5
VLIV ZDROJOVÝCH OMEZENÍ NA VÝBĚR PROJEKTŮ
Experiment zde popsaný je založen na metodě J. Klapky, P. Piňose popsané v [2] a jejím speciálním případě – metodě T. J. Stewarta popsané v [7], kdy se při vícekriteriálním výběru projektů do portfolia nevyskytují žádné synergické efekty, ať už druhého nebo třetího řádu. Experiment spočívá ve srovnání přístupů ke stanovení vhodného portfolia projektů a k dosažení co největších zisků (kriteriálních funkcí), tak aby byla dodržena zdrojová omezení.
5.1
Algoritmus výpočtu Počáteční nastavení jsou tyto : ● počet projektů s , z nichž stanovujeme výsledné portfolio, ● počet ziskových (nákladových) kriteriálních funkcí typu (4.4) je p , ● počet zdrojových omezení typu (4.1) je m , ● náhodně vygenerované počáteční hodnoty a ij , kde i=1,2 , , s , j=1,2 , , m , ● náhodně vygenerované počáteční hodnoty c ij , kde i=1,2 , , s , j=1,2 , , p , ● náhodně vygenerované počáteční hodnoty b j , kde j=1,2 , , m .
5.1.1
Metoda efektivního gradientu
Krok 1. Zvolme i=1 pro všechna i=1,2 , , s (s výjimkou případu, kdy některé projekty nesmí probíhat současně, v tom případě hodnoty odpovídajících proměnných zvolíme). Pak vypočteme
u j=∑ a ij i
j = 1,2 , , m.
(5.1)
i
tj. množství zdrojů, nárokovaných těmi projekty, které jsou zařazeny do portfolia. Krok 2.
V případě, že pro některá j neplatí u j≤b j ( j -tý zdroj by byl přečerpán), pak pro všechna R jako přírůstek funkce z , i taková, že i=1, definujme i z , R , způsobený nahrazením hodnoty i=1 hodnotou i=0 , tj. vyjmutím i -tého projektu z portfolia. Pro všechna i taková, že i=1, vypočteme
i z , R P i=
m
m
∑ u k −bk 2 l u k −bk k =1
,
(5.2)
∑ a ik u k −b k l u k −b k k=1
R k míře úspory zdrojů způsobené vypuštěním tj. „efektivní gradient“ (poměr veličiny i z , i -tého projektu z portfolia). Pozn. :
Tato míra úspory zdrojů, přesněji řečeno míra celkového efektivního využití zdrojů i -tým projektem, je rovna velikosti průmětu vektoru úspory zdrojů, získané vyjmutím i -tého projektu z portfolia, do přímky spojující bod [u1 , u2 , , u m ], představující běžné využití zdrojů, hypoteticky odpovídající dané etapě řešení (včetně případného přečerpání), s jemu nejbližším bodem oblasti přípustné zdrojové disponibility. Projekt, poskytující hodnotě P i minimální hodnotu, bude vyjmut z portfolia. Tedy pro hodnotu h splňující vztah P h = min i P i položíme h =0. Znovu vypočteme všechny hodnoty u j z (5.1) a opakujeme krok 2 tak dlouho, dokud nejsou splněna všechna zdrojová omezení
Strana 48
5Vliv zdrojových omezení na výběr projektů
s
∑ aij i≤b j ,
j = 1,2 , , m .
(5.3)
i=1
Krok 3. Poté, co jsou splněny všechny zdrojové nerovnosti (5.3), hledáme, zda existuje takový projekt
i , z těch pro něž platí i=0 , který může být přidán do portfolia, aniž by se jakékoliv zdrojové omezení narušilo. Neexistuje – li, pak se algoritmus zastaví. Jinak pro každý takový projekt vypočteme
i z , R Di =
m
m
∑ uk −b k 2 k=1
,
(5.4)
∑ a ik u k −b k k=1
kde i znamená v tomto případě úbytek funkce způsobený zařazením i -tého projektu do portfolia (tj. změnou z i=0 na i=1 ). Analogicky jako v (5.2) je zde D i možno chápat jako efektivní gradient, avšak míru celkového efektivního využití zdrojů i -tým projektem zde definujeme jako velikost průmětu vektoru přírůstku zdrojů, způsobeného zařazením i -tého projektu do portfolia, do přímky spojující bod [u1 , u2 , , u m ] s bodem [ b1 , b 2 , , b m ], představujícím maximální možné využití zdrojů. Do portfolia pak přidáme ten projekt, který poskytuje výrazu (5.4) maximální hodnotu. Tento krok se opakuje až do té doby, kdy neexistuje takový projekt který by mohl být přidán do plánu, aniž by se narušila platnost zdrojových omezujících podmínek (5.3). Pak se algoritmus zastaví. 5.1.2
Uvažování zdrojových omezení
Máme množinu všech možných portfolií 2 s , kde s je počet projektů. Pro každé portfolium se otestuje platnost m zdrojových omezení podle (5.3). Pro portfolia, která splňují zdrojová omezení se vypočtou kriteriální funkce s
z j =∑ c ij i , j = 1,2 , , p
(5.5)
i=1
a pro každou takto stanovenou kriteriální funkci z j se stanoví její „ideální“ hodnota funkce I j , tj. horní mez optimální hodnoty veličiny z j , což je maximální hodnota funkce z j za podmínek (5.3) a (5.5) (tj. s ignorováním vlivu ostatních kriteriálních funkcí). Dále se pro každé z j stanoví jeho nejmenší možná hodnota N j (nejhorší zdrojově přípustná hodnota, tj. minimální hodnota z j stanovená za podmínek (5.3) a (5.5), rovněž s ignorováním vlivu ostatních kriteriálních funkcí). Platí tedy N j ≤z j ≤I j . Třetím odhadem kriteriální funkce z j je její realistický odhad („referenční hodnota“) R j . Kterou získáme takto :
R j=
I j N j . 2
Platí N j ≤R j≤ I j . Nyní se pro každé portfolium (splňující zdrojová omezení) vypočte „skalarizující funkce“, převádějící náš problém na monokriteriální optimalizaci. Při řešení úloh velkého rozsahu se osvědčila funkce p
z , R =∑ j=1
kde h0, a dále
I j− z j I j −R j
h
(5.6)
z =[ z 1 , z 2 , , z p ]
5Vliv zdrojových omezení na výběr projektů
Strana 49
R=[ R1 , R2 , , R p ] jsou p rozměrné vektory. Řešení spočívá v nalezení min z , R za podmínek (5.3) a (5.5). Z
kompromisu mezi citlivostí metody a zaokrouhlovacími chybami vyplývá ve většině praktických problémů doporučení volby h = 4. Pozn:
Minimální hodnota z , R , stanovená bez respektování zdrojové podmínky (5.3), by byla rovna nule, neboť jejího zmenšování dosahujeme zvětšováních všech z j až do hodnoty z j =I j , kterou se anuluje čitatel v (5.6). Takto stanovená skalarizující funkce je tedy v podstatě součtem měr relativních odchylek jednotlivých kriteriálních funkcí od jejich ideálních (nejvyšších hypoteticky možných) hodnot. Relativní odchylkou zde rozumíme odchylku vztaženou na jednotku intervalu dostatečně uspokojivých hodnot kriteriální funkce. Ze struktury jednotlivých sčítanců skalarizující funkce je tedy patrno, že váhově jsou preferovány ty z nich, u nichž R j je blízké k I j .
5.1
Numerický příklad Počáteční hodnoty :
s=10, p=12, m=6.
Náhodně generované zadání : cij c1j c2j c3j c4j c5j c6j c7j c8j c9j c10j
ci1
ci2 7 6 7 1 1 9 5 7 6 9
ci3 9 4 3 7 9 2 8 8 4 4
ci4 7 1 1 4 3 2 9 4 9 9
ci5 7 8 1 5 2 4 2 8 1 1
ci6 6 8 8 9 5 8 4 1 7 6
ci7 5 3 7 3 3 1 4 9 7 3
ci8 6 5 5 3 1 7 7 7 3 9
ci9 1 6 3 6 1 4 6 2 9 2
ci10 2 3 3 4 4 6 4 8 3 4
ci11 7 1 9 1 2 8 5 5 4 8
ci12 8 7 6 4 8 2 8 5 6 4
Tab. 1 Náhodně vygenerované hodnoty c ij , i = 1,2 , , s , j = 1,2 , , p. aij a1j a2j a3j a4j a5j a6j a7j a8j a9j a10j
ai1
ai2 18 14 10 15 6 2 11 13 4 14
ai3 2 16 12 3 8 12 4 20 15 17
ai4 19 20 17 9 20 4 11 14 5 6
ai5 17 6 12 12 16 9 1 11 16 4
ai6 10 10 9 6 18 19 10 13 9 19
17 1 7 20 16 10 13 16 15 9
Tab. 2 Náhodně vygenerované hodnoty a ij , i = 1,2 , , s , j = 1,2 , , m.
6 6 2 6 2 2 7 9 3 4
Strana 50
5Vliv zdrojových omezení na výběr projektů bj
b1
b2
97
51
b3
58
b4
b5
76
b6
89
86
Tab. 3 Náhodně vygenerované hodnoty b j , j = 1,2 , , m. Výpočet : Ij
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
Nj
58 N1
58 N2
49 N3
39 N4
62 N5
45 N6
53 N7
40 N8
41 N9
50 N10
58 N11
47 N12
Rj
R1
0
0
0
R2
29
29
0
R3
R4
24,5
19,5
0 R5 31
0
0
R6
R7
22,5
26,5
0 R8 20
0 R9
0 R10
20,5
0 R11
25
29
0 R12 23,5
Tab. 4 Vypočtené hodnoty I j , N j , R j , j = 1,2 , , p. Tabulka č. 4 nám ukazuje vypočtené horní meze I j , j = 1,2 , , p optimálních hodnot kriteriálních funkcí z j , j = 1,2 , , p , dále nejmenší možné hodnoty N j , j = 1,2 , , p a nakonec realistický odhad („referenční hodnotu“) R j , j = 1,2 , , p. Vidíme, že platí N j ≤R j≤ I j . V této diplomové práci jsem pro zjednodušení použil pouze kriteriální funkce získové s
z 1 , z 2 , , z p , proto lze lehce odvodit jednoduchou horní hranici I j=∑ c ij a dolní hranici i=1
I N j N j =0. Pro výpočet R j jsem použil R j = j . 2
Vypočtených hodnot v tabulce č. 4 jsem použil k získání hodnoty skalarizující funkce
z , R podle vztahu (5.6) s doporučenou volbou h=4. Dále jsem pokračoval krokem č. 1 z kapitoly 5.1.1 a pro i=1, i = 1,2 , , s , opět pro zjednodušení jsem neuvažoval případ, kdy některé projekty nesmí probíhat současně, stanovil příslušná u j , j = 1,2 , , m. Posléze následoval krok č. 2, kdy jsem určoval efektivní gradient P i , i = 1,2 , , s , dokud nebyla splněna všechna zdrojová omezení (5.3). Postupné kroky lze vidět v následujících tabulkách č. 5, č. 6, č. 7 a č. 8. uj
u1 107 101 91 77 63 48 35
1 2 3 4 5 6 7
u2 109 101 89 73 56 53 33
u3 125 105 88 68 62 53 39
u4 104 88 76 70 66 54 43
u5 123 105 96 86 67 61 48
u6 124 108 101 100 91 71 55
Tab. 5 Hodnoty u j , j = 1,2 , , m , po vyřazování projektů z portfolia. zj 1 2 3 4 5 6 7
z1
58 57 50 44 35 34 27
z2
58 49 46 42 38 31 23
z3
49 46 45 44 35 31 27
z4
39 37 36 28 27 22 14
z5
62 57 49 41 35 26 25
z6
45 42 35 32 29 26 17
z7
53 52 47 42 33 30 23
z8
40 39 36 30 28 22 20
z9
41 37 34 31 27 23 15
z10 50 48 39 38 30 29 24
z11 58 50 44 37 33 29 24
Tab. 6 Hodnoty z j , j = 1,2 , , p , po vyřazování projektů z portfolia.
z12 47 45 43 37 33 27 18
5Vliv zdrojových omezení na výběr projektů
Pi 1 2 3 4 5 6
P1
P2
P3
P4
P5
P6
P7
Strana 51
P8
P9
P10
0,0021 0,0019 0,0014 0,0014 0,0005 0,0019 0,0031 0,0034 0,0032 0,0156 0,0091 0,0079 0,0294 0,0089 0,0212 0,0151 0,0127 0,0682 0,0342 0,0546 0,0548 0,0770 0,0522 0,0570 0,2036 0,1624 0,1530 0,2170 0,1380 0,1409 0,3423 0,2580 0,3785 0,4147 0,2701 0,2965 6,1712 0,8134 2,9274 0,6779 0,7512
0,0023 0,0094 0,0476 0,1187 -
Tab. 7 Hodnoty efektivního gradientu P i , i = 1,2 , , s , po vyřazování projektů z portfolia.
δι
δ1
1 2 3 4 5 6 7
δ2 1 1 1 1 1 1 1
δ3
δ4
1 1 1 0 0 0 0
δ5
1 1 0 0 0 0 0
δ6
1 1 1 1 1 0 0
δ7
1 0 0 0 0 0 0
δ8
1 1 1 1 1 1 1
1 1 1 1 1 1 1
δ9 1 1 1 1 1 1 0
δ10 1 1 1 1 1 1 1
1 1 1 1 0 0 0
Tab. 8 Potfolio po postupném vyřazování projektů. Postupným opakováním kroku č. 2 jsme získali množství zdrojů, nárokovaných těmi projekty, které jsou zařazeny do portfolia u j , j = 1,2 , , m , portfolio (množinu projektů, pro něž platí i=1 ) a zisky z j , j = 1,2 , , p. Nyní zbývá provést krok č. 3 a zjistit, zda neexistuje projekt, který lze navrátit zpět do portfolia aniž by byla porušena zdrojová omezení (5.3). Pro tento příklad splňují zdrojová omezení (5.3) při navrácení zpět do portfolia 3 projekty : 3 , 4 a 10 . Výpočtem efektivního gradientu D i získáme pro příslušné 3 projekty hodnoty, z nichž vybereme tu největší a příslušný projekt je navrácen do portfolia, znovu se přepočítá (5.3) a pokud už nelze žádný projekt přidat, algoritmus končí. Di 1
D1 -
D2 -
D3 D4 0,4152 0,3951
D5 -
D6 -
D7 -
D8 -
D9 -
D10 0,3744
Tab. 9 Efektivní gradient D i . δι 1
δ1
δ2
1
δ3
0
1
δ4
0
δ5
0
δ6
δ7
1
δ8
1
0
δ9
1
δ10
0
Tab. 10 Portfolio po navrácení projektu.
uj 1
u1
u2 45
u3 45
u4 56
u5 55
u6 57
62
Tab. 11 u j po zařazení projektu.
zj 1
z1
z2 34
z3 26
z4 28
z5 15
z6 33
z7 24
z8 28
z9 23
18
z10 33
z11 30
z12 20
Tab. 12 Výsledné zisky z j . Takže výsledné portfolio nám ukazuje tabulka č. 10, výsledné množství zdrojů, nárokované
Strana 52
5Vliv zdrojových omezení na výběr projektů
těmi projekty, které jsou zařazeny do portfolia, nalezneme v tabulce č. 11 a výsledné zisky jsou v tabulce č. 12. Nyní zkusíme řešit stejný příklad pomocí zdrojových omezení. Pro stejná c ij z tabulky č. 1, a ij z tabulky č. 2 a b j z tabulky č. 3 vygenerujeme všechna možná portfolia, tzn. pro s=10 , 2 s = 2 10 =1024 možných variant portfolií. Pro všechny tyto varianty se vypočtou u j , j = 1,2 , , m a podle vztahu (5.3) se vyberou varianty, které splňují zdrojová omezení. Počet variant splňujících zdrojová omezení je 328 a pro tyto vybrané varianty se vypočtou kriteriální funkce z j , j = 1,2 , , p. Pomocí nichž určíme výsledné hodnoty I j , N j , R j , j = 1,2 , , p , tak že vybereme maximální hodnoty z j z variant portfolií splňujících zdrojová omezení a označíme je jako I j , pro N j se můžeme lehce přesvědčit, že jsou rovné 0 a R j získáme pomocí vztahu
R j=
I j N j . V tabulce č. 13 se můžeme na ně podívat. 2 Ij
I1
I2 37
Nj
N1
Rj
I3 36
I4
I5
38
N2
27
N3
N4
I6 38
N5
I7 28
N6
I8
I9
34
31
N7
I10 26
N8
I11 37
N9
N10
I12 32
31
N11
N12
0
0
0
0
0
0
0
0
0
0
0
R1 18,5
R2 18
R3 19
R4 13,5
R5 19
R6 14
R7 17
R8 15,5
R9 13
R10 18,5
R11 16
0 R12 15,5
Tab. 13 Stanovené meze I j , N j , R j , j=1,2 , , p , po splnění zdrojových omezení. Pokud porovnáme meze získané s uvažováním zdrojových omezení (5.3) z tabulky č. 13 s mezemi získanými bez uvažování zdrojových omezení (5.3) stanovené pro metodu efektivního gradientu z tabulky č. 4 můžeme vidět, že hodnoty mezí s uvažováním (5.3) jsou menší. Pomocí takto stanovených mezí vypočteme pro každou variantu portfolia skalarizující funkci podle vztahu (5.6) a z takto získaných hodnot vybereme tu, která je nejmenší. Pro tento příklad je to =0,6852 , a k ní odpovídající hodnoty u j , j=1,2 , , m ; z j , j=1,2 , , p ; i , i=1,2 , , s můžeme vyčíst z následujících tabulek č. 14, č. 15 a č. 16, což je současně i řešení. δι
δ1
δ2
1
δ3
0
δ4
0
1
δ5
0
δ6
δ7
1
δ8
1
0
δ9
δ10
1
0
Tab. 14 Výsledné portfolio s uvažováním zdrojových omezení. uj
u1
u2
50
36
u3
48
u4
u5
55
u6
54
75
Tab. 15 Množství nárokovaných zdrojů. zj
z1
28
z2
30
z3
31
z4
19
z5
34
z6
20
z7
26
z8
26
z9
19
z10 25
z11 28
z12 24
Tab. 16 Výsledné zisky kriteriálních funkcí. V následujících tabulkách uvádím srovnání řešeného příkladu podle metody efektivního gradientu (EG) a podle řešení při uvažování zdrojových omezení (5.3) (ZO). zj EG ZO ∑ %
z1
z2
z3
z4
34 26 28 15 28 30 31 19 -6 4 3 4 -17,65 15,38 10,71 26,67
z5
z6
33 24 34 20 1 -4 3,03 -16,67
z7
z8
28 23 26 26 -2 3 -7,14 13,04
z9
z10
18 33 19 25 1 -8 5,56 -24,24
Tab. 17 Srovnání kriteriálních funkcí z j .
z11 30 28 -2 -6,67
z12 20 24 4 20
∑ 312 310 -2 -0,64
5Vliv zdrojových omezení na výběr projektů
Strana 53
V tabulce č. 17 jsem srovnal kriteriální funkce, lze vidět, že pro některá z j , j=1,2 , , p , se hodnoty zvýšily, ale pro jiná zase zmenšila. Po provedení sumarizace jsem zjistil, že celkově pro všechna z j se tato hodnota lišila o 2 jednotky ve prospěch metody efektivního gradientu. δι
δ1
EG ZO
1 1
δ2
0 0
δ3
1 0
δ4
0 1
δ5
0 0
δ6
1 1
δ7
1 1
δ8
δ9
0 0
1 1
δ10
0 0
Tab. 18 Výsledná portfolia pro dané metody. V tabulce č. 18 vidíme, že počet zařazených projektů je shodný pro obě metody, liší se jen v případech zařazení projektů 3 a 4 . Ij EG ZO %
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
∑ 58 58 49 39 62 45 53 40 41 50 58 47 600 37 36 38 27 38 28 34 31 26 37 32 31 395 -36,21 -37,93 -22,45 -30,77 -38,71 -37,78 -35,85 -22,50 -36,59 -26,00 -44,83 -34,04 -34,17
Tab. 19 Hodnoty mezí I j . V tabulce č. 19 jsem srovnal hodnoty mezí I j , můžeme vidět, že při uvažování zdrojových omezení jsou tyto hodnoty menší. Pro ukázku zde uvedu ještě jeden příklad pro stejné hodnoty s , p , m jako v předchozím příkladě. Náhodně generované hodnoty jsou : cij c1j c2j c3j c4j c5j c6j c7j c8j c9j c10j
ci1
ci2 5 6 6 6 3 4 5 8 7 7
ci3 3 3 6 7 8 7 1 5 2 1
ci4 9 3 2 1 1 2 5 8 2 4
ci5 3 9 2 8 5 4 4 3 1 7
ci6 6 3 8 1 7 6 7 5 5 6
ci7 2 5 7 5 7 6 1 6 1 7
ci8 3 5 9 4 2 9 8 4 6 4
ci9 8 7 4 3 4 7 3 9 3 4
ci10 7 9 2 3 9 3 9 7 5 7
Tab. 20 Náhodně generovaná c ij . aij a1j a2j a3j a4j a5j a6j a7j a8j a9j a10j
ai1
ai2 5 8 10 19 4 3 11 16 2 12
ai3 2 8 13 9 8 19 6 9 8 9
ai4 10 6 7 20 16 3 16 11 12 5
ai5 13 1 1 13 11 6 14 18 4 13
Tab. 21 Náhodně generovaná a ij .
ai6 3 7 3 14 19 14 12 16 3 16
ci11 4 6 1 9 1 7 8 5 9 6
19 14 2 19 6 7 18 14 5 8
ci12 6 9 8 8 4 9 7 2 3 3
1 7 1 5 4 1 1 9 6 1
Strana 54
5Vliv zdrojových omezení na výběr projektů
bj
b1
b2
94
71
b3
59
b4
b5
62
b6
82
68
Tab. 22 Náhodně generovaná b j . Řešení : Ij
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
Nj
57 N1
43 N2
37 N3
46 N4
54 N5
47 N6
54 N7
52 N8
61 N9
56 N10
59 N11
36 N12
Rj
R1
R2
R3
28,5
21,5
18,5
0
0
0
0 R4
0 R5
23
0 R6
27
0
0
R7
23,5
0
R8
27
R9
26
0 R10
30,5
0 R11
28
0 R12
29,5
18
Tab. 23 Meze I j stanovené pro EG. uj
u1
1 2 3 4 5
u2 90 79 60 56 51
u3 91 85 76 68 66
u4
106 90 70 54 44
u5 94 80 67 56 43
u6
107 95 81 62 59
112 94 75 69 50
Tab. 24 Množství nárokovaných zdrojů u j pro EG. zj
z1
z2 57 52 46 43 38
1 2 3 4 5
z3 43 42 35 27 24
z4 37 32 31 30 21
z5 46 42 34 29 26
z6 54 47 46 39 33
z7 47 46 41 34 32
z8 54 46 42 40 37
z9 52 49 46 42 34
z10 61 52 49 40 33
z11
56 48 39 38 34
z12
59 52 44 40 34
36 35 30 26 25
Tab. 25 Kriteriální funkce z j pro EG. Pi
P1
P2
P3
1 2 3 4
0,0032 0,0252 0,0641 0,1565
0,0047 0,0332 0,1570 0,3567
P4
P5
P6
P7
P8
P9
P10
0,0042 0,0015 0,0018 0,0028 0,0012 0,0045 0,0022 0,0015 0,0368 0,0111 0,0120 0,0267 0,0220 0,0232 0,0190 0,1171 0,0574 0,1284 0,0796 0,0897 0,0940 1,6346 0,5804 0,3224 0,5409 0,4047 -
Tab. 26 Hodnoty efektivního gradientu P i . δι 1 2 3 4 5
δ1
δ2 1 1 1 1 0
δ3 1 1 1 1 1
δ4 1 1 1 1 1
δ5 1 1 0 0 0
δ6 1 1 1 0 0
δ7 1 1 1 1 1
Tab. 27 Vybrané portfolium pro EG. Nyní uvedu výpočty pro ZO :
δ8 1 0 0 0 0
δ9 1 1 1 1 1
δ10 1 1 1 1 1
1 1 1 1 1
5Vliv zdrojových omezení na výběr projektů
Ij Nj Rj
Strana 55
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
39 N1 0 R1 19,5
33 N2 0 R2 16,5
28 N3 0 R3 14
35 N4 0 R4 17,5
41 N5 0 R5 20,5
38 N6 0 R6 19
41 N7 0 R7 20,5
39 N8 0 R8 19,5
42 N9 0 R9 21
42 N10 0 R10 21
44 N11 0 R11 22
29 N12 0 R12 14,5
δ8
δ9
δ10
Tab. 28 Hodnota mezí pro ZO. δι
δ1
1
δ2
1
δ3
1
δ4
0
δ5
δ6
1
1
δ7
0
0
1
1
Tab. 29 Vybrané portfolio. uj
u1
44
u2
67
u3
u4
59
49
u5
65
u6
61
Tab. 30 Množství nárokovaných zdrojů u j . zj
z1
38
z2
30
z3
23
z4
31
z5
41
z6
z7
35
38
z8
37
z9
z10 34
42
z11 42
z12 21
Tab. 31 Kriteriální funkce z i pro ZO. Nyní provedeme porovnání těchto 2 metod pro příklad č. 2 : zj
z1
z2 38 38 0 0
EG ZO ∑ %
z3 24 30 6 25
z4
z5
z6
21 26 33 23 31 41 2 5 8 9,52 19,23 24,24
z7
32 35 3 9,38
z8
37 38 1 2,7
z9
z10
34 33 37 42 3 9 8,82 27,27
z11
z12
∑ 25 371 21 412 -4 41 -16 11,05
34 34 34 42 0 8 0 23,53
Tab. 32 Srovnání kriteriálních funkcí z j . Vidíme, že narozdíl od příkladu č. 1, se tentokrát hodnoty kriteriálních funkcí s uvažováním zdrojových omezení zlepšili a to o plných 41 jednotek (vyjádřeno procentuálně 11,05%). Ze 12 kriteriálních funkcí doznalo zlepšení – tedy zvýšení zisku plných 10, zhoršila se pouze 1 funkce. δι EG ZO
δ1
0 1
δ2
1 1
δ3
1 1
δ4
0 0
δ5
0 1
δ6
1 1
δ7
0 0
δ8
1 0
δ9
1 1
δ10
1 1
Tab. 33 Výsledná portfolia. Co se týče portfolií, tak změna nastala u 3 projektů, přičemž při uvažování ZO je vybrán do portfolia o jeden projekt více. Ij EG ZO %
I1
I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 I12 ∑ 57 43 37 46 54 47 54 52 61 56 59 36 602 39 33 28 35 41 38 41 39 42 42 44 29 451 -31,58 -23,26 -24,32 -23,91 -24,07 -19,15 -24,07 -25,00 -31,15 -25,00 -25,42 -19,44 -25,08
Tab. 34 Srovnání mezí I j . Při porovnání mezí opět vidíme, že při ZO jsou hodnoty horních mezí podle očekávání menší, tentokrát v průměru o 25,08%.
Strana 56
5.2
5Vliv zdrojových omezení na výběr projektů
Experiment
Nyní provedeme experiment s větším množství náhodně generovaných příkladů, abychom zjistili, vzájemné souvislosti mezi pozorovanými charakteristikami z j , I j a i , a v čem se liší přístup při uvažovaní zdrojových omezení oproti metodě efektivního gradientu. Z důvodu výpočetní náročnosti jsem vyzkoušel množinu 250 příkladů. Pro tuto množinu mi vyšlo stejné portfolio pro oba dva případy v celkem 82 příkladech (což je 32,8%), to znamená, že v těchto příkladech bylo stejné i z j . Lze se domnívat, že pro větší počet projektů i , i = 1,2 , , s , než je uvažováno v této práci, tedy s0 , by bylo procento stejných portfolií menší přímo úměrně zvětšujícímu se počtu projektů. Více
Stejně
96 38,40%
Méně
24 9,60%
48 19,20%
Tab. 35 Počet zvětšených jednotlivých z j . Tabulka č. 35 nám ukazuje, že v 38,4% bylo více zvětšených z j na jeden příklad při uvažování zdrojových omezení oproti metodě efektivního gradientu, v 9,6% stejně zvětšených jako zmenšených a v 19,2% bylo více z j zmenšených než zvětšených, což ale, jak uvidíme dále, nemusí nutně znamenat celkové zhoršení kriteriálních funkcí z j . 5 12 0 5 5 9 4 5
2 0 12 2 1 0 2 2
5 0 0 5 6 3 6 5
Tab. 36 Počty zvětšených z j . z1
z2 -3 7 0 6 -1 11 -1 5
z3 -4 6 0 0 -2 -1 -1 10
z4 -1 11 0 4 5 8 0 -2
z5 -1 9 0 -4 3 4 5 -2
z6 4 5 0 2 4 10 0 -4
z7 4 8 0 2 2 2 2 7
z8 -1 2 0 2 -1 3 -3 0
z9 6 1 0 -4 -2 1 -4 10
z10 2 10 0 0 2 8 -5 -3
z11 7 2 0 -2 0 -3 -1 3
z12 0 1 0 -3 -2 -2 1 0
∑ 0 3 0 -2 -4 9 2 -1
13 65 0 1 4 50 -5 23
Tab. 37 Celková suma zisků z j . Tabulky č. 36 a 37 udávají pro 8 náhodně vybraných příkladů z celkového počtu 250 testovaných – pro tabulku č. 36 v prvním sloupci počet zvětšených jednotlivých z j při uvažování zdrojových omezení, ve druhém počet z j se stejnou hodnotou a ve třetím počet zmenšených. V tabulce č. 37 jsou jednotlivá z j přímo vyčíslena a na konci je jejich výsledná suma – vidíme, že pro většinu zde uvedených příkladů je suma jednotlivých kriteriálních funkcí kladná, to znamená celkové zvětšení zisků. Ve 132 příkladech (tj. 78,6% ze 168 příkladů, které mají rozdílná portfolia a tudíž i kriteriální funkce) jsou výsledné zisky lepší při uvažování zdrojových omezení než při metodě efektivního gradientu. Ve zbývajících případech se osvědčila metoda efektivního gradientu.
5Vliv zdrojových omezení na výběr projektů
Strana 57
Porovnáme-li hodnoty horních mezí I j , zjistíme, že při uvažování zdrojových omezení jejich hodnoty vycházejí menší než u mezí používaných při metodě efektivního gradientu.
Strana 59
6
ZÁVĚR
Nejprve jsme se zabývali teorií vícekriteriální analýzy a vyhodnotili současný světový stav v této vědecké oblasti. Porovnávali jsme využití různých kriteriálních funkcí pro řešení konkrétních vícekriteriálních problémů. Zabýval jsem se vlivem stanovení horních mezí různých kriteriálních funkcí na výsledek. Dále byla studována metoda T. J. Stewarta pro vícekriteriální výběr projektů do portfolia (Journal of the Operational Research Society, 1991, pp. 17-26), která je speciálním případem metody J. Klapka, P. Piňos (Europan Journal of Operational Research, 2002, pp. 434-446). Tento speciální případ vznikne, když se nevyskytují žádné synergické efekty, ani vzájemné hierarchické závislosti projektů. Je to metoda heuristická, založená na pojmu efektivního gradientu. Její skalarizující funkce je
p I j− z j z , R =∑ j=1 I j −R j
h
,
kde h0 , přičemž z j , j = 1,2 , , p , jsou kriteriální funkce bivalentních proměnných (v této práci jsem se omezil na kriteriální funkce ziskové), R j je realistický odhad hodnoty kriteriální funkce z j , I j je horní mez hodnoty kriteriální funkce z j . Tato horní mez byla v dosavadních u nás dostupných realizacích Stewartovy metody počítána jako maximální hodnota funkce z j při monokriteriální optimalizaci a při ignorování vlivu zdrojových omezení. Tato heuristická metoda poskytuje řešení, které by bylo možné nazvat suboptimální, ve smyslu řešení blízkého optimálnímu řešení. Položil jsem si za cíl nalézt ještě další suboptimální řešení, aby měl uživatel větší možnost výběru. Proto jsem se rozhodl počítat horní mez I j , jako monokriteriální problém bez respektování ostatních kriteriálních funkcí, ale s respektováním omezujících podmínek. S touto metodou jsem provedl experiment na 250 příkladech, tato množina sice není nijak rozsáhlá – především z důvodu velké početní náročnosti, ale určité výsledky nám poskytla a dovedeme si představit z ní plynoucí závěr. Ve většině případu nám poskytla vyšší kriteriální funkce (cca 80%) a tudíž vyšší zisky, její vyhodnocení uvádím v kapitole 5. Dá se s největší pravděpodobností předpokládat, že podobných výsledků bychom dosáhli i při vyšším počtu příkladů. Zkušenosti z této práce bych chtěl v budoucnu využít i v případě, že kriteriální funkce z j s bivalentními proměnnými bude lineární lomená nebo bude polynomem, což jsou případy, kdy přesné řešení monokriteriální optimalizace, zvláště když ve zdrojových omezeních i v kriteriálních funkcích ziskových mohou být přítomny nelineární synergické efekty, může být při využití standardního softwaru obtížné.
Strana 61
SEZNAM POUŽITÉ LITERATURY [1] P. Vincke: Multicriteria Decision-aid. Wiley 1992. [2] J. Klapka, P. Piňos: Decision Support System for Multicriterial R&D and Information Systems Projects Selection. Europan Journal of Operational Research 140 (2002), pp. 434-446. [3] I. Kaliszewski: Dynamic Parametric Bounds on Efficent Outcomes in Interactive Multiple Criteria Decision Making Problems. European Journal of Operational Research 147 (2003), pp. 94-107. [4] P. Fiala, J. Jablonský, M. Maňas: Vícekriteriální rozhodování. Praha 1994. [5] L. Grygarová: Základy vícekriteriálního programování. Praha 1996. [6] J. Klapka, J. Dvořák, P. Popela: Metody operačního výzkumu. Brno 2001. [7] T. J. Stewart: A Multi-Criteria Decision Support System for R&D Project Selection. Journal of the Operational Research Society (1991), Vol. 42, No. 1, pp. 17-26. [8] J. Bouška, M. Černý, D. Glückaufová: Interaktivní postupy rozhodování. Academia, Praha, 1984. [9] R. E. Steuer: Multiple criteria optimization: theory, computation and application. Wiley, New York, 1986. [10] R. Benayoun, J. Montgolfier, J. Tergny, O. Larichev: Linear programming with multiple objective function: STEP Method (STEM). Mathematical Programming 1 (1971), pp. 366-375. [11] J. P. Brans, B. Mareschal: The PROMCALC & GAIA decision support system for multicriteria decision aid. University of Brussels, 1991. [12] P. Fiala: Kombinované metody řešení úloh vícekriteriálního lineárního programování. Ekonomicko-matematický obzor 25 (1989), č. 2, pp. 130-143. [13] H. Brožová, M. Houška, T. Šubrt: Modely pro vícekriteriální rozhodování, ČZU Praha, 2003. [14] M. Černý, D. Glückaufová: Vícekriteriální rozhodování za neurčitosti, 1. vyd. Praha, Academia 1987. [15] V. Mlynarovič, E. Hozlár: Viackriteriálné rozhodovanie. EU Bratislava, 1993. [16] R. Santhanam, J. Kyparisis: A Multiple Criteria Decision Model for Information System Projekt Selection. Computers and Operations Research, 22 (8), 807-818, 1995.
