Simulazione - uniroma1.itroma/didattica/SSS17-18/parteG.pdf · 2018. 5. 13. · de nirne le...

2Simulazione

Con il termine simulazione si intende la riproduzione del comportamento di un

sistema. In generale, si parla di simulazione sia nel caso in cui viene utilizzato

un modello concreto, sia nel caso in cui viene utilizzato un modello astratto che

riproduce la realta mediante l’uso del computer. Un esempio di modello concreto

e il modello in scala di una nave che viene poi posto in un’apposita vasca per

effettuare prove simulate allo scopo di stimare opportune misure di prestazione. E

chiaro che esistono leggi teoriche della fisica dalle quali ottenere informazioni sulle

prestazioni della nave, ma le analisi di queste leggi e spesso troppo complicata,

per essere effettuata; naturalmente, e anche impraticabile (o quanto meno non

conveniente) la costruzione reale della nave e la prova diretta in mare.

All’interno della Ricerca Operativa, la simulazione utilizza modelli astratti che

vengono costruiti al fine di “replicare” il funzionamento di un sistema. Essa gioca

un ruolo molto importante soprattutto nel progettare un sistema stocastico e nel

definirne le procedure operative: il funzionamento di un sistema e “simulato” uti-

lizzando distribuzioni di probabilita per generare casualmente eventi del sistema

e dal sistema simulato si ottengono osservazioni statistiche sulle prestazioni dello

stesso. Naturalmente affinche cio possa essere realizzato e necessario costruire un

modello di simulazione, che permetta di descrivere le operazioni di un sistema e

come esse devono essere simulate.

Gli aspetti rilevanti che fanno della simulazione uno strumento largamente uti-

lizzato sono legati al fatto che essa permette di

• rappresentare sistemi reali anche complessi tenendo conto anche delle sor-

genti di incertezza;

• riprodurre il comportamento di un sistema in riferimento a situazioni che

M. Roma – Sistemi di Servizio e Simulazione – SAPIENZA Universita di Roma – a.a. 2017-2018

128 SIMULAZIONE

non sono sperimentabili direttamente.

D’altra parte deve essere sempre tenuto sempre ben presente il fatto che

• la simulazione fornisce indicazioni sul comportamento del sistema, ma non

“risposte” esatte;

• l’analisi dell’output di una simulazione potrebbe essere complessa e potreb-

be essere difficile individuare quale puo essere la configurazione migliore;

• l’implementazione di un modello di simulazione potrebbe essere laboriosa

ed inoltre potrebbero essere necessari elevati tempi di calcolo per effettuare

una simulazione significativa.

2.1 GENERALITA SUI MODELLI DI SIMULAZIONE

Come abbiamo gia osservato, per simulare il comportamento di un sistema e

necessario costruire un modello di simulazione. Il modello dovra essere suffi-

cientementre complesso da rispondere alle esigenze dal caso, ma deve comunque

rimanere il piu semplice possibile. Devono inoltre essere chiari i limiti di utilizzo

del modello stesso.

2.1.1 Elementi di un modello di simulazione

Vediamo ora gli elementi che costituiscono un modello di simulazione.

• Variabili di stato

Innanzitutto ricordiamo che un sistema e descritto in ogni istante di tempo

da un insieme di variabili che prendono nome di variabili di stato. Quindi,

ad esempio, in riferimento ad un sistema a coda, e una variabile di stato

il numero degli utenti presenti nel sistema in un certo istante di tempo.

Ricordiamo, inoltre, che esistono sistemi discreti in cui le variabili cambiano

istantaneamente in corrispondenza di precisi istanti di tempo che sono finiti

oppure appartenenti ad un insieme numerabile e sistemi continui in cui le

variabili variano con continuita rispetto al tempo. Si osservi fin d’ora che la

scelta di un modello continuo o discreto da utilizzare non e necessariamente

obbligata dalla tipologia del sistema; si puo infatti decidere, ad esempio, di

costruire un modello discreto per un sistema continuo, a seconda dello studio

che si vuole effettuare. Un esempio tipico e il caso in cui nel rappresentare

una linea ferroviaria, la posizione del treno puo essere descritta da una

variabile reale che fornisce la distanza dalla stazione di origine, oppure da

variabili binarie che descrivono lo stato libero–occupato di ciascuna delle

sezioni di blocco in cui e divisa la linea.


GENERALITA SUI MODELLI DI SIMULAZIONE 129

• Eventi

Si definisce evento un qualsiasi accadimento istantaneo che fa cambiare il

valore di almeno una delle variabili di stato. L’arrivo di un utente ad un

sistema a coda e un evento, cosı come il completamento di un servizio.

Esistono eventi esterni al sistema (eventi esogeni) ed eventi interni (eventi

endogeni). Ad esempio, l’inizio del servizio ad un utente che e in coda in

un sistema a coda e un evento endogeno, perche interno al sistema; l’arrivo

di un utente ad un sistema a coda e un evento esogeno.

• Entita e attributi

Le entita sono singoli elementi del sistema che devono essere definiti. Un

esempio di entita e un utente presso un sistema a coda, oppure puo essere

un servente. Nel primo caso l’entita fluisce all’interno del sistema e si parla

di entita dinamica, nel secondo caso si parla di entita statica.

Le entita possono essere caratterizzate da attributi che forniscono un valore

di un dato assegnato all’entita stessa. Ad esempio, in un sistema a coda

monoservente dove le entita sono il servente e gli utenti, un attributo di

un’entita “utente” potrebbe essere il suo tempo di arrivo al sistema, mentre

il servente e caratterizzato dall’attributo “status” che puo assumere valore

di “libero” o “occupato”. E chiaro che alcuni attributi possono essere di

interesse in alcuni casi e non in altri.

Le entita possono essere raggruppate in classi che sono insiemi di entita dello

stesso tipo, ovvero si possono raggruppare le entita in base ad attributi.

Se, ad esempio, consideriamo persone di sesso maschile e femminile come

utenti di un sistema a coda, essendo le entita le persone, esse possono essere

raggruppate in dua classi in base all’attributo “sesso”.

• Risorse

Le risorse sono elementi del sistema che forniscono un servizio alle entita.

Un’entita puo richiedere una o piu unita di risorsa e se questa non e di-

sponibile l’entita dovra mettersi, ad esempio, in una coda in attesa che si

renda disponibile, oppure intraprendere un’altra azione. Se invece la risorsa

e disponibile, essa viene “catturata” dall’entita, “trattenuta” per il tempo

necessario e poi “rilasciata”. Un esempio di risorsa potrebbe essere data

da un operaio che sovrintende il funzionamento di una macchina che non

puo funzionare senza l’operaio stesso; quando e richiesto l’utilizzo di questa

macchina, se la risora “operaio” e disponibile allora l’esecuzione del lavoro

e effettuata altrimenti si attende che ci sia risorsa (operaio) disponibile.

L’operaio verra “trattenuto” per la durata dell’esecuzione del lavoro e poi

“rilasciato”. Si osservi che, in generale, un elemento del modello potrebbe

essere considerato parimenti un’entita o una risorsa. Questo, ovviamente,

dipende da come si e scelto di costruire un modello.


130 SIMULAZIONE

• Attivita e ritardi

Un’attivita e un’operazione la cui durata e nota a priori all’inizio dell’ese-

cuzione dell’attivita stessa. Tale durata puo essere una costante, un valore

aleatorio generato da una distribuzione di probabilita, oppure data in input

o calcolata in base ad altri eventi che accadono nel sistema. Un esempio e

dato dal tempo di servizio in un sistema a coda.

Un ritardo e un periodo di tempo di durata indefinita che e determinata

dalle condizioni stesse del sistema. Il tempo che un’entita trascorre presso

una coda prima che si liberi una risorsa della quale necessita e un ritardo.

2.1.2 Classificazione dei modelli si simulazione

I modelli di simulazione si possono classificare in base a diversi criteri; una prima

