Che materia stai cercando?

Appunti del corso Sistemi di servizio e simulazione Massimo Roma

Il file contiene gli appunti di tutte le lezioni (compresi esercizi svolti) del corso di Sistemi di servizio e simulazione del professor Massimo Roma da marzo a maggio 2018. Consiglio (se possibile) di stampare il file a colori. Scarica il file in formato PDF!

Esame di Sistemi di servizio e simulazione docente Prof. M. Roma

Anteprima

ESTRATTO DOCUMENTO

Esercizio di esame

Un porto possiede un terminal al quale arrivano navi per operazioni di carico e scarico che avvengono attraverso apposite

gru. Attualmente il porto dispone di una sola gru (carico e scarico di una alla volta). Quando una nave arriva e la gru è

occupata aspetta in coda (FIFO). Gli arrivi delle navi sono poissoniani con media 3 al giorno. Il tempo che una gru impiega

per carico e scarico è distribuito esponenzialmente con media 4 ore.

Supponiamo che lo spazio nel terminal dove le navi attendono il proprio turno sia limitato e non permetta lo stazionamento

di più di 4 navi. Le navi che arrivano poi vengono dirottate verso un altro terminal.

Spiegare come si può rincondurre questo sistema ad un sistema di nascita e morte (cioè definire i coefficienti di nascita

e morte).

Calcolare il numero medio di navi presenti nel terminal ed il tempo medio di attesa.

Mediamente ci possiamo aspettare che ci sia una nave nel sistema

Numero medio di navi in coda, non richiesto ma mi serve per

calcolare Tq

Tempo medio che ci aspettiamo che una nave stia in coda prima delle

operazioni di carico e scarico

13 apr 2018 Sistemi con popolazione finita

È preferibile per comodità pensare ad una popolazione infinita laddove possibile. Con questa assunzione il modello

matematico che ne viene fuori è sufficientemente trattabile. Le cose si complicano se supponiamo che la popolazione sia

finita. Siamo per forza obbligati a fare assunzioni di questo tipo quando: supponiamo di avere un’azienda che affitta

automobili: 500 macchine a disposizione e un’officina dedicata alla manutenzione di queste, qui non possiamo dire di avere

popolazione infinita, oppure in un’azienda ci può essere un ufficio che offre consulenza ai dipendenti, non ha senso pensare

che la popolazione sia infinita.

Se la popolazione è finita e ho n utenti nel sistema e la popolazione intera è U allora fuori dal sistema ne ho U-n, quindi il

processo degli arrivi è condizionato da questo.

U è il numero potenziale di clienti

Riprendiamo l’esempio dell’officina per le macchine. Una volta che una macchina viene servita quando esce torna tra i

potenziali clienti.

Un modello che si presta bene per questa situazione è un modello in cui il tempo che intercorre da quando il cliente esce

dal sistema a quando rientra è distribuito esponenzialmente di parametro λ. In pratica è il tempo che un utente passa fuori

dal sistema.

Riconduciamo questo sistema ad un processo di nascita e morte, troviamo quindi λ e μ.

Ho tanti utenti fuori con tempi distribuiti esponenzialmente. Per sapere tra quanto un utente entrerà nel sistema

consideriamo il tempo residuo più piccolo, ma per l’assenza di memoria queste Ti sono anche esse distribuite

esponenzialmente. Tempi residui permanenza fuori dal sistema

Il più piccolo di questi mi dice quanto devo aspettare affinché si verifichi il primo arrivo.

Il tempo Ti sarà distribuito esponenzialmente di parametro

Dobbiamo precisare che λ diventa 0 se n maggiore o uguale U

Caso monoservente

Metto in evidenza μ/λ

Il λ effettivo da applicare nella formula di Little lo dobbiamo ricavare Caso monoservente, λ effettivo

possiamo anche riscriverlo nella

forma

Caso multiservente

Esercizio di esame

In un’azienda ci sono 5 operatori addetti alla gestione amministrativa. Essi operano indipendentemente e possono avvalersi

uno alla volta dell’esperienza di un esperto contabile. Il tempo che in media trascorre tra una consulenza e un’altra è

distribuito esponenzialmente con media 7 ore (tempo che intercorre tra uscita dal sistema e ingresso successivo di un

utente).

Si assuma che i tempi di servizio siano distribuiti esponenzialmente con media un’ora. Chi arriva e trova occupato deve

mettersi in coda.

Descrivere come si trasforma in un processo di nascita e morte. Basta dire che i tempi residui sono distribuiti anche essi

esponenzialmente per via dell’assenza di memoria e....(quello visto prima).

Questo è l’unico caso in cui va giustificato il perché.

Sistemi con tasso di servizio e/o frequenza di arrivo dipendenti

dallo stato del sistema

Situazione reale in cui il servente o i serventi sono persone. Può darsi che il servente nel momento in cui vede tanta fila si

sbrighi, quindi il tasso di servizio potrebbe dipendere da N. Anche λ potrebbe cambiare con l’aumentare di N, potrebbero

infatti esserci delle persone che rinunciano a fare la fila, quindi rallentamento degli arrivi.

Primo modello: servente decide di cambiare la sua capacità produttiva in base ad n

Supponiamo che μ1 sia il tasso di servizio in condizioni normali (senza coda)

λ costante

Il tasso di servizio dipende da n, il come ce lo dice l’esponente. In pratica ci dice come varia la velocità di servizio. Questo

modello è di uso abbastanza comune rimanendo ovviamente con λ costante

Caso opposto: μn costante, supponiamo di avere arrivi dipendenti dallo stato: ARRIVI RALLENTATI

Dove λ0 è la frequenza media degli arrivi in condizioni normali (cioè senza coda).

Basta fare le trasformazioni Esempio pronto soccorso

Abbiamo un pronto soccorso (tralasciamo le priorità), un modello potrebbe prevedere che un medico pronto a lavorare in

caso di molto affollamento può chiedere ad altri di aiutarlo in modo da aumentare il suo tasso di servizio (infermieri ecc).

Supponiamo di avere questa situazione: il tempo medio che il medico passa a curare il paziente è di 24 minuti se non ci

sono pazienti che aspettano, diventa 12 se ci sono 5 pazienti in coda (quindi 6 nel sistema). Supponiamo λ=2.

Con queste informazioni riusciamo a determinare c

Questo modello può essere utilizzato con una c pari a 0,4.

Per calcolare il numero medio di persone nel sistema n possiamo

utilizzare delle tabelle (grafici) che ci ha fatto vedere (non servono

per l’esame).

Supponiamo di voler costruire un modello di coda in un self service dove noi andiamo, ci serviamo da soli, arrivi

poissoniani, servente sempre immediatamente disponibile, allora facciamo un modello M/M/infinito

È come se avessi sempre tanti serventi disponibili quanti utenti nel sistema

Questo modello è esattamente quello di prima con c=1

Questo può essere visto come un modello in cui il tasso di servizio cambia con n nel caso c=1

Sviluppo in serie

dell’esponenziale

Non ho coda in questo sistema, quindi:

Disciplina della coda basata su criteri di priorità

In alcune situazioni la disciplina di servizio non è FIFO. Supponiamo di lasciare invariate le assuzioni fatte finora. Gli arrivi

potrebbero avere un’etichetta (codice di priorità tipo al pronto soccorso), in pratica è come se dividessimo gli utenti in classi.

Un problema di questo tipo si tratta così:

Supponiamo che ci siano un certo numero di classi di priorità

Avremo un λk per ogni classe

Faccio l’assunzione che all’interno della stessa classe di priorità vale il criterio FIFO

Supponiamo che c’è un servente che sta servendo un utente della classe 5 (supponiamo 10 classi di priorità, numero più

piccolo corrisponde ad una priorità più alta). Supponiamo di avere un sistema generale in cui il servente è occupato, sta

servendo un cliente classe 8, arriva uno della classe 5, può succedere che:

1) il servente interrompe immediatamente il servizio e serve il nuovo utente, quello che era servito si rimette in coda,

questo viene chiamato SERVIZIO CON INTERRUZIONE DI SERVIZIO

a) il servizio potrebbe essere poi continuato da dove è stato interrotto

b) si comincia dall’inizio

2) SERVIZIO SENZA INTERRUZIONE DI SERVIZIO, l’utente con priorità più alta aspetta che l’altro finisca di essere

servito e poi viene servito lui Arrivi poissoniani, tempi di servizio esponenziali

Con interruzione del servizio

PREEMPTED RESUME SYSTEM

PREEMPTED REPRET SYSTEM Quello che cambia è la distribuzione dei tempi di

attesa: aspetteranno poco quelli che hanno priorità

Senza interruzione di servizio alta e tanto quelli che hanno priorità bassa

Le misure di prestazione si calcolano per ogni singola classe Queste formule non fanno parte del

programma di esame anche se le

troviamo ulle dispense

Nel caso s=1 queste formule possono essere utilizzate, continua a valere Little.

Nel caso s>1 bisogna usare una specie di formula iterativa, non ci sono delle formule precise, non le facciamo.

Sistemi a coda con distribuzioni non esponenziali

Vengono meno i modelli di cui abbiamo parlato fino ad ora. Tutte le facilitazioni utilizzate basate sulla distribuzione

esponenziale le perdiamo (esempio assenza di memoria ecc).

Esistono altre metodologie (non solo matematiche), non siamo in grado di ricondurre il processo ad un processo di nascita

e morte.

19 apr 2018

Modelli per sistemi a coda con distribuzioni non esponenziali

Tratteremo sistemi che continuano ad avere la M nella notazione di Kendall

Processo di arrivi ancora poissoniani. Per quanto riguarda i tempi di servizio non fornisco la distribuzione di

probabilità ma fornirò soltanto media e varianza.

Formula di Pollaczek-Kintchine

Non si pone nessuna condizione sulla distribuzione dei tempi di servizio. Tq avrà un’espressione che dipende dal

momento secondo dei tempi di servizio.

Teorema:

Consideriamo un sistema M/G/1 in condizioni stazionarie. Sia λ la frequenza media degli arrivi e siano 1/μ e σ^2

rispettivamente media e varianza dei tempi di servizio ti^s, allora:

Dim:

Facciamo uso di un risultato: supponiamo di avere un certo numero di variabili aleatorie iid con una media comune per

tutti che indico come valore atteso di x, interessa conoscere il valore atteso della somma.

Se m fosse stato fissato avremmo avuto m volte il valore atteso di x, siccome m a

sua volta è una variabile aleatoria viene fuori un altro valore atteso.

Ci sono più modi di dimostrare il teorema. Adottiamo i tempi residui di servizio.

i entra, un certo j è servito in quel momento, Ri sono i tempi residui di servizio visti dall’i-esimo utente che arriva

Voglio scrivere in forma semplice l’espressione della variabile aleatoria ti^q

Numero di utenti in coda all’arrivo dell’utente i-esimo

Per la proprietà PASTA che continua a valere queste quantità sono tutte osservate all’arrivo dell’i-esimo utente, ecco

perché dipendono tutte da i.

Ora faccio tendere i all’infinito Dobbiamo ora ricavare R

R è il limite del valore atteso di Ri

Grafichiamo R al variare di τ

Consideriamo un istante di tempo t in cui vale R(t)=0

Integrale definito da 0 a t della funzione quindi è l’area sotto al grafico

Questo integrale lo posso riscrivere come:

Ora facciamo tendere t all’infinito

Legge forte dei grandi numeri: se abbiamo un certo numero di variabili aleatorie iid con una certa media comune m, quando

