Vícekriteriální hodnocení variant – VHV V lineárním programování jsme se naučili hledat optimální řešení pro úlohy s jedním (maximalizačním nebo minimalizačním) kritériem za předpokladu, že podmínky i účelová funkce byly dány lineárními funkcemi. (V případě, že by funkce byly např. kvadratické, mluvili bychom o kvadratickém programování.) Pro úlohy, v nichž není účelová funkce jediná, ale je jich více, je nutné použít trochu jiné postupy. V takovém případě mluvíme o vícekriteriálním rozhodování. Na první pohled se nabízí možnost nějak vhodně kritéria „sečíst,ÿ abychom dostali jen jediné kritérium. Pokud bychom však jen tak „bohapustěÿ kritéria sečetli, jistě bychom udělali chybu, nemůžeme přeci sčítat jen tak např. milióny korun a známky ze školy. Navíc některá kritéria mohou být důležitější (např. čistý trestní rejstřík pro výběr osoby na post generálního ředitele nejmenované firmy) než jiná (např. výška postavy nebo známka z kreslení) a na tyto skutečnosti je třeba brát zřetel.
3
Metody odhadu vah Důležité pravidlo pro volbu vah: Váhy vždy volíme tak, aby součet vah přes
všechna kritéria dával jedničku. Pokud tedy váhy pro i-té kritérium označíme symbolem vi , pro i = 1, . . . , k, kde k je počet kritérií, pak váhy volíme tak, P aby ki=1 vi = 1, vi ≥ 0. Dalším důležitým pravidlem je, že čím důležitější je kritérium, tím větší
váhu musíme kritériu přidělit. Co se týče volby vah, existují dvě možnosti. První, že váhy prostě stanovíme „natvrdoÿ – tzn. že si řekneme, jak důležitá jsou pro nás jednotlivá kritéria a že např. první kritérium bude mít váhu 20%, druhé 30% a třetí 50%. Zapsáno v matematických symbolech v = (v1 , v2 , v3 ) = (0.2, 0.3, 0.5). Druhou možností je stanovit váhy pomocí některé z následujících čtyř metod. Jednotlivé metody si předvedeme na následujícím příkladu: Příklad – Upír Je hluboká noc a vy se právě probouzíte ve své vyhřáté postýlce. Je šero, jen světlo z ulice matně osvětluje místnost. Máte dojem, že se nad vámi sklání postava v temném plášti s nezvykle dlouhými špičáky. Špatný sen, pomyslíte 1
si, otočíte se na druhý bok a v klidu usnínáte, když v tom na krku ucítíte ostrou bolest. Omdlíte. Probouzíte se a přemýšlíte o tom, že takhle „blbej senÿ se vám už léta nezdál. Copak ještě někdo věří na upíry? Ale moment. Něco není v pořádku. Tohle není vaše postel. Ježíši, tohle je přece rakev. Přemýšlíte, co se děje. Na mrtvolu se cítíte docela živě. A pak vám to dojde. To nebyl sen, je ze vás UPÍR. Zazmatkujete a propadnete panice. Opět omdlíte. Když se proberete, vidíte všechno z té lepší stránky. Můj život stejně za moc nestál, pomyslíte si. Teď budu žít navěky. Ale . . . začínám mít hlad. Čím se živí upíři? Krev, potřebuji krev. Zakousnete psa, který měl právě v úmyslu proběhnout kolem, ale to vás neuspokojí. Chce to něco kvalitnějšího. Chce to výbornou lidskou krev. Do místnosti vstoupí jakýsi shrbený stařík a představí se jako váš sluha. Jste trochu v šoku, ale za chvíli začnete mít jasno. Zatímco stařík uklízí spoušť, kterou způsobila vaše chuť po krvi a na kousky rozcupovaný mrtvý pes, vysvětluje vám pravidla, která platí v říši upírů. Každý upír ovládá území do vzdálenosti 10 km od hradu, na němž sídlí. Zde může vysávat kohokoliv, kdo se mu bude líbit. Okruhy se ale překrývají a pro mladé upíry není vhodné lovit v blízkosti hradů jiných upírů, sic by je to mohlo stát jejich dlouhověký život. Není vhodné se přibližovat k česneku, kostelům, dřevěným kolíkům a stříbrným kulkám. To vše rozhodně upírův zdravotní stav nevylepší. No a co se tak povídá, je lepší si vybírat lidi s kvalitní krví, protože jinak upír ráno pozná, co je to „krevní kocovinaÿ. Achych ouvej, to bylo informací. Až se mi z toho hlava točí, pomyslíte si. Nu což, chce to udělat dobrý plán. Začnete tím, že si sestavíte seznam kritérií, podle kterého si pak vyberete nejlepší oběť. Nakonec jich vymyslíte devět: 1. Vzdálenost od česnekového pole (ČES) – je udávána v metrech a jedná se o vzdálenost obydlí případné oběti od nejbližšího většího zdroje česneku. Čím větší vzdálenost, tím lépe. 2. Vzdálenost nejbližšího upíra (VUP) – je udávána v kilometrech a označuje, jak daleko od místa oběti se nachází nejbližší další upírský hrad. Čím bude dále, tím lépe. 3. Kvalita prostředí (KPR) – je hodnocena body na stupnici 0 – 100 bodů 2
a označuje, jak kvalitní je životní prostředí oběti, aby byla zajištěna co nejlepší kvalita krve, cílem je co nejvyšší dosažené hodnocení. 4. Vzdálenost od kostela (KOS) – je udávána v kilometrech a jedná se o vzdálenost obydlí oběti od nejbližšího kostela nebo jiného svatého místa, kde by hrozilo nebezpečí. Čím dále od takového místa, tím lépe. 5. Krevní skupina (KS) – každý upír preferuje jinou krevní skupinu a vybírá si pochopitelně tu nejlepší. Krevní skupina je hodnocena jako ve škole známkou v rozsahu 1 – 5, čím lepší (nižší hodnota) známka, tím lépe. 6. Obranyschopnost (OS) – muži jsou lepšími bojovníky a nejednou byl upír zastrašen silným mužem. Proto je obranyschopnost také důležitým kritériem. Většinou je hodnocení takové, že muži mají 1 a ženy (jako slabší stvoření) 0. Žena je také krásnější a atraktivnější, takže osoby s ohodnocením 0 jsou žádanější. Většinou je toto kritérium pro upíra nejdůležitější. Čím menší hodnota, tím lépe. 7. Finanční zázemí (FIN) – dobré finanční zázemí oběti je důležité, neboť upír pak může s majetkem nakládat dle svého uvážení. Hodnoceno je průměrným měsíčním příjmem za poslední rok v Kč, cílem je co nejlepší (nejvyšší) finanční zázemí. 8. Vzdálenost od rakve (VOR) – upír pracuje jen v desetikilometrovém okruhu a dál si netroufá jít, nicméně čím blíže bydlí oběť k hradu, tím je méně práce ji naštívit a zakousnout. Vzdálenost je udávána v kilometrech a čím je nižší, tím lépe. 9. Věk (VĚK) – je udáván v letech, mladá krev je pochopitelně chutnější a tak čím nižší věk, tím lépe. Pokračování příště
3.1
Metoda pořadí
• Kritéria seřadíme nejprve podle pořadí od nejdůležitějšího po nejméně důležité.
• Předpokládejme, že máme k kritérií. Nejdůležitější kritérium ohodnotíme
k body (bi = k), druhé nejdůležitější k − 1 body (bi = k − 1), atd. až poslední (nejméně důležité) jedním bodem (bi = 1). 3
• V případě, že by některá kritéria byla stejně důležitá, obodujeme je příslušným průměrem.
• Váhu příslušného kritéria pak dostaneme podle vztahu vi = bi / •
Pk
Pk
i=1 bi .
je součtem bodů rozdělených mezi jednotlivá kritéria. Pro tento P součet platí ki=1 bi = k(k + 1)/2. i=1 bi
Ukažme si nyní tuto metodu na příkladu Upíra. Nejprve očíslujeme jednotlivá kritéria a přidělíme jim index i = 1, . . . , 9. Pak kritéria seřadíme podle pořadí. Nakonec každému kritériu přiřadíme 1 až 9 bodů (bi ) tak, aby nejdůležitější kritérium dostalo 9 bodů, . . . , a nejméně důležité dostalo jeden bod. i
pořadí
bi
ČES
1
9
1
VUP
2
2–3
7.5
7.5/45 = 0.17
KPR
3
2–3
7.5
7.5/45 = 0.17
KOS
4
6
4
4/45 = 0.09
KS
5
7
3
3/45 = 0.07
OS
6
1
9
9/45 = 0.20
FIN
7
8
2
2/45 = 0.04
VOR
8
4
6
6/45 = 0.13
VĚK
9
5
5
5/45 = 0.11
45
1
součet
vi = b i /
P9
kritérium
i=1 bi
1/45 = 0.02
Snadno si můžeme ověřit, že pro devět kritérií (k = 9) součet všech bodů ve sloupci bi se rovná
3.2
k(k+1) 2
=
9·10 2
= 45.
Bodovací metoda
• Výpočet vah je při použití této metody identický s postupem uvedeným v předchozí metodě, jediný rozdíl je v přidělení bodů bi .
• Opět platí pravidlo, že čím důležitější je některé kritérium, tím vyšší dostane počet bodů.
• Každé kritérium v této metodě ohodnotíme body z nějakého předem daného intervalu, např. bi ∈< 0, 10 >.
• Váhu příslušného kritéria pak dostaneme podle vztahu vi = bi / 4
Pk
i=1 bi .
Pro příklad Generálního ředitele určíme váhy následovně: i
bi
ČES
1
1
1/53 = 0.019
VUP
2
9
9/53 = 0.170
KPR
3
9
9/53 = 0.170
KOS
4
4
4/53 = 0.075
KS
5
4
4/53 = 0.075
OS
6 10
10/53 = 0.189
FIN
7
3
3/53 = 0.057
VOR
8
8
8/53 = 0.151
VĚK
9
5
5/53 = 0.094
53
1
součet
3.3
vi = b i /
P9
kritérium
i=1 bi
Metoda párového srovnávání (Fullerova metoda)
• Tato metoda bývá nazývána Fullerovou metodou proto, že při její aplikaci sestavujeme váhy pomocí tzv. Fullerova trojúhelníku.
• Princip párového srovnávání je takový, že vždy porovnáváme dvě kritéria a z každé takové dvojice kritérií vybereme to důležitější.
• Srovnáváme-li každá dvě kritéria z celkového počtu k kritérií, vybíráme
všechny kombinace dvou prvků z k. Celkový počet porovnání je tedy roven N = k2 = k(k−1)(k−2)! = k(k−1) . 2!(k−2)! 2
• Pro větší přehlednost při srovnávání sestavujeme tzv. Fullerův trojúhelník. Trojúhelník má vždy k − 1 dvojřádků. V prvním řádku jsou všechny
kombinace pro porovnání s prvním kritériem, v druhém kombinace pro porovnání s druhým kritériem, kromě té, která je v předchozím řádku, v každém dalším řádku jsou kombinace pro porovnání s dalším kritériem, které nejsou v předchozích řádcích. Každý řádek má tedy o 1 člen méně, než řádek předchozí.
5
1
1
1
1 ...
1
1
2
3
4
5 ...
k
2
2
2
2 ...
k−1
3
4
5
6 ...
2
k
... ... k−3 k−3 k−3 k−2 k−1
k
k−2 k−2 k−1
k
k−1 k
• Označme symbolem ni počet zakroužkovaných i, konkrétně tedy počet zakroužkovaných jedniček označíme n1 , apod.
• Váhy potom spočítáme podle vztahu vi =
n Pk i
i=1
ni
=
ni . N
Ukažme si metodu na příkladu Upíra. Nejprve sestavíme Fullerův trojůhelník a pak v každé dvojici zakroužkujeme kritérium, které nám připadá důležitější. 1 1 1
1 1
1 1 1
2 3 4
5 6
7 8 9
2 2 2
2 2
2 2
3 4 5
6 7
8 9
3 3 3
3 3
3
4 5 6
7 8
9
4 4 4
4 4
5 6 7
8 9
5 5 5
5
6 7 8
9
6 6 6 7 8 9 7 7 8 9 8 9 6
Počet porovnání N =
3.4
9 2
=
9·8 2
= 36.
i
ni
vi = ni /N
1
0
0/36 = 0.00
2
6
6/36 = 0.17
3
7
7/36 = 0.19
4
4
4/36 = 0.11
5
1
1/36 = 0.03
6
7
7/36 = 0.19
7
2
2/36 = 0.06
8
6
6/36 = 0.17
9
3
3/36 = 0.08
součet
36
1
Kvantitativní párové srovnávání (Saatyho metoda)
• Saatyho metoda patří mezi nejčastěji používané metody pro volbu vah, používá se např. v postupu AHP.
• Srovnávají se opět vždy páry kritérií (stejně jako v předchozím případě)
a hodnocení se ukládá do tzv. Saatyho matice S = (sij ) podle následují-
cího systému:
(sij ) =
1 – i a j jsou rovnocenná 3 – i je slabě preferováno před j
5 – i je silně preferováno před j 7 – i je velmi silně preferováno před j 9 – i je absolutně preferováno před j
• Hodnoty 2,4,6 a 8 jsou ponechány pro hodnocení mezistupňů. • Je zřejmé, že sii = 1, neboť kritérium je rovnocenné samo se sebou. • Navíc musí platit, že sji = 1/sij pro všechna i. • Hodnota sij představuje přibližný poměr vah kritéria i a j, v matematickém zápisu sij ≈ vi /vj .
7
• Předpokládejme, že skutečný poměr vah je vi /vj , my tento poměr odhadujeme hodnotou sij a chceme, aby se toto sij co nejméně lišilo od vi /vj . – Minimalizujeme tedy součet čtverců rozdílu F =
k X k X i=1 j=1
za podmínky:
Pk
i=1
vi sij − vj
2
−→ min
vi = 1
– To je ale problém kvadratického programování a při výpočtech by mohlo dojít k potížím. – Pro snadnější výpočet se používá metoda geometrického průměru, neboli metoda nejmenších logaritmických čtverců. – Jde o minimalizaci kvadratické formy F =
k X X i=1 j>i
za podmínky:
(ln sij − (ln vi − ln vj ))2 −→ min
Pk
i=1
vi = 1
– Řešením je geometrický průměr řádků matice S:
vi =
"
k Q
sij
j=1
" k k P Q
i=1
j=1
#1/k
sij
#1/k
pro i = 1, . . . , k.
– Problémem ovšem je, že matice S musí být ”uspokojivě konzistentní,” tzn. σ2
<
0.1 pro
k=3
2
<
0.2 pro
k = 4, 5, 6, 7
σ2
<
0.3 pro
k>7
σ
kde σ 2 je odhad rozptylu. – Platí σ 2 = F/d, kde F je hodnota výše uvedené kvadratické formy ad=
k(k−1) 2
− (k − 1) =
(k−1)(k−2) , 2
což je počet srovnání snížený
o počet lineárně nezávislých váhových parametrů. 8
• Samotná metoda je velmi jednoduchá a zahrnuje následujících 5 kroků. • Nejprve vyplníme Saatyho matici: 1. Na diagonále budou jedničky (sii = 1). 2. sij ∈< 0, 9 >, pokud i je preferováno před j. 3. sji = 1/sij • Pro každé i spočítáme hodnotu si =
k Q
sij .
j=1
• Pro každé i spočítáme hodnotu Ri = (si )1/k = • Dále spočítáme
k P
√ k
si .
Ri .
i=1
• Nakonec určíme váhy kritérií podle vztahu vi =
Ri . k P Ri i=1
Pro ilustraci metody použijeme příklad Upíra, tentokrát ovšem budeme uvažovat pouze prvních 5 kritérií. sij
f1
f2
f3
1/150
0.367
5 P
5
100
2.512
0.373
4
5
100
2.512
0.373
1
2
3/8
0.822
0.122
1
1/25
0.525
0.078
součet
6.738
1
f4
f5
5 Q
si =
sij
Ri = (si )1/5
j=1
f1
1
1/5 1/5 1/3 1/2
f2
5
1
1
4
f3
5
1
1
f4
3
1/4 1/4
f5
2
1/5 1/5 1/2
9
vi = R i /
Ri
i=1
0.054
