Kvantitatív módszerek II. Fejezetek az operációkutatásból

Kvantitatív módszerek II. Fejezetek az operációkutatásból Szerzők: Bakos Viktor Bánhalmi Árpád Fejes Ferenc Dr. Fenyves Ferenc Horváth Gézáné dr. Pákolicz Orsolya

OPCIM4ED

2011. július 29. –20:17 (1. lap 1. oldal)

Kvantitatív módszerek II. Fejezetek az operációkutatásból Szerzők:

Bakos Viktor Bánhalmi Árpád Fejes Ferenc Dr. Fenyves Ferenc Horváth Gézáné dr. Pákolicz Orsolya

PR-405-II/11

OPCIM4ED

2011. július 29. –20:17 (3. lap 3. oldal)

Szerzők:

c Bakos Viktor 2011. (1. fejezet)

c Bánhalmi Árpád 2011. (5. fejezet)

c Fejes Ferenc 2011. (2. és 3. fejezet)

c Dr. Fenyves Ferenc 2011. (1. fejezet)

c Horváth Gézáné dr. 2011. (6. fejezet)

c Pákolicz Orsolya 2011. (4. fejezet) Alkotó szerkesztő Horváth Gézáné dr. ISBN 978-963-394-677-0 A kiadvány szerzői jogi védelem alatt áll, arról másolat készítése a kiadó előzetes írásbeli engedélye nélkül tilos. A kiadvány másolása és jogosulatlan felhasználása bűncselekmény! Kiadja a Perfekt Gazdasági Tanácsadó Oktató és Kiadó Zártkörűen Működő Részvénytársaság a Sanoma company A kiadásért felelős: Kiss János Tamás vezérigazgató Borítóterv: Korda Ágnes Felelős szerkesztő: Budavári Andrea Műszaki szerkesztő: Fried Katalin Terjedelem: (A/5) ív Prospektkop Nyomda A kiadványt újrahasznosított papírra nyomtattuk.

OPCIM4ED

2011. július 29. –20:17 (4. lap 4. oldal)

TARTALOM Bevezetés : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

7

1. A lineáris algebra alapjai (Dr. Fenyves Ferenc) : : : : : : : : : : : : : : : : : :

9

1.1. Mátrixaritmetika : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

9

1.2. Lineáris terek (vektorterek) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

26

1.3. Elemi bázistranszformáció (Bakos Viktor) : : : : : : : : : : : : : : : : : : : :

32

1.4. Mátrixaritmetikai példák : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

41

1.5. Gazdasági feladatok megoldása mátrixaritmetikával : : : : : : : : : : :

44

1.6. Feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

55

1.7. Megoldások az 1. fejezet feladataihoz : : : : : : : : : : : : : : : : : : : : : : : : :

65

2. Bevezetés a lineáris programozásba (Fejes Ferenc) : : : : : : : : : : : : : : : 75 2.1. Lineáris modellek : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

77

2.2. Grafikus módszer : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

79

2.3. Dualitás : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

87

2.4. Többváltozós lineáris programozási feladat : : : : : : : : : : : : : : : : : : : :

93

2.5. Szimplex módszer : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

95

2.6. Feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 107 2.7. Megoldások a 2. fejezet feladataihoz : : : : : : : : : : : : : : : : : : : : : : : : : : 118 3. Hozzárendelési feladat (Fejes Ferenc) : : : : : : : : : : : : : : : : : : : : : : : : : : : : 138 3.1. Magyar módszer : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 140 3.2. Feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 148 3.3. Megoldások a 3. fejezet feladataihoz : : : : : : : : : : : : : : : : : : : : : : : : : : 152 4. Szállítási feladat (Pákolicz Orsolya) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 163 4.1. A kiegyensúlyozott feladat matematikai modellje : : : : : : : : : : : : : : 163 4.2. Nem kiegyensúlyozott szállítási feladatok : : : : : : : : : : : : : : : : : : : : : 173 4.3. Szállítási modellek további vizsgálata : : : : : : : : : : : : : : : : : : : : : : : : : 175 4.4. Feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 178 4.5. Megoldások a 4. fejezet feladataihoz : : : : : : : : : : : : : : : : : : : : : : : : : : 182 5

OPCIM4ED

2011. július 29. –20:17 (5. lap 5. oldal)

KVANTITATÍV MÓDSZEREK

5. Hálótervezés (Bánhalmi Árpád) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 185 5.1. Irányított gráfok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 185 5.2. Súlyozott élű irányított gráfok mátrixreprezentációja

::::::::::

187

5.3. Hálótervezés : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 189 5.4. A háló kiértékelése : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 192 5.5. Feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 201 5.6. Megoldások az 5. fejezet feladataihoz : : : : : : : : : : : : : : : : : : : : : : : : : 205 6. Döntésanalízis döntési fa alkalmazásával (Dr. Horváth Gézáné Ph.D) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 213 6.1. Bayes-elemzés szerepe a döntéshozatalban : : : : : : : : : : : : : : : : : : : : 213 6.2. Egyszerű döntési diagram szerkesztésének bemutatása : : : : : : : : : 215 6.3. A Bayes-tételen alapuló döntési modell : : : : : : : : : : : : : : : : : : : : : : : 217 6.4. Esettanulmány a Bayes-döntési modell bemutatására : : : : : : : : : : 231 6.5. Feladatok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 237 6.6. Megoldások a 6. fejezet feladataihoz : : : : : : : : : : : : : : : : : : : : : : : : : : 243

