Tema 3. Teo ia de cues
Lali Ba i`e e
Depa amen de Ma em`a iques - UPC
Enginye ia de Sis emes Ae oespacials
EETAC
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 1 / 23
Con ingu s
Con ingu s
3.1 P oc´es de Poisson
3.2 In oducci´o a la eo ia de cues
3.3 Poblaci´o in ini a (N=∞)
3.4 Poblaci´o ini a (N < ∞)
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 2 / 23
3.1 P oc´es de Poisson
3.1 P oc´es de Poisson
De inici´o Un p oc´es ´es una col·lecci´o de a iables alea `o ies X( ), on
∈R, si el p oc´es ´es con inu; ∈N, si el p oc´es ´es disc e . La a iable
ep esen a el emps.
En un p oc´es de naixemen ,X( )comp a a ibades independen s amb una
ce a in ensi a . X(0) = 0, i en ce s ins an s de emps enim un
“naixemen ” o “a ibada”, de mane a que X( )s’inc emen a en 1.
Exemples
IX( ) = # co xes que han passa pe un pea ge ins a l’ins an .
IX( ) = # ucades ebudes pe una cen ale a a l’ins an .
X( a, b) = X( b)−X( a)comp a el nomb e d’a ibades en e ai b.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 3 / 23
3.1 P oc´es de Poisson
P oc´es de Poisson
De inici´o Un p oc´es de Poisson d’in ensi a λ´es un p oc´es que compleix
alguna de les p opie a s equi alen s seg¨uen s:
1. En in e als d (di e encial de emps) a iben Po(λ·d )elemen s.
2. X( )∼Po(λ· )pe a o a ∈R.
A m´es, si 1< 2< 3< 4,X( 1, 2)iX( 3, 4)s´on independen s.
E(X( )) = λ· .
3. El emps Ten e dues a ibades ´es independen i es dis ibueix
seguin una Exp(λ).
T∼Exp(λ),E(T) = 1
λ.
Obse aci´o Els p ocessos de Poisson s´on un cas pa icula de p oc´es de
naixemen s.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 4 / 23
3.1 P oc´es de Poisson
P opie a s
1. Els p ocessos de Ma ko no enen mem`o ia (Memo yless). Un p oc´es de
Poisson ´es un p oc´es de Ma ko .
Pa adoxa de l’au oes opis a Suposem que en una ca e e a passen co xes
seguin un p oc´es de Poisson amb pa `ame e λ= 6. En mi jana, passen 6
co xes cada ho a, ´es a di , un cada 10 minu s.
Quin ´es el emps que hau `a d’espe a , en mi jana, un au oes opis a que
a iba a la ca e e a en un ins an qualse ol?
P oc´es de Poisson: el emps d’espe a, T, ´e una espe an¸ca E(T) = 10
minu s.
In u¨ıci´o Mi jana del emps d’espe a: 5 minu s.
Reali a ´
Es m´es p obable a iba en e dues a ibades mol dis an s, que
en e dues a ibades mol p ope es. Pe an , hau `a d’espe a m´es.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 5 / 23
3.1 P oc´es de Poisson
Suposem que els co xes a iben exac amen cada 10 minu s. Mi jana del
emps d’espe a: 5 minu s.
P oc´es de Poisson. Mi jana del emps d’espe a: 10 minu s.
Obse aci´o Els p ocessos de Poisson no enen mem`o ia (Memo yless).
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 6 / 23
3.1 P oc´es de Poisson
2. Si condicionem que X( ) = n, alesho es les a ibades s´on uni o mes en
l’in e al [0, ].
3. Me ge X1( ),X2( )p ocessos de Poisson amb in ensi a s λ1iλ2,
espec i amen . Alesho es:
X( ) = X1( ) + X2( )´es un p oc´es de Poisson amb in ensi a λ1+λ2.
4. Spli X( )p oc´es de Poisson amb in ensi a λ. Seleccionem cada
elemen que a iba amb p obabili a p∈[0,1]. Alesho es, les a ibades
seleccionades o men un p oc´es de Poisson amb in ensi a λ·p.
5. Diag ama d’es a s
Ei´es l’es a (esde enimen ) en qu`e X( ) = i(hi ha ia ibades).
E0E1E2E3· · ·
λλλλ
El emps de sal a d’un es a al seg¨uen ´es Exp(λ).
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 7 / 23
3.2 In oducci´o a la eo ia de cues
3.2 In oducci´o a la eo ia de cues
Una cua ´es un p oc´es de naixemen i mo : a ibades i so ides.
El sis ema ´e dues pa s: els se ido s i la cua.
| {z }
se ido s | {z }
cua
| {z }
sis ema
ISemp e suposa em que hi ha una ´unica cua.
IPo ha e -hi m´es d’un se ido .
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 8 / 23
3.2 In oducci´o a la eo ia de cues
No aci´o de Kendall
M / M / s / k // N
↓ ↓ ↓ ↓ ↓
1 2 3 4 5
1. Dis ibuci´o d’a ibada. P oc´es de Poisson amb in ensi a λ > 0.
2. Dis ibuci´o de so ida (o de se ei). P oc´es de Poisson amb in ensi a
µ > 0. El emps mi j`a de se ei ´es 1/µ.
3. Nomb e de se ido s: s≥1.
4. Capaci a del sis ema: k≥s. Po se ini a o in ini a. Si no es posa
la k, ol di que la capaci a ´es in ini a.
5. Poblaci´o. Po se ini a o in ini a. Si no es posa la N, ol di que la
poblaci´o ´es in ini a.
M ol di “Memo yless”, ´es a di , p oc´es de Poisson. Hi poden ha e cues
amb al es dis ibucions, que no es udia em.
Pol´ı ica de cua FIFO (Fi s In, Fi s Ou )
Hip`o esi de eball Pe e i a l’e ec e de les condicions inicials: espe em un
emps pe qu`e la cua s’es abili zi, lla o s l’es udiem. Diem que es udiem les
cues en `egim es aciona i od’equilib i.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 9 / 23
3.3 Poblaci´o in ini a (N=∞)
Pa `ame es elaciona s amb el emps d’espe a
IW= emps espe a d’un usua i al sis ema
Llei de Li le: L=λ·W⇒W=L
λ=1
µ−λ
IWs= emps espe a d’un usua i al se ido = emps de se ei =1
µ
IWq= emps espe a d’un usua i a la cua =
=W−Ws=1
µ−λ−1
µ=λ
µ(λ−µ)
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 16 / 23
3.3 Poblaci´o in ini a (N=∞)
3.3.2 M / M / s (s > 1,k=N=∞)
Diag ama d’es a s
E0E1E2· · · Es−1EsEs+1 · · ·
λ λ λλλλ
λ
sµ
sµ
sµ
(s−1)µ
3µ
2µ
µ
In ensi a ρ=λ
sµ
S’ha de compli ρ < 1pe al que la cua sigui es able.
Obse aci´o Pe a aques model i els seg¨uen s no calcula em els
pa `ame es, u ili za em el Fo mula i.
Obse aci´o Pe a aques model amb´e es compleix que ρ´es la acci´o de
emps que un se ido es `a ocupa .
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 17 / 23
3.3 Poblaci´o in ini a (N=∞)
3.3.3 M / M / 1 / k (s= 1,k ini a, N=∞)
Diag ama d’es a s
E0E1E2· · · Ek−1Ek
λ λ λλλ
µ
µ
µ
µµ
In ensi a ρ=λ
µ
ILes a ibades a l’es a Ekes pe den.
ISi ρ≥1pe dem en ades, pe `o la cua no se `a mai massa g an.
Iρ∈R+. Si ρ6= 1, u ili zem el Fo mula i; si ρ= 1 es an els c`alculs
a m`a, enin en comp e que, en aques cas, pk+1 = 0 (i,pe an ,
pi= 0 si i>k.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 18 / 23
3.3 Poblaci´o in ini a (N=∞)
IIn ensi a d’a ibades: λpe uni a de emps.
IIn ensi a d’en ades: λpe uni a de emps:
λ=
k
X
i=0
λi·pi=λ·p0+λ·p1+· · · +λ·pk−1+ 0 ·pk=
=λ(p0+p1+· · · +pk−1) = λ(1 −pk)
IIn ensi a de p`e dues: λ−λ
IL,Wamb λ: mi janes sob e el nomb e d’en ades.
Obse aci´o En algun cas ens podem p egun a quan alen LiW, sob e el
nomb e d’a ibades.
Els c`alculs s´on semblan s, amb λen lloc de λ.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 19 / 23
3.3 Poblaci´o in ini a (N=∞)
3.3.3 M / M / s / k (s≥1,k ini a, N=∞)
Diag ama d’es a s
E0E1E2· · · Es−1EsEs+1 · · · Ek−1Ek
λ λ λλλλλλλ
sµ
sµ
sµ
sµ
sµ
(s−1)µ
3µ
2µ
µ
In ensi a ρ=λ
sµ
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 20 / 23
3.4 Poblaci´o ini a (N < ∞)
3.4 Poblaci´o ini a (N < ∞)
Exemple Una companyia de axis ´e 10 axis. Quan algun axi s’espa lla,
en a a la cua de epa aci´o.
La p obabili a que en i un axi a la cua de epa aci´o ´es m´es pe i a, com
m´es g an sigui la cua.
Obse aci´o En aques model, cada usua i ´e la se a λ.
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 21 / 23
3.4 Poblaci´o ini a (N < ∞)
3.4.1 M / M / 1 // N (s= 1,k=∞,N ini a)
Diag ama d’es a s
E0E1E2· · · EN−1EN
Nλ (N−1)λ(N−2)λ2λλ
µ
µ
µ
µ
µ
In ensi a mi jana d’en ada
λ=
N
X
i=0
λi·pi=
N
X
i=0
λ(N−i)·pi=Nλ
N
X
i=0
pi−λ
N
X
i=0
i·pi= (N−L)λ
Exlicaci´o La in ensi a d’en ada en mi jana, λ, ´es la in ensi a d’a ibada
pa icula , λ, pel nomb e mi j`a d’usua is o a del sis ema, (N−L).
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 22 / 23
3.4 Poblaci´o ini a (N < ∞)
3.4.2 M / M / s / / N (s≥1,k=∞,N ini a)
Diag ama d’es a s
E0E1E2· · · Es−1EsEs+1 · · · EN−1EN
Nλ (N−1)λ(N−2)λ(N−s+ 2)λ(N−s+ 1)λ(N−s)λ(N−s−1)λ2λλ
sµ
sµ
sµ
sµ
sµ
(s−1)µ
3µ
2µ
µ
Lali Ba i`e e - AM2 Tema 3. Teo ia de cues 23 / 23
