MMMPG
prova scritta dell’1/12/07
Esercizio 1. Marco e Luca lavorano in un call center e si occupano dello stesso tipo di chiamate. Quando arriva una chiamata per loro, un meccanismo la smista ad uno dei due a caso. Se però uno dei due è assente, questo è segnalato al meccanismo che provvede ad inoltrare la chiamata sempre a colui che è presente.
Le chiamate arrivano secondo un processo di Poisson e passa mediamente un quarto d’ora tra l’una e l’altra. Il sistema permette di mettere in attesa le chiamate quando entrambi sono occupati. Supponiamo (per quanto questo sia irrealistico) che le persone in attesa non riattacchino.
Sia Marco sia Luca impiegano in media 5 minuti a dare le informazioni richieste e concludere quindi una chiamata. Se però uno dei due è libero, aiuta l’altro nella ricerca delle informazioni e succede che lavorando così in collaborazione completano una chiamata in 4 minuti, mediamente. Ma se, durante un tale aiuto, arriva una seconda chiamata, l’aiutante lascia il compagno e risponde.
1. Giovedì Luca è ammalato e quindi Marco è solo. Descrivere Xt = “il numero di chiamate in attesa più la chiamata in corso di servizio” con un processo a salti, scrivendo (anche senza i calcoli intermedi) la distribuzione a regime, se c’è.
2. Se ci sono k chiamate in attesa (es. k = 1,2,3), quanto deve aspettare mediamente l’ultima di queste prima di iniziare la propria conversazione? Però, con che probabilità avviene che ci sono k chiamate in attesa? Quindi, in media, quanto deve attendere l’ultimo che è in attesa prima di iniziare il proprio servizio?
3. Venerdì Luca rientra. Descrivere il sistema con un processo a salti e calcolare la distribuzione invariante.
4. Supponiamo infine che, dopo un mese, a causa delle troppe assenze di Luca, Marco sia diventato molto più veloce: impiega solo 3 minuti in media quando serve una telefonata da solo, non utilizza l’aiuto di Luca quando questi è libero, e viceversa accelera il lavoro di Luca quando Luca è impegnato (e lui è libero) facendo sì che il lavoro di Luca si completi in 2 minuti, mediamente (come sopra, se nel frattempo arriva una nuova chiamata, Marco la prende e lascia Luca). Descrivere ora il sistema con un processo a salti.
5. Facoltativo: nella situazione del punto 4, introduciamo il vincolo che il sistema non metta chiamate in attesa. Calcolare la distribuzione invariante.
Esercizio 2. Un magazzino viene usato per depositare temporaneamente delle merci, in transito dalla produzione alla destinazione. Ogni giorno, alle ore 8, un camion carica 100 pezzi dal magazzino e li porta a destinazione, ed in serata rientra. Se in magazzino ci sono meno di 100 pezzi alle 8, il camion viene impiegato per altri scopi e rimanda al giorno successivo. Al magazzino arrivano gruppi di N pezzi per volta, da due produttori, A e B, una volta al giorno, dalle 9 in poi. Solo che la produzione di B è irregolare: con probabilità p non fa pervenire la merce.
Si supponga che all’inizio (tempo zero) il magazzino sia vuoto, oppure ci siano 50 pezzi.
i) Supponiamo N = 50, p = 1/2. Descrivere il sistema con una catena di Markov a tempo discreto e calcolare la probabilità che il camion non venga utilizzato per quel tipo di trasporto.
ii) Supponiamo N = 10, p = 0. Descrivere il sistema con una catena di Markov e trovare le distribuzioni invarianti, calcolando per ciascuna di esse la probabilità che il camion non venga utilizzato.
Soluzioni
Esercizio 1. 1. E’ un semplice processo di nascita e morte con tassi di crescita λ = ET1a = 151 (misurando il tempo in minuti) e tasso di descrescita μ = ET1s = 15. Pertanto, posto ρ = λμ = 13, che essendo minore di uno garantiche che ci sia regime, vale
πk = 1 − ρρk = 23 1 3
k
. Questa è la probabilità che ci siano k chiamate nel sistema.
2. Se ci sono k chiamate in attesa, l’ultima di queste deve attende che sia completata la chimata in corso più le k − 1 davanti a sè, quindi k chimate in tutto, quindi in media deve aspettare k ⋅ ETs = 5k. La probabilità di essere in questa situazione è la probabilità che ci siano k+ 1 chiamate nel sistema, quindi πk+1. Il tempo medio è, per la formula di
fattorizzazione,
∑
k=1
∞
5kπk+1 = 5 23
∑
k=1
∞
k 13
k+1
= 5 23 1
3
∑
k=1
∞
k 13
k
= 109
∑
k=0
∞
k 13
k = 109
1 3
1 − 13 2 = 53
1 3 2 3
= 56 .
Quasi un minuto.
3. Il numero Xt di chiamate presenti nel sistema è di nuovo un processo di nascita e morte. Però i tassi non sono omogenei. Il tasso di crescita è sempre λ = 151 . Se sono entrambi impegnati, quindi dallo stato k = 2 in poi, il tasso di descrescita è (per il teorema sul minimo di variabili esponenziali) μ∗ = 2 ET1s = 25 = 0.4. Se invece uno solo è
occupato, cioè k = 1, il tasso di descrescita è 14 = 0.25. Vale a0 = 1, a1 =
1 15
1 4
= 415,
a2 = 415
1 15
2 5
= 415 1
6, a3 = 415
1 15
2 5
2
= 415 1 62 e così via, quindi ak = 154 6k−11 per ogni k = 1,2,3,... Quindi
∑
k=0
∞
ak = 1 +
∑
k=1
∞
4 15
1
6k−1 = 1 + 415
∑
k=0
∞
1 6k
= 1 + 415 1
1 − 16 = 1 + 415 6
5 = 33
25 = 1.32 da cui
π0 = 2533, πk = 2533 4 15 1
6k−1 = 2099 1 6k−1 per ogni k = 1,2,3,...
4. E’ necessario distinguere gli stati: M= Marco lavora e Luca è libero, L(+M) = Luca lavora e Marco lo aiuta. Infatti i tassi di servizio a partire da questi stati sono diversi. Non è più un processo di nascita e morte. Lo stato zero (nessuna chiamata nel sistema) porta allo
stato M con tasso λ ⋅ 12 = 301 ed allo stato L(+M) con tasso λ ⋅ 12 = 301 (una chiamata ha ugual probabilità di finire a Marco o a Luca). Lo stato M porta a 0 con tasso
μM = ET1
sM = 13; lo stato L(+M) porta a 0 con tasso μL+M = 12. Ci sono poi gli stati k = 2,3,... come sopra, cioè con entrambi impegnati ed eventualmente qualche chiamata in attesa. Lo stato M porta a k = 2 con tasso λ e lo stesso vale per L(+M). Da k = 2 in su è come sopra in salita, mentre il tasso di decrescita è ora μ∗∗ = ET1
sM + ET1s = 13 + 15 =
8
15 = .533. Lo stato k = 2 porta in M con tasso 15, in L(+M) con tasso 13.
5. Il grafo è il precedente però solo fino a k = 2, quindi ci sono 4 stati. Basta fare il bilancio di flusso.
Esercizio 2. i) Prendiamo come stato Xn del sistema il numero di pezzi nel magazzino, alla sera del generico giorno. Si parte da magazzino vuoto. Dopo averci pensato un po’ si riconosce che, a regime, il numero di pezzi nel magazzino può solo essere 0, 50, 100, 150.
Quando Xn = 0, il camion non porta pezzi. Varrà Xn+1 = 50 se solamente A rifornisce, quindi con probabilità 0.5. Varrà Xn+1 = 100 se anche B rifornisce, quindi con probabilità 0.5. Non si può restare in 0.
Quando Xn = 50, il camion non porta pezzi. Si passa da 50 a 100 se solamente A rifornisce, quindi con probabilità 0.5. Si passa da 50 a 150 se anche B rifornisce, quindi con probabilità 0.5. Non si può restare in 50.
Quando Xn = 100, il camion porta via tutti i pezzi, quindi è come partire da Xn = 0.
Quando Xn = 150, il camion porta via 100 pezzi, quindi è come partire da Xn = 50.
In conclusione
p0,50 = p0,100 = 1
2, p50,100 = p50,150 = 1 2, p100,50 = p100,100 = 12 , p150,100 = p150,150 = 12.
Lo stato 0 è transitorio, la classe50, 100, 150 irriducibile. Non ci sono simmetrie evidenti. Il bilancio di flusso in 50 è
π50 = 12π100, 1
2 π150 = 12π50
che sostituite in π50+ π100 + π150 = 1 fornisce π50+ 2π50 + π50 = 1, π50 = 14, π100 = 12, π150 = 14 .
La probabilità che il camion non venga utilizzato per quel tipo di trasporto è π50 = 14. ii) Gli stati sono 0, 10, 20, ..., 110. Ci sono due classi irriducibili, 20, 40, 60, 80, 100, e 30, 50, 70, 90, 110, ciascuna con distribuzione invariante uniforme (per simmetria), e tutte le distribuzioni invarianti sono delle forma
0, 0, α
5 , 1 − α 5 , α
5 , 1 − α 5 , α
5, 1 − α 5 , α
5 , 1 − α 5 , α
5 , 1 − α 5
con α ∈ 0, 1. Per tutte la probabilità che il camion non venga utilizzato per quel tipo di trasporto è 1 − α5 − 1−α5 = 45.