distinzione gia vista e tra

• modelli continui, in cui le variabili variano con continuita;

• modelli discreti, in cui il valore delle variabili cambia in ben definiti istanti

di tempo.

Un’altra distinzione e tra:

• modelli statici, che rappresentano un sistema in un particolare istante di

tempo;

• modelli dinamici, che rappresentano un sistema in evoluzione nel tempo.

Infine, si possono distinguere

• modelli deterministici, che non contengono componenti probabilistici;

• modelli stocastici, che presentano elementi soggetti ad aleatorieta.

In questa trattazione considereremo modelli di simulazione discreti, dinamici,

stocastici che vengono comunemente chiamati modelli di simulazione ad eventi

discreti. Molte applicazioni sono ben rappresentate da modelli di questo tipo

ed inoltre approssimando variazioni continue con variazioni discrete e possibile

utilizzare modelli ad eventi discreti anche per approssimare il comportamento di

sistemi continui semplificando quindi molto l’analisi.

2.1.3 Simulazione ad eventi discreti

Nella simulazione ad eventi discreti il sistema e rappresentato, nella sua evoluzione

nel tempo, con variabili che cambiano instantaneamente il loro valore in ben

definiti istanti di tempo appartenenti ad un insieme numerabile. Questi istanti

sono quelli nei quali accadono gli eventi. E chiaro che, essendo questi modelli

di natura dinamica, e necessario registrare, ovvero tenere memoria, del tempo



(simulato) che procede. In particolare sara necessario definire un meccanismo di

avanzamento del tempo per far procedere il tempo simulato da un valore ad un

altro. La variabile che in un modello di simulazione fornisce il valore corrente del “Simulation

clock”tempo simulato si chiama “simulation clock”, ed esistono due modi per definire

il suo avanzamento:

• avanzamento del tempo al prossimo evento,

• avanzamento del tempo ad incrementi prefissati.

Il primo e quello piu diffuso ed e quello a cui faremo riferimento. In questo caso

il “simulation clock” e inizializzato a zero e viene avanzato al tempo dell’accadi-

mento del primo degli eventi futuri; poi il sistema viene aggiornato tenendo conto

dell’evento che e accaduto, si aggiornano i tempi degli eventi futuri e si itera il

procedimento. A differenza dell’avanzamento ad incrementi prefissati, i periodi

di inattivita non vengono considerati.

Un esempio puo essere visto considerando un sistema di code in cui gli eventi sono

l’arrivo di un cliente, la conclusione di un servizio; entrambi sono eventi perche

provocano il cambiamento di valore di qualche variabile di stato. Il meccanismo

di avanzamento del tempo segue in questo caso l’accadere di questi due eventi

nell’ordine cronologico in cui essi si verificano.

Un esempio di simulazione ad eventi discreti

Vediamo, ora, un semplice esempio di come si realizza un simulazione ad eventi

discreti. Consideriamo a tale scopo un sistema a coda costituito da una coda

e da un singolo servente e supponiamo che i tempi di interarrivo siano unifor-

memente distribuiti tra 1 e 3 minuti e che anche i tempi di servizio siano uni-

formemente distribuiti tra 0.5 e 2 minuti. Vediamo, ora, come si puo effettuare

una simulazione di questo sistema. Poiche si tratta di un sistema regolato da

due processi stocastici (gli arrivi e i servizi) per generare gli eventi e necessario

generare osservazioni casuali dalle due distribuzioni di probabilita che regolano

i due processi (come questo puo essere effettuato sara oggetto di considerazioni

successive nel paragrafo 2.3). Supponiamo di avere a disposizione le due liste

che forniscono, rispettivamente i tempi di interarrivo generati casualmente dalla

distribuzione corrispondente e i tempi di servizio anch’essi generati casualmente

dalla distribuzione corrispondente:

Tempi di interarrivo Tempi di servizio

1.9 1.7

1.3 1.8

1.1 1.5

1.0 0.9...

...


132 SIMULAZIONE

Supponendo che al tempo t = 0 nessun utente e presente nel sistema. Osservando

i valori campionati riportati nelle due liste, si ricava facilmente la successione degli

eventi:

Tempo t Eventi

1.9 arriva un utente inizia il servizio

3.2 arriva un utente e si pone in coda

3.6 finisce un servizio e il primo utente in coda inizia il servizio



5.4 finisce un servizio e il primo utente in coda inizia il servizio...

...

Limitando questa semplice simulazione al tempo t = 5.4 (in modo che due utenti

sono entrati e hanno completato il servizio), possiamo calcolare, ad esempio, il

tempo medio di permanenza nel sistema: il primo utente rimane nel sistema

1.7 minuti, il secondo 2.2 minuti e quindi il valore medio e 1.95. Questa stima,

ovviamente non ha alcun senso perche ottenuta dalla particolare sequenza di

numeri casuali delle due liste. Quindi, se l’esempio da un lato vuole mettere

evidenza il meccanismo di una simulazione ad eventi discreti, dall’altro mette fin

d’ora in evidenza un errore che si potrebbe commettere nel reputare affidabili

i risultati di una sola esecuzione e che ha avuto una durata arbitraria. D’altra

parte c’e anche da tener presente che se siamo interessati a valutare misure di

prestazioni del sistema a regime, ovvero quando sono state raggiunte condizioni di

stazionarieta, sara necessario non prendere in considerazione il sistema durante il

periodo iniziale di transitorio. Queste problematiche rappresentano un elemento

chiave di ogni simulazione e saranno considerate in dettaglio nel seguito.

2.1.4 Schema dello studio di un problema basato sulla simulazione

In questo paragrafo riportiamo uno schema che descrive la successione delle varie

fasi che caratterizzano uno studio basato sulla simulazione.

1. Analisi del problema

Consiste nel comprendere il problema cercando di capire quali sono gli scopi

dello studio e di identificare quali sono le componenti essenziali e quali sono

le misure di prestazione che interessano. Naturalmente, se una versione

del sistema e gia operativa, si deve osservare tale sistema per dedurne le

caratteristiche fondamentali.

2. Formulazione del modello di simulazione

Poiche stiamo trattando sistemi stocastici, per formulare un modello di si-



mulazione e necessario conoscere le distribuzioni di probabilita delle quan-

tita di interesse. Infatti, per generare vari scenari rappresentativi di come

un sistema funziona, e essenziale che una simulazione generi osservazioni

casuali da queste distribuzioni. Ad esempio, nei sistemi a coda e necessaria

la distribuzione dei tempi di interarrivo e i tempi di servizio; nella gestione

delle scorte e necessaria la distribuzione della richiesta dei prodotti e la

distribuzione del tempo tra un’ordine e il ricevimento della merce; nella ge-

stione dei sistemi di produzione con macchine che occasionalmente possono

guastarsi, sara necessario conoscere la distribuzione del tempo fino a che

una macchina si guasta e la distribuzione dei tempi di riparazione. General-

mente e possibile solo stimare queste distribuzioni derivandole, ad esempio,

dall’osservazione di sistemi simili gia esistenti. Se dall’analisi dei dati si

vede che la forma di questa distribuzione approssima una distribuzione ti-

po standard, si puo utilizzare la distribuzione teorica standard effettuando

un test statistico per verificare se i dati possono essere rappresentati bene

mediante quella distribuzione di probabilita. Se non esistono sistemi simili

dai quali ottenere dati osservabili si deve far ricorso ad altre fonti di infor-

mazioni: specifiche delle macchine, manuali di istruzioni delle stesse, studi

sperimentali, etc.

La costruzione di un modello di simulazione e un procedimento complesso.

In particolare, facendo riferimento alla simulazione ad eventi discreti, la

costruzione di un modello prevede le seguenti fasi:

(a) Definizione delle variabili di stato.

(b) Identificazione dei valori che possono essere assunti dalle variabili di

stato.

(c) Identificazione dei possibili eventi che fanno cambiare lo stato del

sistema.