6

OPCIM4ED

2011. július 29. –20:17 (6. lap 6. oldal)

BEVEZETÉS Ez a könyv bővített és átdolgozott kiadása a 2005-ben megjelent Kvantitatív módszerek II. tankönyvnek. Az új kiadás a bolonyai képzés operációkutatás tananyagát – az eredetihez képest kibővítve – tárgyalja. Mielőtt ezekkel a módszerekkel foglalkozunk, tisztáznunk kell az operációkutatás fogalmát. Több évtized elteltével sem sikerült minden szakembert kielégítő definíciót adni erre a fogalomra. A sokféle definíció közül vizsgáljunk meg néhány számunkra megfelelőt. „Az operációkutatás a döntés előkészítés tudománya.” Ez a definíció keveset árul el magáról az operációkutatásról; csupán azt jelzi, hogy milyen célra használható. „Az operációkutatás az a tudomány, amely az optimális döntések előkészítésében matematikai módszereket használ.” Az optimális szóval utalás történik a döntés előkészítés minőségére, illetve ebből a definícióból megtudjuk, hogy ez az új tudományág kapcsolatban van a matematikával. „Az operációkutatás tudományos módszerek alkalmazása az ipar, a kereskedelem, az államigazgatás és a honvédelem területén, olyan komplex problémák megoldására, amelyek emberekből, gépekből, anyagokból és pénzeszközökből álló nagy rendszerek irányítása és vezetése során lépnek fel.” Ebből a definícióból kitűnik, hogy az operációkutatás mely területeken alkalmazható, amelyeket a XXI. században kiegészíthetünk a szolgáltatások további területeivel is (oktatás, egészségügy, kultúra stb.). További információ, hogy ez a tudomány komplex, bonyolult problémáknak, nagy rendszereknek az optimális megoldását keresi. Az operációkutatás kezdettől olyan team munkát jelent, amelyben a matematikus a különböző szakterületek gazdasági, számítástechnikai szakembereivel együtt dolgozik. Az új tudományág határterület a matematika, a gazdaságtudomány és a számítástudomány között. Az operációkutatás középpontjában a közgazdasági és a matematikai modell áll. Hosszú az út a döntési probléma megfogalmazásától a modell megalkotásáig. A feladat a probléma részletes leírásával – a változók, a korlátozó feltételek megadásával – kezdődik, majd a célra vonatkozó ismeretek mélyítésével, pontosításával folytatódik. A szükséges adatok megszerzése és pontosságuknak ellenőrzése után következik az adott körülményeknek 7

OPCIM4ED

2011. július 29. –20:17 (7. lap 7. oldal)

KVANTITATÍV MÓDSZEREK

legjobban megfelelő modell számszerűsítése és megoldása. A modell helyességét a gyakorlattal való egybevetéssel ellenőrizzük. A döntéshozó szempontjából a modelleknek kettős hasznuk van. Egyik oldalról a döntéshozó a rendszer részletekbe menő vizsgálatára kényszerül; a modell előkészítése során fel kell tárnia a rendszer összefüggéseit, és így a modell a gazdasági folyamat elemzésének eszközévé válik. Másrészt viszont az operációkutatási modell alkalmas a vizsgált paraméterek különböző kritériumok szerinti optimális értékeinek meghatározására, ezért képes a döntés orientálására is. Könyvünk a gazdasági felsőoktatás hallgatóit bevezeti a lineáris algebrai alapok után (amit kibővítettünk az elemi bázistranszformáció eljárásának és alkalmazásainak bemutatásával) a lineáris programozásba, a hozzárendelési probléma modellezésébe, a szállítási probléma disztribúciós megoldásába, a hálótervezésbe és a Bayes-döntésanalízisbe. A fejezetek végén található feladatok és azok részletes megoldásai hozzásegítik a BA képzések hallgatóit a sikeres megmérettetéshez. A szerzők várják és előre köszönik a tisztelt Olvasók észrevételeit, megjegyzéseit. Budapest, 2011. május A szerkesztő BGF KKK Módszertani Intézeti Tanszéki Osztály

8

OPCIM4ED

2011. július 29. –20:17 (8. lap 8. oldal)

A BAYES-TÉTELEN ALAPULÓ DÖNTÉSI MODELL s1

= 7000

P s1

( ) = 015

s2

= 8000

P s2

56 000 a0

megrendel

( ) = 045 64 000

s3

= 8000

( ) = 0 4

P s3

72 000 s1

= 7000

P s1

( ) = 015

s2

= 8000

P s2

42 500 a1

gyártás

(automata)

( ) = 045 47 500