faccio la somma di un certo numero n di queste variabili e divido per n questa tende ad m se n tende all’infinito

Per l’ultimo termine siamo nel caso della legge dei grandi numeri

Ho ottenuto quindi la R che stavo cercando

Questa dimostrazione l’abbiamo fatta supponendo che la disciplina di servizio fosse FIFO, il risultato vale in tutti i casi a

patto che la disciplina della coda sia indipendente dai tempi di servizio.

Fissiamo l’attenzione sulla prima, su Tq.

Vale per sistemi M/G/1, 1/μ è la media dei tempi di servizio, σ^2 è la varianza.

Supponiamo di gestire questo sistema, la media dei tempi di servizio è in qualche

modo fissata, ma possiamo intervenire sulla varianza, ovvero sulla REGOLARITÀ

del servizio. Se volessimo dimiuire i tempi di attesa Tq dovremmo prendere i valori

di σ più piccoli possibili, prossimi a 0.

Se prendo σ pari a 0 che sistema abbiamo? Abbiamo un M/D/1 perhé non

c’è varianza.

Allora possiamo intervenire e far variare a parità di media del tempo di servizio Tq

agendo sulla regolarità del servizio. Tq viene minimizzata quando il servizio è più

regolare possibile.

M/D/1 è un caso particolare di M/G/1

Un altro caso particolare è M/M/1

Se in M/G/1 metto σ^2=1/(μ^2) allora diventa M/M/1

Osserviamo che:

Se in un sistema con arrivi poissoniani passiamo da tempi di servizio

esponenziali a deterministici il tempo di attesa in coda si dimezza

Ci interessano anche modelli con σ^2 che sta in mezzo tra 0 e 1/(μ^2). Dal punto di vista della varianza rappresentano

due estremi.

La distribuzione di Erlang è per sistemi di tipo M/Ek/1. Anche questi sono un caso particolare dei sistemi M/G/1

È una distribuzione a due parametri, rappresenta tutti quei casi che stanno in mezzo ai due casi estremi: Tutto torna

M/Ek/1 sappiamo dalla proprietà della distribuzione esponenziale che se ho la somma di k variabili aleatorie iid secondo la

distribuzione esponenziale con media pari a 1/(kμ) la somma è una variabile distribuita secondo Erlang di parametri k e μ.

Questo ci interessa tutte le volte che il servizio che viene erogato al cliente viene erogato come somma di servizi

indipendenti ciascuno con durata esponenziale.

20 apr 2018

Nel caso M/D/1 si può anche arrivare alle formule in forma chiusa, nel caso M/Ek/1 non ci sono formule in forma chiusa.

Esercizio di esame 2004

Una banca ha 5 cassieri e ciascuno di essi ha una coda di clienti davanti a sé. I clienti che arrivano scelgono una cosa a

caso e aspettano di essere serviti. Gli arrivi sono poissoniani con frequenza media di 40 l’ora.

I tempi di servizio di ciascun cassiere sono esponenziali con media 5 minuti.

La banca sta considerando la possibilità di rendere la coda unica così ogni cliente viene

servito dal primo cassiere che si libera. Detrminare l’effetto sul tempo medio di attesa in

coda.

Se lo penso con una coda davanti a ciascun cassiere ho in pratica 5 sistemi a coda M/M/1 indpendenti, la frequenza media

di arrivo ha frequenza λ per la probabilità che il flusso vada in quella coda

Sono sistemi indipendenti, ne studio uno

Stazionarietà raggiunta

Vediamo cosa succede se abbiamo un solo sistema M/M/5 con λ complessivo e con μ che continua ad essere pari a 12.

Stazionarietà raggiunta La probabilità che il

sistema sia vuoto è

abbastanza bassa

Lo si confronta con 1/6 di prima, il tempo è più piccolo

Determinare le misure di prestazione nel caso M/M/5

Esercizio di esame del 2004

Un piccolo albergo dispone di 5 camere, vuole effettuare un’analisi sul servizio prestato alla clientela. Da un’indagine sui

dati si è dedotto che i clienti arrivano casualmente (quindi arrivi poissoniani) con media 3 al giorno e che la loro

permanenza media nell’albergo è di 1 giorno ed è distribuita esponenzialmente.

Descrivere il sistema a coda.

Il sistema è l’albergo, il servizio è la camera, abbiamo quindi 5 serventi in parallelo, il tempo di servizio è il tempo di

permanenza nella camera.

Il sistema non ha coda, ha capacità del sistema uguale al numero dei serventi (se un cliente arriva e non

trova un servente libero va da un’altra parte, non aspetta che si liberino le stanze). ERLANG LOSS

SYSTEM

Determinare la probabilità che nell’albergo non vi sia nessun cliente.

Probabilità abbastanza bassa

Determinare la probabilità che un cliente arrivi e trovi tutto pieno.

L’11% del tempo l’albergo risulta pieno quindi c’è la rinuncia al servizio di chi arriva.

Determinare il numero medio di clienti presenti nell’albergo.

In media 3 camere su 5 saranno occupate

Esercizio di esame

Una società costruisce immobili, gli acquirenti stipulano il contratto di acquisto e poi attendono che l’immobile sia realizzato

prima di poterne entrare in possesso. Vengono stipulati in media 9 contratti l’anno con una distribuzione di Poisson. La

società adotta la strategia di iniziare a costruire una nuova casa non appena è stata conclusa la casa precedente. La

società dispone di un numero di operai tale da permettere la costruzione di 12 case l’anno, ma non è nota la distribuzione

di probabilità secondo la quale esse vengono realizzate. Si dispone tuttavia del numero di giorni impiegati l’anno

precedente per realizzare le case.

L’anno prima per realizzare le case hanno impiegato:

30, 32, 29, 34, 27, 29, 29, 33, 30, 31 giorni per le rispettive case.

Utilzzando questi dati è possibile calcolare la varianza della distribuzione assumendo che all’anno ci siano 365 giorni.

Descrivere un sistema a coda che permette di studiare questo problema.

L’utente entra nel sistema quando stipula il contratto, dopo averlo stipulato si mette in attesa. La stipula del contratto

avviene in maniera poissoniana, quindi arrivi al sistema poissoniani con media λ=9 l’anno.

Per ogni cliente l’attesa è finché iniziano a costruire la sua casa, quando iniziano la sua viene servito, appena finito il tempo

di servizio il cliente esce dal sistema.

Tempo medio che trascorre tra la stipula del contratto e l’effettiva entrata in possesso della casa dal cliente

Numero medio dei contratti attivi (stipulati ma senza aver ancora consegnato la casa al cliente)

Contratti mediamente attivi, cioè stipulati con clienti che sono in attesa di ricevere l’immobile

Determinare come cambiano le due misure di prestazione T ed N se si assume che i tempi di costruzione delle case siano

distribuiti esponenzialmente.

Descrivere come è possibile intervenire sui tempi di costruzione per minimizzare il tempo necessario per la consegna

delle case ai clienti determinando come cambiano in questo caso le due misure di prestazione già calcolate.

Abbiamo visto analizzando la formula di T che il minimo si ottiene quando σ è pari a 0, ovvero quando il sistema diventa

M/D/1 ovvero tempi di servizio costanti Non è cambiato molto perché anche nel caso precedente σ

era abbastanza basso.

Esercizio di esame

Presso un parrucchiere arriva in media un cliente ogni 30 minuti, si assume che i tempi di interarrivo siano distribuiti

esponenzialmente (quindi arrivi poissoniani). Il parrucchiere impiega a servire un cliente in media un tempo distribuito

esponenzialemente con media 20 minuti. Descrivere il modello

Probabilità che il parrucchiere non sia impegnato a servire nessun cliente

Per un terzo del tempo il parrucchiere non ha niente da fare

Probabilità che ci siano più di 3 clienti

Numero medio di clienti presso il parrucchiere

Tempo medio che il cliente passa nel negozio prima di essere servito e tempo medio che passa nel negozio in tutto

Supponiamo che presso il parrucchiere possano esserci al più 3 clienti (due in attesa e uno in servizio). Per motivi di

spazio gli eventuali ulteriori clienti non possono entrare. Calcolare la probabilità che il negozio sia pieno

Probabilità bassa

Calcolare la frequenza media effettiva di arrivo Si sono abbassati gli ingressi per via del fenomeno di rinuncia

Lunghezza media della fila in attesa

Calcolare come varia la percentuale di utilizzazione del servente dal primo caso (senza limiti di capacità) al secondo caso

in cui vi è la limitazione.

Passa da un 67% ad un 58%. Nel primo caso non viene rifiutato nessuno quindi il parrucchiere lavora di più.

Reti di code

Sistema di produzione: tante stazioni di servizio, il semilavorato va su una stazione, passa poi per un’altra e altre ancora. Il

flusso di un’entità non è più limitato ad un sistema di ingressi e uscite ma ci sono tanti sistemi in sequenza tra loro.

Supponiamo di avere un grafo orientato, in ogni nodo ci mettiamo un sistema a coda, viene fuori una rete di code.

Ognuno dei rettangoli è un sistema a coda. Un oggetto potrebbe

entrare dall’esterno, tornare indietro, passare ad altri sistemi.

RETE APERTA: se ci sono ingressi dall’esterno del sistema in almeno un nodo e uscite dal sistema in almeno un nodo

RETE CHIUSA: non ci sono ingressi o uscite in nessun nodo della rete.

Quando dobbiamo definire una rete dobbiamo definire:

! TOPOLOGIA DELLA RETE

" per ogni ingresso che c’è la distribuzione di probabilità dei TEMPI DI INTERARRIVO nei nodi dove sono

previsti ingressi

# in analogia a quello che avviene nei sistemi singoli bisogna definire ognuno dei sistemi, cioè la DISTRIBUZIONE di

PROBABILITÀ DEI TEMPI di SERVIZIO ed il NUMERO dei SERVENTI per ogni nodo della rete

$ REGOLE DI INSTRADAMENTO insieme di regole che specificano quando un’entità esce da un luogo a quale luogo si

reca e con quale probabilità questo avviene, cioè dare la probabilità che un’entità che esce da un nodo vada in un altro

nodo.

Lo STATO DELLA RETE è un vettore n che ha tante componenti quanti i nodi della rete

Numero di utenti nell’i-esimo sistema

Elementi nuovi rispetto al singolo sistema:

Gli arrivi dall’esterno stanno nel primo sistema, gli arrivi nel secondo sistema dipendono dalle uscite dal primo sistema.

Bisogna quindi studiare anche le uscite dei sistemi che nella maggior parte dei casi rappresentano gli ingressi ad altri

sistemi.

Se la rete è solo in avanti (non ci sono i feeback, cioè ritorni di nuovo in uno stesso sistema) FIT FORWARD = flusso in

avanti, la rete così è meno complicata. Nella rete fit forward non è possibile che un’entità richieda due volte lo stesso

servizio.

Analizziamo le uscite da un singolo sistema

Risultato teorico importante Teorema di BURKE

Consideriamo un qualsiasi sistema M/M/s (s maggiore o uguale 1 incluso s = infinito), con frequenza media di arrivo pari a λ

e in condizioni stazionarie. Abbiamo i seguenti due risultati:

! il processo delle partenze dal sistema (le uscite) è un processo di Poisson di parametro λ

" per ogni istante di tempo t arbitrario il numero degli utenti presenti nel sistema è indipendente dalla sequenza dei tempi

di partenza prima dell’istante t.

Il primo dice che in un sistema M/M/s arrivi poissoniani, tempo di servizio esponenziali, non ha detto quanto è μ perché