(d) Realizzazione di una misura del tempo simulato, “simulation clock”,

che registra lo scorrimento del tempo simulato.

(e) Realizzazione di un metodo per generare casualmente gli eventi.

(f) Identificazione delle transizioni di stato generate dagli eventi.

3. Analisi del modello di simulazione

Nella fase di analisi del modello deve essere verificata l’accuratezza del mo-

dello realizzato con diverse modalita. Di solito cio viene fatto attraverso

un’analisi concettuale del modello che puo essere effettuata insieme agli

esperti del settore applicativo in modo da evidenziare eventuali errori e/o

omissioni.


134 SIMULAZIONE

4. Scelta del software e costruzione di un programma

Dopo aver costruito il modello, esso deve essere tradotto in un programma.

A tale scopo e possibile utilizzare diversi strumenti.

• Linguaggi “general purpose”.

Linguaggi come JAVA, C++, FORTRAN, etc. Erano molto utilizzati

alla nascita della simulazione ma richiedono molto tempo di program-

mazione e quindi si preferisce, in genere, utilizzare linguaggi specifici

per la simulazione.

• Linguaggi di simulazione generali.

Forniscono molte caratteristiche necessarie per realizzare un modello

di simulazione riducendo cosı il tempo di realizzazione; esempi sono

SIMAN, MODSIM, GPSS, SIMSCRIPT, etc. Anche se meno flessibili dei

linguaggi “general purpose” sono il modo piu naturale per realizzare

un modello di simulazione.

• Simulatori.

Sono packages per la simulazione orientati alle applicazioni. Esistono

numerosi pacchetti software di tipo interattivo per la simulazione co-

me ARENA, SIMIO, WITNESS, EXTEND, MICRO SAINT. Alcuni sono

abbastanza generali anche se dedicati a specifici tipi di sistemi come

impianti industriali, sistemi di comunicazione, altri invece sono molto

specifici come, ad esempio, nel caso di simulatori di centrali nucleari

o di simulatori della fisiologia cardiovascolare. I simulatori permetto-

no di costruire un programma di simulazione utilizzando menu grafici

senza bisogno di programmare. Sono abbastanza facili da imparare e

un inconveniente che molti di essi hanno e di essere limitati a model-

lare quei sistemi previsti dalle loro caratteristiche standard. In ogni

caso alcuni simulatori prevedono la possibilita di incorporare routi-

nes scritte in un linguaggio general purpose per trattare elementi non

standard. Spesso hanno anche capacita di animazione per mostrare

la simulazione in azione e questo permette di illustrare facilmente la

simulazione anche a persone non esperte.

• Fogli elettronici (spreadsheets).

Quando si hanno problemi di piccole dimensioni si possono anche uti-

lizzare fogli elettronici, come ad esempio Excel, per avere un’idea del

funzionamento di un sistema.

5. Validazione del modello di simulazione

Nella fase successiva e necessario verificare se il modello che e stato realizza-

to fornisce risultati validi per il sistema in esame. Piu in particolare si deve

verificare se le misure di prestazione del sistema reale sono bene approssi-

mate dalle misure generate dal modello di simulazione. Cio e molto difficile



da effettuare, specialmente in fase di progettazione quando il sistema reale

non esiste.

6. Progettazione della simulazione

Prima di passare all’esecuzione della simulazione e necessario decidere co-

me condurre la simulazione. Spesso una simulazione e un processo che

evolve durante la sua realizzazione e dove i risultati iniziali aiutano a con-

durre la simulazione verso configurazioni piu complesse. Ci sono inoltre

problematiche di tipo statistico:

• la determinazione della lunghezza del transitorio del sistema prima di

raggiungere condizioni di stazionarieta, momento dal quale si inizia

a raccogliere dati se si vogliono misure di prestazione del sistema a

regime;

• la determinazione della lunghezza della simulazione (durata) dopo che

il sistema ha raggiunto l’equilibrio. Infatti, si deve sempre tener pre-

sente che la simulazione non produce valori esatti delle misure di pre-

stazione di un sistema in quanto ogni singola simulazione puo essere

vista come un “esperimento statistico” che genera osservazioni stati-

stiche sulle prestazioni del sistema. Queste osservazioni sono poi uti-

lizzate per produrre stime delle misure di prestazione e naturalmente

aumentando la durata della simulazione puo aumentare la precisione

di queste stime;

• la determinazione del numero delle repliche di una simulazione. In-

fatti, sara necessario effettuare un certo numero di run indipendenti

affinche si raggiunga l’accuratezza desiderata nella stima delle misure

di interesse.

7. Esecuzione della simulazione e analisi dei risultati

L’output della simulazione fornisce stime statistiche delle misure di presta-

zione di un sistema. Un punto fondamentale e che ogni misura sia accompa-

gnata dall’“intervallo di confidenza” all’interno del quale essa puo variare.

Questi risultati potrebbero evidenziare subito una configurazione del si-

stema migliore delle altre, ma piu spesso verranno identificate piu di una

configurazione candidata ad essere la migliore. In questo caso potrebbero

essere necessarie ulteriori indagini per confrontare queste configurazioni.

8. Presentazione delle conclusioni

In conclusione, e necessario redigere una relazione ed una presentazione

che riassuma lo studio effettuato, come e stato condotto e includendo la

documentazione necessaria. Includere nella presentazione un’animazione di

una simulazione e di solito molto efficace.


136 SIMULAZIONE

2.1.5 Applicazioni tipiche della simulazione

La simulazione e uno strumento molto flessibile: puo essere utilizzata per studiare

la maggior parte dei sistemi esistenti. E impossibile enumerare tutte le aree

specifiche in cui la simulazione puo essere utilizzata. Come esempi, riportiamo,

di seguito, solo alcune importanti tipiche categorie di applicazioni in cui si usa la

simulazione.

• Progettazione e definizione delle procedure operative di un sistema di ser-

vizio.

• Gestione di sistemi di scorte.

• Progetto e definizione delle procedure operative di sistemi di produzione.

• Progetto e funzionamento del sistemi di distribuzione.

• Analisi dei rischi finanziari.

• Gestione dei progetti.


ANALISI DELL’INPUT 137

2.2 ANALISI DELL’INPUT

Per effettuare una simulazione di un sistema che presenta elementi stocastici

e necessario specificare le distribuzioni di probabilita che regolano i processi che

caratterizzano il sistema stesso. Ad esempio, nei sistemi a coda devono essere note

le distribuzioni di probabilita dei tempi di interarrivo e dei tempi di servizio. Se e

possibile raccogliere dati reali (osservazioni) sulle variabili aleatorie di interesse,

essi possono essere utilizzati per determinare queste distribuzioni facendo uso di

tecniche di inferenza statistica. Questa prima fase viene di solito chiamata analisi

dell’input e sara oggetto di studio di questo paragrafo.

Una volta stabilite tali distribuzioni, la simulazione procede generando valori

casuali da queste distribuzioni, ovvero, durante ogni esecuzione, la simulazione

genera osservazioni casuali di variabili aleatorie distribuite secondo particolari

distribuzioni di probabilita. Successivamente, vengono utilizzate tecniche stati-

stiche per interpretare i risultati ottenuti da una simulazione (analisi dell’output).

Questi ultimi due aspetti saranno trattati rispettivamente nei successivi paragrafi

2.3 e 2.4.

2.2.1 Generalita

In generale, nello studio di un fenomeno riguardante un insieme di elementi (po-

polazione) che presenta caratteristiche aleatorie, molto spesso si dispone solo di

informazioni su una parte di essi (campione) e si vogliono dedurre proprieta ge-

nerali riguardanti l’intera popolazione. L’inferenza statistica si occupa di questa

problematica e riveste un importante strumento di analisi. Esula dallo scopo di

queste note una trattazione degli elementi dell’inferenza statistica che verranno

assunti come noti. Una breve rassegna di alcuni importanti risultati e riportata

