Sorbanállási modellek

Döntéselőkészítés VIII. előadás

Döntéselőkészítés

Sorbanállási modellek Sorbanállás: A sorbanállás, a várakozás általános probléma közlekedés, vásárlás, tankolás, étterem, javításra várás, stb. Ezen feladatok elmélete és gyakorlata a matematikai közgazdaságtan önálló területe.


1

Két alapvető kérdést kell megválaszolni: • mikor következik be és milyen időtartamú a sorbanállás, • a leggazdaságosabban hogyan oldható meg a sorbanállás mérséklése, illetve kiküszöbölése. A továbbiakban a sorbanállási problémák elméletébe történő bevezetés a cél 4 alapvető modellel fogunk megismerkedni.


Alapfogalmak: Kiszolgálóhelyre bizonyos egységek ( emberek, gépkocsik, stb. ) szabályos, vagy szabálytalan időközökben érkeznek.Ezeket az egységeket röviden beérkezéseknek nevezzük. A kiszolgálóhelyeken az igényelt tevékenység végrehajtására egy vagy több ún. kiszolgálási csatorna áll a beérkezések rendelkezésére. A kiszolgálási csatornára várakozók sorokat alkotnak. Döntéselőkészítés

2

Alapfogalmak: (postai példa)

kollégiumok

Pénztár1

tanulmányi ép.

Pénztár2

igazgatási ép. források

sorok

kiszolgáló csatornák


Sorbanállási rendszer = sorok + kiszolgáló csatornák Sorbanállási rendszerek leglényegesebb jellemzője: • beérkezések közötti időtartam, • kiszolgálás időtartama. Ezek lehetnek: • állandó értékek, • determinisztikusan változó értékek, • sztochasztikusan változó (ismert valószínűségi eloszlással rendelkező valószínűségi változó). Döntéselőkészítés

3

Mikor keletkezhet sor? • Beérkezések közötti időtartam és a kiszolgálás időtartama állandó, de a beérkezések közötti időtartam rövidebb, mint a kiszolgálás időtartama nem foglakozunk vele, modellezésre nincs szükség. • Beérkezések és/vagy a kiszolgálás időtartama valószínűségi változó.


További osztályozás: • korlátos forrású vagy nem korlátos forrású rendszer (előfizetéses menza, menzai étkezés) • zárt vagy nyílt sorbanállási rendszer (Egy üzemben a gépek meghibásodásával kapcsolatos sorbanállási rendszerek zártak, mert a megjavított gépek visszakerülve a termelésbe újra meghibásodhatnak ellenkező esetben, ha a kiszolgálást követően nem jöhet létre körfolyamat, nyílt a rendszer.) • egy csatornás vagy több csatornás rendszer ( egy pénztár, vagy több pénztár esete) Döntéselőkészítés

4

Példák: Kiszolgálás jellege

Beérkezések

Kiszolgálási csatornák

telefonálás

telefonhívások

telefon-áramkörök

javítás

gépmeghibásodás

szerelők

gyártás

rendelés

mühelyek

kiszolgálás

vevők

eladók

utazás

utasok

tömegközlekedési eszközök

vendéglátás

vendégek

pincérek

kirakodás

hajók

dokkok


Jelölések (pl. egy termelő üzem esetén) : m - az egységek száma a vizsgált jelenség egészében (m végtelen is lehet) pl.: egy gyárban található gépek száma n - beérkezések száma a rendszerben (a sorban állók és a kiszolgálásban részesülők száma együttesen) pl.: a meghibásodott gépek száma v – beérkezések száma a sorban pl.: javításra váró gépek száma j – a kiszolgálásban részesülő egységek száma pl.: a javítás alatt levő gépek száma Döntéselőkészítés

5

Jelölések: S – a kiszolgáló csatornák száma pl.: a szerelők száma a gyárban - az üresen álló csatornák száma pl.: azon szerelők száma, akiknek nincs munkájuk Mi a továbbiakban olyan esetekkel foglalkozunk, amikor • n, v, j valószínűségi változók (ismert eloszlással – ezen eloszlásokat kísérletekkel, megfigyelésekkel határozzák meg) • várakozó sor hossza nem korlátozott. Döntéselőkészítés

Jelölések: csatornák

források sor(ok)

S-a csatornák száma

v-beérkezések a sorban j-egységek kiszolgálás alatt n-beérkezések a rendszerben m-egységek a vizsgált jelenség egészében Döntéselőkészítés

6