indipendentemente da μ le uscite sono uguali agli arrivi.

Il secondo dice: fissato t, vediamo lo stato del sistema, questo non dipende dalle partenze che sono accadute prima di t,

come se ci fosse l’assenza di memoria.

Un’ipotesi che faremo sempre è che non ci siano capacità limitate nei sistemi: TUTTI I SISTEMI PRESENTI

NELLA RETE SONO A CAPACITÀ INFINITA

Serie di code

Una rete così semplice ha arrivi dall’esterno solo nel primo nodo e uscite solo nell’ultimo.

Supponiamo che gli arrivi dall’esterno siano poissoniani e che i tempi di servizio per ogni stazione di servizio siano distribuiti

esponenzialmente con tasso μi

In virtù del teorema di Burke un sistema fatto così lo studiamo nel seguente modo:

Per il teorema di Burke le uscite dal primo sistema sono uguali agli ingressi, quindi studiamo gli m sistemi singolarmente.

Come se fossero isolati

Se sto pensando a sistemi isolati, quindi indipendenti

Ipotizziamo un sistema fatto così:

Per ciascuno dei due sistemi so calcolare tutte le misure di prestazione. Per l’indipendenza la probabilità che il sistema

sia allo stato n la dovrei scriverere così:

È la probabilità congiunta che il sistema 1 si trovi allo stato n1 e che il sistema 2 si trovi allo stato 2. Questo si chiama

SISTEMA TANDEM.

Per l’indipendenza questa probabilità congiunta diventa

Nel caso di m qualsiasi (finito) Questa si chiama SOLUZIONE IN FORMA PRODOTTO

Per calcolare le misure di prestazione della rete sommo le misure di prestazione dei singoli sistemi

Esempio

Abbiamo due stazioni di lavoro monoserventi in serie. La prima è una stazione di lavorazione la seconda è una stazione di

collaudo (controllo qualità). I pezzi semilavorati arrivano alla prima stazione secondo un processo di Poisson con media 10

l’ora. I tempi di servizio dei serventi sono distribuiti esponenzialmente con media rispettivamente 12 e 15 pezzi l’ora.

Vogliamo studiare questo sistema e trovare il numero medio di utenti nella rete ed il tempo di permanenza.

Studio separatamente i due sistemi Se anche una sola delle stazioni non avesse ρ

minore di 1 allora l’intera rete sarebbe non

stazionaria

Per come è fatta la rete per trovare le misure complessive della rete basta aggregare le misure delle singole stazioni

Reti aperte

Reti dove è previsto che ci siano almeno un ingresso e un’uscita da e verso l’esterno.

La rete chiusa rappresenta quelle situazioni in cui l’uscita di un’entità implica l’immediato ingresso di un’altra ed il numero

rimane costante. In una rete chiusa N è un dato.

Definizione: Reti aperte di Jackson

Una rete aperta si dice di Jackson se:

! gli arrivi dall’esterno ad un nodo i-esimo (con i=1,...,n) sono poissoniani di parametro γi con γi>0 per almeno un i

(ovvero devo avere almeno un ingresso)

" i tempi di servizio di ciascuno degli Si serventi presenti al nodo i sono indipendenti e distribuiti secondo la

distribuzione esponenziale di parametro μi

# la probabilità che un utente completato il servizio presso un nodo i si rechi al successivo nodo j (i,j=1,...,m) è

assegnata pari a pij ed è indipendente dallo stato del sistema

La prima ci dice che gli arrivi al sistema rete (a ciascuno dei nodi) sono poissoniani e c’è almeno un arrivo.

La seconda ci dice che in analogia ai sistemi M/M/s i tempi di servizio sono esponenziali di parametro μi.

Le probabilità di ROUTING sono assegnate, cioè fanno parte dei dati del problema e sono indipendenti dallo stato

del sistema.

Allora in un sistema di questo tipo abbiamo nodi in cui ci sono arrivi dall’esterno, nodi in cui no, la capacità di ogni sistema è

infinita, per ogni nodo i può succedere che:

- l’utente entra provenendo da un’altra parte

- in uscita ci potrebbe essere o l’uscita definitiva dal sistema o un feedback, cioè un ritorno ad un nodo del sistema. Quindi

un utente con probabilità pij si reca ad un altro nodo della rete oppure esce dalla rete con probabilità 1-la somma di tutte le

pij MATRICE DI ROUTING

instradamento, dati del problema

26 apr 2018 Reti di code

Sistemi a coda connessi tra loro.

Teorema di Burke ingressi e uscite poissoniane di parametro λ.

Lo stato del sistema n, la probabilità congiunta si fattorizza nel prodotto delle probabilità.

Soluzione in forma prodotto

Questo vale se il sistema è aciclico (flusso solo in avanti).

Se ci fosse un ciclo (la freccia blu) il processo delle uscite si disaggregherebbe tra le unità che escono dalla rete e le unità

che tornano indietro. I processi disaggregati sono anche questi di Poisson. Il processo che entra nel sistema si compone

con quello del ritorno del ciclo, 1 vede due arrivi poissoniani, l’aggregato è anche esso poissoniano ma di parametri diversi.

L’indipendenza dei processi qui non c’è, quello che arriva dal

feedback dipende da quanti sono entrati, i due processi di

Poisson che stiamo aggregando non sono indipendenti, ecco

quindi perché i cicli ci danno problemi, si perde la poissonianità

degli ingressi ai nodi.

Si sono introdotte delle classi di reti che permettono di studiare la rete risultante, sono le RETI DI JACKSON

Reti di Jackson: reti aperte

Una rete si dice di Jackson se è data da:

1) arrivi alla rete (dall’esterno) poissoniani di parametro γi (γi>0 per almeno un i)

2) i tempi di servizio di ciascuno degli Si serventi presenti in un nodo i sono indipendenti distribuiti esponenzialmente di

parametri μi

3) pij (probabilità di routing dal nodo i al nodo j) sono note e indipendenti dallo stato della rete

4) la soluzione in forma prodotto per le reti di Jackson continua a valere

Matrice di routing

Matrice quadrata di ordine m (numero dei nodi)

Per ogni nodo j della rete γj sono gli ingressi dall’esterno ma abbiamo dei feedback, vediamo gli ingressi effettivi in un nodo:

Vale per tutte le reti aperte, sia di Jackson che no

Sistema di variabili non omogeneo che ha come variabili λi

La prima cosa da fare è trovare i λ

Caso monoservente: Sj=1 per ogni j=1,...m

Anche nel caso in cui ci sono dei cicli continua a valere la soluzione in

Teorema di Jackson: forma prodotto se la rete è aperta

Sia data la rete aperta di Jackson con m nodi ciascuno a singolo servente. La distribuzione di probabilità (congiunta) che la

rete si trovi allo stato n (n è un vettore) n=(n1,....,nm) si fattorizza nel prodotto delle probabilita marginali P(n)=pn1pn2...pnm

dove (Si potrebbe quindi scomporre la rete in tanti sistemi e studiarli tutti uno per uno come M/M/1)

Dim:

Dobbiamo riprendere un’equazione di bilancio. Bilancio globale dice che facendo il diagramma di stato il flusso entrante

deve essere uguale al flusso uscente. Equazione di bilancio dettagliato: Immagino che la rete sia in un certo stato fissato

n, penso di cambiare soltanto tra nj-1 ed nj

Abbiamo applicato l’equazione di bilancio dettagliato

Scaliamo ad ogni passaggio di un utente, si

arriverà alla fine a 0

In pratica abbiamo lasciato tutti i nodi come erano

tranne nj al quale abbiamo scalato ogi volta un utente

Lo facciamo ora per tutti i nodi

Sostituiamo P(0...0) sopra ed esce fuori che:

Per il teorema di Jackson possiamo studiare una rete di Jackson aperta come tanti sistemi M/M/1 indipendenti.

Sarebbe vera solo se in ogni nodo un utente ci andasse una sola volta

Possiamo fare anche in altri modi Throughput

time

Frazione di utenti che come primo nodo visitano il nodo j

Questa seconda formula l’ha ricavata

dall’equazione di λj dividendola per λ

Esercizio di esame del 2009

Si consideri una rete di Jackson aperta composta da 3 stazioni. Alla prima stazione arriva un utente all’ora.

Dalla stazione 1 gli utenti con probabilità 1/3 si recano alla stazione 2 oppure raggiungono la stazione 3.

Dalla stazione 2 gli utenti tornano all’ingresso della stessa con probabilità 1/2 oppure escono all’esterno della rete. Dalla

stazione 3 gli utenti escono all’esterno della rete oppure con probabilità 1/3 tornano alla stazione 1.

Le stazioni 2,3 sono identiche, monoserventi con tempi di servizio esponenziali con μ2=3/2 e μ3=3/2. La stazione 1 è

monoservente e ha tempi di servizio exp con μ=2 utenti l’ora. Verificare se la rete raggiunge la condizione stazionaria e in

caso calcolare N e T. La rete raggiunge

la condizione di

stazionarietà

Mediamente abbiamo tra i 4 e i 5 utenti nel sistema

Tempo di attraversamento medio degli utenti

Quando la rete è di Jackson studiarla è semplice, studiamo m sistemi singoli a coda e poi aggreghiamo le misure di

prestazione.

Nel caso multiservente il risultato sarà lo stesso.

27 apr 2018 Caso multiservente

Teorema di Jackson

Data la rete di Jackson aperta, la probabilità che la rete si trovi allo stato n (probabilità congiunta che il nodo 1 si trovi allo

stato n1, il 2 ad n2...)

Anche nel caso multiservente una rete di Jackson aperta si studia scomponendola in m sistemi a coda M/M/sj

Esempio

Considerare un call center al quale arrivano chiamate secondo la distribuzione di Poisson con media 35 l’ora.

Alle chiamate che arrivano il gestore fornisce due operazioni: digitare 1 per il servizio reclami oppure 2 per il servizio

informazione. Si stima che il tempo di ascolto del messaggio di scelta del tasto è distribuito esponenzialmente con media 2

al minuto. Non vi è rinuncia al servizio, gli utenti vengono tenuti in attesa. Il 55% delle chiamate chiedono di accedere al

servizio reclami e le rimanenti 45% chiedono di accedere al servizio informazioni. Il nodo del processo dei reclami ha 3

serventi che operano in parallelo che operano con tempi di servizio distribuiti esponenzialmente con media 6 l’ora. Il nodo

del processo informazioni ha 7 serventi che operano in parallelo e operano con tempi di servizio distribuiti esponenzialmente

con media 20 minuti. Il 2% dei clienti che hanno usufruito del servizio reclami decidono di usufruire anche del servizio

informazioni. L’1% che hanno usufruito delle informazioni chiedono di usufruire anche del servizio reclami. Gli altri escono

dal sistema.

Si vuole determinare la lunghezza media della coda in ciascun nodo, Njq per ogni j. Tempo medio totale che un cliente

passa in linea con il call center, T.

Dobbiamo verificare che il sistema raggiunge la condizione stazionaria. Stazionari

Studiamo ciascun nodo singolarmente

Grazie all’assunzione che queste reti sono di Jackson lo studio si effettua riconducendoci a studiare i singoli nodi della rete

Reti di Jackson chiuse

Vengono utilizzate per modellare casi in cui il numero delle entità che circolano nella rete rimane costante. Quando

un’entità esce viene immediatamente rimpiazzata.

Un settore dove vengono spesso usati questi sistemi è quello del car sharing.

In una rete chiusa se il numero degli utenti che circolano è fissato allora N è un dato del problema.

Il numero di tutti i possibili stati della rete è:

m nodi di N utenti hanno 15 modi diversi di disporsi

Al coefficiente binomiale si arriva tenendo conto che ogni nodo può assumere fino a N+1 stati (0,1,2,3,4)

N è fissato quindi AMMETTE SEMPRE DISTRIBUZIONE STAZIONARIA

Sistema omogeneo

Se vogliamo usare di nuovo la matrice di routing il sistema che viene fuori è:

In una rete chiusa la probabilità di uscire non c’è, quindi bisogna sommare le probabilità di rientrare in un nodo della rete.

Se prendiamo la matrice di routing

Se questo sistema avesse rango pieno (matrice del sistema non singolare) ammetterebbe un’unica soluzione, quella nulla.

Siccome il rango non è pieno (c’è almeno una riga linearmente dipendente) allora possiamo ottenere anche soluzioni non

nulle. Allora i λ hanno almeno un parametro libero

Una soluzione positiva del sistema

Chiamiamo

Vediamo cosa accade alla probabilità congiunta

CASO MONOSERVENTE

TEOREMA: data una rete di Jackson chiusa con m nodi e singolo servente Sj=1 per j=1,...,m allora analogamente al caso

di reti aperte la probabilità congiunta che il sistema sia allo stato n ha una soluzione in forma prodotto

G(N) fattore di normalizzazione, ci sta perché la somma di tutte le pn deve fare 1. Ha la stessa funzione della P(0...0)

di ieri.

Dim: somma tutti i possibili stati della rete

CASO MULTISERVENTE

Tempo medio che un utente passa in servizio nel nodo j

Numero medio di volte che un utente torna nel nodo j

Teorema di Gordon-Newell

Probabilità congiunta della rete si fattorizza anche in questo caso del prodotto delle probabilità marginali

Esercizio d’esame18/09/2012

Si consideri una rete di Jackson aperta in cui sono presenti 4 stazioni. S1 ha due server, ciascuno dei quali è in grado di

processare 20 pezzi/ora. S2 ed S3 hanno ciascuno un solo servente in grado di processare α/2 pezzi l’ora. S4 ha due

server ciascuno dei quali è in grado di processare 18 pz/h. Da S1 i pezzi processati raggiungono S2 con probabilità a

oppure S3 con probabilità b. Da S2 e da S3 i pezzi processati raggiungono S4 e da S4 escono dal sistema. I pezzi

entrano nel sistema secondo arrivi poissoniani presso la stazione S1 dove in media arrivano λ pz/h.

1) determinare l’intervallo di valori di α per i quali la rete ammette una distribuzione stazionaria in funzione di a e λ.

2) posti λ=30, a=0,4, α=40 determinare T, Njq per j=1,...4

Impostare il sistema

Determino i ρ e impongo che siano tutti minori di 1

chiedeva in funzione di a e λ, quindi dobbiamo togliere b

I valori che ci ha dato soddisfano le condizioni di

stazionarietà

Esercizio di esame 15/11/2012

Rete di Jackson aperta con 4 stazioni. S1 ha un solo un server che processa 20 pz/h. S2 ed S3 ciascuno 2 server che

processano rispettivamente 2pz/h e 4pz/h. S4 un server in grado di processare 2 pz/h. I pezzi semilavorati entrano nel

sistema con arrivi poissoniani presso la stazione S1 dove in media arrivano α pezzi ora e dalla stazione S2 dove in

media arrivano 2α pezzi ora. Da S1 i processati raggiungono S3, da S2 raggiungono S3 con probabilità 0,6 oppure S4.

Da S3 i pezzi escono dal sistema. Da S4 i pezzi escono dal sistema con probabilità 0,5 oppure tornano nella stazione

S2. Determinare quale stazione all’aumentare di α raggiunge per prima un fattore di utilizzazione pari a 1.

Ci si chiedeva quale stazione all’aumentare di α raggiunge un fattore di utilizzazione pari a 1

Quello col coefficiente più grande è quello che per primo raggiungerà 1. La prima a creare problemi è la stazione 2

all’aumentare di α, quindi in caso è lì che si dovrebbe intervenire.

Posto α=1 determinare T, numero di pezzi in coda in ciascuna stazione, numero medio di pezzi nel sistema.

Studiamo i singoli sistemi Numero medio di utenti presenti

nella rete

Esercizio appello 30/01/2013

Un sistema di lavorazione è costituito da 3 stazioni di lavorazione p1 p2 cq. P1 e p2 sono monoserventi, lavorano 40 pz/h.

Cq effettua il controllo qualità e possiede 2 serventi che sono in grado di effettuare un controllo in media 40 pz/h ciascuna.

Ingressi in p1 e p2 con frequenza media pari a 21pz e 28pz l’ora. Dopo la lavorazione in p1 e p2 i pezzi vengono inviati a cq

σ pezzi in uscita da cq torna in cq. Una percentuale pari a σ/2 viene rinviata a p1 per essere rilavorata.

a) specificare quali assunzioni devono essere fatte per modellare il sistema come una rete di Jackson aperta. Supponendo

che sia una rete di Jackson determinare il valore massimo che può assumere σ affinché la rete sia stazionaria. Fissato σ

determinare le misure di prestazione.

Dobbiamo supporre arrivi poissoniani, tempi di servizio dstribuiti esponenzialmente, le pij siano indipendenti dallo stato

del sistema, quindi devono valere le 3 condizioni.

Dobbiamo risolvere un sistema di disequazioni frazionarie

Per la stazionarietà deve essere:

Se è uguale a 31/120 il ρ va a 1 ed il sistema esplode

0,2 è compreso nell’intervallo che abbiamo trovato quindi

tutti i ρ sono minori di 1

03 mag 2018 Simulazione

Riprodurre il funzionamento di un sistema. Abbiamo un sistema reale che già esiste nella realtà o che deve essere creato.

L’idea è quella di creare un modello e riprodurre quello che succederebbe nella realtà. Possono essere modelli concreti o

modelli matematici (astratti).

MODELLI ASTRATTI sono modelli che si formano col linguaggio della matematica (problemi di programmazione lineare,

intera, non lineare). Si costruiscono delle relazioni che vengono sintetizzate in forma matematica. Questo tipo di modello

spesso è chiamato MODELLO DI PROGRAMMAZIONE MATEMATICA, O OTTIMIZZAZIONE, si cerca la soluzione ottima.

MODELLI DI SIMULAZIONE: modelli astratti, vengono costruiti grazie ad un’implementazione di qualche linguaggio

direttamente sul calcolatore. Mentre nel modello matematico c’è una relazione tra variabili e quantità reali qui ci sarà una

doppia freccia tra una parte del sistema e ciò che lo realizza (programma).

Riprodurre il funzionamento di un sistema: un sistema comprende delle grandezze aleatorie, come tali l’unica possibilità che

abbiamo di generare gli eventi di un sistema è quello di utilizzare una certa distribuzione di probabilità.

Generati gli eventi si fanno osservazioni statistiche e si deducono delle cose. La simulazione è un evento probabilistico,

statistico, l’analisi che si fa è del tipo WHAT IF, cosa accade se? Si chiamano ANALISI DI SCENARIO, si fanno variare dei

parametri e si vede cosa succede.

I risultati ottenuti permetteranno l’analisi di scenario, non si ha un approccio WHAT BEST ma WHAT IF, non cerchiamo

quindi l’ottimo ma vediamo cosa succederebbe se variassimo i parametri. La simulazione non determina la soluzione

ottima.

Per trovare l’ottimo con un problema di simulazione si dovrebbero fare infinite prove.

La simulazione:

! rappresenta sistemi complessi in presenza di fonti di incertezza (utilizziamo modelli stocastici)

" riproduzione di sistemi non sperimentabili direttamente (o perché non ci sono perché sono in fase di progetto oppure

perché bisogna capire se comprare o no alcune cose)

L’implementazione potrebbe essere difficoltosa, dal punto di vista computazionale il tempo di calcolo potrebbe essere

lungo. Si cerca di progettare dei modelli completi ma semplici.

Elementi che caratterizzano un modello di simulazione

! VARIABILI DI STATO:

insieme di variabili che descrivono in ogni istante di tempo il sistema (in un sistema a coda era n, numero di utenti medio nel

sistema). Ci sono variabili di stato DISCRETE o CONTINUE. La scelta discreto o continuo è legata al sistema che stiamo

modellando ma anche alle scelte di chi sta progettando

" EVENTI:

Qualsiasi accadimento che fa variare valore ad almeno una variabile di stato (in un sistema a coda potrebbero essere un

arrivo o un’uscita dal sistema). Gli eventi possono essere di origine interna al sistema o esterna (inizio del servizio è un

evento interno che fa variare il numero degli utenti in coda, l’arrivo di un utente è esogeno). Eventi ESOGENI ed eventi

ENDOGENI

# ENTITÀ e ATTRIBUTI

entità = singolo elemento nel sistema, deve essere definita in maniera esplicita, possono essere DINAMICHE o STATICHE

(in un sistema a coda utente e servente sono due entità, il cliente è entità dinamica). Alle entità vengono attaccate delle

etichette (gli attributi) che sono ad esempio in un sistema la singola coda, ingressi singoli, un solo servente, potrei

enumerare gli ingressi, potrei mettere count sugli ingressi.

$ RISORSE:

Forniscono un servizio all’entità. L’entità per usufruire del servizio ha bisogno che questa risorsa sia disponibile. La

macchina che è il servente funziona ad esempio solo se c’è un operaio che la sorveglia, allora l’operaio è una risorsa.

SIZE-DELAY-RELEASE l’utente che arriva cattura la risorsa la utilizza e poi la rilascia

! ATTIVITÀ e RITARDI:

Attività è un’operazione per cui è noto a priori il suo tempo (non è deterministico ma conosco a priori la sua distribuzione di

probabilità). Un ritardo è qualcosa che verrà generato dal funzionamento del sistema. Ci occuperemo di

modelli discreti,

dinamici, stocastici

Modello preda-predatore Modello continuo

Modello deterministico

Officina con diversi lavori L, due macchine M

I lavori vengono assegnati alle macchine quando queste si rendono disponibili

Se schematizzassimo il funzionamento di questo sistema faremmo una simulazione, è

deterministico perché non vi è incertezza.

Di questi modelli non ci occuperemo

Modelli di simulazione ad eventi discreti

SIMULAZIONE AD EVENTI DISCRETI: Le variabili di stato cambiano valori in istanti di tempo ben definiti in un insieme dei

tempi numerabile (finito o infinito). Gli istanti di tempo sono gli istanti che rappresentano l’accadimento di un evento.

Per rappresentare un modello di questo tipo devo tenere conto dell’avanzamento del tempo.

La prima problematica che si pone è il TEMPO SIMULATO (simulation clock)

Due tipi:

! avanzamento del tempo ad incrementi prefissati. Ci sono tanti istanti di tempo che va a scandire in cui non

succede nulla.

Quello che si fa più spesso:

" meccanismo di avanzamento del tempo al prossimo evento. Dal punto di vista computazionale è un metodo

più economico.

Esempio

Cosa non si deve fare.

Supponiamo di voler simulare un sistema a coda in cui i tempi di interarrivo siano distribuiti uniformemente tra 1 e 3 minuti.

Tempi di servizio anche essi distribuiti uniformemente tra 0,5 e 2 minuti.

Supponiamo che qualcuno ci dia due liste con i tempi di interarrivo e i tempi di servizio

Tempi di interarrivo Tempi di servizio Ora facciamo scorrere i tempi al prossimo evento e vediamo cosa succede