nell’Appendice. Richiamiamo di seguito solo alcune importanti osservazioni e le

ben note definizioni di media campionaria e varianza campionaria

Solitamente viene fatta l’assunzione che esiste una distribuzione di probabilita

della popolazione nel senso che se da essa vengono estratti casualmente alcu-

ni elementi, ad essi sono associate variabili aleatorie indipendenti identicamente

distribuite secondo tale distribuzione. In questo senso, un insieme di variabili

aleatorie X1, . . . , Xn di variabili aleatorie indipendenti tutte con la stessa distri-

buzione si dice campione di questa distribuzione. L’interesse principale risiede

nella possibilita di dedurre caratteristiche della distribuzione non nota sulla base

dei dati a disposizione. Naturalmente ci sono casi in cui della distribuzione della

popolazione non si conosce nulla (se non il fatto che essa e discreta o continua),

mentre in altri casi la distribuzione e nota ma non sono noti alcuni suoi parametri.

Formalmente, sia dato un campione X1, . . . , Xn estratto da una popolazione,

ovvero le Xi sono variabili aleatorie indipendenti identicamente distribuite, e sia

µ e σ2 rispettivamente la loro media e la loro varianza (ovvero la media e la


138 SIMULAZIONE

varianza della popolazione). La media campionaria e data daMedia cam-

pionaria

Xn =1

n

n∑i=1

Xi.

Xn e una variabile aleatoria funzione delle Xi e si verifica facilmente che risulta

E(Xn) = µ e V ar(Xn) =σ2

n.

La varianza campionaria e data daVarianza

campiona-

ria s2n =

1

n− 1

n∑i=1

(Xi − Xn

)2e si verifica facilmente che risulta E(s2

n) = σ2.

2.2.2 Scelta delle distribuzioni di input

Se e possibile raccogliere dati reali sulle variabili aleatorie di interesse, essi possono

essere utilizzati per determinare una distribuzione di probabilita che meglio li

rappresenta secondo tre metodi:

1. i dati sono usati direttamente nella simulazione (“trace driver simulation”).

2. i dati sono raccolti per generare una distribuzione empirica, ovvero per

definire una funzione di distribuzione empirica che verra usata per produrre

l’input della simulazione;

3. i dati raccolti sono utilizzati per definire una distribuzione teorica. Vengono

utilizzate tecniche statistiche per analizzare se una distribuzione teorica tra

quelle note sia adatta a rappresentare i dati, effettuando i test di ipotesi

per verificare la rappresentativita della distribuzione ipotizzata (problema

del “fitting”).

Il primo approccio ha senso solamente quando si possono raccogliere grandi quan-

tita di dati rappresentativi del funzionamento del sistema; ha l’ovvio difetto di

rappresentare il “passato” ed e usato raramente; puo essere utile per effettua-

re una validazione del modello, ovvero per confrontare il modello con il sistema

reale, ma non permette un’analisi previsionale.

Il secondo approccio elimina questo inconveniente poiche, almeno per distribuzio-

ni continue, puo essere ottenuto ogni valore compreso tra il minimo e il massimo

osservati.

Se si puo determinare una distribuzione teorica che si adatta bene ai dati, il terzo

approccio e quello preferibile. I motivi per cui una distribuzione teorica in genere

e preferibile a una empirica sono i seguenti:

• le distribuzioni empiriche possono avere irregolarita (specialmente se i dati

sono scarsi) mentre le distribuzioni teoriche sono piu “smooth”, nel senso



che tendono a regolarizzare i dati e rappresentano un comportamento ge-

nerale;

• le distribuzioni empiriche non permettono di generare valori al di fuori del

range di valori osservati, mentre le misure di prestazione possono, a volte,

dipendere anche da eventi “eccezionali” che corrispondono a valori fuori da

tale range;

• le distribuzioni teoriche sono un modo compatto di rappresentare un in-

sieme di valori, mentre in una distribuzione empirica, se ci sono n dati

disponibili, si ha bisogno di 2n valori per rappresentarla: il dato e le corri-

spondenti probabilita cumulative (si hanno quindi grandi quantita di dati

da memorizzare);

• le distribuzioni teoriche si possono variare piu facilmente. Ad esempio se la

distribuzione esponenziale degli arrivi di un sistema di code ha media pari a

1/λ = 5, per effettuare una diminuzione del 20% sara sufficiente considerare

1/λ = 4.9.

Tuttavia esistono situazioni in cui nessuna distribuzione teorica si adatta ai dati

osservati e allora in questo caso si deve usare una distribuzione empirica.

Un difetto dell’uso di distribuzioni teoriche sta nel fatto che esse possono generare

anche valori molto grandi (anche se con probabilita molto piccole), quando nella

pratica questi non vengono mai assunti realmente.

2.2.3 Distribuzioni empiriche

Supponiamo di disporre di n osservazioni X1, . . . , Xn di una variabile aleatoria e

di voler costruire, a partire da esse, una distribuzione continua. Supponiamo di

aver ordinato le Xi per valori crescenti e sia X(i) l’i-esima osservazione in ordine

crescente, ovvero risulti

X(1) ≤ X(2) ≤ . . . ≤ X(n).

Si puo costruire la distribuzione empirica come una distribuzione continua lineare

a tratti, cosı definita:

F (x) =

0 se x < X(1)

i− 1

n− 1+

x−X(i)

(n− 1)(X(i+1) −X(i))se X(i) ≤ x < X(i+1),

i = 1, . . . , n− 1

1 se X(n) ≤ x


140 SIMULAZIONE

Si osservi che per ogni i vale F (X(i)) =i− 1

n− 1che e approssimativamente (per n

grande) la proporzione delle Xi che sono minori di X(i).

Esempio 2.2.1 Disponendo dei seguenti valori osservati: 1, 0.4, 4, 2, 2.5, 3.6, 3 costruire

il grafico della distribuzione empirica. Dopo aver ordinato le osservazioni si ottiene il

grafico della F (x) riportato nella Figura 2.2.1.

1/6

1/3

1/2

2/3

5/6

1

1

2

3 4

0.4

2.5

3.6

Figura 2.2.1 Grafico della distribuzione empirica dell’Esempio 2.2.1

Come abbiamo gia osservato, uno svantaggio nell’utilizzare una distribuzione em-

pirica e che le variabili aleatorie generate da essa durante un’esecuzione di una

simulazione non possono essere mai piu piccole di X(1) o piu grandi di X(n).

Analogamente si possono costruire distribuzioni empiriche per distribuzioni di-

screte; infatti, e sufficiente per ogni x definire p(x) come “proporzione” delle Xi

che sono uguali ad x.

2.2.4 Distribuzioni teoriche

• Distribuzioni Continue

Le distribuzioni teoriche continue alle quali si puo fare riferimento nella co-



struzione di un modello di simulazione sono molte. Quelle piu comunemen-

te utilizzate sono la distribuzione uniforme, la distribuzione esponenziale,

la distribuzione gamma, la distribuzione normale, la distribuzione lognor-

male, la distribuzione di Weibull, la distribuzione beta, la distribuzione

triangolare.

In realta spesso si tratta di famiglie di distribuzioni in quanto sono presenti

uno o piu parametri che possono essere classificati in:

· parametro di posizione: specifica un punto del range della distribuzione

e una sua variazione provoca solamente una traslazione;

· parametro di scala: specifica l’unita di misura dei valori,

· parametro di forma: specifica l’andamento della distribuzione.

• Distribuzioni Discrete

Le distribuzioni teoriche discrete che vengono di solito utilizzate come in-

put di una simulazione sono: la distribuzione uniforme, la distribuzione

di Bernoulli, la distribuzione binomiale, la distribuzione geometrica, la

distribuzione di Poisson, la distribuzione binomiale negativa.

Per una descrizione dettagliata di ogni singola distribuzione di probabilita e del-

le caratteristiche specifiche, si rimanda ad un qualsiasi testo di Calcolo delle

