Sistemi di servizio e simulazione - Teoria - prof.Massimo Roma

ρm) SOLUZIONE IN FORMA PRODOTTO.

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

Reti aperte di Jackson

Una rete aperta di dice di Jackson se: 0

a) Gli arrivi dall’esterno ad un nodo i-esimo (con i=1,…m) sono poissoniani di parametro γi con γi>

per almeno un i;

b) I tempi di servizio di ciascuno degli Si serventi presenti al nodo i sono indipendenti e distribuiti

secondo la distribuzione esponenziale di parametro μi;

c) La probabilità che un utente completato il servizio presso un nodo i si rechi al successivo nodo j

(i,j=1,…m) (probabilità di routing) è assegnata pari a pij ed è indipendente dallo stato del sistema.

∑

= +

Supporremo che la capacità di ogni sistema è infinita. Per ogni nodo j gli arrivi sono: .

=1

γi

Poiché le e le pij sono note, si ha un sistema di m equazioni in m incognite (λj) che ammette soluzione

Λ=(λ1,…λm)T Γ=(γ1…γm)T,

unica se la matrice dei coefficienti è non singolare. Possiamo definire e

Λ=Γ+P Λ dove P è la matrice di routing.

possiamo scrivere il sistema in forma vettoriale: T

Teorema di Jackson

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=(n1,n2…nm) si fattorizza nel prodotto delle

distribuzioni di probabilità marginali P(n)=P(n1,n2…nm)=p p ….p dove p =ρ (1-ρ ). DIM:

jnj

n1 n2 nm nj j

prendiamo in considerazione un’equazione di bilancio dettagliato considerando solo il nodo j-esimo

supponendo che negli altri non avvenga nessuna transizione di stato. Nel passaggio dallo stato n allo

j-1

stato nj oppure dallo stato nj all’n possiamo scrivere: p =μ p . Siccome e sono costanti

λ λ μ

j-1 nj-1 nj-1 nj nj

possiamo riscrivere l’equazione nella forma: : p =μ p . Poiché abbiamo assunto che negli altri nodi

λ

j nj-1 j nj

non ci siano transizioni possiamo riscrivere

P(n1,….n -1,…nm)=μjP(n1,…nj,…nm) ovvero P(n1,…nj…nm)=ρjP(n1,…n ,…nm). Applicando nj volte

λ

j j j-1

questa relazione otteniamo P(n1,…nj…nm)=ρ P(n1,…,0,…nm). Se ripetiamo il procedimento per ogni

jnj

∏

j=1,…m si ha P(n1,..,nm)= (0, … 0)

. Dobbiamo calcolare P(0,…0) che è la probabilità che

=1

tutti i nodi siano allo stato 0. Imponiamo quindi la condizione che

∞ ∞ ∞

∑ ∑ ∑ ∏ (0, 0)

… . … = 1

. Nell’ipotesi che le serie convergano (ρj<1 per ogni

1=0 2=0 =0 =1

j=1,…m) si ha: 1 1 1

P(0,…0)= = = =(1-ρ1)(1-

1 1 1

∞ ∞ ∞ ∞ ∞ ∞

1 2

∑ ∑ ∏ ∑ ∑

….∑ 1 2 ….∑ ∗ ∗…

1=0 2=0 =0 1=0 2=0 =0

=1 1−1 1−2 1−

ρ2)..(1-ρm)

P(n1,…nj,….,nm)=∏

se sostituiamo P(0..0) così trovato sopra viene: (1 − )

.

=1

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

indipendenti. 5

Jackson per reti aperte multi servente

Data la rete di Jackson aperta, la probabilità congiunta che la rete si trovi allo stato n=(n1,..nm) si

fattorizza nl prodotto di tutte le distribuzioni marginali, ovvero P(n)=P(n1,…nm)=pn1 pn2 pn3…pnm,

dove:

1

( ) 0, <

!