Arrivo del primo utente e inizio servizio (non fa coda)

Arrivo del secondo utente che trova il servente occupato quindi si pone in coda

Fine del servizio al primo utente e inizio del servizio al secondo utente

Arrivo del terzo utente che non trova il servente libero e si mette in coda

Arrivo del quarto utente che si mette in coda

Fine del servizio al secondo utente che quindi esce ed inizia il servizio al terzo utente

La scansione del tempo è in base a istanti prefissati quando accade un evento. Fermiamo la simulazione all’istante 5,4:

abbiamo avuto 2 utenti che sono entrati, hanno finito e sono usciti.

Il primo utente è entrato all’istante 1,9 ed è uscito a 3,6 quindi è stato nel sistema 1,7

Potrei dire ingenuamente che quello è il tempo medio di permanenza nel sistema

Questa affermazione è ingenua perché:

La dipendenza di questi risultati è fortissima dalla generazione dei numeri, sono osservazioni casuali, se le rigenero i numeri

cambiano, quindi cambiano anche le conclusioni.

Problemi:

! lunghezza arbitraria della simulazione (perché mi sono fermato all’istante 5,4?)

" dipendenza stime (risultati finali) sulle misure di prestazione dalle osservazioni casuali generate (se genero una nuova

lista avrò nuovi numeri quindi conclusioni diverse)

# le nostre stime sono influenzate dalle condizioni iniziali (se avessi detto che ci sono 10 utenti all’istante t=0 che stanno in

fila le conclusioni sarebbero state molto diverse). Stime che considerano anche il transitorio iniziale (dipendenza dalle

condizioni iniziali).

Per ovviare a questi 3 inconvenienti possiamo:

! In alcune simulazioni sarà importante studiare anche il transitorio non solo le condizioni stazionarie come abbiamo fatto

nel caso dei sistemi a coda. Nella simulazione prenderemo quindi in considerazione lo stato stazionario, ma anche intervalli

di tempo limitati (orario di apertura delle poste dalle 8 alle 14).

" Si fanno più repliche della simulazione con liste diverse. Se aumentiamo la numerosità del campione

l’affidabilità aumenta

Tutto questo si chiama Progettazione della simulazione.

04 mag 2018

Vediamo la seguente sequenza di operazioni che devono essere effettuate partendo dal problema di analisi fino ai risultati

che si ottengono alla fine del problema.

1. Analisi del problema: fase in cui si cercano di capire gli aspetti che caratterizzano il problema. Bisogna interfacciarsi in

tale fase con il committente del problema.

2. Formulazione del modello: ricordiamoci che stiamo analizzando una situazione reale che presenta fonti di incertezza.

Dal nostro punto di vista bisogna trovare le distribuzioni che caratterizzeranno i dati del modello. Questa fase di analisi dati

la deve fare chi costruisce il modello. Questo è fondamentale perché stiamo parlando di modelli stocastici. Ciò che devo

assolutamente determinare sono i processi di arrivo e delle partenze. Avrò delle distribuzioni di proprietà che regoleranno

tale comportamento. Se devo modellare un impianto ed il suo funzionamento tenendo conto dei guasti di quest’ultimo, devo

ricavare la distribuzione di tali guasti. Immaginiamo di poter disporre di questi dati forniti da chi li ha e se li ha. In altre

situazioni dove invece sono già disponibili (esempio una serie storica più lunga) il problema principale risulta essere quello

del recupero dati. Vi è anche un altro aspetto da dover tenere presente. Abbiamo parlato di recupero dati perché abbiamo

considerato un sistema che già esiste. Sappiamo però che un modello di simulazione si può pensare costruito per

riprodurre un sistema che è ancora in fase di progettazione. Si fa ricorso alle informazioni che ci sono quando questo

sistema ancora non esiste. Risulta una fase difficile e complessa. Supponiamo di aver recuperato tali dati. Stiamo

pensando ad un modello di simulazione ad eventi discreti. Quali aspetti dobbiamo considerare?

a. Definizione delle variabili di stato: sono quelle che caratterizzano il sistema.

b. Identificazione degli eventi

c. Identificazione dei valori che possono assumere le variabili di stato

d. Creare ed implementare un simulation clock: un modo per scandire il tempo, avanzamento a tempi prefissati

oppure ad avanzamento degli eventi (questo secondo tipi ci fa risparmiare tempo).

e. Definire metodo per generare eventi casuali

f. Capire tutte le transizioni di stato che ci sono state: sono quelle che mi rappresentano l’andamento del sistema

nel tempo

Questo secondo punto consta di più punti. Tali punti sono svolti da un simulatore e devono essere solo implementati nel

caso in cui il simulatore debba essere programmato da capo.

3. Analisi del modello di simulazione: quello che otteniamo dal modello è una rappresentazione algebrica, ovvero in

modello algebrico. La costruzione del modello si ottiene attraverso l’implementazione dei vari blocchi che definiscono il

modello stesso. Vi è una corrispondenza funzionale tra il processo reale e l’oggetto, inteso come oggetto informatico.

Costruito il modello questo dovrà essere analizzato in modo tale da capire nel dettaglio la formulazione fatta. Finché il

modello non viene implementato si parla di modello concettuale. Si fa quindi l’analisi di tale modello concettuale. Tale

modello nella pratica una volta fatto va analizzato insieme a chi ha fornito il problema.

4. Scelta del software (linguaggio) per l’implementazione del modello:

a. Linguaggi general purpose

b. Linguaggi specifici per la DES

1. SIMAN

2. MODSIM

3. SIMSCRIPT

c. Simulatori: pacchetto software, molto spesso basato su interfacce grafiche. Arena ad esempio traduce

operazioni nel linguaggio SIMAN. Quello che si fa oggi è usare questi simulatori. Col passare del tempo si arricchiscono di

molti tool. i. ARENA

ii. SIMIO

iii. WITNESS

iv. EXTENT

Nel corso tratteremo e vedremo ARENA e SIMIO, ma nello specifico più ARENA. Arena ha le classiche finestre di Windows,

l’uso risulta abbastanza comodo. Non è un oggetto accademico, ma ARENA si utilizza nelle aziende veramente. SIMIO è un

prodotto più recente, è più flessibile. ARENA è orientato ai processi, SIMIO invece è ad oggetti. Occorre quindi creare prima

l’oggetto se non c’è già, risulta più complicato ma è più flessibile in quanto permette di definire oggetti nuovi.

a. Fogli elettronici

5. Verifica e validazione del modello: validare vuol dire vedere se le misure tirate fuori dal modello sono una

rappresentazione buona della realtà. Quest’ultima fase risulta molto complicata da fare. Esistono un certo numero di tecniche

che si basano su diversi approcci per capire se il modello costruito funziona bene. Si può pensare di fare un’analisi di

sensibilità sull’output del modello. Tale validazione però non è vera e propria perché non abbiamo i dati, in quanto il sistema

ancora non esiste perché dobbiamo crearlo noi. Nel caso in cui questo sistema già esista, occorre fare una validazione più

accurata. Dal punto di vista statistico riusciremo a capire se i valori ottenuti sono buoni o meno.

6. Progettazione della simulazione: supponiamo di essere interessati a misure in regime stazionario. Dobbiamo decidere:

a. Lunghezza della simulazione

b. Lunghezza del transitorio iniziale, altrimenti si introdurrebbe la distorsione dovuta alle condizioni iniziali. Tale

oggetto si chiama warm up del modello

c. Numero di repliche (run) da effettuare per ottenere un’accuratezza prefissata sull’output della simulazione

Questi tre parametri saranno i tre paramenti che caratterizzeranno la progettazione. Una volta fatto il modello non basta

premere run. Non è un uso del basso livello del simulatore quello che deve essere fatto.

7. Esecuzione della simulazione: ARENA ad esempio come output dà un pdf con tutti i valori relativi al modello. Una cosa

che spesso succede è dare tutti i risultati di tutte le repliche, ma questo risulta inutile, in quanto ci interessano i valori

ottenuti complessivi finali. Spesso questi simulatori danno un output molto esteso.

8. Presentazione delle conclusioni dello studio: un’idea è quella di creare dei tool grafici. Tale presentazione dei risultati

dello studio richiede qualcosa che attiri l’attenzione. È abbastanza comune fare video grafici per far vedere il funzionamento

del modello.

Studieremo i tre blocchi: Generazioni

Analisi input Analisi output

osservazioni casuali

Cominciamo ovviamente dal primo.

Mettiamoci nel caso fortunato in cui qualcuno ha memorizzato tutti i dati di input in un database. Il nostro compito sarà

estrarre tali dati da una distribuzione che si adatta. Nel modulo processo che andiamo a compilare dobbiamo andare a

specificare le risorse impiegate ed i tempi di tale determinato processo. Tale fase l’abbiamo già trattata nel corso di

modellistica ed identificazione, per questo non ci soffermeremo troppo, mentre ci soffermeremo di più sugli altri 2 blocchi.

Analisi di input

Dato un campione vogliamo estrarre delle informazioni da quest’ultimo facendo inferenza statistica. L’assunzione che si fa è

che esiste una distribuzione di probabilità della popolazione. Le informazioni che abbiamo sono solo circa tale campione,

per questo dobbiamo fare questa inferenza statistica. Si indica solitamente con X1,…,Xn il campione. Il campione è formato

dai dati a disposizione dal nostro punto di vista. Questi Xi risultano iid. Quello che conosciamo sono media e varianza della

popolazione, rispettivamente μ e σ^2. Stimatore corretto di μ

Stimatore corretto di σ^2

Dobbiamo scegliere una distribuzione di input. Dobbiamo scegliere tra queste tipologie di approcci:

1. Trace drive simulation: distribuzione guidata dai dati. È un approccio che ha come controindicazione il fatto che

siccome il modello non fa altro che riprodurre il passato (rigenera sempre eventi già accaduti) può tenere conto di eventi

particolari che erano stati osservati nello storico che si ha. Tale approccio non viene sostanzialmente mai seguito

2. Distribuzione empirica: ho dei dati a disposizione e da questi costruisco la distribuzione empirica, tutti gli eventi però

che verranno generati saranno interni all’intervallo di dati forniti (non verranno mai generati valori che superano il max o il

min presente all’interno dei valori forniti).

Vediamo un esempio di distribuzione empirica:

Mettiamo in ordine Formula di interpolazione

La formula in mezzo è quella che congiunge tutti i punti

nell’intermezzo tra i due casi estremi (0 e 1).

Supponiamo Equiprobabili

3. Distribuzione teorica: è l’approccio che si utilizza per la maggiore. Utilizzo delle distribuzioni standard, cercando quella

che si adatta meglio. Quello che ci interessa è il parametro di forma d di scala. Per quanto riguarda le discrete, esistono dei

software che dati in input dei dati fanno fitting.

Per quanto riguarda la Scelta di una distribuzione teorica, dobbiamo:

1. Verificare l’indipendenza delle osservazioni

2. Individuare una famiglia di distribuzioni

3. Stimare i parametri della distribuzione

4. Verificare se i risultati sono rappresentativi

Verifica dell’indipendenza delle osservazioni

Per l’indipendenza la prima cosa che vado a studiare è il coefficiente di correlazione ρ. Se è verificata l’indipendenza tale

parametro vale 0. Se la nostra stima del coefficiente di correlazione è significativamente diversa da zero allora ci

aspettiamo che non vi sia indipendenza. Per questo si fa o il grafico ridotto a ρ oppure il diagramma di dispersione che

rappresenta delle osservazioni estratte da una distribuzione esponenziale con media 1.