Probabilita.

2.2.5 Scelta di una distribuzione teorica

Determinare quale distribuzione teorica e adatta a rappresentare dei dati e un

problema complesso. Un modo efficiente per effettuare questa scelta puo essere

cosı schematizzato:

Dopo una preliminare verifica dell’indipendenza delle osservazioni, si cerca di in-

dividuare una o piu famiglie di distribuzioni candidate, stimando poi nella fase

successiva i parametri di queste distribuzioni. A questo punto e necessario effet-

tuare una verifica della rappresentativita dei dati reali da parte della distribuzioni

scelta. Se tale verifica non ha successo, e necessario individuare una differente

famiglia di distribuzioni ed eventualmente iterare il processo fino a che la verifica

e soddisfatta.

Indipendenza delle osservazioni

Preliminarmente e necessario verificare l’indipendenza delle osservazioni in quan-

to questa e un’assunzione essenziale per l’utilizzo di tecniche statistiche quali la

stima della massima verosimiglianza o il test chi–quadro. Un primo strumen-

to di analisi e basato su una tecnica grafica. Siano X1, . . . , Xn le osservazioni


142 SIMULAZIONE

Verif ica dell段ndipendenza

delle osservazioni

Individuazione di una

famiglia di distribuzioni

Stima dei parametri

della distribuzione

Verif ica della rappresentat ivit�

elencate cosı come sono state osservate nel tempo; un modo possibile per ave-

re un’idea informale sull’indipendenza consiste nel valutare la correlazione fra

diverse osservazioni. Sia

ρj =

n−j∑i=1

(Xi − Xn)(Xi+j − Xn)

(n− j)s2n

la stima del coefficiente di correlazione ρj di Xi e Xi+j , ovvero di due osservazioni

distanti j. Se le osservazioni sono indipendenti allora il coefficiente di correlazione

e nullo, cioe ρj = 0 per ogni j = 1, . . . , n− 1. Tuttavia poiche ρj e una stima di

ρj , anche nel caso di osservazioni indipendenti ρj potrebbe essere non nullo. Ci

si aspetta, comunque che esso sia prossimo a zero, e quindi possiamo dire che se

ρj e diverso da zero in maniera significativa, allora le Xi non sono indipendenti.

Ci sono due modi grafici per verificare informalmente se le Xi sono indipendenti:

il grafico di ρj al variare di j e il diagramma di dispersione delle osservazioni

X1, . . . , Xn, ovvero le coppie (Xi, Xi+1) con i = 1, 2, . . . , n − 1. In caso di os-

servazioni indipendenti i punti dovrebbero risultare distribuiti casualmente sul

piano, altrimenti, in presenza di correlazioni, essi saranno concentrati intorno a

rette.



Individuazione di una famiglia di distribuzioni

Una volta verificata l’indipendenza delle osservazioni, il passo successivo e quello

di individuare una distribuzione da scegliere come input della simulazione che

sia rappresentativa della variabile aleatoria in ingresso alla simulazione. In una

prima fase vorremmo individuare una famiglia generale senza occuparci, per ora,

dei suoi parametri. In alcuni casi, quando esiste una conoscenza “a priori” del

fenomeno che la variabile aleatoria rappresenta, essa puo essere utilizzata per

ottenere la distribuzione. Cio e fatto su base teorica e non richiede osservazioni.

Ad esempio, se supponiamo che dei clienti arrivano ad un sistema di servizio uno

alla volta e che il numero dei clienti che arrivano in intervalli disgiunti e indi-

pendente, allora ci sono motivi teorici per assumere che i tempi di interarrivo

siano variabili aleatorie indipendenti identicamente distribuite secondo la distri-

buzione esponenziale. Oppure, puo anche accadere che la conoscenza “a priori”

permetta solo di escludere alcune distribuzioni. Tuttavia, nella pratica spesso

queste informazioni “a priori” non sono disponibili, o comunque non sufficienti.

Quello che si fa piu frequentemente e ricorrere a due strumenti di analisi stati-

stica: le statistiche riassuntive delle osservazioni e i grafici dell’andamento delle

osservazioni.

• Statistiche riassuntive

Dalle osservazioni e possibile ricavare stime di parametri dalle quali cercare

di individuare una famiglia di distribuzioni che meglio realizza il fitting

dei dati. I parametri che di solito vengono presi in considerazione sono i

seguenti:

– l’intervallo [X(1), X(n)] che ha per estremi il piu piccolo e il piu grande

valore osservati e che approssima il range della distribuzione;

– la stima della media µ data Xn =1

n

n∑i=1

Xi;