Felmerülő kérdések: • Mennyi az átlagosan a rendszerben tartózkodók száma? M(n) = ? ( a rendszerben levő egységek várható értéke) • Mennyi átlagosan a sorban álló egységek száma? M(v) = ? ( a sorban álló egységek várható értéke) • Átlagosan hány csatorna áll üresen? M( ) = ? ( az üres csatornák várható értéke) • Mi alapján döntsük el a kiszolgáló egységek (csatornák) optimális számát?


Emlékeztető várható érték számítására: Vegyük például a kocka dobást. Lehetséges dobások: 1 dobása 2 dobása 3 dobása 4 dobása 5 dobása 6 dobása

Ezek valószínüsége: p1 =1/6 Dobások várható értéke: p2 =1/6 M=1*1/6+2*1/6+3*1/6+ p3 =1/6 4*1/6+5*1/6+6*1/6=21/6 p4 =1/6 p5 =1/6 Általában a várható érték: p6 =1/6 M= kimenetelek értéke*hozzájuk tartozó valószínűség értéke Döntéselőkészítés

7

Tegyük fel: minden csatornában az egyszerre kiszolgáltak száma egy. • Ekkor ha n S, akkor n=j. (Rendszerben levő egyedek száma megegyezik a kiszolgálási csatornákban levő egyedek számával). Az is fennáll, hogy n+ =S. • Ha n>S, valamint =0, akkor S=j és n=v+j, azaz ha a csatornák száma kisebb a rendszerben levő egységek számánál, akkor várakozó sor keletkezik. A továbbiakban még azt is feltesszük, hogy egy sorral van dolgunk. Döntéselőkészítés

Várható értékek számítása: Tegyük fel, ismert annak a valószínűsége, hogy n beérkezés történt pn . Tehát ismertek a 0 p0, 1 p1, 2

p2, 3

p3, … , n

pn, … , m

pm értékek.

A rendszerben levők lehetséges száma: 0, 1 , 2 , 3 , … , n, … , m Ekkor a sorbanállási rendszerben levők várható értéke: m

n * pn

M(n)= 0*p0 + 1*p1 + 2*p2 + . . . + m*pm = n 0


8

Várható értékek számítása: Tehát ismertek az egyes beérkezések valószínüségi értékei: 0 p0, 1 p1, 2 p2, 3 p3, … , n pn, … , m pm . A várakozó sorban levők lehetséges száma: 0, 1 , 2 , 3 , … , n, … , m-S, és a hozzájuk tartozó valószínüségek: pS, pS+1, pS+2, pS+3, … , pm A várakozó sorban tartózkodó egyedek számának várható értéke: m

M(v)= 0*ps + 1*ps+1 + 2*ps+2 + . . . + (m-S)*pm = (n S ) * p n n S


Várható értékek számítása: Tehát ismertek az egyes beérkezések valószínüségi értékei 0 p0, 1 p1, 2 p2, 3 p3, … , n pn, … , m pm . Az üres csatornák lehetséges száma: 0, 1 , 2 , 3 , … , n, … , S, és a hozzájuk tartozó valószínüségek: pS, pS-1, pS-2, pS-3, … , p0 Az üresen álló csatornák számának várható érték: M( )= 0*pS + 1*pS-1 + 2*pS-2 + . . . + S*p0 = S

S

n * pS n 0

(S n ) * p n

n n 0


9

Igazolható az alábbi összefüggés: M(n) + M( ) = M(v) + S A továbbiakban az alábbi sorbanállási modellekkel foglalkozunk: • nem korlátos forrású rendszer ( m • egy csatornás rendszer ( S=1 ) • több csatornás rendszer ( S>1 )

esete )

• korlátos forrású rendszer ( m adott érték ) • egy csatornás rendszer ( S=1 ) • több csatornás rendszer ( S>1 ) Döntéselőkészítés

Csatornák optimális számának meghatározása: Elv: költség minimalizálás. c1

jelölje azt az időegységre vonatkozó fajlagos költséget, amely abból adódik, hogy az egyed a kiszolgáló központban (sorbanállási rendszerben) tölti az időt.

(kiesik a munkából az egyed) c2

jelölje egy csatorna időegységre vonatkozó fajlagos fenntartási és üzemeltetési költségét.

Cél: kétféle költség összegének minimalizálása! K = c1*M(n) + c2*S

min


10

Csatornák optimális számának meghatározása: Elv: költség minimalizálás. Ha csak a veszteségidőket vesszük figyelembe, akkor az egyedek (ügyfelek) részéről a várakozó sorban eltöltött idő, a kiszolgáló központ részéről az üresjárati idő (csatornák állás ideje) a meghatározó.

c1’, c2’

ezen veszteség időkre vonatkozó fajlagos költségeket jelentsék