Stima del coefficiente di correlazione

Individuazione di una famiglia di distribuzioni

Si fa riferimento ai dati, si utilizza tutto ciò che viene fuori dalla statistica descrittiva di tali dati, utilizziamo anche grafici

quali istogrammi per capire l’andamento che più si adatta ai dati in questione. Della distribuzione si vanno a trovare:

1. Elemento più grande e più piccolo

2. Media campionaria

3. Mediana

4. Varianza

5. Coefficiente di variazione

6. Grado di asimmetria

Sappiamo a priori come sono caratterizzate certe distribuzioni. La prima osservazione che si fa è quella di confrontare

media e mediana, che ci dice quanto è simmetrica la distribuzione.

1,2,3,4,5

Pi=0,2

Media=3 Distribuzione simmetrica

Mediana=3

Sappiamo che per una distribuzione esponenziale il coefficiente di variazione è pari ad 1.

Il coefficiente di variazione è pari ad 1 per quella di Poisson, minore di uno per la distribuzione binomiale.

Tutto questo serve per orientarsi circa quale test di ipotesi fare.

Il secondo passo importante è l’uso di un istogramma. Vogliamo vedere se la distribuzione continua approssima bene

l’istogramma. Fare tale istogramma vuol dire dividere in tanti intervallini e chiamare hj il numero di osservazioni che cadono

in tale intervallino dell’istogramma j-esimo. Mi costruisco poi l’istogramma. La funzione h che ho definito risulta quindi a tratti

e mi da informazioni su questi dati.

Supponiamo di avere una variabile aleatoria X e che f sia la sua densità di probabilità.

Il problema nel fare l’istogramma è dover determinare il numero degli intervalli, ovvero k. Tale parametro dobbiamo

deciderlo noi. L’intervallo tra la più piccola e la più grande osservazione deve essere sezionato in k pezzi. Se k risulta

molto grande, l’istogramma risente molto degli andamenti locali. Se k risulta piccolo viceversa si vanno a perdere

andamenti significativi locali che in questo modo vengono assorbiti in questi tratti. Esistono delle linee guida in letteratura

per determinare k, ma non funzionano. La regola di Sturges, dice di prendere k tale che k=[1+log2 (n)]. Questa è una

regola proposta, ma si dice che non funziona. Quello che si fa è cercare in maniera empirica come meglio scegliere

questo parametro.

10 mag 2018 Generazione

Analisi input Analisi output

osservazioni casuali

Generazione osservazioni casuali da

distribuzioni di probabilità assegate

Rientra nel contesto di calcolo delle probabilità.

Quando abbiamo parlato della simulazione ad eventi discreti abbiamo visto un esempio di simulazione fatto a mano.

Sistema monoservente monocoda con arrivi distribuiti uniformemente, servizio idem. Modello che non abbiamo studiato dal

punto di vista analitico.

Per simulare, cioè far funzionare il sistema, abbiamo dovuto generare degli eventi: arrivi, utenti in coda, servizi, uscita ecc.

Abbiamo supposto di avere dei dati derivanti dalle osservazioni.

Si parte da osservazioni generate dalla distribuzione uniforme nell’intervallo [0,1) poi attraverso opportune trasformazioni

si arriva ai dati nella forma necessaria.

Il calcolatore è una macchina deterministica, i dati ci servono casuali, c’è una incongruenza. Si generano eventi casuali

utilizzando una macchina deterministica. Vediamo perché le cose funzionano: si cerca di generare osservazioni in maniera

deterministica aventi proprietà statistiche che permettono di considerare queste osservazioni come casuali, cioè che hanno

proprietà statistiche tali da approssimare bene osservazioni veramente casuali.

Dice questo: ho dei dati deterministici ma se poi faccio un’analisi statistica su questi trovo dei risultati molto simili a

quelli che avrei se fossero casuali.

Quando generiamo numeri casuali dalla distribuzione uniforme [0,1) si dice che facciamo una generazione di osservazioni

PSEUDOCASUALI uniformemente distribuite in 0,1: U(0,1).

L’algoritmo più comune va sotto il nome di GENERATORI CONGRUENZIALI LINEARI.

È una procedura iterativa che a partire da un’osservazione iniziale (SEME DEL GENERATORE) che diamo noi, genera in

maniera iterativa altre osservazioni in modo da avere una successione di osservazioni che possiamo considerare casuali

U(0,1)

Si assegna un valore intero m

Si assegna un primo valore di questa successione Z0 che viene chiamato SEME

Lo schema iterativo è: Operazione modulo m (il resto della divisione)

Utilizzo a e c che sono due costanti anche esse fissate, a si chiama MOLTIPLICATORE, c si chiama INCREMENTO

Con questa regola genero numeri interi (se parto con numeri interi)

Le Zi devono rappresentare numeri interi (anche più grandi di 0,1) per rappresentarli in [0,1) quindi si usano le frazioni

Esempio Se proseguissi genererei gli stessi numeri, non ha alcun senso. Questa

generazione ci produce una sequenza di numeri interi compresi tra 0 e m-1

Ho generato tutti i numeri tranne lo 0.

Il generatore si dice a periodo pieno se vengono generati tutti i numeri interi compresi tra 0 ed (m-1)

Quello che abbiamo generato ora non è a periodo pieno perché non ci restituisce tutti i numeri interi tra 0 ed m-1.

Quando accade che c=0 abbiamo posto uguale a 0 la parte additiva, si parla di GENERATORE MOLTIPLICATIVO.

Si passa alle frazioni. Le Zi non superano mai m-1 quindi sono tutti numeri frazionari.

Per realizzare una successione pseudo-casuale in [0,1) dobbiamo precisare alcune cose:

! Vorrei avere un periodo molto lungo, in modo tale da non generare gli stessi numeri da un certo punto in poi, cercare di

avere generatori a periodo pieno con periodo molto lungo

" I numeri che non prenderemo mai sono i numeri irrazionali, dobbiamo allora affrontare il problema dei numeri irrazionali

che non verranno mai generati.

Esiste un modo per essere sicuri di generare una successione a periodo pieno?

Sì, opportuna scelta dei parametri che caratterizzano i generatori.

Esiste un risultato (che non dimostriamo) che dà condizioni sufficienti sul fatto che un generatore abbia periodo pieno

Teorema

Un generatore congruenziale lineare ha periodo pieno se sono verificate le seguenti condizioni:

Vediamo come risolvere il secondo problema

Abbiamo numeri razionali in [0,1) ma il generatore non genera numeri irrazionali.

Per ovviare a questo inconveniente si cerca di scegliere m molto grande, allora generiamo tantissime frazioni nell’intervallo

[0,1) quindi generiamo un insieme denso nell’intervallo [0,1).

La densità è una proprietà molto importante, se abbiamo un numero irrazionale possiamo generare una successione di

razionali che converge a questo numero irrazionale. La densità dà la possibilita di approssimare bene anche i numei reali,

quello che faccio è generare una successione di numei razionali in [0,1) ma talmente densa in modo da approssimare bene

anche numeri irrazionali che la sequenza non genera. Risolvo il prolema sempre con i parametri. Scelgo m molto grande in

modo da generare un sottoinsieme denso dell’intervallo [0,1).

Come faccio a partire dalle osservazioni in 0,1 ad avere osservazioni in una distribuzione qualsiasi?

Supponiamo di avere le Ui osservazioni pseudo-casuali uniformemente distribuite in [0,1)

Metodo della TRASFORMAZIONE INVERSA

Metodo ACCEPTANCE REJECTION

Metodo della TRASFORMAZIONE INVERSA

Semplice, si basa su un risultato:

PROPOSIZIONE

Data una variabile aleatoria uniforme in [0,1) allora per ogni funzione di distribuzione continua F la variabile aleatoria

X=F^(-1)(U) ha come funzione di distribuzione la F

Vogliamo generare osservazioni da questa distribuzione di probabilità assegnata continua, questa proposizione dice: ho

una successione assegnata, faccio questo: mi calcolo

Osservazioni casuali estratte da una distribuzione

A partire dalle U applichiamo l’inversa della funzione di ripartizione, queste le possiamo considerare come osservazioni

estratte da una distribuzione continua

Esempio Ho le Ui che sono le osservazioni che stanno tra 0 e 1, per ognuna di queste trovo Xi

(funzione inversa)

Dim: Funzione di distribuzione di X. La dimostrazione sarà che

F è di ripartizione, quindi non decrescente. Ho che:

Quindi posso sostituire sopra

Può capitare che la F sia non definita quando la funzione non è strettamente monotona. In questi casi si usa la

PSEUDO INVERSA

Basta definire

Esempio

Voglio generare osservazioni casuali da una distribuzione esponenziale

Qualcuno mi dà delle osservazioni casuali

Calcolo l’inversa

Passiamo da osservazioni pseudocasuali in 0,1 a osservazioni estratte da diverse distribuzioni

Osservazione:

Osservazioni pseudocasuali in 0,1

Sono anche queste osservazioni pseudo-casuali in [0,1)

Cambia la correlazione, non ottengo le stesse Xi nei due casi. Il cambiamento della correlazione sarà importante quando

parleremo di teniche per la riduzione della varianza

Vediamo ora come si procede nel caso discreto

Caso discreto

Vediamo graficamente come si fa Formalmente devo determinare il più

piccolo valore di ksegnato tale che

E porre

Tesi

Dobbiamo far vedere che

Caso in cui abbiamo difficoltà a calcolare l’inversa:

In questo caso devo scrivere in forma esplicita la funzione inversa, può

non essere sempre possible

11 mag 2018

In riferimento ad un sistema a coda devo generare tempi di interarrivo e tempi di servizio.

Generare osservazioni casuali da distribuzioni di probabilità.

La maggior parte dei metodi si basano sulla generazione di osservazioni casuali uniformemente distribuite nell’intervallo

[0,1). Generiamo realizzazioni di variabili aleatorie.

Vogliamo far sì che tutti gli infiniti numeri in [0,1) possano comprarire nella successione con la stessa probabilità. Utilizziamo

un algoritmo di tipo deterministico, è inevitabile che la generazione di osservazioni casuali venga fatta in maniera

deterministica.

Con opportune scelte di m, a, c si riesce ad avere delle osservazioni che se analizzate con metodi statistici sono buone

approssimazioni di osservazioni davvero distribuite uniformemente in [0,1). Noi generiamo solo numeri razionali, se

prendiamo numeri m molto grandi i punti generati sono molto densi, la densità è una proprietà topologica che permette di

approssimare anche i numeri irrazionali attraverso una sequenza di numeri razionali.

Abbiamo due metodi per trasformare i dati.

Esercizio esame del 07/01/2008

Si vuole generare una succesione di osservazioni casuali da una distribuzione triangolare, che ha per funzione di

distribuzione la seguente:

Con il metodo della trasformazione inversa (dobbiamo definirla). Generare i primi 4 termini della successione utilizzando

come generatore di numeri pseudocasuali in [0,1) un generatore congruenziale lineare moltiplicativo (c=0) con seme 3 m=5

e a=3.

Svolgimento:

Dobbiamo vedere se la funzione è invertibile.

Tra 0 e 1 è un arco di parabola, per x tra 1 e 2 è un arco di parabola con la concavità verso il basso, poi vale 1

Funzione continua, nell’intervallo [0,2] è strettamente monotona crescente, quindi

l’invertibilità è garantita.

Poiché è definita per casi dei valori delle ascisse anche per l’inversa sarà uguale.

Il generatore congruenziale lineare ha questa espressione:

Esame 11/02/2009

