Složité rozhodovací úlohy

Teorie systémů a operační analýza 1

Složité rozhodovací úlohy

RNDr. Jiří Dvořák, CSc.

[email protected]

TSOA: Složité rozhodovací úlohy 2

Typy složitých rozhodovacích úloh

Úlohy s velkým počtem izolovaných lokálních extrémů

(mnohoextremální úlohy)

Úlohy velkého rozsahu

Dynamické úlohy (optimalizace rozhodovacích procesů)

Úlohy s neurčitostmi (stochastické úlohy, fuzzy úlohy)

Vícekriteriální úlohy

Úlohy s více rozhodovateli (úlohy teorie her)


Mnohoextremální úlohy

Metody pro řešení úloh s mnoha izolovanými lokálními extrémy:

Metody pro nalezení globálního extrému, např. metoda vnější aproximace a sečných nadrovin metoda větví a mezí tunelovací metoda

Heuristické metody, např. simulované žíhání (simulated annealing) zakázané hledání (tabu search) genetické algoritmy


Rozsáhlé úlohy LPU rozsáhlých úloh lineárního programování je matice A obvykle

řídká, což znamená, že má nejvýše několik procent nenulových prvků. Existují speciální metody lineární algebry pro efektivní implementaci operací s řídkými maticemi.

Pro řešení úloh LP s řídkou maticí je možné použít odpovídající implementaci revidované simplexové metody. V revidované simplexové metodě se nepočítá celá simplexová tabulka, ale pouze údaje nezbytně nutné pro jednotlivé iterace. Klíčovým bodem algoritmu je inverze bázické matice B.

Některé rozsáhlé úlohy LP mají navíc speciální strukturu určenou vzájemně provázanými dílčími úlohami. Pro řešení takových úloh mohou být použity dekompoziční metody (např. Dantzig-Wolfeho metoda nebo Bendersova metoda).


Diskrétní dynamické úlohy

Diskrétní rozhodovací proces můžeme definovat jako množinu vektorů {y0, y1, … , x0, x1, … }, kde yi je stav v i-té etapě procesu, xi je rozhodnutí v i-té etapě procesu, přičemž y0 je počáteční stav a pro ostatní stavy platí yi+1 = fi (yi, xi).

Cílem je nalezení takové rozhodovací strategie {x0, x1, … }, která optimalizuje kriteriální funkci F(y0, y1, … , x0, x1, … ) sdruženou s daným procesem, přičemž jsou splněny dané omezující podmínky.

K řešení diskrétních dynamických rozhodovacích úloh se používají metody dynamického programování.


Spojité dynamické úlohySpojitý rozhodovací proces můžeme definovat jako dvojici

, kde x(t) je vektorová rozhodovací funkce, y(t) je vektorová stavová funkce a t je čas, přičemž platí

Cílem je nalezení takové rozhodovací funkce x(t), která optimalizuje nějaký funkcionál sdružený s daným procesem, přičemž jsou splněny dané omezující podmínky.