– la stima della mediana data da{X(n+1)/2 se n e dispari

[X(n/2) +X((n/2)+1)]/2 se n e pari;

– la stima della varianza σ2 data da

s2n =

n∑i=1

(Xi − Xn)2

n− 1;

– stime di misure di variabilita:

· nel caso continuo, la stima del rapporto cv =√σ2/µ

(coefficiente di variazione) data da cv =√s2n/Xn


144 SIMULAZIONE

· nel caso discreto, la stima del rapporto τ = σ2/µ

data da τ = s2n/Xn

– la stima del grado di asimmetria ν =E[(X − µ)3]

(σ2)3/2

data da ν =

n∑i=1

[(Xi − Xn)3]/n

(s2n)3/2

.

Un confronto tra media e mediana puo farci capire se considerare la distri-

buzione simmetrica o no; questo perche nel caso di distribuzioni continue

simmetriche, media e mediana coincidono, come ad esempio nel caso della

distribuzione normale (nel caso di distribuzioni discrete questo e vero solo

se il numero dei valori distinti che possono essere assunti e pari, altrimenti

sono solo approssimativamente uguali). E importante tener presente che si

hanno solo le stime dei parametri, pertanto anche nel caso di distribuzioni

continue simmetriche, stima di media e mediana possono non essere esat-

tamente uguali.

Per quanto riguarda la misura di variabilita data nel caso continuo dal

rapporto cv, si ha che cv = 1 per la distribuzione esponenziale indipenden-

temente dal parametro; nel caso discreto si considera invece il rapporto τ e

si ha che τ = 1 per la distribuzione di Poisson e τ < 1 per la distribuzione

binomiale.

Il grado di asimmetria ν vale zero per distribuzioni simmetriche mentre se

ν > 0 la distribuzione ha asimmetria verso destra (ν = 2 per la distribuzione

esponenziale); se ν < 0 la distribuzione ha asimmetria verso sinistra.

• Uso di grafici (tecnica dell’istogramma)

Per distribuzioni continue e molto utile costruire un istogramma di valori

assunti dalla variabile aleatoria sulla base delle osservazioni che si hanno

a disposizione. Un istogramma puo essere considerato una “stima grafica”

del grafico della densita di probabilita corrispondente alla distribuzione dei

dati X1, . . . , Xn. Le funzioni densita di probabilita tipiche hanno forme

che in molti casi sono ben riconoscibili e quindi un istogramma puo fornire

utili indicazioni. Ricordiamo che per costruire un istogramma si suddivide

l’intervallo formato dal minimo e dal massimo dei valori assunti dai dati, in

k intervalli disgiunti adiacenti

[b0, b1), [b1, b2), . . . , [bk−1, bk)

di uguale ampiezza ∆b = bi − bi−1. Per j = 1, 2, . . . , k si definisce hj il

numero delle osservazioni che cadono nel j-esimo intervallo diviso il numero

totale delle osservazioni, ovvero la proporzione delle Xi contenute nel j-

esimo intervallo [bj−1, bj). Si definisce la funzione



h(x) =

0 se x < b0

hj se bj−1 ≤ x < bj , j = 1, 2, . . . , k

0 se x ≥ bk.

Il grafico di h(x) e costante a tratti e puo fornire una buona indicazione

sul tipo di distribuzione che ha la variabile aleatoria in questione, confron-

tandolo con i grafici delle densita di probabilita ignorando, per il momento,

posizione e scala, ma considerando solo la forma.

Mostriamo ora le motivazioni che sono alla base del fatto che la forma di

h(x) dovrebbe “somigliare” alla densita di probabilita f dei dati. A questo

scopo, sia X una variabile aleatoria con densita di probabilita data da f .

Allora per ogni j fissato (j = 1, 2, . . . , k), applicando il teorema della media

si ha

P (bj−1 ≤ X ≤ bj) =

∫ bj

bj−1

f(x)dx = ∆b f(y)

per qualche y ∈ (bj−1, bj). D’altra parte hj approssima P (bj−1 ≤ X ≤ bj)

che e il valore di h(y) perche h(x) = hj per ogni x ∈ [bj−i, bj); si ha dunque:

h(y) = hj ≈ ∆bf(y). Quindi, h(y) e approssimativamente proporzionale a

f(y), ovvero h e f hanno approssimativamente forma simile.

Una difficolta e data dall’assenza di criteri generali per scegliere k. C’e una

regola detta regola di Sturges che suggerisce di scegliere k = b1 + log2 nc. Regola di

SturgesTale regola non e pero utile in generale e si raccomanda piuttosto di provare

differenti valori di ∆b e scegliere il piu piccolo che fornisce un istogramma

“smooth”. La scelta di ∆b e problematica in genere; infatti se si sceglie

troppo piccolo, l’istogramma sara molto poco uniforme (frastagliato); se si

sceglie troppo grande l’istogramma puo avere una forma a blocchi e il vero

andamento della densita che stiamo cercando sara mascherata in quanto i

dati sono sovraggregati.

Nel caso di variabili discrete si puo ugualmente rappresentare la distribuzio-

ne di probabilita usando un istogramma; per ogni valore xj che puo essere

assunto dai dati, sia hj = nj/n dove nj e il numero delle occorrenze di tali

valori, ovvero hj e la proporzione delle Xi che sono uguali a xj . Si tracciano

poi le barre verticali di altezza hj in corrispondenza di xj .


146 SIMULAZIONE

Stima dei parametri

Dopo aver individuato una o piu famiglie di distribuzioni candidate a rappre-

sentare i dati osservati, e necessario determinare i parametri di queste distri-

buzioni in modo che siano completamente definite e utilizzabili in ingresso ad

una simulazione. Gli stessi dati utilizzati per individuare le famiglie di distri-

buzioni sono utilizzati per stimare i loro parametri. La stima dei parametri e

un argomento vasto che si assume noto. Alcuni cenni riguardanti lo stimatore

di massima verosimiglianza (Maximum Likelihood Estimator) sono riportati nel

paragrafo 3.3.

Verifica della rappresentativita della distribuzione di probabilita

Dopo aver individuato una o piu distribuzioni di probabilita candidate e i relativi

parametri, si devono esaminare queste distribuzioni di probabilita per verificare

se esse rappresentano bene i dati osservati. A tale scopo, si utilizzano di solito

procedure euristiche basate su confronti grafici e test statistici.

• Procedure grafiche

Per distribuzioni continue, si confronta l’istogramma dei dati con il grafico

della densita di probabilita della distribuzione di probabilita ipotizzata,

oppure, per distribuzioni discrete, si confronta l’istogramma con la funzione

p(x) della distribuzione ipotizzata.

Un altro possibile confronto e tra il grafico della distribuzione empirica e il

grafico della funzione di distribuzione della distribuzione ipotizzata.

• Test statistici

Come e noto, i test delle ipotesi possono essere utilizzati per verificare se

le osservazioni X1, . . . , Xn sono un campione indipendente di una partico-

lare distribuzione di probabilita con funzione di distribuzione F . I due test

piu comuni sono i test Chi–quadro e Kolmogorov–Smirnov e sono adat-

ti al caso che stiamo esaminando anche se essi presentano le loro limita-

zioni intrinseche. Un’esposizione sintetica di questi due test e riportata

nell’Appendice.

2.2.6 Scelta delle distribuzioni di input in assenza di dati

In alcuni casi, nella pratica, puo accadere che non sia possibile raccogliere dati

sul funzionamente del sistema che si vuole studiare perche esso e ancora in fase

di progettazione e quindi non ancora esistente. In questi casi non sono quindi

disponibili dati da utilizzare per selezionare una distribuzione di input ad una

simulazione e quindi non sono applicabili le tecniche viste fino ad ora. Senza

entrare nei dettagli, osserviamo solamente che sara necessario far ricorso a proce-

dure euristiche che si basano sulla natura del sistema, sul ricorso a persone esperte



di sistemi della tipologia di interesse, sulle limitazioni fisiche o convenzionali del

processo in esame.


148 SIMULAZIONE

2.3 GENERAZIONE DI OSSERVAZIONI CASUALI

Una volta determinate le distribuzioni di input, la simulazione dovra generare du-

rante ogni esecuzione osservazioni casuali di variabili aleatorie distribuite secondo

particolari distribuzioni di probabilita. Ad esempio, nel simulare un sistema di

code M/M/1 si avra bisogno di generare i tempi di interarrivo in accordo alla di-

stribuzione esponenziale e cosı anche per i tempi di servizio. Un esempio banale

di cio e stato mostrato alla pagina 131, dove nell’effettuare una semplice esem-

plificazione di una simulazione abbiamo avuto bisogno delle due liste di valori

generati casualmente dalle distribuzioni corrispondenti.

Ogni metodo per generare osservazioni casuali da distribuzioni fissate utilizza va-

riabili indipendenti identicamente distribuite secondo la distribuzione uniforme in

[0, 1) (che indichiamo con U(0, 1)), nel senso che costruisce le osservazioni casuali

desiderate a partire da numeri casuali generati uniformemente in [0, 1) attraverso

opportune trasformazioni. Quindi preliminarmente analizziamo brevemente nel

prossimo paragrafo la generazione di numeri casuali con distribuzione uniforme

e nel paragrafo successivo studieremo come generare osservazioni casuali secondo

distribuzioni fissate a partire dalla distribuzione U(0, 1).

2.3.1 Generazione di numeri pseudocasuali con distribuzione uniforme

In generale, per generare successioni di numeri casuali si potrebbero utilizza-

re metodi quali il lancio dei dadi, l’estrazione da urne, ma ovviamente questi

metodi non sono utilizzabili nella simulazione dove e necessario generare lunghe

successioni di numeri casuali in tempi molto brevi. Attualmente per generare suc-

cessioni di numeri casuali si ricorre all’uso del calcolatore e in realta quello che si

fa e la generazione deterministica di successioni di numeri aventi proprieta stati-

stiche che approssimano molto bene quelle di successioni veramente casuali e che

ad un’analisi statistica risultano indistinguibili da successioni di numeri casuali.Numeri

pseudo-

casuali

I numeri determinati con questa procedura si chiamano numeri pseudocasuali.

Per generare numeri pseudocasuali con distribuzione uniforme esistono diversi

metodi; i piu utilizzati sono i generatori congruenziali lineari. In questi metodiGeneratori

con-

gruenziali

lineari

una successione di numeri interi Zi viene definita dalla seguente formula ricorsiva

Zi+1 = aZi + c ( mod m )

dove a si chiama moltiplicatore e c viene detto incremento1. Il termine Z0 si

chiama seme. Il generatore si dice moltiplicativo se c = 0. Quindi vengono

generati al piu m numeri interi Zi distinti con 0 ≤ Zi ≤ m − 1. Per ottenere

numeri casuali Ui in [0, 1) e sufficiente definire Ui = Zi/m.

1La notazione “ mod m ” indica la congruenza modulo m, ovvero il resto della divisione per m


GENERAZIONE DI OSSERVAZIONI CASUALI 149

Esempio 2.3.1 Vediamo un esempio di generatore moltiplicativo (c = 0). Prendiamo

a = 3, Z0 = 3 e m = 7. Si ottiene

Z1 = 9 ( mod 7 ) = 2

Z2 = 6 ( mod 7 ) = 6

Z3 = 18 ( mod 7 ) = 4

Z4 = 12 ( mod 7 ) = 5

Z5 = 15 ( mod 7 ) = 1

Z6 = 3 ( mod 7 ) = 3

Z7 = 9 ( mod 7 ) = 2

Naturalmente la successione e periodica di periodo al piu pari ad m. Se un

generatore ha periodo pari ad m, ovvero il periodo massimo, si dice che il gene- Periodo

pienoratore ha periodo pieno e, in questo caso, ogni scelta del seme Z0 portera alla

generazione dell’intero ciclo di valori da 0 a m− 1. Se invece un generatore non

ha periodo pieno allora la lunghezza del ciclo puo dipendere dal particolare valore

del seme Z0. E importante avere periodo lungo o, ancora meglio, periodo pieno in

modo che vengono generati tutti gli interi tra 0 e m−1 ed inoltre essi appariranno

esattamente una volta ogni ciclo e questo contribuisce all’uniformita delle Ui.

Il teorema che segue riporta le condizioni che devono essere soddisfatte dai

parametri m, a e c affinche il generatore abbia periodo pieno.

Teorema 2.3.1 Un generatore congruenziale lineare ha periodo pieno se e

solo se sono soddisfatte le seguenti condizioni:

i) m e c sono primi tra loro;