Trasformazione inversa

Generatore congruenziale lineare

Inverto la funzione: Cambio segno per poter riapplicare il log

Dobbiamo usare questa

Generare le prime 4 osservazioni Fare i conti

Esercizio di esame

Dstribuzione di Cauchy

Trasformazione inversa

Generatore congruenziale lineare:

Quando facciamo la trasformazione inversa la lasciamo come parametrica, poi all’ultimo ci mettiamo i numeri

Funzione monotona crescente, possiamo fare l’inversa su tutto l’asse reale

Questa è la trasformazione inversa

Esame 19/12/2014

Distribuzione la cui densità di probabilità è la seguente:

Dobbiamo trovare la funzione di ripartizione, bisgona fare l’integrale

Dovremmo verificare che non sia una densità, cioè:

In questo caso è così, in teoria si dovrebbe fare questa verifica e poi la continuità, quindi vedere quanto fa F(1) da destra e

da sinistra È una funzione invertibile in [0,2]

Ora a partire da questa si fa la stessa cosa che negli esercizi precedenti.

Metodo acceptance-rejection

Supponiamo di voler generare osservazioni estratte da una distribuzione di probabilità che ha per funzione di ripartizione F

e la densità f. Supponiamo di disporre di un metodo per generare osservazioni casuali da un’altra distribuzione, che ha

densità g.

Genero osservazioni Y (che non è la distribuzione desiderata) poi si accettano o si rifiutano quelle della distribuzione la

cui densità è quella desiderata f. L’accettazione o il rifiuto avvengono con probabilità proporzionale al rapporto

Si prende questo rapporto e si cerca una costante che sia un upper bound di questo. Si cerca una c tale che risulti f/c

minore o uguale c per ogni y

Passo 1: Si genera una osservazione casuale della variabile aleatoria y, quella della distribuzione di appoggio

Si genera un numero casuale U della distribuzione uniforme in [0,1) indipendente da Y

Passo 2: Se risulta che U è minore o uguale di f(Y)/cg(Y) allora c’è l’accettazione, si pone X=Y e stop, altrimenti si torna al

Passo 3: passo 1 e si itera

Se in g ci mettiamo 1 allora anche le y sono numeri in [0,1), possiamo farlo perché la g la scegliamo noi.

Accettiamo quando si verifica l’evento, quello che dovremmo fare è cercare la probabilità che questo evento accada, è

un evento condizionato.

In termini generali il tipo di distribuzione di probabilità che mi aspetto per le x generate in questo modo è la

distribuzione di probabilità delle y condizionata all’accettazione.

Proposizione:

La variabile aleatoria X generata con il metodo A-R ha densità di probabilità f. (Questo è il risutato teorico che ci dice che

l’algoritmo funziona)

Dim:

Ricaveremo le espressioni di alcuni pezzi pioi le metteremo insieme per avere il risultato finale.

Questa la teniamo da parte

Nell’algoritmo ci sta una richiesta che le u sono generate indipendentemente

Calcoliamo ora dalla x. Se sono indipendenti questa probabilità condizionata è uguale alla

probabilità in cui viene meno il condizionamento.

Mettiamo da parte anche questo

Mettiamo da parte anche questo

La probabilità al denominatore è venuta 1/c

quindi sostituisco

Ho fatto vedere che la funzione di distribuzione di X è uguale a F(x), cioè la distribuzione desiderata.

Il test sostanzialmente è il test che fa tonrare le cose, c serve a far tornare i conti con la densità se no rimarrebbe

una costante. Esempio

Osservazioni casuali da variabile aleatoria con densità

(È la distribuzione β con parametri 1 e 2)

Qui usare il metodo dell’inversa sarebbe difficile da applicare. Applichiamo il metodo alternativo della accettazione. Devo

appoggiarmi ad una distribuzione nota della quale so generare le osservazioni. Devo quindi inventarmi una g(x) densità di

probabilità per la quale dispongo di un mertodo per generare osservazioni casuali.

Prima cosa che serve è il calcolo della c, che era la limitazione superiore.

Potremmo riuscire a determinre con delle maggiorazioni a priori, se no calcolo il punto di

massimo, sostituisco e trovo il valore massimo assunto dalla funzione.

Per far vedere che è un massimo si calcola la derivata seconda per x=1/4 ci accorgiamo che è minore di 0 quindi abbiamo

un punto di massimo relativo.

Per trovare c devo fare

Non dobbiamo per forza trovare il massimo, dobbiamo trovare solo una limitazione superiore, anche più grande del

massimo. In certi casi conviene trovare il punto di massimo ma andrebbe bene qualsiasi punto.

Test:

Abbiamo il test, ora possiamo scrivere il metodo

In genere dobbiamo solo scrivere lo schema del metodo, se non espressamente richiesto non dobbiamo generare i dati.

Passo 1: genero una osservazione casuale U1 (devo generare la Y)

Passo 2: genero osservazione casuale U2 U(0,1) (che sarebbe la U)

Passo 3: se U (cioè U2): Altrimenti si torna al passo 1

17 mag 2018 Progettazione di una simulazione

L’estensione dei file di Arena è sempre d.o.e

D.O.E

Cose da tenere sotto controllo:

➡ dobbimo utilizzare le statistiche per interpretare i risultati della simulazione, purtroppo però i risultati delle simulazioni

sono correlati e non indipendenti. Primo problema: I PROCESSI DI OUTPUT NON SONO INDIPENDENTI.

➡ per garantirci una certa accuratezza predefinita nei dati di uscita dobbiamo fare un certo numero di repliche: il carico

computazionale richiesto potrebbe essere non banale. Ovvero per raccogliere la quantità di dati necessaria affinché la

statistica sia significativa potremmo avere tempi molto elevati: POSSIBILE ELEVATO CARICO COMPUTAZIONALE.

Dalle slide

n è il numero delle repliche, m la lunghezza delle repliche

Supponiamo di avere i dati di output di una simulazione: questi dati dal punto di vista teorico li potremmo vedere (li

chiamiamo Yi) come delle realizzazioni di variabili aleatorie.

Per noi i dati di uscita sono interpretabili come un processo stocastico Yi a tempo discreto.

Le Yi potrebbero essere il tempo passato in coda dell’i-esimo utente oppure una qualche misura di prestazione che mi

interessa. Queste Yi nella maggior parte dei casi non sono indipendenti ma correlate, così non possiamo applicare i

metodi standard della statistica. Allora si fanno un certo numero di repliche nel seguente modo:

Siccome le repliche sono indipendenti ogni riga è indipendente dalle altre righe.

Faccio tante righe ma invece di ragionare per righe ragiono per colonne. Ogni volta che prendo un elemento questo

appartiene ad una replica diversa, queste righe sono indipendenti quindi i valori appartengono a repliche diverse.

Ragionando per righe nella tabella riesco a risolvere il problema dell’indipendenza.

Una grossa distinzione: sono interessato a misure di prestazione del sistema a regime stazionario oppure potremmo avere il

problema di rappresentare il funzionamento di un sistema considerando anche le condizioni iniziali e quelle finali.

Esempio ufficio postale che apre alle 9 e chiude alle 14. Non si raggiunge la condizione di stazionarietà. Il sistema ha un

inizio e una fine. All’inizio e alla fine il sistema sarà vuoto. Dobbiamo distinguere due diversi modi di fare la simulazione:

➡ ORIZZONTE FINITO (con terminazione) riflette un’analisi tipo quella dell’ufficio postale

➡ ORIZZONTE INFINITO Sistema di produzione continuo h24 nel quale dobbiamo misurare le misure di

Non voglio che la stima sia influenzata dal transitorio iniziale.

prestazione nella stazionarietà.

La simulazione più facile è quella ad orizzonte finito perché non dobbiamo eliminare la distorsione dalle condizioni iniziali e

non dobbiamo determinare n perché c’è qualcosa che ci dice che la simulazione deve finire ad un certo punto.

Se dobbiamo studiare lo stato stazionario dobbiamo essere sicuri di non essere influenzati dalle condizioni iniziali e avremo il

problema di decidere quanto grande deve essere n.

Distribuzione transitoria (simulazione ad orizzonte finito)

Funzione di distribuzione uguale ad una probabilità condizionata da I, cioè dalle

condizioni iniziali

Distribuzione transitoria (simulazione senza terminazione)

se questo limite esiste allora si parla di distribuzione stazionaria (da un certo i in poi le

variabili Yi hanno la stessa distribuzione)

Non dipendono da i, le i possono influenzare solo la rapidità di convergenza.

Simulazione con terminazione - analisi del transitorio

Dividiamo la simulazione in due tipi: Simulazione senza terminazione - analisi dello stato stazionario

Analisi del transitorio

X variabile aleatoria che rappresenta una certa misura di prestazione

Xi realizzazione dell’i-esima replica

Siccome sto pensando che Xi è una realizzazione fatta su repliche diverse e le repliche sono indipendenti allora le Xi

sono indipendenti (sto ragionando per righe)

Stimatore corretto di Semiampiezza dell’intervallo di

Stimatore corretto della varianza confidenza 100(1-α)%

Esempio

Supponiamo di avere una banca con 5 cassieri e una coda, apre alle 9 e chiude alle 17, resta in funzione finché l’ultimo

cliente entrato fino alle 17 viene servito, arrivi poissoniani con una certa media, tempo di servizio esponenziale con media 4

minuti, nessun cliente presente all’inizio. Ho necessità di analizzare il funzionamento del sistema dalle 9 alle 17.

Facciamo diverse repliche (genero osservazioni dalle due distribuzioni di probabilità)

Replica. Clienti. Ore. t medio di attesa

1. 484. 8:12. 1:53 484 clienti sono entrati, il funzionamento è stato di 8 ore ma ci sono

stati dei minuti in più, 8 ore e 12. Facendo la media dei tempi di

2. 475. 8:14. 1:66 attesa dei 484 clienti viene che mediamente hanno aspettato 1 min

e 53 secondi. Cambiano le ossevazioni tra le repliche

3

4

5

Cambiando il seme si generano repliche diverse, se lasciassi lo stesso seme otterrei sempre le stesse osservazioni.

Supponiamo di farne 10. Perché 10?

Per analizzare in maniera significativa ragiono per colonne. Vado a calcolare la media dei numeretti, la stima della varianza,

intervallo di confidenza

Tempo medio di attesa in coda di un cliente: media 2:03 con varianza 0,31. Punto critico con t di student t9(1-α/2)

prendo α90% mi viene 2.03 centro dell’intervallo +-0,32 (semiampiezza intervallo di confidenza)

Quindi tutte le stime le faccio per colonne, ho la garanzia dell’indipendenza.

C’è un problema importante che dobbiamo iniziare ad analizzare: perché fare 10 repliche?

Dobbiamo avere delle linee guida che ci dicono come determinare n. N è in relazione all’accuratezza che ci aspettiamo,

all’aumentare di n mi aspetto una maggiore accuratezza: devo capire quanto sono distante dal valore che sto

approssimando, quindi devo valutare l’errore. Supponiamo che stiamo stimando il valore medio, dobbiamo valutare due

grandezze standard: ERRORE ASSOLUTO ed ERRORE RELATIVO.

Errore assoluto Si fissa una soglia. α, voglio far sì che n sia tale che la prob che l’errore assoluto

sia sotto una cera soglia β fissata a priori almeno pari a 1-α.

In questo caso è semplice perché ho già la semiampiezza dell’intervallo di confidenza.

Ci aspettiamo che l’errore assoluto effettivamente sia minore di β in almeno il 90% dei casi (se prendiamo l’intervallo di

confidenza al 90%)