s3

= 8000

( ) = 0 4

P s3

52 500 s1

= 7000

P s1

( ) = 015

s2

= 8000

P s2

46 000 a2

gyártás

(hagyományos)

( ) = 045 52 000

s3

= 8000

( ) = 0 4

P s3

58 000

6.2. ábra Döntési fa a „vásárolni, vagy gyártani” jellegű problémához

M (C 2 ) = 015 · 46 000 + 045 · 52 000 + 040 · 58 000 = 53 500 A legalacsonyabb várható költsége az automata gépsoron történő gyártásnak van, tehát a legkedvezőbb az a1 döntési alternatíva.

6.3. A BAYES-TÉTELEN ALAPULÓ DÖNTÉSI MODELL Az üzleti életben rendszeresen előforduló, nagy kockázattal járó döntési helyzetek megoldásához – az összes lehetséges információt figyelembe vevő leghatékonyabb eszköz a Bayes-tételen alapuló döntési modell. A módszer lényege, hogy az a priori (előzetes) valszn sgek és az ehhez további informcik beszerzésével meghatározható feltteles valszn sgek birtokban a Bayes-tétel alkalmazásával a posteriori (utólagos, felülvizsgált) valszn sgek és feltteles valszn sgek szmthatk. Ezek a posteriori, többlet információt tartalmazó valszn sgek rszei a Bayes-dntsi modell bemeneteli adatainak. Jelölje a döntési modellben: 217

6FEJ

2011. július 26. –11:06 (5. lap 217. oldal)

DÖNTÉSANALÍZIS DÖNTÉSI FA ALKALMAZÁSÁVAL

az (e ) információszerzésre vonatkozó = {e1 e2 : : : ek };

dntsi lehetsgek halmazt

E

=

beszerezhet informcik összes lehetséges (z ) kimenetelnek halmazt Z = {z0 z1 : : : zl }; az (a ) döntési változók halmazát A = {a0 a1 : : : am }; a döntéseket követő (s )esemnyek halmazt S = {s1 s2 : : : sn }! a

A Bayes-dntsi modell strukt rja döntési diagrammal reprezentálható. A dntsi diagram, fa csompontokbl: kezdőpontból, elágazási pontokból, végpontokból; gakbl s utakbl ll. Bizonyos csomópontokat g köt össze. Az t a kezdőpontból valamely végpontba vezető ágak egymásutánja. s1

s2 e0

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

v e0 z0 a1 s1

a1

z0

v e0 z0 a1 s2

a0

s0

v e0 z0 a0 s0

s1

v e1 z1 a1 s1

a1 s2 z1

v e1 z1 a1 s2

a0

s0

v e1 z1 a0 s0 e1 s1

v e1 z2 a1 s1

a1 s2 z2

v e1 z2 a1 s2

a0

s0

v e1 z2 a0 s0

kezd˝opont

elágazási pontok

végpontok

utak

6.3. ábra Döntési diagram szerkezete A kezdőpontból kiinduló ágak az információszerzésre vonatkozó döntési változó (e ) értékeit jelzik és az információ megszerzésének a költségét is 218

6FEJ

2011. július 26. –11:06 (6. lap 218. oldal)

A BAYES-TÉTELEN ALAPULÓ DÖNTÉSI MODELL

tartalmazzák. Ezen elágazási pontokat követő ágak a beszerezhető információk kimeneteleit (zj ) jelölik, és a P (zj ) valószínűségeket is tartalmazzák minden j -re. A következő lépcsőben az újabb elágazási pontokból induló ágak a döntési változó (a ) lehetséges értékeit, a cselekvési lehetőségeket reprezentálják. Az utolsó szintnél minden elágazási pontból a lehetséges (si ) események ágaznak ki P (si ) valószínűségeivel vagy P (si | zj ) feltételes valószínűségeivel. A végpontokhoz v (s ) becsült nyereség, illetve veszteség értékek rendelhetők. A végpontok v (e z a s ) utakkal azonosíthatók. A döntési probléma megoldását a döntési fa számszerűsítésével kezdjük. Ezt követően minden elágazási pontra ki kell számítani a várható nyereség/veszteség értékét. Az egyes döntési pontokban a legnagyobb értéket választva, majd a fán tovább haladva ezeket kell versenyeztetni. Végül a nem tökéletes ei információ értéke az ei (i = 0) ághoz tartozó maximális várható nyereség érték és az e0 (nincs többlet információ) ágon elérhető maximális nyereség várható értéke különbségeként megbecsülhető, és összehasonlítandó az ei információ költségével. A döntési fa alkalmazható a termelés, a szolgáltatás, a marketingkutatás és az üzleti élet egyéb területein. Az oktatásban, az egészségügyben és a politikában is széles körben alkalmazható a döntések megalapozott előkészítésére. A továbbiakban először egy egyszer bb esetet trgyalunk. A döntési diagram szerkezete egyszerűbbé válik, ha pl. termel vllalatok kapacitsnak bvtsekor a menedzsment a döntés-előkészítésbe külső céget nem von be. A döntési modell ilyenkor nem tartalmazza az információszerzésre vonatkozó e döntési változót és a beszerezhető információ zj lehetséges kimeneteleit.

