Metodi e Modelli Matematici di Probabilit` a per la Gestione
Prova scritta del 30/1/06
Esercizio 1 Una banca ha N correntisti. Indichiamo con Nn il numero di correntisti esistenti il giorno n-esimo. Descriviamo il numero Nndi correntisti tramite una catena di Markov, in diverse situazioni.
1) Supponiamo che approssimando i risultati di indagini statistiche, la banca sappia che ogni giorno c’`e probabilit`a p0 che un conto venga chiuso ed 1 − p0 che nessuno venga chiuso; e che c’`e probabilit`a p1 che venga aperto un nuovo conto, 1 − p1 che non ne venga aperto alcuno. Descrivere in questo caso la catena di Markov, stabilire in che relazione devono essere p0 e p1 affinch´e si stabilisca un regime e calcolare a regime la probabilit`a di avere almeno un conto aperto. Infine, fare un esempio numerico di p0 e p1 che produca un numero medio di conti aperti pari a 100.
2) Esaminiamo un modello diverso. Ogni giorno, ciascun correntista ha probabilit`a p0 di cancellare il conto corrente. D’altra parte, come sopra, ogni giorno con probabilit`a p1 si presenta un nuovo cliente per aprire un conto (oppure non se ne presenta nessuno).
Descrivere il numero di correntisti tramite una catena di Markov: `e sufficiente indicare gli stati, le transizioni possibili e calcolare (in funzione di p0 e p1) le seguenti probabilit`a di transizione
pk,k+1, pk,k, pk,k−1.
Esercizio 2 Nel nostro ufficio ci sono tre sportelli che si occupano dei clienti. I clienti arrivano in media ogni 20 minuti e ogni sportello impiega in media 10 minuti per servire un cliente. Supponiamo come sempre che tutti i tempi d’attesa siano esponenziali. Quando tutti gli sportelli sono occupati non arrivano nuovi clienti.
i) Costruire una catena di Markov in tempo continuo che rappresenta il sistema.
ii) Calcolare la probabilit`a invariante.
iii) Calcolare la probabilit`a che, quando due degli sportelli sono occupati, arrivi un nuovo cliente prima che uno dei due si liberi.
[I punti (iv) e (v) sono indipendenti l’uno dall’altro]
iv) Supponiamo che i tre sportelli abbiano tempi medii di servizio diversi e pari a 5, 10, 15 minuti: costruire una catena di Markov che rappresenti questa nuova situazione.
Ritorniamo ora ad avere tempi medii di servizio uguali per i tre sportelli. Nell’ufficio ci sono spesso altre attivit`a supplementari da svolgere, che si presentano con intervalli esponenziali di media 3 ore. Quando si presenta una di queste attivit`a da svolgere, il primo sportello che si libera dai clienti chiude per occuparsi dell’attivit`a, e impiega un tempo esponenziale di media 2 ore per portarla a termine. In questo intervallo gli altri due sportelli continuano ad occuparsi dei clienti come prima. Ammettiamo per semplicit`a
per evitare di dover considerare una coda di attivit`a supplementari).
iv) Descrivere questa nuova situazione modificando la catena del punto i).
[Sol. Es. 1]
1.1. Se un certo giorno il numero di conti `e k, il giorno successivo pu`o essere (schemati- camente):
• k − 1 se uno chiuso e zero aperti
• k se zero aperti e zero chiusi, oppure uno chiuso e uno aperto
• k + 1 se uno aperto e zero chiusi.
Gli stati sono gli interi non negativi, le transizioni possibili quelle dette, ed infine pk,k−1 = p0(1 − p1)
pk,k = (1 − p0) (1 − p1) + p0p1
pk,k+1 = (1 − p0) p1.
Per il caso k = 0 valgono le solite eccezioni. E’ una catena di nascita e morte con λ = (1 − p0) p1, µ = p0(1 − p1). Raggiunge il regime stazionario se (1 − p0) p1 < p0(1 − p1), ovvero
p0(1 − p1) + p0p1 > p1
da cui p0 > p1 (come dev’essere intuitivamente).
Probabilit`a di avere almeno un conto aperto:
1 − π0 = 1 −
1 − (1 − p0) p1
p0(1 − p1)
= (1 − p0) p1
p0(1 − p1). Numero medio di conti aperti:
Xkπk =
1 −(1 − p0) p1
p0(1 − p1)
Xk (1 − p0) p1
p0(1 − p1)
k
= (1 − p0) p1
p0(1 − p1) :
1 −(1 − p0) p1
p0(1 − p1)
.
Risolviamo l’equazione α/ (1 − α) = 100: α = 100 (1 − α), 101α = 100, α = 100/101, (1 − p0) p1
p0(1 − p1) = 100 101. Si pu`o scegliere liberamente p0 e trovare p1:
(1 − p0) p1 = 100
101p0(1 − p1) p1 = 100
101p0 :
1 − p0
101
.
1.2. Ora in teoria da k conti di un giorno si pu`o passare a 0, 1, ..., k + 1. Gli stati sono sempre gli stessi. Vale
• k → k + 1 se nessuno rinuncia e ne arriva uno nuovo, quindi con probabilit`
pk,k+1 = (1 − p0)kp1
• k → k se nessuno rinuncia e nessuno arriva, oppure uno rinuncia ed arriva uno nuovo, quindi con probabilit`a
pk,k = (1 − p0)k(1 − p1) + kp0(1 − p0)k−1p1
(infatti il numero R di quelli che rinunciano `e una binomiale di parametri k, p0 e vale P (R = 1) = k1p0(1 − p0)k−1)
• k → k − 1 se uno rinuncia e nessuno arriva, oppure due rinunciano e ne arriva uno nuovo, quindi con probabilit`a
pk,k−1 = kp0(1 − p0)k−1(1 − p1) + k (k − 1)
2 p20(1 − p0)k−2p1.
[Sol. Es. 2]
i) Utilizziamo quattro stati 0, 1, 2, 3 che indicano il numero di sportelli occupati.
Il grafo con le transizioni `e il seguente:
0 1 2 3
λ
µ
λ
2µ
λ
3µ
con λ = 3, µ = 6 (misurando il tempo in ore). I tassi di transizione tengono conto del fatto che nello stato con k (k = 1, 2, 3) sportelli occupati, ognuno dei k sportelli pu`o terminare il servizio, quindi il tempo esponenziale associato alla transizione corrisponde al minimo di k tempi esponenziali con parametro µ.
ii) Impostiamo il bilancio di flusso:
λπ0 = µπ1 (nodo 0) 3µπ3 = λπ2 (nodo 3) (µ + λ)π1 = 2µπ2+ λπ0 (nodo 1) Si trova
π1 = λ
µπ0, π2 = λ2
2µ2π0, π3 = λ3
6µ3π0, π0 = quindi
π0 = 48
79, π1 = 24
79, π2 = 6
79, π3 = 1 79
iii) La probabilit`a p che dallo stato 2 si passi a 3 piuttosto che a 1 `e data da
p = λ
λ + 2µ = 1 5
transizioni possibili, con i relativi tassi. Poich`e i tre sportelli hanno tassi diversi, dobbi- amo utilizzare degli stati che specifichino completamente la situazione di ciascun sportello, ovvero se `e libero o occupato. Chiamiamo convenzionalmente gli sportelli A, B, C e uti- lizziamo le lettere maiuscole per indicare che lo sportello `e occupato e minuscole per indicare che `e libero. Per esempio nello stato abc tutti gli sportelli sono liberi, in Abc solo il primo `e occupato, ecc. . .
Inoltre dobbiamo specificare il modo in cui viene scelto lo sportello che serve un nuovo cliente nel caso ce ne sia pi`u di uno libero. Supponiamo che venga scelto sempre lo sportello con tempo di servizio minore. Un altra scelta altrettanto ragionevole `e quella di mandare il cliente a uno degli sportelli liberi scelto a caso.
• abc−→ Abcλ
• Abc
µA
−→ abc, Abc−→ ABcλ
• aBc
µB
−→ abc, aBc−→ ABcλ
• abC
µC
−→ abc, abC −→ AbCλ
• ABc
µA
−→ aBc,ABc
µB
−→ Abc, ABc−→ ABCλ
• AbC −→ abC,AbCµA −→ Abc,µC AbC −→ ABCλ
• aBC −→ abC,aBCµB −→ aBc,µC aBC −→ ABCλ
• ABC −→µA aBC,ABC −→µB AbC, ABC −→ ABcµC
Dove µA = 12, µB = 6, µC = 4.
v) Dato che i tempi di servizio sono uguali possiamo ritornare ad indicare solo il numero di sportelli occupati. Per gestire i servizi speciali indichiamo con una a la presenza di un servizio speciale in attesa e con una x un servizio speciale che `e in corso di svolgimento da parte di uno sportello (e quindi c’`e uno sportello in meno disponibile). Sia inoltre θ il tasso di arrivo dei servizi speciali e ρ il loro tasso di servizio.
Per esempio 0xx `e lo stato in cui due sportelli sono occupati in servizi speciali e non c’`e nessun cliente da servire, lo stato 2ax `e lo stato in cui ci sono due clienti e il terzo sportello `e chiuso a causa di un servizio speciale (la x) mentre un ulteriore servizio speciale attende che uno sportello si liberi.
• 0−→ 1, 0λ −→ 0xθ
• 1−→ 2, 1λ −→ 1x, 1θ −→ 0µ
• 2−→ 3, 2λ −→ 2x, 2θ
2µ
−→ 1
• 3−→ 2, 33µ −→ 3aθ
• 0x−→ 1x, 0xλ −→ 0xx 0xθ −→ 0ρ
• 1x−→ 2x, 1xλ −→ 1xx, 1xθ
µ
−→ 0x, 1x
ρ
−→ 1
• 2x−→ 2xa, 2xθ
2µ
−→ 1x, 2x
ρ
−→ 2
• 0xx−→ 1xx, 0xxλ
2ρ
−→ 0x
• 1xx−→ 0xx, 1xxµ −→ 1x2ρ
• 2xa
2µ
−→ 1xx, 2xa
ρ
−→ 2x
• 3a
3µ
−→ 2x