ii) se q e un numero primo che divide m, allora q divide a− 1;

iii) se 4 divide m, allora 4 divide a− 1.

E obiezione comune a tutti i generatori pseudo–random il fatto che le Zi non

sono realmente casuali, ma ogni Zi e completamente determinata dai quattro

parametri m, a, c e Z0. Tuttavia, un’attenta scelta di questi parametri induce

le Zi ad assumere valori tali che le Ui corrispondenti siano indipendenti identica-

mente distribuite secondo la distribuzione uniforme in [0, 1). Un’altra obiezione

riguarda il fatto che, ovviamente ogni numero reale nell’intervallo [0, 1) dovra

avere la stessa probabilita di essere generato, mentre le Ui assumono solamente

valori razionali. A questo inconveniente si puo ovviare scegliendo m molto grande

(m ≥ 109) in modo che i numeri generati Ui costituiscono un sottoinsieme denso

dell’intervallo [0, 1).

Nei linguaggi di programmazione sono di solito disponibili generatori di numeri

pseudocasuali ed esistono metodi statistici per valutarne la qualita.


150 SIMULAZIONE

Tra tutti i generatori di numeri pseudocasuali basati su metodi congruenziali

moltiplicativi, nel caso di computer a 32 bit, il piu utilizzato e il generatore di

Learmouth–Lewis dato da c = 0, a = 75 e m = 231 − 1.

2.3.2 Generazione di osservazioni casuali da una distribuzione di probabilita

Esaminiamo ora come, a partire da numeri casuali uniformemente distribuiti in

[0, 1) sia possibile generare osservazioni da una fissata distribuzione di probabilita.

Per questo scopo sono state introdotte molte tecniche. Ci limitiamo nel seguito

a considerarne due tra le piu utilizzate: il metodo della trasformazione inversa e

il metodo dell’accettazione–reiezione.

Metodo della trasformazione inversa

E un metodo per generare osservazioni da una distribuzione di probabilita. Il

metodo si basa sul seguente risultato teorico [Ross, 2003a] valido nel caso di

distribuzioni continue:

Proposizione 2.3.2 Sia U una variabile aleatoria uniforme in [0, 1). Allora

per ogni funzione di distribuzione continua F , la variabile aleatoria

X = F−1(U)

ha funzione di distribuzione F .

Dimostrazione: Sia FX la funzione di distribuzione della variabile aleatoria X.

Quindi, per ogni y risulta

FX(y) = P (X ≤ y) = P(F−1(U) ≤ y

).

Poiche F (x) e una funzione di distribuzione, essa e monotona crescente e quindi

si ha che F−1(U) ≤ y se e solo se U ≤ F (y). Quindi, poiche U ha distribuzione

uniforme, si ha

FX(y) = P (U ≤ F (y)) = F (y),

ovvero F e la funzione di distribuzione della X.

Quindi, sulla base di questo risultato, data una distribuzione di probabilita

con funzione di distribuzione F , a partire dalla distribuzione uniforme in [0, 1)

possiamo costruire una variabile aleatoria la cui funzione di distribuzione e F .

Osservazione 2.3.3 Nel caso in cui la funzione F non e strettamente monotona,

non e possibile definire la sua inversa; in questi casi, si puo utilizzare la funzione



pseudoinversa data da

F−1(x) = inf {y ∈ IR | x ≤ F (y)} .

Esempio 2.3.4 Supponiamo di voler costruire una successione di numeri pseudocasuali

come osservazioni dalla distribuzione esponenziale, ovvero con funzione di distribuzione

F (x) = 1 − e−λx. Innanzitutto determiniamo F−1: da u = F (x) = 1 − e−λx si ricava

x = −1/λ ln(1− u), ovvero

F−1(u) = − 1

λln(1− u).

Quindi se U e una variabile aleatoria uniformemente distribuita in [0, 1),

X = F−1(U) = − 1

λln(1− U) (2.3.1)

e una variabile aleatoria con distribuzione esponenziale con media 1/λ. Quindi, da-

ta una successione di numeri pseudocasuali con distribuzione uniforme in [0, 1), dal-

la (2.3.1) possiamo ottenere una successione di numeri pseudocasuali con distribuzione

esponenziale.

Esempio 2.3.5 Utilizzando quanto ricavato nel precedente Esempio 2.3.4 si puo otte-

nere la generazione di osservazioni casuali dalla distribuzione di Erlang. Infatti sappiamo

che la somma di k variabili aleatorie indipendenti identicamente distribuite secondo la

distribuzione esponenziale, ciascuna con media 1/(kµ) ha distribuzione di Erlang di para-

metro k e media 1/µ. Quindi avendo una successione di numeri uniformemente distribuiti

in [0, 1), u1, . . . , uk, le osservazioni dalla distribuzione di Erlang possono essere ottenute

da

x =

k∑i=1

ln(1− ui)−kµ

che e equivalente a

x = − 1

kµln

[k∏i=1

(1− ui)

].

Osservazione 2.3.6 E importante osservare che se una variabile aleatoria U ha

distribuzione uniforme in [0, 1), anche 1 − U ha distribuzione uniforme in [0, 1)

e quindi nella (2.3.1) si puo sostituire nell’argomento del logaritmo (1 − U) con

U . Tuttavia, come vedremo nel seguito nel paragrafo 2.5.1 sulle tecniche per la

riduzione della varianza, questo cambiamento potrebbe indurre un cambiamento

nella correlazione delle variabili X generate.

Il metodo della trasformazione inversa puo essere esteso ed utilizzato anche nel

caso di distribuzioni discrete, ovvero quando si assume che la variabile X sia una


152 SIMULAZIONE

variabile aleatoria discreta. In questo caso, naturalmente si ha

F (x) = P (X ≤ x) =∑xi≤x

p(xi),

dove p(xi) = P (X = xi).

Supponiamo quindi che X assuma i valori x1, x2, . . . e supponiamo che essi siano

ordinati, ovvero x1 < x2 < · · · . Data una variabile U uniformemente distribuita

in [0, 1) si definisce la variabile X nel seguente modo: si determina il piu piccolo

intero positivo k tale che U ≤ F (xk) e si pone X = xk. Dobbiamo ora dimostra-

re che effettivamente la X cosı generata e quella desiderata, ovvero che risulta

P (X = xi) = p(xi) per ogni i. Infatti si ha:

• per i = 1 risulta X = x1 se e solo se U ≤ F (x1), ma F (x1) = p(x1) perche

le xi sono ordinate. Ora, poiche la U e uniformemente distribuita in [0, 1),

