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 = 5 4x1 + x2 + 2x3 + s2 = 11 3x1 + 4x2 + 2x3 + s3 = 8 −5x1 − 4x2 − 3x3 + z = 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
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 (csak a pozitív elemekkel osztunk, a többi hányadost gyelmen kívül hagyjuk), a hányadosokat az utolsó oszlop után írtuk be: s3
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 legkisebb 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
h.
s1
s2
s3
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
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
h.
x1
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
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
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. A fennt ismertetett un. primál szimplex módszer alkalmazható a standard normál maximumfeladat megoldására. Ez a feladat Megjegyzések.
x ≥0 Ax ≤ b, (aholb ≥ 0 c> x = z → max
alakba írható, ahol x = (x1 , . . . , xn )> ∈ Rn×1 a keresett n dimenziós oszlopmátrix/vektor 0 = (0, . . . , 0)> ∈ Rn×1 , az n dimenziós oszlop zérusvektor, az x ≥ 0 egyenl®tlenség koordinátánként (elemenként) értend®, A = (aij ) ∈ Rk×n egy
10
k × n típusú (adott) mátrix, b = (b1 , . . . , bk )> ∈ Rk×1 adott k dimenziós nemnegatív koordinátákkal rendelkez® oszlopmátrix/vektor c = (c1 , . . . , cn )> ∈ Rn×1 egy n dimenziós adott sorvektor, c> = (c1 , . . . , cn ) ∈ R1×n . Feltételezhet®, hogy c> ≥ 0> , c> 6= 0> vagyis a ci értékek között vannak pozitívok, ugyanis ellenkez® esetben x = 0 adja az
optimális megoldást.
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 = maximum, feltéve, hogy 2x1 + 3x2 + x3 4x1 + x2 + 2x3 3x1 + 4x2 + 2x3 x1 , x2 , x3
≤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:
(ö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
11
Bevitel a WinQSB-be mátrixos formátumban:
A megoldás táblázata:
12
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®. 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:
13
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ük 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))
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®).
14
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).
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:
15
• 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álhas-
suk), • 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.
16
Egy termelési feladat.
(ld. Varga J.: Gyakorlati programozás, Tankönyvkiadó, Bp. 1985, 262-268) . 100000m3 tölgyrönköt kell f¶részáruvá feldolgozni 4 üzemben, melyek közel azonos technikai felszereltség¶ek. Mindegyikben 6 féle terméket tudnak el®állítani: I, II, III-adosztályú szelvényárut, dongát, parkettalécet, bányaszéldeszkát és közben fürészpor és darabos hulladék keletkezik. 1. Döntés el®készítése
2.
. E termékek el®állítására öt technológia van. E próbavágások alapján az alábbiak, 1m3 rönkre vonat-
Technológiák számszer¶sítése
technológiák kihozatali kozóan, %-ban Technológiák I. o. szelv.árú II. o. szelv.árú III. o. szelv.árú Donga Parkettaléc Bányaszéldeszka Darabos hulladék Fürészpor
mutatói
I 10 30 20 25 15
II 40 10 40 10
III 50 30 20
IV 10 30 15 4 25 16
V 5 25 15 12 28 15
Az üzemek kapacitása messze meghaladja a feldolgozandó mennyiséget, csupán a parkettagyártó gépsor kapacitása korlátozott évi 10000m3 -re. 3.
Technikai korlátok.
. Az egyes termékekb®l az évi kereslet/terv I.o legalább 1000m3 , II. o. legalább 5000m3 , donga legfeljebb 20000m3 , parkettaléc legalább 5000m3 -t kell el®állítani, és a hulladék (fürészpor és darabos hulladék) nem haladhatja meg a 45%-ot. 4. Keresleti korlátok
, a késztermékek árai:
5. A célt befolyásoló adatok
17
Késztermék Ft/m3 I. o. szelv.árú 3000 II. o. szelv.árú 2400 III. o. szelv.árú 1400 Donga 3500 Parkettaléc 3100 Bányaszéldeszka 1000 Darabos hulladék 500 Fürészpor 100 Így 1m3 rönk feldolgozásával az árbevétel : Techn. Árbevételek (Ft) Össz.(Ft) I. 0,1· 3000+0,3· 2400+0,2· 1400+0,15· 100 1440 +0,25· 500 II. 0,4· 3500+0,1· 3100+0,4· 500+0,1· 100 1920 III. 0,5· 3100+0,3· 500+0,2· 100 1720 IV. 0,1· 3000+0,3· 2400+0,15· 3100+0,04· 1000 1666 +0,16· 100+0,25· 500 V. 0,05· 3000+0,25· 2400+0,15· 3500+0,12· 3100 1802 +0,15· 100+0,28· 500 6. Matematikai modell.
Legyen x1 , x2 , x3 , x4 , x5 az egyes technológiák szerint felvágandó rönk mennyisége m3 -ben, akkor
18
x1 , x2 , x3 , x4 , x5 ≥ 0
nemnegativitás
0, 1x1 + 0, 1x4 + 0, 05x5 ≥ 1000
I.oszt. terv
0, 3x1 + 0, 3x4 + 0, 25x5 ≥ 5000
II.oszt. terv
0, 4x2 + 0, 15x5 ≤ 20000
donga tervkorl.
0, 1x2 + 0, 5x3 + 0, 15x4 + 0, 12x5 ≥ 5000
park.léc terv
0, 1x2 + 0, 5x3 + 0, 15x4 + 0, 12x5 ≤ 10000
park.léc kapac.
0, 4x1 + 0, 5x2 + 0, 5x3 + 0, 41x4 + 0, 43x5 ≤ 45000
hulladék
x1 + x2 + x3 + x4 + x5 = 100000 teljes készlet
Az
, azaz a célfüggvény:
árbevétel maximalizálása a cél
1440x1 + 1920x2 + 1720x3 + 1666x4 + 1802x5 = z → max
Megoldás: Bevitel a WinQSB programba:(FAUZEM.LPP)
19
A megoldás a program segítségével:
20
Combined Report for fauzem5 13:40:22 Decision
Solution
Variable
Value
Sunday
February
15
Unit Cost or Profit c(j)
Total
Reduced
Basis
Allowable Allowable
Contribution
Cost
Status
Min. c(j)
Max. c(j)
17,454,550. 52,363,630. 0
basic basic at bound
-M 1,741.667 -M
1,731.2 2,073.867 2,543.03
at bound
-M
1,770.909
basic
1,744.3
2,016.00
1 X1 2 X2 3 X3
12,121.21 27,272.72 0
1,440. 1,920. 1,720.
4 X4
0
1,666.
5 X5
60,606.06
1,802.
0 0 823.0303 0 104.9091 109,212,100. 0
Function
(Max.) =
179,030,300.
Objective
1 2 3 4 5 6 7
2009
Left Hand Constraint Side
Right Hand Direction Side
Slack or Surplus
Shadow Price
Allowable Allowable Min. RHS Max. RHS
C1 C2 C3 C4 C5 C6 C7
>= >= <= >= <= <= =
3,242.424 13,787.88 0 5,000.00 0 454.5451 0
0 0 648.4848 0 2,206.061 0 1,440.00
-M -M 12,500. -M 5,000.002 44,545.45 87,878.79
4,242.424 18,787.88 20,000.00 10,000.00 10,000.00 44,545.45 100,000.00
1,000. 5,000. 20,000. 5,000. 10,000. 45,000. 100,000.
4,242.424 18,787.88 21,666.67 10,000.00 11,600.00 M 101,136.4
21
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 −823, 03, 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) −823, 03a3 -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 648, 48, ami azt jelenti, hogy ha C3 jobboldalát b3 -mal megnöveljük, (esetünkben 20000 + b3 -ra) akkor az célfüggvény értéke (közelít®leg) 648, 48b3 -mal n®. Az utolsó két oszlop 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ó 7 sora azt mutatja, hogy a korlátozó feltétel jobboldala milyen határok között változhat, ahhoz, hogy még létezzen optimális megoldás.
A megoldás értelmezése: x1 x2 x3 x4 x5
= 12121 = 27273 =0 =0 = 60606
els® technológiával felvágandó második technológiával felvágandó harmadik technológiával felvágandó negyedik technológiával felvágandó ötödik technológiával felvágandó
Árbevétel 179 030 412 Ft Gyártott termékek: I.oszt. 0, 1 · 12121 + 0, 1 · 0 + 0, 05 · 60606 = 4242 = 1000+többlet, II.oszt. 0, 3 · 12121 + 0, 3 · 0 + 0, 25 · 60606 = 18787, 8 = 5000+ többlet, III.oszt. 0, 2 · 12121 = 2424, 2, Donga 0, 4 · 27273 + 0, 15 · 60606 = 20000, Parkettaléc 0, 1 · 27273 + 0, 5 · 0 + 0, 15 · 0 + 0, 12 · 60606 = 10000 = 5000+ többlet, Bányaszéldeszka 0, 04 · 0 = 0, Hulladék 0, 4·12121+0, 5·27273+0, 05·0+0, 41·0+0, 43·60606 = 44545, 48 = 45000hiány. Túlteljesítések: I.oszt. 3242 II. oszt. 13788 Dongából a megengedett 20000-t termeljük Parkettalécb®l 5000-rel túlteljesítjük a tervet, és a teljes kapacitást kihasználjuk.
22
A hulladék 45% alatt van. 1m3 rönköt 1790,30 Ft áron értékesítjük.
A modell módosításai: 1. Ha a II. oszt. árúból 13788m3 eladhatatlan, csak 11000 adható el, akkor módosítani kell a problémát, egy új feltétel közbeiktatásával: 0, 3x1 + 0, 3x4 + 0, 25x5 ≤ 11000
Az új probléma lehet megoldhatatlan, kaphatunk új optimumot. 2. Ha pl. bányaszéldeszkából 1000m3 -re van igény, akkor az új feltétel 0, 04x4 ≥ 1000
3. Ha a hulladékra nem teszünk kikötést akkor eggyel kevesebb feltételünk lesz, az optimális megoldás magasabb célértéket eredményezhet. 4. Az is el®fordulhat, hogy az egyes f¶részüzemek technikai színvonala különböz®, ekkor szét kell osztanunk a gyártandó termékeket az üzemek között, feltéve, hogy az összkapacitásuk meghaladja a feldolgozandó nyersanyagot.