A döntési fa kezdőpontjából az a döntési változó (kapacitásbővítés) értékeihez tartozó ágak indulnak ki és ezek mindegyikéhez elágazási pontok tartoznak. Az elágazási pontokból kiinduló ágak jelölik a döntést követő eseményeket a hozzájuk rendelt P (si ) szubjektív valószínűségekkel. A v (si ) végpontokhoz a becsült nyereség értékek tartoznak. A végpontok v (aj si ) utakkal azonosíthatók. 6.1. példa. A) A „Csepel” Kerékpárgyár főmérnökének egy fontos alkatrész gyártásáról, vagy beszállítatásáról kell döntenie. Ez a döntés és az elérhető profit nagysága összefügg az újonnan kifejlesztett kerékpár iránt várható kereslettel.

219

6FEJ

2011. július 26. –11:06 (7. lap 219. oldal)


Az alábbi táblázat tartalmazza a becsült profitot, illetve veszteséget 1000 ban a döntési alternatíva és a kereslet nagyságának függvényében. Döntési lehetőségek Gyártás (a1 ) Beszerzés (a2 )

alacsony (s1 ) −20 10

Kereslet nagysága közepes (s2 ) magas (s3 ) 40 100 45 70

Az új kerékpár iránti kereslet valószínűsége, ha a kereslet alacsony 035, ha a kereslet közepes 035, ha a kereslet magas 030. Keresse meg az optimális döntési alternatívát döntési fa alkalmazásával!

Megolds. A modell változóinak és eseményeinek halmaza:

S = {s1 s2 s3 }.

A = {a0 a1 },

Az alkatrészellátásra vonatkozó döntések:

a1 : „Csepel” Kerékpárgyár állítja elő a2 : Beszállítóval gyártatja le

Lehetséges események és valószínűségei:

s1 : alacsony kereslet P (s1 ) = 035 s2 : közepes kereslet P (s2 ) = 035 s3 : magas kereslet P (s3 ) = 030

A döntési fa kezdőpontja: dntsi pont. A döntési pontból a1 a2 döntési változatoknak megfelelő ágak indulnak ki. Az ágak csomópontokban végződnek. A döntési fa csomópontjaiból a döntéshozótól és a döntéstől független s1 , s2 , s3 eseményeknek megfelelő ágak következnek. Mivel ezen események vala-

melyike a majdani döntéstől függetlenül bekövetkezik, ezért mind a három döntési alternatívát P (si ) valószínűséggel követik az si események. Az események ágai végpontokban végződnek. Ezekhez a végpontokhoz hozzárendeljük a várható nyereségeket, illetve veszteséget. A döntési fánknak hat végpontja van. A döntési diagram információinak felhasználásával az egyes döntési alternatívákhoz kiszámíthatjuk a várható nyereség értékét. M (a1 ) = 035 · (−20 000) + 035 · 40 000 + 030 · 100 000 = 37 000

M (a2 ) = 035 · (10 000) + 035 · 45 000 + 030 · 70 000 = 40 250

A várható nyereség értéke magasabb, ha beszállítókkal gyártatják az alkatrészt. 220

6FEJ

2011. július 26. –11:06 (8. lap 220. oldal)


Gyártás

Nyereség

Kereslet alacsony

P s1

közepes

P s2

( ) = 035

−20 000

( ) = 035 40 000

magas

( ) = 030

P s3

100 000

alacsony

P s1

( ) = 035

közepes

P s2

10 000 Rendelés

( ) = 035 45 000

magas

( ) = 030

P s3

70 000

6.4. ábra. Döntési fa „vásárolni vagy gyártani” jellegű problémához 6.1. példa. B) A „Csepel” Kerékpárgyár főmérnöke nincs megelégedve az egyszerű döntési modell alapján készített döntés megalapozottságával. Kíváncsi, hogy megérné-e a cégnek egy előzetes piackutatást lebonyolítani. Ismeretes a marketing osztály eddigi sokéves tevékenysége alapján, hogy magas kereslet esetén 06 valószínűséggel lesz kedvező a piackutatás eredménye; közepes kereslet esetén 06 valószínűséggel lesz kedvezőtlen ez; és alacsony kereslet mellett 09 valószínűséggel lesz kedvezőtlen a piackutatás eredménye. Mi a valószínűsége, hogy a piackutató részleg jelentése kedvező? Mi a cég optimális stratégiája a Bayes-döntési fa kiértékelése alapján?

Megolds. A modell változóinak és eseményeinek halmaza bővül:

E = {e1 e2 : : : ek }

Z = {z0 z1 : : : zl }:

Az előzetes információszerzésére vonatkozó döntés:

e0 : nem alkalmazunk előzetes vizsgálatot, e1 : megszervezzük az előzetes piackutatást. A beszerezhető információk kimenetele:

z0 : a piackutatás eredménye kedvezőtlen, z1 : a piackutatás eredménye kedvező. Rajzoljuk fel a Bayes-döntési fát! (6.5. ábra)

A Bayes-döntési fa e1 ágának számszerűsítéséhez szükségünk van a valszn sgi fa megrajzolsra s az inverz feltteles valszn sgek kiszmtsra. 221

6FEJ

2011. július 26. –11:06 (9. lap 221. oldal)

DÖNTÉSANALÍZIS DÖNTÉSI FA ALKALMAZÁSÁVAL ( ) = 035 ( ) = 035 P (s3 ) = 030 P s1

M

−20 000 40 000 100 000

P s2

a1

(e0 ) = 40 250 ( ) = 035 ( ) = 035 P (s3 ) = 030 P s1

10 000 45 000 70 000

P s2

a2 e0

( | z0 ) ( | z0 ) P ( s3 | z0 ) P s1

−20 000 40 000 100 000

P s2

a1

( ) = 0645

P z0

( | z0 ) ( | z0 ) P ( s3 | z0 ) P s1

e1

10 000 45 000 70 000

P s2

a2

( | z1 ) ( | z1 ) P ( s3 | z1 ) P s1

−20 000 40 000 100 000

P s2

a1

( ) = 0355

P z1

( | z1 ) ( | z1 ) P ( s3 | z1 ) P s1

10 000 45 000 70 000

P s2

a2

6.5. ábra. Bayes-döntési fa struktúrája (hiányzó valószínűségekkel) A rendelkezésünkre álló valószínűségek P (s1 ) = 035, P (s2 ) = 035, P (s3 ) = = 030

A feltételes valószínűségek: P (z1 | s3 ) = 06, P (z1 | s2 ) = 04, = 01, P (z0 | s3 ) = 04, P (z0 | s2 ) = 06, P (z0 | s1 ) = 09

P ( z 1 | s1 ) =

Számszerűsítsük a valószínűségi fát! (6.6. ábra) P z0

(

| s1 ) = 0 9

P z1

(

| s1 ) = 0 1

P z0

(

| s1 ) = 0 6

P z1

(

| s2 ) = 0 4

P z0

(

| s3 ) = 0 4

(

| s3 ) = 0 6

( ) = 035

P s1

( ) = 035

P s2

( ) = 030

P s3

P z1

P s1

(

∩ z0 ) = 0315

P s1

(

| z0 ) = 0488

(

∩ z1 ) = 0035

P s1

(

| z1 ) = 0099

P s2

(

∩ z0 ) = 021

P s2

(

| z0 ) = 0326

P s2

(

∩ z1 ) = 014

P s2

(

| z1 ) = 0394

P s3

(

∩ z0 ) = 012

P s3

(

| z0 ) = 0186

(

∩ z1 ) = 018

P s3

(

| z1 ) = 0507

P s1

P s3

6.6. ábra. Valószínűségi fa

222

6FEJ

2011. július 26. –11:06 (10. lap 222. oldal)

A BAYES-TÉTELEN ALAPULÓ DÖNTÉSI MODELL ( ) = 035 ( ) = 035 P (s3 ) = 030 P s1 a1

M

P s2

(e0 ) = 40 250 ( ) = 035 ( ) = 035 P (s3 ) = 030 P s1 a2

e0

P s2

( | z0 ) = 0488 ( | z0 ) = 0326 P (s3 | z0 ) = 0186 P s1

a1

( ) = 0645

P z0

P s2

( | z0 ) = 0488 ( | z0 ) = 0326 P (s3 | z0 ) = 0186 P s1

e1

a2

P s2

( | z1 ) = 0099 ( | z1 ) = 0394 P (s3 | z1 ) = 0507 P s1

a1

( ) = 0355

P z1

P s2

( | z1 ) = 0099 ( | z1 ) = 0394 P (s3 | z1 ) = 0507 P s1

a2

P s2

−20 000 40 000 100 000 10 000 45 000 70 000 −20 000 40 000 100 000 100 000 45 000 70 000 −20 000 40 000 100 000 10 000 45 000 70 000

6.7. ábra. Bayes-döntési fa Az input adatok ismeretében rajzoljuk fel és számszerűsítsük a Bayesdöntési fát! (6.7. ábra)

z0 ágon: M (a1 | z0 ) = 0488 · (−20) + 0326 · 40 + 0186 · 100 = 2188 ezer M (a2 | z0 ) = 0488 · 10 + 0326 · 45 + 0186 · 70 = 3257 ezer A várható nyereség a z1 ágon: M (a1 | z1 ) = 0099 · (−20) + 0394 · 40 + 0507 · 100 = 6448 ezer M (a2 | z1 ) = 0099 · 10 + 0394 · 45 + 0507 · 70 = 5421 ezer A várható nyereség az e1 ágon: M (e1 ) = 0655 · 3257 + 0355 · 6448 = 44 22375 ezer A várható nyereség a

