A DÖNTÉSELMÉLET ELEMEI
Irodalom: Temesi J., A döntéselmélet alapjai, Aula, 2002, Budapest Lawrence, J.A., Pasternack, B.A., Applied management science, John Wiley & Sons Inc. 2002 Stevenson, W. J., Operation management, McGraw-Hill, Irvin, 2008 Decision theory: web Google keresés= 87,2 millió találat Döntéselmélet: web Google keresés= 22,6 ezer találat Döntéselmélet néhány területe: • orvosi, • jogi, bírói, • közgazdasági, • m¶szaki, • egyéb. Módszerek és a kapcsolódó fontosabb szoftverek • AHP analytic hierarchy process (Saaty, 1980, EC expert choice) • PROMETHEE preference ranking organization method for enrichment evaluation (Brans, 1982, Decision Lab) • GAIA geometric analysis for interactive assistance (Marechal, Brans, 1988,Decision Lab) • WINGDSS, Sztaki • WinQSB (Quantitative System for Business) decision analysis (Yih-Long Chang, Georgia Institute of Technology)
1
2
1. ALAPFOGALMAK
(ld. Temesi J.: A döntéselmélet alapjai, 11-13) 1.1 Néhány jellemz® döntési probléma
Cselekvéseinket döntések irányítják. Nagyon gyakran kerülünk döntési (kényszer)helyzetbe. Néha azonnal kell dönteni, máskor lehet®ségünk van (s®t kényszerítve vagyunk) átgondolt, indokolt döntéseket hozni.
1. Termelési feladat: többféle termék el®állításának mennyiségér®l döntünk.
Cél a maximális pro t, vagy maximális pro t minimális környezeti károsítással, vagy maximális pro t minimális munkaer® felhasználásával.
2. Befektetési feladat: maximális hozamot biztosító portfolio kiválasztása.
Korlátok: pénzügyi, szempontok: óvatosság vagy kockázat, befektetés id®tartama.
3. Iskola választási probléma: új lakóhelyre költözünk és keressük a legjobb
iskolát. Szempontok: lakástól való távolság, iskola színvonala, tandíj, zsúfoltság, iskola felszereltsége: sport, számítógépes hálózat.
4. Szemétéget® telepítése.
Szempontok: technológia, helyi munkaer®, költségek, környezeti feltételek, lakossági hozzáállás.
5. Közbeszerzési pályázat kiértékelése.
Pl. banki számítógépes tender értékelése. Szempontok: ár, hardver min®sége, szolgáltatási feltételek, garanciális feltételek, betanítás. Minden esetben a cél egyetlen cselekvés (a legjobb termelési terv, legjobb befektetés, iskola stb.) kiválasztása.
3
1.2 Matematikai programozás, feltételes széls®értékszámítás
Döntési változók: x = (x1 , . . . , xn ) ∈ Rn egy n-dimenziós vektorba foglalva, Feltételek leírása: adott gi : Rn → R i = 1, . . . , k + l függvények segítségével gi (x) = 0
(i = 1, . . . , k); k < n
gj (x) ≤ 0
(j = k + 1, . . . , k + l);
egyenl®ség típusú feltételek egyenl®tlenség típusú feltételek
Döntési halmaz: alternatívák halmaza gi (x) = 0, i = 1, . . . , k,
( X=
)
x ∈ Rn : gj (x) ≤ 0 j = k + 1, . . . , k + l.
Egyetlen célfüggvény: f (x) = max ha, x ∈ X Mivel f (x) = min ⇔ −f (x) = max, ha, x ∈ X, ezért elegend® csak max keresésével foglalkozni. Megoldás: lineáris vagy egész programozás, feltételes széls®értékszámítás. Példa lineáris programozásra (két változó, gra kus megoldás):(ELOAD1.LPP)
x1 , x2 ≥ 0, x1 + 2x2 ≥ 6 x2 − x1 ≤ 3 x1 + x2 ≤ 10 2x1 − 3x2 = z → max vagy min
4
Az egyenl®tlenségrendszernek elegettev® pontok halmaza egy sokszög mely az ábrán színezve van. A 2x1 − 3x2 = z egyeneseket valamely z = konstans esetén ábrázolva párhuzamos egyeneseket kapunk (ábránkon a z = 20, 6, −12, 5 egyeneseket rajzoltuk be. z maximális értékét akkor kapjuk, ha az egyenes átmegy a (10, 0) csúcsponton, minimális értékét pedig akkor kapjuk, ha az egyenes átmegy a (3, 5, 6, 5) csúcsponton, zmax = 20, zmin = −12, 5. Megoldás:
5
Több változó esetén a szimplex módszert használhatjuk. Példaként tekintsük a következ® LP feladatot: z = 5x1 + 4x2 + 3x3 2x1 + 3x2 + x3 4x1 + x2 + 2x3 3x1 + 4x2 + 2x3 x1 , x2 , x3
= maximum, feltéve, hogy ≤5 ≤ 11 ≤8 ≥0
Vezessük be a s1 , s2 , s3 hiányváltozókat (a feltételi egyenl®tlenségek jobb- és baloldalának különbségét (angolul: slack variable, slack=er®tlen, laza, pangó, slacks=hosszú nadrág, pantalló). Ezek segítségével az eredetivel ekvivalens probléma: z s1 s2 s3
= 5x1 + 4x2 + 3x3 = maximum, feltéve, hogy = 5 − 2x1 − 3x2 − x3 = 11 − 4x1 − x2 − 2x3 = 8 − 3x1 − 4x2 − 2x3 x1 , x2 , x3 , s1 , s2 , s3 ≥ 0
Itt a s1 , s2 , s3 változókat bázisváltozóknak, x1 , x2 , x3 -at nembázis változóknak nevezük. Induljunk ki az x1 = x2 = x3 = 0 megoldásból, ekkor s1 = 5, s2 = 11, s3 = 8 és a célfüggvény z = 0.Próbáljunk egy jobb megoldást keresni. Mivel a célfüggvényben x1 együtthatója pozitív, ezért x1 értékét megnövelve z értéke n®. De x1 értékét nem növelhetjük akármekkorára, mert a hiányváltozóknak nemnegatíveknek kell maradniuk. Ha x1 ≥ 0, x2 = x3 = 0 akkor az s1 = 5 − 2x1 ≥ 0 s2 = 11 − 4x1 ≥ 0 s3 = 8 − 3x1 ≥ 0
x1 ≤ 25 = 2, 5 x1 ≤ 11 4 = 2, 75 8 x1 ≤ 3 = 2, 66..
egyenl®tlenségek mindegyikének teljesülnie kell ezért 0 ≤ x1 ≤ 2, 5 azaz x1 -et legfeljebb 2, 5-re növelhetjük. Legyen tehát 5 1 x1 = , x2 = x3 = 0 akkor s1 = 0, s2 = 1, s3 = 2 2 z értéke 5 ·
5 2
= 12, 5-re n®tt.
6
Hogyan tovább? Mivel most s1 = x2 = x3 = 0 így x1 szerepét s1 veszi át, a célfüggvényt és a feltételeket át kell írnunk ennek megfelel®en. A s1 de níciójából x1 = 2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3
ezt a célfüggvénybe, s2 , s3 -ba helyettesítve kapjuk, hogy z = 5 (2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3 ) + 4x2 + 3x3 = 12, 5 − 2, 5s1 − 3, 5x2 + 0, 5x3 s2 = 11 − 4 (2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3 ) − x2 − 2x3 = 1 + 2s1 + 5x2 s3 = 8 − 3 (2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3 ) − 4x2 − 2x3 = 0, 5 + 1, 5s1 + 0, 5x2 − 0, 5x3
Az új változókkal a problémánk: z x1 s2 s3
= 12, 5 − 2, 5s1 − 3, 5x2 + 0, 5x3 = maximum, feltéve, hogy = 2, 5 − 0, 5s1 − 1, 5x2 − 0, 5x3 = 1 + 2s1 + 5x2 = 0, 5 + 1, 5s1 + 0, 5x2 − 0, 5x3 s1 , x2 , x3 , x1 , s2 , s3 ≥ 0
Ismét látható, hogy s1 = x2 = x3 = 0 esetén x1 = 2, 5, s2 = 1, s3 = 0, 5 és z = 12, 5. Mivel most a célfüggvényben egyedül x3 együtthatója pozitív, ennek növelésével növelhetjük a célfüggvényt. Mennyivel növelhetjük? Az x3 ≥ 0, s1 = x2 = 0-nál az x1 , s2 , s3 ≥ 0 feltételekb®l x1 = 2, 5 − 0, 5x3 ≥ 0 x3 ≤ 5 s2 = 1 ≥ 0 ez minden x3 esetén teljesül s3 = 0, 5 − 0, 5x3 ≥ 0 x3 ≤ 1
ezért x3 = 1 s3 = 0 és s1 = x2 = 0, a célfüggvény 0, 5 · 1 = 0, 5-del n®, 13-ra. Az új (nembázis, vagy független) változók s1 , x2 , s3 , az x3 szerepét s3 veszi át. Mivel a s3 = 0, 5 + 1, 5s1 + 0, 5x2 − 0, 5x3 egyenletb®l x3 = 1 + 3s1 + x2 − 2s3
ezt behelyettítve z, x1 , s2 -be (végezze el a számításokat!) kapjuk, az új változókkal felírt problémát: z x1 s2 s3
= 13 − s1 − 3x2 − s3 = maximum, feltéve, hogy = 2 − 2s1 − 2x2 + s3 = 1 + 2s1 + 5x2 = 1 + 3s1 + x2 − 2s3 s1 , x2 , s3 , x1 , s2 , x3 ≥ 0
7
Most már nincs pozitív együttható z képletében, nem tudjuk z -t növelni. Mivel s1 , x2 , s3 ≥ 0 ezért z = 13 − s1 − 3x2 − s3 ≤ 13, de s1 = x2 = s3 = 0 (míg x1 , s2 , x3 értékeit az el®z® képletekb®l számolhatjuk) mellett z = 13 így az optimális megoldás z = 13.
Az el®z®kben tárgyalt feladat szimplex táblája az s1 , s2 , s2 hiányváltozók bevezetése utáni rendszer 2x1 + 3x2 + x3 + s1 4x1 + x2 + 2x3 + s2 3x1 + 4x2 + 2x3 + s3 −5x1 − 4x2 − 3x3 + z
=5 = 11 =8 =0
(ahol x1 , x2 , x3 , s1 , s2 , s3 ≥ 0 és a z maximumát keressük) együtthatóinak mátrixából áll: x1 x2 x3 s1 2 3 1 s2 4 1 2 s3 3 4 2 z −5 −4 −3
s1 1 0 0 0
s2 0 1 0 0
s3 0 0 1 0
z 5 11 8 0
A táblázat sorainak, oszlopainak jelölését, a célfüggvényt és az egyenletek jobboldalán álló számokat egy-egy vonallal elválasztottuk. 1. lépés. El®ször megkeressük a pivot elemet (pivot= forgó, forgócsap, to pivot on forog vmi körül), a belép® változót és az elhagyott változót. Kiválasztjuk az alsó sor "legnegativabb" elemét (azaz a legnagyobb abszolút érték¶ negatív elemet) ez példánkban −5. Ha több ilyen is van akkor nem számít melyiket választjuk. Ennek az oszlopa lesz a pivot oszlop. Ezután a az utolsó oszlop minden elemét osztjuk a pivot oszlop megfelel® elemével, a hányadosokat az utolsó oszlop után írtuk be: s3 z h.
x1
x2
x3
s1
s2
s1
2
3
1
1
0
0 5
5 2
s2
4
1
2
0
1
0 11
11 4
s3
3
4
2
0
0
1 8
8 3
z −5 −4 −3
0
0
0 0
= 2, 5
pivot sor
= 2, 75 = 2, 66
A hányadosok közül megkeressük a legkisebbiket (ha több ilyen is van, akkor mindegy melyiket vesszük) ennek sora a pivot sor nálunk a legkissebb hányados 2,5 az els®
8
sorban így a pivot sor az els® sor. A pivot elem a pivot sorban és pivot oszlopban lév® elem, nálunk 2. A belép® változó a pivot oszlopnak megfelel® változó (nálunk x1 ), a kilép® változó a pivot sornak megfelel® változó (nálunk s1 ). 2.
lépés.
elemmel:
Most a pivotálás következik. A pivot sor elemeit elosztjuk a pivot x1
x2
x3
s3
z
h.
s1
s2
s1
1 1, 5 0, 5 0, 5
0
0 2, 5
5 2
s2
4
1
2
0
1
0 11
11 4
s3
3
4
2
0
0
1
8
8 3
z −5 −4 −3
0
0
0
0
= 2, 5
pivot sor
= 2, 75 = 2, 66
majd e sor alkalmas többszöröseit a többi sorból levonva elérjük, hogy a pivot oszlop többi elemei zérusok legyenek. Nálunk az els® sor négyszeresét kell levonni a második sorból, majd az els® sor háromszorosát kell levonni a harmadik sorból, végül az els® sor ötszörösét kell az utolsó sorhoz hozzáadni. A kilép® változó nevét a belép®vel kell helyettesíteni. Az így kapott táblázat x1
x2
x3
s1
s2
x1
1
1, 5
0, 5
0, 5
0
0 2, 5
s2
0
−5
0
−2
1
0
s3
0 −0, 5
0, 5 −1, 5
0
1 0, 5
0
0 12, 5
z
0
3, 5 −0, 5
2, 5
s3
z
1
Ezután ismételjük az 1. és 2. lépést az új táblázattal mindaddig amíg az utolsó sor elemei nemnegatívak vagy zérusok lesznek. Ekkor az optimális megoldás a jobboldali oszlopból olvasható le. Táblázatunkban a -0,5 oszlopa lesz a pivot oszlop, a pivot sort pedig ismét az utolsó oszlop és a pivot oszlop megfelel® elemeinek hányadosai közül a legkisebb hányados sora adja (csak pozitív elemekkel osztunk), esetünkben a harmadik sor. A belép® változó a pivot oszlopnak megfelel® változó (nálunk x3 ), a kilép® változó a pivot sornak megfelel® változó (nálunk s3 ).
9
x2
x3
s1
s2
x1
1
1, 5
0, 5
0, 5
0
0 2, 5
2,5 0,5
s2
0
−5
0
−2
1
0
−
s3
0 −0, 5
0, 5 −1, 5
0
1 0, 5
0
0 12, 5
z
0
3, 5 −0, 5
2, 5
s3
h.
x1
z
1
0,5 0,5
=5
=1
pivot sor
A harmadik sort 0,5-tel elosztjuk, majd az így kapott sor 0,5-szeresét az els®b®l levonjuk és az utolsó sorból is levonjuk. A kapott táblázat (melyb®l az utolsó oszlop hányadosait lehagytuk) x1
x2 x3
2
s3 z
0 −1 2
1
s2
0 −5
0 −2
1
0 1
x3
0 −1
1 −3
0
2 1
0
0
0
1 13
3
0
s2
x1
z
2
s1
1
Mivel az utolsó oszlopban már nincs negatív elem, ezért a megoldás befejez®dött, z maximális értéke 13, és a baloldali oszlopban szerepl® változók optimális értékeit a z oszlopból olvashatjuk le azaz most x1 = 2, s2 = 1, x3 = 1 a többi változó optimális értéke zérus, azaz x2 = s1 = s3 = 0. Több változó (szimplex módszer, ill.megoldás komputerrel, szoftver pl WinQSB) El®ször bemutatjuk a fenti feladat azaz a z = 5x1 + 4x2 + 3x3 2x1 + 3x2 + x3 4x1 + x2 + 2x3 3x1 + 4x2 + 2x3 x1 , x2 , x3
= maximum, feltéve, hogy ≤5 ≤ 11 ≤8 ≥0
LP feladat megoldását a WinQSB szoftverrel. Az adatbevitel (mátrixos formában) és a megoldás táblázata:
10
(öt változó, megoldás WinQSB-vel ):(ELOAD1B.LPP) x1 , x2 , x3 , x4 , x5 ≥ 0, x1 + 2x3 − 2x4 + 3x5 x1 + 3x2 + x3 + x5 x2 + x3 + x4 2x1 + 2x3
≤ 60 ≤ 12 ≤ 10 ≤ 20
3x1 + 4x2 + 5x3 + 3x4 − 2x5 = z → max vagy min
Bevitel a WinQSB-be mátrixos formátumban:
11
A megoldás táblázata:
A megoldás táblázatában a redukált költség nulla érték¶ célváltozóknál szerepel, és azt mutatja, hogy hogyan változik a célfüggvény értéke, ha az illet® célváltozóra pozitív értéket követelünk meg. Például, x3 = 0-nál a redukált költség −1, ami azt jelenti, hogy ha x3 ≥ 0 helyett x3 ≥ a3 (> 0)-t követeljük meg, akkor az célfüggvény értéke (közelít®leg) −a3 -mal változik. Egy feltételnél szerepl® árnyékár azt mutatja meg, hogy a feltétel jobboldalán álló konstans változása hogyan hat a célfüggvény értékére. Például, a C3 feltételnél az árnyékár 3, ami azt jelenti, hogy ha C3 jobboldalát b3 -mal megnöveljük, (esetünkben 10 + b3 -ra) akkor az célfüggvény értéke (közelít®leg) 3b3 -mal n®.
12
Az utolsó két oszlop fels® 1-5 sorai azt mutatják, hogy a célfüggvényben az illet® célváltozó együtthatója milyen határok között változhat ahhoz, hogy még létezzen optimális megoldás. Az utolsó két oszlop utolsó 4 sora azt mutatja, hogy a korlátozó feltételek jobboldalai milyen határok között változhatnak, ahhoz, hogy még létezzen optimális megoldás. További megjegyzések: El®fordulhat az, hogy a lineáris programozási feladatnak több megoldása van. Példaként tekintsük a (ELOAD2.LPP) x1 , x2 , x3 , x4 ≥ 0 x1 − x2 + x3 ≤ 8 x2 + x3 − x4 ≤ 11 x1 + 2x2 − x3 + x4 ≤ 10 z = 6x1 + 2x2 + 5x3 + 7x4 → max
feladatot. Ennek két bázismegoldása van (0, 0, 8, 18) és (0, 7, 15, 11) és nyilván ezek konvex kombinációja, azaz λ(0, 0, 8, 18)+(1−λ)(0, 7, 15, 11) bármely λ ∈ [0, 1] mellett is megoldás. Megtörténhet az is, hogy nincs megoldás, erre példa a (ELOAD3.LPP) x1 , x2 ≥ 0 x1 + x2 ≤ 120 x1 ≤ 90 12x1 + 12x2 ≥ 1680 z = 14x1 + 6x2 → max
feladat. Így el®fordulhat, hogy a döntési probléma megoldáshoz pótlólagos információra van szükségünk, vagy pedig a feltételeinken kell enyhítenünk. Ez vezetett el a célprogramozáshoz, ahol a célokat ket részre osztjuk, egy részük szigorúan betartandó, a másik részü csak egy bizonyos szinten tartandó be. Egy másik lehet®ség a többcélú programozás. Ha több célfüggvényünk van, melyeket egy vektorba foglalunk f (x) = (f1 (x), )f2 (x), . . . , fk (x))
13
akkor a max f (x) x∈X
maximumprobléma megoldása egy un. Pareto-optimális megoldás ez olyan x∗ vektort (vagy vektorokat) jelent melyekhez nem tudunk megadni (nem létezik) olyan ˆ ∈ X , hogy f (ˆ x x) ≥ f (x∗ ) és f (ˆ x) 6= f (x∗ ) teljesül (vektorok egyenl®tlensége koordinánként értend®). Mivel a Pareto optimális megoldások halmaza gyakran végtelen, így annak megkeresése nem adja meg a döntési probléma megoldását. Ezért egy un. kompromisszumos megoldást keresünk • • • •
súlyozásos módszerrel, lexikográ kus módszerrel, korlátok módszerével, kompromisszumprogramozás elvével.
Súlyozásnál az egyes célfüggvényeket fontossági súlyokkal látjuk el, és pl. súlyozott
átlagként vagy összegként egyetlen célfüggvényt alkotunk. Lexikográ kus módszernél el®ször a legfontosabb cél szerint értékelünk, ha egy megoldás van akkor készen is vagyunk, ha több akkor ezeket a fontosságban következ® szempont szerint értékeljük, és így tovább. A korlátok módszerénél egy kivételével az összes többi célt valamely kívánatos korlát segítségével beépítjük a feltételi rendszerbe. A kompromisszumprogramozásban olyan döntést választunk, mely az ideális (minden cél szerint a legjobb, és általában nem létez®) változathoz legközelebb esik. 1.3 Alapfogalmak
(ld. Temesi J.: A döntéselmélet alapjai, 18-20)
Alternatívák: a különböz® döntési lehet®ségek, ezek halmaza a döntési tér. Leírásuk: explicit (pl. felsorolás), vagy implicit. Jellemz®ik: • • • •
számosság, számszer¶síthet®ség, kölcsönkapcsolatok (függetlenség), bizonytalanság (véletlent®l való függés).
14
Célok (kritériumok,értékelési tényez®k): azok az irányok, amerre a rendszert
vinni szeretnénk. Ezek sok esetben nem feltétlenül elérhet®, vagy számszer¶síthet® kívánságokat jelentenek. Hierarchikusan elrendezve ®ket, a legmagasabb szinten lev®k általában kevésbé operácionálisak, az alacsonyabban lév® kritériumok már kezelhet®k, míg a legalacsonyabb szinten lév®k, mint számszer¶ értékelési tényez®k jelennek meg. Az értékelési tényez®knek rendelkezniük kell az alábbi tulajdonságokkal: • teljesség (egyetlen fontos tényez® se maradjon ki), • operácionalizálhatóság (elemzésre alkalmas legyen), • felbonthatóság (az alternatívákat az adott tényez® szerint külön is vizsgálhassuk), • redundancia kisz¶rése (felesleges, ismétl®d® szempont elhagyása), • minimalitás (ne legyen ugyanolyan jó, de kisebb elemszámú tényez®halmaz),
Döntéshozók: azok a személyek, akik felel®sek
• az információk megadásáért, • az alternatívák meghatározásáért, kiértékeléséért, • a megoldás realizálásáért.
Döntéshozó magatartása: racionális (optimalizálásra törekszik), vagy irracionális. A döntéshozó a problémák egy részét objektíven látja (együtthatók, mérések eredményei, számított értékek), másik részét preferenciák adják.
Magatartástudomány: a döntéshozókra a korlátozott racionalitás elve érvényesül. Döntési folyamat: • • • • • •
döntési szituáció keletkezése (kon iktus feloldása), döntési probléma megfogalmazása, döntési probléma formalizálása (pl. matematikailag), döntési probléma módszerének megválasztása, megoldás: egyetlen cselekvés kiválasztása, adaptálás, értékelés, elemzés: helyes volt-e a döntés, vagy újra kell kezdeni.