K řešení spojitých dynamických rozhodovacích úloh se používají metody dynamického programování a metody variačního počtu.

)(),( tt yx

)(tF x

tttdt

td),(),(

)(yxf

y


Stochastické programováníÚloha stochastického programování v nerovnicovém tvaru:

kde je náhodný vektor definovaný na pravděpodobnostním prostoru (, , P) a jeho rozdělení pravděpodobnosti nezávisí na rozhodnutí x; funkce f : Rn× R a g : Rn× Rm jsou měřitelné pro každé x Rn.

Řešením této úlohy se rozumí řešení deterministického ekvivalentu, který je definován tak, aby byla korektně odstraněna náhodnost z původní úlohy.

Při konstrukci deterministického ekvivalentu je nutné rozhodnout, co budeme považovat za přípustné řešení a co budeme považovat za optimální řešení.

Xf x0ξxgξx ,);();(min


Příklady konstrukce množiny přípustných řešení Použití středních hodnot:

nebo

Použití scénářů:

kde S je konečná množina významných realizací nazývaných scénáře.

Použití pravděpodobnostních omezení:

nebo

0ξxgx )(; EXM

0ξxgx );(PXM

migPXM ii ,...,1,0);( ξxx

S

s

s

XM

ξ

0ξxgx );(

0ξxgx );(ξEXM


Příklady konstrukce účelové funkce

Použití střední hodnoty náhodného vektoru :

Použití střední hodnoty funkce f(x; ):

Kombinace střední hodnoty a rozptylu funkce f(x; ):

kde > 0.

)(;)( ξxx EfF

);()( ξ ξxx fEF

);();()( ξξ ξxξxx fDfEF


Vícekriteriální úlohy

Problém vícekriteriálního rozhodování:

Je dána nějaká množina možných variant (rozhodnutí, řešení) a máme vybrat variantu, která je co nejlepší vzhledem k dané množině kritérií (hledisek, charakteristik).

Typy vícekriteriálních úloh: Úlohy vícekriteriálního hodnocení variant (přípustné

varianty jsou vymezeny explicitně). Úlohy vícekriteriálního programování (přípustné

varianty jsou vymezeny implicitně soustavou podmínek a všechna kritéria jsou kvantitativní).


Typy kritérií

Uvažovaná kritéria bývají obvykle konfliktní. Mohou se mezi nimi vyskytnout jak kritéria kvantitativní (kardinální), tak kritéria kvalitativní (ordinální). V případě současného výskytu kvalitativních i kvantitativních kritérií se provádí přechod k jednomu typu kritérií, buď ke kvalitativním nebo ke kvantitativním.

Kvantitativní kritéria umožňují pro každou variantu stanovit hodnoty kritérií. Tato kritéria bývají často nesouměřitelná v důsledku vyjádření v různých jednotkách. U některých metod pro řešení vícekriteriálních úloh je třeba tuto nesouměřitelnost odstranit určitou normalizací (např. přechodem k ukazatelům, které vyjadřují procenta plnění původních ukazatelů).

Kvalitativní kritéria dovolují pouze stanovit, zda je nějaká varianta podle určitého kritéria lepší či horší než jiná, nebo zda jsou podle tohoto kritéria obě srovnávané varianty rovnocenné.


Úloha vícekriteriálního programování

kde

Tento zápis neurčuje úlohu vícekriteriálního programování jednoznačně, neboť význam operátoru max pro vektory není přesně definován.

Úkolem je najít takový vektor x, který splňuje omezující podmínky a v němž kriteriální funkce f1(x), f2(x), … , fp(x) nabývají co možná největších hodnot.

T21 )(,...),(),()( xxxxf pfff

T21 )(,...),(),()( xxxxg mggg

X x0xgxf ,)()(max


Dominovaná a nedominovaná řešení

Nechť x1 a x2 jsou přípustná řešení. Řekneme, že řešení x1 dominuje řešení x2 , jestliže pro všechna k = 1, … , p platí fk(x1) fk(x2), přičemž existuje r takové, že fr(x1) > fr(x2). To znamená, že x1 musí být lepší alespoň podle jednoho kritéria, přičemž podle žádného není horší.

Řekneme, že řešení x je nedominované (paretovsky optimální), jestliže neexistuje žádné přípustné řešení, které by je dominovalo. Řešení splňuje podmínku paretovské optimality, jestliže žádné kritérium nelze zlepšit, aniž by došlo ke zhoršení jiného kritéria.


Metody vícekriteriálního programování

Tyto metody jsou založeny na jednorázovém nebo opakovaném použití metod jednokriteriální optimalizace a můžeme je členit takto:

Metody založené na apriorních informacích o preferencích rozhodovatele: agregace kritérií lexikografická optimalizace minimalizace vzdálenosti od ideálního vektoru

Interaktivní metody: doplňující informace o preferencích rozhodovatele jsou

zadávány až v průběhu řešení úlohy


Metody agregace kritérií

Ze zadaných kritérií se pomocí vhodné agregační funkce konstruuje skalární kritérium.

Nejčastějším případem agregační funkce je vážený součet kritérií:

kde vk > 0 jsou váhy kritérií. Obvykle se ještě požaduje, aby

p

kkk fvF

1

)()( xx

p

kkv

1

1


Lexikografická optimalizace

Předpokládejme, že je dáno pořadí kritérií podle klesající důležitosti. Množinu přípustných řešení zužujeme tak, že na ni postupně aplikujeme jednotlivá kritéria v daném pořadí.

Tedy nejprve řešíme úlohu jednokriteriální optimalizace při použití prvého kritéria, na získanou množinu optimálních řešení této úlohy pak aplikujeme druhou účelovou funkci, atd.

Tento postup končí získáním jediného optimálního řešení, nebo vyčerpáním všech kritérií, nebo zjištěním, že optimální řešení neexistuje.


Minimalizace vzdálenosti od ideálního vektoru (cílové programování)

Je dán vektor ideálních hodnot jednotlivých kritérií (tento vektor může být také určen optimalizací jednotlivých účelových funkcí na množině přípustných řešení).

Při použití nějaké vhodné metriky se hledá takové řešení, v němž je vzdálenost vektoru hodnot kritérií od ideálního vektoru h minimální. Řešíme tedy úlohu

Příklady metrik (vk > 0 jsou váhy kritérií):

Xd x0xgxfh ,)()(,min

p

kkkk fhvd

1

2)()(, xxfh

p

kkkk fhvd

1

)()(, xxfh


Úloha vícekriteriálního hodnocení variantPředpokládejme, že všechna kritéria jsou kvantitativní. Pak je

úloha vícekriteriální hodnocení variant charakterizována kriteriální maticí

kde yij je hodnota j-tého kritéria pro i-tou variantu.

Ideální varianta (nemusí reálně existovat) je reprezentována vektorem nejlepších hodnot jednotlivých kritérií.

Bazální varianta (nemusí reálně existovat) je reprezentována vektorem nejhorších hodnot jednotlivých kritérií.

npnn

p

p

yyy

yyy

yyy

...

...

...

21

22221

11211

Y


Dominované a nedominované varianty

Nechť všechna kritéria jsou maximalizační a nechť ai = (yi1, yi2, … , yip) a aj = (yj1, yj2, … , yjp) jsou dvě varianty. Řekneme, že varianta ai dominuje variantu aj , jestliže pro všechna k = 1, … , p platí yik yjk, přičemž existuje r takové, že yir > yjr. To znamená, že ai musí být lepší alespoň podle jednoho kritéria než aj , přičemž podle žádného není horší.

Řekneme, že varianta a je nedominovaná (paretovsky optimální), jestliže neexistuje žádné jiná varianta, která by ji dominovala. Varianta splňuje podmínku paretovské optimality, jestliže žádné kritérium nelze zlepšit, aniž by došlo ke zhoršení jiného kritéria.


Metody vícekriteriálního hodnocení variant

Metody vícekriteriálního vyhodnocování variant můžeme členit obdobně jako metody vícekriteriálního programování podle toho, zda jsou či nejsou dány nějaké doplňující informace a zda jsou dány předem nebo až v průběhu výpočtu. Je zde také možno najít obdobné výpočetní metody (metoda agregace kritérií, lexikografická metoda, metoda minimalizace vzdálenosti od ideálního vektoru).

Kromě toho zde však existují i metody specifické, využívající konečnost množiny variant a schopné pracovat s kvalitativními kritérii. K takovým patří také metody založené na teorii fuzzy množin (mlhavých množin). V těchto metodách se na základě dílčích preferencí rozhodovatele konstruuje mlhavá relace, z níž se pak pomocí prahů preference a indiference resp. dispreference získává výsledná nemlhavá preferenční relace, podle které lze pak varianty nějakým způsobem uspořádat.


Metoda TOPSISJedná se o výběr varianty, která je co nejblíže k ideální variantě

reprezentované vektorem (H1, H2, … , Hp) a co nejdále od bazální varianty reprezentované vektorem (D1, D2, … , Dp).

1. Konstruuje se normalizovaná kriteriální matice R = (rij), kde

2. Vypočteme váženou kriteriální matici W = (wij), kde

wij = vj rij a vj je váha j-tého kritéria.

3. Určíme ideální a bazální variantu:

n

iij

ijij

y

yr

1

2

pjwDwH iji

jiji

j ,...,2,1,min,max


4. Vypočteme vzdálenosti i-té varianty od ideální a bazální varianty:

5. Vypočteme relativní ukazatele vzdálenosti i-té varianty od bazální varianty:

Varianty uspořádáme podle klesajících hodnot ukazatele ci.

niDwdHwdp

jjiji

p

jjiji ,...,2,1,)(,)(

1

2

1

2

nidd

dc

ii

ii ,...,2,1,


Metody odhadu vah kritérií

Přímé určení vah

Ordinální srovnání kritérií všech najednou (metoda pořadí) párové (Fullerova metoda)

Kardinální srovnání kritérií všech najednou (bodovací metoda) párové (Saatyho metoda)

Srovnání variant (metoda entropie)


Metoda pořadíMějme p kritérií a q expertů. Kritéria jsou uspořádána přiřazením

přirozených čísel p, p – 1, … , 1. Nejdůležitějšímu kritériu je přiřazeno číslo p, nejméně důležitém číslo 1.

Nechť aij je číslo přiřazené i-tému kritériu j-tým expertem.

Váha i-tého kritéria podle j-tého experta:

Výsledná váha i-tého kritéria:

2)1(

1

pp

a

a

av ij

p

iij

ijij

2)1(

11

qpp

a

q

v

v

p

iij

q

jij

i


Bodovací metodaMějme p kritérií a q expertů. Pro zvolenou bodovací stupnici musí

j-tý expert ohodnotit i-té kritérium hodnotou aij ležící v dané stupnici. Čím je kritérium důležitější, tím je bodové ohodnocení větší.



p

iij

ijij

a

av

1

q

v

v

q

jij

i

1


Fullerova metodaMějme p kritérií a q expertů. Každý expert postupně srovnává

každá 2 kritéria mezi sebou, takže tedy provede

srovnání.

Srovnání se mohou provádět v tzv. Fullerově trojúhelníku, v němž jsou zachyceny všechny možné dvouprvkové kombinace kritérií. Experti u každé dvojice zakroužkují to kritérium, které pokládají za důležitější. Nechť aij je počet zakroužkování i-tého kritéria u j-tého experta.



N

a

a

av ij

p

iij

ijij

1

q

v

v

q

jij

i

1

2)1(

2

ppp

N


Úvod do teorie herTeorie her se zabývá modelováním konfliktních

rozhodovacích situací. Tyto situace můžeme členit takto: antagonistický konflikt (co jedni hráči ztrácejí, ostatní

získávají) a neantagonistický konflikt (mohou existovat rozhodnutí výhodná pro všechny účastníky a jsou případně možné i kooperace mezi hráči)

hry s přenosnou výhrou (je možné přerozdělení výhry po ukončení hry) a hry s nepřenosnou výhrou

hry s úplnou informací (hráči mají před každým tahem přesnou informaci o dosavadním průběhu hry) a hry s neúplnou informací

konečné hry (všichni hráči mají konečně mnoho strategií) a nekonečné hry


Hra v normálním tvaruZákladní matematický model teorie her:

{Q; X1 , X2 , … , XN ; M1(x), M2(x), … , MN (x)}

kde Q = {1, 2, … , N } je množina hráčů, Xi je prostor strategií i-tého hráče, Mi (x) je výplatní funkce i-tého hráče. Výplatní funkce jsou definovány na kartézském součinu X1 … XN .

Hra s konstantním součtem: M1(x) + M2(x) + … + MN (x) = konst pro všechna x

Celkový objem výher tedy nezávisí na zvolených strategiích. Tyto hry mají výrazně antagonistický charakter.

Hra s nekonstantním součtem:

M1(x) + M2(x) + … + MN (x) = (x)


Rovnovážné strategie v antagonistickém konfliktu

Uvažujme antagonistický konflikt dvou hráčů:

{Q = {1, 2}; X , Y ; M1(x, y), M2(x, y)},

kde M1(x, y) + M2(x, y) = konst pro všechna x, y.

Strategie x* X, y* Y nazveme rovnovážné, jestliže pro všechna x, y platí současně

M1(x, y*) M1(x*, y*), M2(x*, y) M2(x*, y*)

Podmínky pro rovnovážné strategie ve hře s nulovým součtem:

M(x, y*) M(x*, y*) M (x*, y),

kde M(x, y) = M1(x, y) = – M2 (x, y). Hodnota M(x*, y*) se nazývá cenou hry.

Hra s konstantním součtem je ekvivalentní hře s nulovým součtem, kde M(x, y) = M1(x, y) – M2 (x, y).


Maticová hraMaticová hra je konečná hra dvou hráčů s nulovým součtem,

kde X = {1, 2, … , m}, Y = {1, 2, … , n} a M(i, j) = aij . Matice A = (aij ) typu (m, n) se nazývá maticí hry (tato matice je maticí výplat prvého hráče).

Sedlový prvek: Řekneme, že prvek ars je sedlovým prvkem matice hry, jestliže je současně nejmenší v r-tém řádku a největší v s-tém sloupci, tj. pro všechna i X a j Y platí

ais ars arj

Pokud má matice sedlový prvek, pak tento prvek je cenou maticové hry a jemu odpovídající strategie jsou rovnovážnými strategiemi.

Pokud matice neobsahuje sedlový prvek, hledáme rovnovážné strategie ve smíšeném rozšíření maticové hry.


Smíšené rozšíření maticové hryMějme maticovou hru s prostory strategií X = {1, 2, … , m},

Y = {1, 2, … , n} (tyto strategie označujeme jako ryzí) a s maticí hry A = (aij ) typu (m, n).

Smíšeným rozšířením této maticové hry nazýváme hru dvou hráčů s nulovým součtem s prostory strategií (tyto strategie nazýváme smíšené)

a výplatní funkcí

Smíšená strategie je rozložením pravděpodobnosti na prostoru ryzích strategií.

0xxxm

iimS xxxxX

1

T21 ,1,),,,(

0yyyn

iinS yyyyY

1

T21 ,1,),,,(

Ayxyx T

1 1

),(

m

i

n

jjijiS yaxM


Řešení smíšeného rozšíření maticové hrySmíšené rozšíření každé maticové hry má řešení v rovnovážných

strategiích. Rovnovážné strategie smíšeného rozšíření maticové hry se nezmění, přičteme-li ke každému prvku matice totéž kladné nebo záporné číslo c. Cena hry s takto pozměněnou maticí je potom rovna v + c, kde v je cena původní hry.

Nechť matice A má všechny prvky kladné. Pak rovnovážné smíšené strategie lze najít řešením dvojice duálně sdružených úloh LP:

kde 1 = (1, 1, … , 1)T.

Cena hry w = 1/ (*) = 1/ (*) a rovnovážné strategie x* = w *, y* = w *. Jestliže matice A vznikla z matice jiné hry přičtením konstanty c, pak cena původní hry v = w – c.

0ξ1ξA

ξ

,

min)(

T

1

m

ii

0η1Aη

η

,

max)(1

n

jj


Hry proti příroděHrou proti přírodě rozumíme hru dvou hráčů s nulovým součtem,

z nichž prvý hráč je racionální (inteligentní), tj. snaží se maximalizovat svou výhru, zatímco druhý hráč je indiferentní (neinteligentní), tj. je k výsledku hry lhostejný. Neinteligentního hráče nazýváme přírodou, protože často reprezentuje nějaký přírodní proces.

Rozhodování za rizika:Prvý hráč zná pravděpodobnostní rozdělení, podle něhož příroda volí své strategie (stavy). Pak je možno použít Bayesovo kritérium.

Rozhodování za neurčitosti:Prvý hráč nezná pravděpodobnostní rozdělení, podle nějž příroda volí své stavy. Pak je možno použít např. tato kritéria: Laplaceovo, Waldovo, Savageovo, Hurwiczovo.


Kritéria ve hrách proti příroděMějme maticovou hru proti přírodě s maticí hry A = (aij ) typu (m, n),

přičemž prvý hráč je inteligentní.

Bayesovo kritérium:

kde pj je pravděpodobnost j-tého stavu přírody.

Laplaceovo kritérium:

Waldovo kritérium: Savageovo kritérium: Hurwiczovo kritérium:

kde [0; 1] je jakýmsi ukazatelem optimismu prvého hráče.

n

jjij

ipa

1

max

n

jij

ia

n 1

1max

ijji

aminmax

ij

jij

jiaa min)1(maxmax

)max(maxmin ijkjkji

aa

Date post:	31-Dec-2015
Category:	Documents
Upload:	evan-jimenez
View:	121 times
Download:	6 times

Složité rozhodovací úlohy

Documents