A Bayes-döntési modell kiértékelése alapján javasolható, hogy végeztessék el az előzetes piackutatást, és annak kedvező kimenetele esetén a „Csepel” Kerékpárgyárban gyártsák le az adott alkatrészeket; amennyiben a piackutatási eredmény kedvezőtlen, érdemes beszállítóra bízni a gyártást.

223

6FEJ

2011. július 26. –11:06 (11. lap 223. oldal)


6.2. példa. Az University Press könyvkiadó szerkesztője megkapta a „Bevezetés az operációkutatásba” című egyetemi tankönyv kéziratát. A szerkesztő már ismeri a szerzőket, a könyv sikerét 065 valószínűségűre becsülte. Ha a tankönyv sikeres lesz, akkor a várható profit 750 000 . Ha a kiadó a tankönyv kiadása mellett dönt és ez a hallgatók körében nem arat sikert, akkor 250 000 veszteségre számítanak. Mielőtt a kiadásról döntenének, lehetőség van a kézirat felülvizsgálatára. A felülvizsgálati folyamat kimenetele lehet kedvező vagy kedvezőtlen. Múltbeli tapasztalatok alapján annak a valószínűsége, hogy a felülvizsgálati folyamat eredménye kedvező, feltéve, hogy a könyv sikeres 0,7; annak a valószínűsége, hogy a felülvizsgálati folyamat eredménye kedvezőtlen, feltéve, hogy a könyv nem arat sikert 0,75. Szerkesszük meg a Bayes-döntési fát, feltételezve, hogy először dönteni kell a kézirat felülvizsgálatáról, illetve annak elfogadásáról, vagy visszautasításáról! Elemezzük ki a döntési fát és határozzuk meg az optimális stratégiát a kiadó részére! Ha a kézirat felülvizsgálata 5000 -ba kerül, akkor miként alakul a javaslat?

Megolds. A modell változóinak és eseményeinek a halmaza:

E = {e0 e1 }

A = {a0 a1 }

Z = {z0 z1 }

S = {s0 s1 }:

A kézirat felülvizsgálatára vonatkozó döntési alternatívák:

e0 : nem küldik a kéziratot felülvizsgálatra; e1 : megrendelik a kézirat felülvizsgálatát.

A kézirat kiadására vonatkozó döntési alternatívák:

a0 : nem fogadják el a kéziratot kiadásra; a1 : kiadják az egyetemi tankönyvet,

A kézirat felülvizsgálatának lehetséges eredménye:

z0 : kedvezőtlen; z1 : kedvező.

Az egyetemi tankönyv iránti kereslet:

s0 : a könyv nem lesz sikeres az egyetemi hallgatók körében; ennek valószínűsége 035, a várható veszteség 250 000 . s1 : a tankönyv sikert arat; ennek valószínűsége 065, a várható profit 750 000 .

224

6FEJ

2011. július 26. –11:06 (12. lap 224. oldal)


Adottak továbbá a következő a priori valószínűségek: P (z1 | s1 ) = 07, P (z0 | s0 ) = 075, amelyekből kiszámíthatók a komplementer feltételes valószínűségek: P (z0 | s1 ) = 03, P (z1 | s0 ) = 025. (6.8. ábra) a0

0 ( ) = 035

P s0

−250 000

a1

( ) = 065

P s1

e0

( )

P z1

e1

( )

P z0

P s0

(

| z1 )

P s1

(

| z1 )

P s0

(

| z0 )

(

| z0 )

P s1

750 000 0 −250 000 750 000 0 −250 000 750 000

6.8. ábra. Bayes-döntési fa szerkezete Az a priori P (si ) valószínűségek revíziója elvégezhető a felülvizsgálatra vonatkozó feltételes valószínűségek formájában megadott referenciák (új információk) figyelembevételével. Az a priori P (si ) valószínűségek a Bayestétel alkalmazásával meghatározott, nagyobb biztonságot adó P (si | zj ) a posteriori valószínűségekkel helyettesíthetők a döntési fa számszerűsítésénél. Tehát írjuk fel a rendelkezésre álló valószínűségek segítségével a valószínűségi fát! (6.9. ábra) P z1

(

| s1 ) = 025

(

| s0 ) = 075

P z1

(

| s1 ) = 0 7

(

| s1 ) = 0 3

P s0

(

∩ z1 ) = 00875

P s0

(

∩ z0 ) = 02625

P s1

(

∩ z1 ) = 04550

(

∩ z0 ) = 01950

( ) = 035

P s0

P z0

( ) = 065

P s1

P z0

P s1

6.9. ábra. Valószínűségi fa 225

6FEJ

2011. július 26. –11:06 (13. lap 225. oldal)


A valószínűségi fából kiszámítható, hogy milyen valószínűséggel lesz a piackutatás eredménye kedvező P (z1 ), illetve kedvezőtlen P (z2 ).

P (z1 ) = P (s1 ∩ z1 ) + P (s2 ∩ z1 ) = 05425 P (z2 ) = 1 − P (z1 ) = 04575 A valószínűségi fa alapján egyszerűen meghatározhatók az a posteriori valószínűségek, amelyek a döntési fa döntési alternatíváit követő eseményekhez rendelendők.