pnj={ quindi anche nel caso multi servente una rete di Jackson aperta

1

( ) 0, ≥

−

!

si studia scomponendola in m sistemi a coda M/M/sj

Reti di Jackson chiuse

N un dato, costante. Il sistema ammette sempre la condizione stazionaria. Poiché risulta per ogni j

γj=0

∑

allora il sistema + = 1. . diventa un sistema omogeneo. In forma matriciale:

λj= =1

∑

(I-P )Λ=0. Se nessun utente può uscire dalla rete = 1 quindi la matrice I-P non è a rango

T T

=1

pieno (matrice del sistema singolare, c’è almeno una riga linearmente dipendente dalle altre)

possiamo ottenere infinite soluzioni in quanto i hanno almeno un parametro libero.

λ

Teorema di Jackson per reti chiuse monoserventi (e multi serventi)

Data una rete di Jackson chiusa con m nodi e singolo servente Sj=1 per j=1…m allora la distribuzione

1 1 2

congiunta è data da P(n)=P(n1,…nm)= 1 2 … . con n1+n2+…+nm=N e dove

()

1 2

∑

G(N)= 1 2 … . . G(N) è detto fattore di normalizzazione (perché

1,2,…, 1+..+=

∏

la somma delle pn deve essere =1). DIM: P(n1,..,nm)= , dove C è una costante che possiamo

=1

∑ ∏

determinare imponendo che: = 1 dalla quale otteniamo

1,2,…, 1+..+= =1

1

C= 1 2

∑ 1 2 ….

1,2,…, 1+..+=

Questo teorema può essere esteso anche al caso multi servente s ≥ 1, chiamiamo Xj= che

rappresenta il tempo medio che un utente passa in servizio nel nodo j dove è il valore atteso del

∑

numero delle visite an nodo j-esimo che soddisfa l’equazione =

=1

Teorema di Gordon-Newell

La distribuzione congiunta che la rete si trova nello stato n=(n1,…nm) è data da

, <

1 !

∏

P(n)=P(n1,…nm)= dove p̂ nj={ dove

=1

() , ≥

−

!

∑

G(N)= 1 2 …

1,2,.. 1+2+..+=

Simulazione

Elementi che caratterizzano un modello di simulazione:

variabili di stato (discrete o continue), eventi (accadimento che fa variare almeno una delle variabili di

stato, endogeni o esogeni), entità (singoli elementi del sistema, dinamiche o statiche) e attributi

(etichette delle entità), risorse (forniscono servizio alle entità, size-delay-release), attività e ritardi

(operazioni per cui è nota a priori la distribuzione di probabilità).

Modelli di simulazione ad eventi discreti

Le variabili di stato cambiano in istanti di tempo definiti in un insieme numerabile. Avanzamento del

tempo ad istanti prefissati o al prossimo evento.

Problemi: 6

Lunghezza arbitraria della simulazione, dipendenza stime dalle osservazioni casuali generate, stime

influenzate dalle condizioni iniziali.

Fasi della simulazione:

analisi del problema, formulazione del modello (trovare le distribuzioni che caratterizzano i dati del

modello, oppure recuperare dati già esistenti, definire le variabili di stato, identificare gli eventi,

identificare i valori che possono assumere le variabili di stato, creare ed implementare un simulation

clock cioè come scandire il tempo, definire metodo per generare eventi casuali, capire tutte le

transizioni di stato che ci sono state), analisi del modello di simulazione, scelta del software, verifica e

validazione del modello (vedere se le misure date dal modello rappresentano bene la realtà),

progettazione della simulazione (decidere lunghezza simulazione, lunghezza del transitorio iniziale

WARM UP, numero di repliche da effettuare per ottenere l’accuratezza prefissata sull’output),

esecuzione della simulazione, presentazione delle conclusioni dello studio.

Analisi di input

Dato un campione si estraggono informazioni attraverso l’inferenza statistica. Si assume che esiste una

distribuzione di probabilità della popolazione. X1,…Xn è il campione, Xi sono iid

1 =1

∑

̅ = stimatore corretto di μ

1 =1

2 2

∑ ( )

= − ̅ stimatore corretto di .

σ

2

−1

Bisogna scegliere una distribuzione di input

Tre approcci:

1) TRACE DRIVE SIMULATION (distribuzione guidata dai dati)

2) DISTRIBUZIONE EMPIRICA (costruisco una distribuzione empirica dai dati, tutti gli eventi

generati però saranno interni all’intervallo di dati forniti)

3) DISTRIBUZIONE TEORICA (utilizzo le standard, cerco quella che si adatta meglio). Bisogna:

a. verificare l’indipendenza delle osservazioni (cioè studiare il che deve fare 0)

ρ

b. individuare la famiglia di distribuzioni (della distribuzione si vanno a trovare elemento

più grande e più piccolo, media campionaria, mediana, varianza, coefficiente di

correlazione, grado di asimmetria (che si misura confrontando media e mediana, se

coincidono allora simmetrica) per una distribuzione esponenziale il coefficiente di

variazione è 1, minore di 1 per la binomiale e per la Poisson. Si ricorre anche all’uso di

istogrammi per vedere se la distribuzione dei dati lo approssima bene. L’intervallo tra

la più piccola e la più grande osservazione deve essere sezionato in k pezzi, se k molto

grande l’istogramma risente di andamenti locali, se molto piccolo andamenti

significativi possono essere assorbiti nei tratti.

c. stimare i parametri della distribuzione

d. verificare se i risultati sono rappresentativi (procedure grafiche e test statistici).

Generazione di osservazioni casuali

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

trasformazioni si arriva ai dati nella forma necessaria. Le osservazioni vengono generate dal

calcolatore in maniera deterministica ma si cerca di far sì che abbiano proprietà statistiche simili alle

osservazioni casuali. Generazioni PSEUDOCASUALI uniformemente distribuite in [0,1).

Generatori congruenziali lineari

Procedura iterativa che parte da un’osservazione iniziale (SEME) e genera una succ