Errore relativo

Per come è definito al denominatore c’è μ, il problema è che μ non lo conosciamo, di solito ci mettiamo uno stimatore.

La ricaviamo così: Questo posso

controllarlo nella pratica

Man mano che faccio le repliche posso verificare questa condizione. μ non lo posso calcolare ma posso calcolare una

stima corretta. Divido per 1-L

Sono andato a crearmi una maggiorazione dell’errore relativo

Se voglio che l’errore relativo sia sotto uncerto γ devo prendere

L era l’upper bound del rapporto tra semiampiezza intercallo di confidenza e stima dela media

Analizzando questi due valori possiamo sapere quanto deve essere grande n.

Quindi n si determina facendo riferimento ad uno dei due errori, si agisce sull’unica grandezza che possiamo veirifcare cioè

semiampiezza dell’intervallo di confidenza.

Procedure Procedura a due fasi

Si fanno un certo numero di repliche fissate n0 e calcolo

n0 è arbitrario ma è relativo a quanto costa fare una replica

Seconda fase: eventuali altre replcihe (senza calcolare sn^2) fino alla precisione desiderata

Procedura iterativa

Passo 0: si effettuano n0 repliche e si pone n=n0

Passo 1: si calcolano si usa come stima di μ e stop

Passo 3:

Altrimenti si effettua un’ulteriore replica, si pone n=n+1 e si va al Passo 1

Quella che di solito si effettua è la procedura iterativa

Riprendiamo l’esempio della banca

Decidiamo di fare ad esempio 5 repliche iniziali, facciamo i conti, vediamo l’errore assoluto, se va bene ok, se no ne

calcolo un’altra.

Supponiamo di voler stimare con errore pari a 0,25

Procedura a due fasi Questo è quello che dobbiamo andare a vedere se

è verificato

Procedura a due fasi

Procedura iterativa

Supponiamo di volere un errore relativo γ=0.10

Ogni volta ricalcolo la stima della varianza campionaria

All’aumentare delle repliche la varianza si allontanava dal valore con 10 repliche

18 mag 2018 Con terminazione

SIMULAZIONI Senza terminazione

Simulazione con terminazione: abbiamo già dato l’evento che dice FINE DELLA SIMULAZIONE, la lunghezza è quindi già

stabilita (m prestabilito).

Devo prendere l’output dei dati su tutto l’orizzonte temporale che ho realizzato, devo analizzare anche i dati che generano

distorsioni. Non mi preoccupo del funzionamento stazionario, prendo tutti i dati fino alla fine della simulazione. L’unica cosa

da determinare è quante repliche fare.

Ne caso senza terminazione n lo dobbiamo decidere noi, m lunghezza, l la lunghezza del WARM UP?

Fissiamo l’attenzione su una sola misura di prestazione. Vogliamo stimare il valor medio di questa variabile aleatoria che

stiamo cercando di trovare, la chiamiamo X, μ è il valore atteso di x. Abbiamo un campione Xi, i varia sulle varie

simulazioni (per ogni replica vado a stimare la grandezza, poi cerco di utilizzare tutti gli strumenti statistici ragionando però

sulle varie repliche per garantire l’indipendenza). (Ragiono per colonne)

Cerco di stimare media e varianza attraverso la media campionaria e varianza campionaria.

Stimatore corretto

Fissato un livello di accuratezzza α in 0,1 possiamo calcolare l’intervallo di confidenza approssimato al 100(1-α)%

Usiamo la T-student Punto critico della distribuzione di probabilità (potevo prendere anche la normale) è un

valore tabellato

Calcoliamo la semiampiezza dell’intervallo di confidenza

Il problema che ci siamo posti ieri è quello di capire quante repliche fare, l’unica cosa da decidere è n per avere

sufficiente accuratezza. Analiticamente sono disposto ad accettare un errore relativo o assoluto non superiore ad una

certa soglia. La scelta di n si fa in base al grado di accuratezza da ottenere in base all’errore relativo e all’assoluto.

Errore assoluto

Voglio garantire che l’errore assoluto sia minore di una certa soglia

Quindi ci assicuriamo che: Impongo che la smiampiezza sia minore o

Faccio questo guardando l’intervallo di confidenza uguale di β

Aumentando le repliche si restringe, se ho già raggiunto l’accuratezza che mi serve posso fermarmi, altriementi

aumento n.

Errore relativo

L’errore relativo ha una definizione diversa, μ non la posso controllare Sostituendo μ con la stima

Di μ ho solo una stima, per stimare l’errore relativo posso fare solo così: commettiamo un errore

Se ho un controllo su quella quantità (minore o uguale di L)

Se voglio che:

Con diversi passaggi per ottenere la diseguaglianza dobbiamo fare questo controllo:

Questa trasformazione è dovuta al fatto che approssimiamo μ con la media campionaria.

Controlliamo facendo le repliche verificando di aver raggiunto o meno la precisione voluta. Procedura iterativa, aggiungo

repliche finché non ottengo soddisfatta la diseguaglianza.

PROCEDURA ITERATIVA.

L’altra procedura (PROCEDURA IN DUE FASI) la facciamo quando dobbiamo risparmiare conti sulla varianza. Facciamo

un certo numero di repliche iniziali n0, facciamo i conti media varianza Ic, non è soddisfatta la disequazione, aggiungo una

replica e ricalcolo tutto tranne la varianza campionaria. Questo metodo a due fasi funziona se lasciare invariata la varianza

campionaria al crescere di n comporta un errore molto piccolo altrimenti no.

Esempio (esame del 2006)

Effettuando una simulazione per stimare il tempo medio di attesa in coda di un utente in un sistema M/M/2 con λ=4 e μ=3.

(Analiticamente potremmo calcolare tutto). Facciamo un modello di simulazione, facciamo 6 repliche, per il tempo medio di

attesa in coda otteniamo:

! 0.32

" 0.25

# 0.20

$ 0.40

% 0.29

& 0.19

Calcolare la stima della media in un intervallo di confidenza al 95%.

Determinare se le 6 repliche effettuate sono sufficienti ad ottenere un errore assoluto sulla media inferiore a 0.075.

In caso negativo applicare la procedura iterativa per determinare n in modo tale da ottenere questo errore assoluto,

sapendo che nelle repliche successive abbiamo questi numeri:

0.26. 0.31. 0.22. 0.25

Svolgimento:

Calcoliamo la semiampiezza dell’intervallo di confidenza Uso la t-student (pochi numeri, solo 6)

Ora confronto se questo è più piccolo di β

Non lo è, allora procedura iterativa, aggiungo una replica

Confrontiamo con β, ci siamo. Quindi 6 repliche non erano sufficienti ma 7 sono sufficienti per dire che l’errore assoluto è

minore di β.

Se avessi avuto l’errore relativo avrei dovuto vedere con quale numero confrontare il β, cioè γ/(1+γ)

Simulazioni senza terminazione

Simulazioni senza terminazione cioè dobbiamo stimare le quantità nel caso in cui il sistema ha raggiunto l’equilibrio

statistico di situazione stazionaria. Chiamiamo Yj il processo di output (dati di uscita) quello che vogliamo stimare è il limite

per j che tende all’infinito di queste Yj.

Esiste un certo j dal quale poi il sistema ha raggiunto lo stato stazionario.

Fisso m, non ho l’evento naturale che mi definisce la lunghezza della replica a priori.

Operiamo come nel caso con terminazione: calcoliamo la media campionaria, quello che accade è che questo non è uno

stimatore corretto perché vi è una distorsione introdotta dai valori iniziali.

Problema dello STARTUP

Facciamo il grafico del valore atteso delle tiq al variare di i. In ascissa abbiamo i cienti che arrivano, facciamo tanti grafici

variando le condizioni iniziali. Ci aspettiamo un grafico in cui le curve all’inizio fanno un po’ come vogliono ma da un certo

punto in poi tutte dovranno tendere all’asintoto 8,1.

Se per fare la media consideriamo la prima parte ovviamente la media non è uno

stimatore corretto. Quello che vogliamo capire è da che punto in poi considerare i

dati.

In una simulazione del genere si buttano via tutti i dati che riguardano i primi

(esempio) 480 clienti. APPROCCIO REPLICHE-CANCELLAZIONI. vengono

trascurati gli output riferiti al tratto transitorio.

Questa procedura si chiama WARM UP (riscaldamento del modello)

l è la lunghezza del WARM UP, quindi sommo a partire dall’intero successivo ad l

Determinare l tale che per i>l risulti Non distorta

Le procedure per individuare l sono grafiche non analitiche. Si confrontano i grafici delle diverse misure di prestazione che

ci interessano e si cerca di vedere qual è il valore soglia

Vediamo un altro grafico

Sistema a tandem con un feedback

Faccio 10 repliche, il grafico si riferisce a m=160 ore, disegna il valore di ni

In un grafico del genere è impossibile trovare il punto di inizio delle condizioni stazionarie.

Nella simulazione sono fondamnetali le TECNICHE PER LA RIDUZIONE DELLA VARIANZA

Vogliamo mantenere invariato il valore della media, vogliamo però diminuire la varianza.

Vediamo come definire una procedura che possa fare un trattamento dei dati lasciando invariato il valor medio cercando di

ridurre la varianza. Facciamo quindi delle trasformazioni.

PROCEDURA DI WELCH

Abbiamo le solite n repliche indipendenti di lunghezza m (sto supponendo di conoscere m) si fa questo:

➡ n repliche di lunghezza m

➡ si prendono le medie sulle colonne

➡ prendiamo

Prendo le k osservazioni prima, la j-esima e le k dopo, ho in tutto 2k+1 elementi. Per ogni j sostituisco l’Ysegnatoj con

questa media. Se ho k=3 e sono centrato sulla seconda osservazione non ne ho 3 prima. Quindi quando j è più grande di

k+1 allora questo ha senso, altrimenti devo ridurre l’ampiezza della finestra (k).

Se non ho a sinistra più di k osservazioni allora

prendo quelle che ci sono

K è l’intero inferiore di m/4.

Queste sono medie mobili, quindi ho sostituito ai dati iniziali le Yj dipendenti da k

Ora grafichiamo questo, mi aspetto che il grafico sia migliore di quello precedente, cioè in cui è più evidente l

Se usassimo un k ancora piu grande l’andamento sarebbe ancora più “SMOOTH”

Da qui si vede che da un certo punto in poi c’è un valore soglia

Quindi: PROCEDURA DI WELCH La media non è cambiata

La varianza è diminuita già dal primo passo di

un fattore n

Media mobile che per le prime iterazioni ha meno termini

Se portiamo avanti questa cosa l’ultimo Ysegnato che andrò a scrivere sarà m-k

In questo caso l’ultimo sarà quello che dista dall’ultima esattamente il valore della finestra. In pratica all’inizio si riduce la

finestra, a destra non si calcolano proprio


PAGINE

107

PESO

47.08 MB

AUTORE

CSY

PUBBLICATO

5 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria gestionale
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher CSY di informazioni apprese con la frequenza delle lezioni di Sistemi di servizio e simulazione e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Roma Massimo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Sistemi di servizio e simulazione

Sistemi di servizio e simulazione - Teoria - prof.Massimo Roma
Appunto
Appunti del corso Ottimizzazione Combinatoria 2, prof. Antonio Sassano
Appunto
Sistemi di servizio e simulazione - Teoria - prof.Massimo Roma
Appunto
Appunti del corso di Ottimizzazione Combinatoria 2 prof Antonio Sassano
Appunto