P (s1 | z1 ) = P (Ps1(z∩ )z1 ) = 08387 P (s0 | z1 ) = P (Ps0(z∩ )z1 ) = 01613 1 1 P (s1 ∩ z0 ) P (s0 ∩ z0 ) P (s1 | z0 ) = P (z ) = 04262 P (s0 | z0 ) = P (z ) = 05738 0 0 2

Most már képesek vagyunk számszerűsíteni a Bayes-döntési fát. (6.10. ábra) a0

0 ( ) = 035

400 000

P s0

−250 000

a1

( ) = 065

P s1

e0

394 98725

a0

( ) = 04575

P z0

750 000 0

P s0

(

| z0 ) = 05738

P s1

(

| z0 ) = 04262

P s0

(

| z1 ) = 01613

(

| z1 ) = 08387

−250 000

a1 e1

750 000 0

( ) = 05425

P z1

P s1

−250 000

750 000

6.10. ábra. Bayes-döntési fa

M (e 0 ) >M (e 1 ). Teljesen fölösleges a kézirat felülvizsgálatára pénzt és időt pazarolni, hiszen mindenképpen a kiadás mellett kell dönteni a Bayesmodell alapján is. Ezt a döntést a szerkesztő bátran vállalhatja. A Bayesdöntési fa eredményeivel az University Press menedzsmentje is meggyőzhető a szerkesztő döntésének helyességéről. 226

6FEJ

2011. július 26. –11:06 (14. lap 226. oldal)


6.3. példa. A) Egy szolgáltató cég felméréseik kiértékelésére számítógépes rendszert akar telepíteni. A cél a rendszer méretének optimalizálása. Dönteni kell nagyméretű, közepes méretű, vagy kisméretű rendszer lízingelése között. A döntési alternatíva kiválasztása a cég szolgáltatása iránt várhatóan jelentkező alacsony, vagy magas igénytől függ. A szakemberek a magas igény bekövetkezésének valószínűségét 30%-ra becsülik. Az alábbi táblázat tartalmazza a nyereség várható nagyságát a döntési alternatívák és a lehetséges események szerint csoportosítva. Döntési alternatíva Magas várható igény Alacsony várható igény Nagyméretű rendszer 200 000 −20 000 Közepes méretű rendszer 150 000 20 000 Kisméretű rendszer 100 000 60 000 Rajzoljuk fel a döntési fát, és határozzuk meg a kiépítendő számítógépes rendszer optimális méretét!

Megolds. A döntési alternatívák:

a1 : nagyméretű számítógépes rendszer lízingelése, a2 : közepes méretű számítógépes rendszer lízingelése, a3 : kisméretű számítógépes rendszer lízingelése. Az si esemény lehetséges kimenetelei: s1 : az igény magas a cég szolgáltatásai iránt P (s1 ) = 030, s2 : az igény alacsony a cég szolgáltatásai iránt P (s2 ) = 070.

Az egyes ágakhoz tartozó várható nyereség nagyságának számítása:

M (a1 ) = 03 · 20 0000 + 07 · (−20 000) = 46 000 M (a2 ) = 03 · 15 0000 + 07 · 20 000 = 59 000 M (a3 ) = 03 · 10 0000 + 07 · 60 000 = 72 000 A legkedvezőbb döntés: a kisméretű rendszer kiépítése. (6.11. ábra) Újabb információk beszerzésével pontosítani lehet a kereslet nagyságára vonatkozó valószínűségeket. 6.3. példa. B) [Módosított változata a 6.3. példa A) pontjának] Tegyük fel, hogy a szolgáltató cég felkér egy piackutató szakembert, hogy végezzen vizsgálatot a bevezetendő új szolgáltatások potenciális felhasználóira vonatkozóan! 227

6FEJ

2011. július 26. –11:06 (15. lap 227. oldal)

DÖNTÉSANALÍZIS DÖNTÉSI FA ALKALMAZÁSÁVAL Várható profit 46 000 a1 nagy

59 000 a2 k¨ ozepes

72 000 kicsi

Profit ( ) = 03

s1

P s1

s2

P s2

s1

P s1

s2

P s2

s1

P s1

s2

P s2

200 000

( ) = 07

−20 000

( ) = 03

150 000

( ) = 07

20 000

( ) = 03

100 000

a3

( ) = 07

60 000

6.11. ábra. Döntési fa A piackutatói vizsgálat új információi – feltételes valószínűségek – az a priori P (si ) valószínűségekkel együtt a Bayes-tétel alkalmazása után a poszteriori valószínűségeket eredményeznek, amelyek pontosítják a cég becslését a várható kereslet nagyságára vonatkozóan. A piackutató szakember vizsgálatának eredménye lehet kedvező (z1 ) és kedvezőtlen (z0 ). A kapott eredményeket táblázatba rendeztük. Az új információk feltételes valószínűségek formájában: Események

Piackutatási eredmény kedvező ( z1 ) A várható kereslet magas (s1 ) P (z1 | s1 ) = 08 A várható kereslet alacsony (s2 ) P (z1 | s2 ) = 01