si ha P (X = x1) = P (U ≤ F (x1)) = F (x1) = p(x1)

• per i ≥ 2 risulta X = xi se e solo se F (xi−1) < U ≤ F (xi) per come e scelto

i. Inoltre, poche la U e uniformemente distribuita in [0, 1) si ha

P (X = xi) = P (F (xi−1) < U ≤ F (xi)) = F (xi)− F (xi−1) = p(xi)

Il metodo della trasformazione inversa nel caso discreto ha una giustificazione

molto intuitiva: si divide l’intervallo [0, 1) in sottointervalli contigui di ampiezza

p(x1), p(x2), . . . e si assegna X a seconda del fatto che questi intervalli contengano

la U che e stata generata.

Esercizio 2.3.7 Si vuole generare una successione di osservazioni casuali da una distri-

buzione triangolare avente funzione di distribuzione

F (x) =

0 x ≤ 0x2

20 < x ≤ 1

1− (2− x)2

21 < x ≤ 2

1 x > 2

con il metodo della trasformazione inversa. Generare i primi quattro termini della suc-

cessione utilizzando come generatore di numeri pseudocasuali in [0, 1) un generatore

congruenziale lineare moltiplicativo con Z0 = 3, m = 5 e a = 3.

Esercizio 2.3.8 Si vuole generare una successione di osservazioni casuali da una distri-

buzione di probabilita avente per funzione di distribuzione

F (x) = exp

{− exp

(−x− µ

σ

)}




cessione (ponendo σ = 2 e µ = 1) utilizzando come generatore dei numero pseudocasuali

in [0, 1) un generatore congruenziale lineare moltiplicativo con Z0 = 5, m = 7 e a = 3.

Esercizio 2.3.9 Si vuole generare una successione di osservazioni casuali dalla distribu-

zione di probabilita di Cauchy avente per funzione di distribuzione

F (x) =1

2+

1

πarctan

x− st

−∞ < x <∞


cessione (ponendo s = 0 e t = 1) utilizzando come generatore dei numero pseudocasuali

in [0, 1) un generatore congruenziale lineare moltiplicativo con Z0 = 5, m = 7 e a = 3.

Metodo dell’accettazione–reiezione

Il metodo della trasformazione inversa e basato sul calcolo della trasformazione

inversa F−1 che non sempre puo essere calcolata o comunque non in maniera

efficiente. Per questa ragione sono stati sviluppati altri metodi fra i quali il

metodo che esaminiamo in questo paragrafo detto “acceptance–rejection” o anche

“metodo del rigetto”.

Consideriamo il caso continuo e supponiamo di voler generare osservazioni ca-

suali da una distribuzione di probabilita avente funzione di distribuzione F e

densita di probabilita f (il caso discreto si tratta in maniera del tutto analoga).

Supponiamo di disporre di un metodo per generare osservazioni casuali da una

variabile aleatoria Y avente per densita di probabilita una funzione g(x). Il me-

todo accettazione–reiezione utilizza queste osservazioni per generare osservazioni

casuali dalla distribuzione di probabilita avente per densita di probabilita la fun-

zione f(x). In particolare, si generano osservazioni casuali della variabile aleatoria

Y e poi si accettano o si rifiutano queste osservazioni come osservazioni casuali

delle distribuzione con densita data dalla f con una probabilita proporzionale al

rapporto f(Y )/g(Y ). Piu in dettaglio, sia c una costante tale che

f(y)

g(y)≤ c, per ogni y.

Il metodo si puo schematizzare nel seguente modo:

Passo 1: si genera un osservazione casuale della variabile aleatoria Y ;

Passo 2: si genera un numero casuale U dalla distribuzione uniforme in [0, 1)

(indipendente da Y );


154 SIMULAZIONE

Passo 3: se U ≤ f(Y )

cg(Y )allora si pone X = Y e STOP

altrimenti si torna al Passo 1.

Le generazione viene quindi effettuata mediante un algoritmo iterativo che ad

ogni passo genera un coppia di osservazioni casuali (Y, U) e si arresta quando e

soddisfatta la diseguaglianza U ≤ f(Y )

cg(Y ), accettando il valore di Y come osserva-

zione casuale della X. Alla fine dell’algoritmo si avra quindi che la variabile X ha

la distribuzione condizionata di Y dato l’evento “accettazione”, ovvero l’evento{U ≤ f(Y )

cg(Y )

}.

Si puo dimostrare che la variabile aleatoria X le cui osservazioni casuali sono

generate con il metodo accettazione–reiezione ha la densita di probabilita voluta,

ovvero vale la seguente proposizione.

Proposizione 2.3.10 La variabile aleatoria X generata con il metodo

accettazione–reiezione ha densita di probabilita f .

Dimostrazione: Osserviamo innanzitutto che, poiche la posizione X = Y si ha

quando avviene l’“accettazione”, allora risulta

P (X ≤ x) = P

(Y ≤ x/U ≤ f(Y )

cg(Y )

).

Inoltre, per l’indipendenza di Y da U si ha

P

(U ≤ f(Y )

cg(Y )/Y = y

)= P

(U ≤ f(y)

cg(y)

)=

f(y)

cg(y)(2.3.2)

Utilizzando la (2.3.2) si ottiene

P

(U ≤ f(Y )

cg(Y )

)=

∫ ∞−∞

P

(U ≤ f(Y )

cg(Y )/Y = y

)g(y)dy =

∫ ∞−∞

f(y)

cg(y)g(y)dy =

1

c

perche f e una densita di probabilita. Utilizzando le relazioni gia ottenute,

possiamo quindi calcolare

P (X ≤ x) = P

(Y ≤ x/U ≤ f(Y )

cg(Y )

)=P(Y ≤ x , U ≤ f(Y )

cg(Y )

)P(U ≤ f(Y )

cg(Y )

) =

= c

∫ x

−∞P

(U ≤ f(Y )

cg(Y )/Y = y

)g(y)dy

= c

∫ x

−∞

f(y)

cg(y)g(y)dy =

∫ x

−∞f(y)dy = F (x).



Esempio 2.3.11 Applichiamo il metodo dell’accettazione–reiezione per generare osser-

vazioni casuali da una variabile aleatoria avente densita di probabilita f(x) = 20x(1−x)3,

0 < x < 1 (si tratta della distribuzione beta con parametri 2 e 4). Innanzitutto dobbiamo

scegliere la funzione g(x): in questo una scelta di una funzione molto semplice e g(x) = 1,

0 < x < 1, ovvero si sceglie la distribuzione uniforme. Ora si deve determinare una co-

stante c tale che risultif(x)/g(x) ≤ c per ogni x. Naturalmente, in questo caso si puo

determinare facilmente c massimizzando la funzione f(x)/g(x); poiche la derivata prima

di f(x)/g(x) si annulla in x? = 1/4 e la derivata seconda in questo punto e negativa, il

punto x? e un punto di massimo per la funzione f(x)/g(x) e risulta

f(x)

g(x)≤ 135

64= c,

e quindi il test diventa U ≤ 256/27x(1− x)3.

Quindi il metodo in questo caso puo essere cosı realizzato:

Passo 1: si genera un’osservazione casuale U1 e dalla distribuzione uniforme in [0, 1);

Passo 2: si genera un’osservazione casuale U2 dalla distribuzione uniforme in [0, 1);

Passo 3: se U2 ≤256

27U1(1− U1)3 allora si pone X = U1 e STOP, altrimenti si torna al

Passo 1.

Esistono inoltre tecniche speciali per generare osservazioni da variabili aleatorie

distribuite secondo distribuzioni particolari per le quali si rimanda alla letteratura

dedicata.


Simulazione - uniroma1.itroma/didattica/SSS17-18/parteG.pdf · 2018. 5. 13. · de nirne le...

Documents

Transcript of Simulazione - uniroma1.itroma/didattica/SSS17-18/parteG.pdf · 2018. 5. 13. · de nirne le...