Cél: kétféle költség összegének minimalizálása! K = c1’*M(v) + c2’*M( )

min


Nem korlátos, egycsatornás sorbanállási rendszer Legegyszerübb eset: -egyetlen kiszolgáló egység van -sem igények, sem a várakozó helyek nincsenek korlátozva Jelölések:

- jelentse az időegység alatt átlagosan beérkezett egyedek számát ( beérkezési ráta ) - jelentse az időegység alatt átlagosan kiszolgált egyedek számát folyamatos kiszolgálást feltételezve ( kiszolgálási ráta ) ψ

λ μ

-forgalom intenzitása

0<

< 1 kell legyen!

egyébként a sor végtelenné válik


11

Feltételek a továbbiakra: • Stacioner folyamatról van szó függetlenek az időtől .

a pi valószínüségek

• A beérkezések Poisson- folyamatot alkotnak a beérkezések száma paraméterü Poisson -eloszlású valószínüségi változó. • Egy egység kiszolgálásának időtartama paraméterü exponenciális eloszlású valószínüségi változó.


Ha ezen feltételek mellett ismernénk a p0,p1,p2,….,pm értékeket, akkor számolhatók a várható értékek. A p0,p1,p2,….,pm értékek meghatározása egy, az előbbi feltételek figyelembevételével felírható egyenletrendszer segítségével történik.(Ettől eltekintünk.) Az adódó általános formula: pn =

np

n=1,2,….

0

p0=? Mivel p0+ p1+ p2+… = 1 (teljes eseményrendszerről van szó) 1= p0 + p1 + p2 +…+ pn + …. = p0 + p0 + = p0( 1+

+

2+

3+

végtelen geom. sor

…. ) = p0* 1/ (1-

2p

0+

0+

3p

…. =

)


12

Tehát a keresett valószínüségek:

p0

1 ψ

pn

(1 ψ)ψ n

Ezek segítségével a keresett várható értékek: A rendszerben található egységek várható száma: M (n )

n(1 ψ)ψ n

n * pn n 0

....

n 1

ψ 1 ψ


A sorban állók várható száma: M( v )

(n S )p n n S

np n

(n 1)p n n 1

n 1

pn n 1

de S=1, ezért

M(n) (1 p 0 )

M (n ) ψ

ψ2 1 ψ


13

A várakozási idő: ts - jelentse a sorbanállási időt tr - jelentse a rendszerben eltöltött időt Stacionárius esetben a rendszerbe időegység alatt érkező egységek várható száma azonos a rendszerből távozó egységek várható számával. A várható sorbanállási idő: M(t s )

M(v) λ

1 ψ2 λ1 ψ

1 ψ μ1 ψ


A rendszerben eltöltött idő várható értéke: M( t r )

M(n) λ

1 ψ λ1 ψ

1 1 μ1 ψ

A kettő különbsége a kiszolgálási idő várható értékét adja: M( t r ) M( t s )

1 1 μ1 ψ

1 ψ μ1 ψ

1 μ


14

Oldjuk meg az alábbi feladatot: Egy hivatal egyik irodájában, ahol munkanapokon 10 órán keresztül fogadják az ügyfeleket, 60 személy fordul meg naponta.Az itt dolgozó ügyintéző óránként 8 személyt képes meghallgatni.Tegyük fel, hogy a beérkezések Poisson-eloszlásuak, míg az ügyintézés ideje pedig exponenciális eloszlású. • Mi a valószínüsége, hogy kettő vagy annál kevesebb

ügyfél van az irodában? •Mekkora lesz a várakozó sor várható hossza? •Mennyi a várható sorbanállási idő? Döntéselőkészítés

és értékének meghatározása történjen egy órára vonatkozóan. =6

ψ

ezekből

=8

λ μ

6 8

3 4

Annak valószínüsége, hogy kettő vagy annál kevesebb ügyfél van az irodában: P(n

2)

(1 - ψ) ψ(1 - ψ) ψ 2 (1 - ψ)

p 0 p1 p 2 1 - ψ ψ - ψ2

P(n

2)

1 ( 3 / 4) 3

ψ2 - ψ3

1- ψ3

37 / 64 Döntéselőkészítés

15

Az irodában található ügyfelek várható száma: M( n )

ψ 1 ψ

3/4 1 3/4

3

A várakozó ügyfelek várható száma: M( v )

ψ2 1 ψ

(3/4)2 1 3/4

9 4

2


A sorbanállás várható időtartama: M( t s )

M(n) μ

M(v) λ

3 óra 8

22.5perc


16

Vége a mai órának! Döntéselőkészítés

17

Sorbanállási modellek

Recommend Documents