Piackutatási eredmény kedvezőtlen ( z0 ) P (z0 | s1 ) = 02 P (z0 | s2 ) = 09

Rajzoljuk fel a döntési fát, és adjuk meg az optimális döntési változatot!

Megolds. Az új információk figyelembevétele mellett a döntési diagram szerkezete az alábbiak szerint módosul (6.12. ábra):

Az a priori P (si ) valószínűségek revíziója elvégezhető a piackutatás eredményeinek figyelembevételével. Az a priori P (si )valószínűségek a Bayestétel alkalmazásával meghatározott, nagyobb biztonságot adó P (si | zj ) a posteriori valószínűségekkel helyettesíthetők a döntési fa számszerűsítésénél (6.13. ábra).

228

6FEJ

2011. július 26. –11:06 (16. lap 228. oldal)

A BAYES-TÉTELEN ALAPULÓ DÖNTÉSI MODELL s1

200 000

a1 s2

−20 000 150 000

s1 z1

a2 s2

20 000 100 000

s1 a3 s2

60 000 200 000

s1 a1 s2

−20 000 150 000

s1 z2

a2 s2

20 000 100 000

s1 a3 s2

60 000

6.12. ábra. A döntési diagram (e1 ) új ágának szerkezete P z1

(

| s1 ) = 08

P z0

(

| s1 ) = 02

P z1

(

| s2 ) = 01

(

| s2 ) = 09

P s1

(

∩ z1 ) = 024

P s1

(

∩ z2 ) = 006

P s2

(

∩ z1 ) = 007

(

∩ z2 ) = 063

( ) = 0 3

P s1

( ) = 0 7

P s2

P z0

P s2

6.13. ábra. Valószínűségi fa A döntési fából kiszámítható, hogy milyen valószínűséggel lesz a piackutatás eredménye kedvező P (z1 ), illetve kedvezőtlen P (z0 ).

P (z1 ) = P (s1 ∩ z1 ) + P (s2 ∩ z1 ) = 031

P (z0 ) = 1 − P (z1 ) = 069

A valószínűségi fa alapján egyszerűen meghatározhatók a posteriori valószínűségek, amelyek a döntési fa döntési alternatíváit követő eseményekhez rendelendők. P (s1 | z1 ) = P (Ps1(z∩ )z1 ) = 07742 P (s2 | z1 ) = P (Ps2(z∩ )z1 ) = 02258 1 1 P (s1 ∩ z0 ) P (s2 ∩ z0 ) P (s1 | z0 ) = P (z ) = 0087 P (s2 | z0 ) = P (z ) = 0913 0 0 229

6FEJ

2011. július 26. –11:06 (17. lap 229. oldal)


A várható nyereség nagysága a z1 ágon: M (a1 | z1 ) = 0772 · 200 + 0228 · (−20) = 15 0324

M (a2 | z1 ) = 0772 · 150 + 0228 · 20 = 120 645 M (a3 | z1 ) = 0772 · 100 + 0228 · 60 = 90 968 A várható nyereség nagysága a z0 ágon: M (a1 | z0 ) = 0913 · 200 + 0087 · (−20) = −860 M (a2 | z0 ) = 0913 · 150 + 0087 · 20 = 31 310 M (a3 | z0 ) = 0913 · 100 + 0087 · 60 = 63 480 M (e1 ) = 031 · 15 0324 + 069 · 63 480 = 90 401

A szolgáltató cég döntési stratégiája a döntési alternatívákhoz kiszámított várható nyereség értékei alapján (6.14. ábra): Várható profit 150 324

( ) = 031

s1

s2

a1

P z1

profit

a2

120 646

s1

s2 a3

z1

90 968

s1

s2

−860 z0

s2

a1

( ) = 069

P z0

s1

a2

31 310

s1

s2 a3

63 480

s1

s2

P s1

(

| z1 ) = 07742

P s2

(

| z1 ) = 02258

P s1

(

| z1 ) = 07742

P s2

(

| z1 ) = 02258

P s1

(

| z1 ) = 07742

(

| z1 ) = 02258

P s1

(

| z0 ) = 0913

P s2

(

| z0 ) = 0087

P s1

(

| z0 ) = 0913

P s2

(

| z0 ) = 0087

P s1

(

| z0 ) = 0913

(

| z0 ) = 0087

P s2

P s2

200 000 −20 000 150 000 20 000 100 000 60 000 200 000 −20 000 150 000 20 000 100 000 60 000

6.14. ábra. Döntési fa (e1 ) előzetes vizsgálat esetére vonatkozó ága • ha a piackutatás eredménye kedvező, akkor ajánlott egy nagy kapacitású számítógépes rendszer lízingelése; • ha a piackutatás eredménye kedvezőtlen, akkor kis kapacitású számítógépes rendszer kiépítése is elegendő. 230

6FEJ

2011. július 26. –11:06 (18. lap 230. oldal)

Kvantitatív módszerek II. Fejezetek az operációkutatásból

Recommend Documents