1Le r dPsono un modello di sist emi ad event i discr et iche t r ae or igine dal lavor o di Car l AdamPet r i. Vant aggi delle r dP: Le r dPsono un f or malismo gr af ico e mat emat icoallo st esso t empo. Per met t ono di dar e una r appr esent azione compat t a di sist emi con gr ande spazio di st at o.Consent ono di r appr esent ar e il concet t o di concor r enza.Consent ono una r appr esent azione modular e.9. Ret i di Pet r i (r dP)Mar ia Paola Cabasino, Dicembr e 20102Con il t er mine r et e di Pet r i si indica unampia classe di modelli ad event i discr et i. Noi t r at t er emo il modello logico delle di Pet r i (r et e di post o/ t r ansizione) e il modello t empor izzat o, ot t enut o dal modello logico associando allevoluzione della r et e una st r ut t ur a di t empor izzazione.det er minist ico st ocast icoRet i di Pet r i: modello t empor izzat o3Una r dP un gr af o bipar t it o e pesat o. Idue t ipi di ver t ici sono det t i: post i (r appr esent at i da cer chi) e t r ansizioni (r appr esent at e da bar r e).Def inizione: Una r et e post o/ t r ansizione una st r ut t ur a N=(P,T,Pr e,Post ) dove: P: insieme dei post i (| P| =m), T: insieme delle t r ansizioni (| T| =n), Pr e: P x T N: la mat r ice di pr e-incidenza chespecif ica gli ar chi dir et t i dai post i alle t r ansizioni. Post : P x T N: la mat r ice di post -incidenza chespecif ica gli ar chi dir et t i dalle t r ansizioni ai post i.Hp: eP T = C P T= CRet i di Pet r i: Modello logico 4Esempio: P={p1,p2,p3,p4} T={t1,t2,t3,t4,t5} 2 p1 p2 p3 p4 t1 t2 t3 t4 t5 1 1 0 0 00 0 1 1 0Pr0 0 0 0 10 0 0 0 1e ( ( (= ( ( 1 0 0 0 10 2 0 0 0P0 0 1 0 00 0 0 1 0ost ( ( (= ( ( Not azione:Pr e(p2,t2)=2Pr e(p,)-5Mat r ice di incidenza C: P x T ZC= Post -Pr eEsempio:0 1 0 0 10 2 1 1 00 0 1 0 10 0 0 1 1C ( ( (= ( ( NB: La mat r ice di incidenza per de qualche inf or mazione sulla st r ut t ur a della r et e (es cappi).6Dat a una t r ansizione t eT si def iniscono i seguent i insiemi di post i: t ={peP|Pr e(p,t ) > 0}: linsieme dei post i in ingr esso a t ; t ={peP|Post (p,t ) > 0}: linsieme dei post i in uscit a da t .Dat o un post o pePsi def iniscono i seguent i insiemi di t r ansizioni: p={t eT |Post (p,t ) > 0}: linsieme delle t r ansizioni in ingr esso a p; p ={t eT |Pr e(p,t ) > 0}: linsieme delle t r ansizioni in uscit a da p.Esempio:t2={p1}, t2={p2},p2={t2} e p2={t3,t4} (vedi r dPpag.4).------ --Mar cat ur a e sist ema di r et eLa mar cat ur a def inisce lo st at o della r dP.Mar cat ur a: E una f unzione M : P N che assegna a ogni post o un numer o int er o non negat ivo di mar che (o get t oni).2 p1 p2 p3 p4 t1 t2 t3 t4 t5 -Una r et e N con una mar cat ur a iniziale M0 det t a una r et e mar cat a o sist ema di r et e, e viene indicat a come (N,M0).Abilit azione e scat t oUna t r ansizione t abilit at a dalla mar cat ur a M se M > Pr e (-,t )cio se ogni post o pePdella r et e cont iene un numer o di mar che par i o super ior e a Pr e(p,t ).Not azione: M[ t ) indica che t abilit at a da M;M[ t ) indica che t non abilit at a da M.Una t r ansizione sor gent e sempr e abilit at a.Una t r ansizione tabilit at a da M pu scat t ar e por t ando alla mar cat ur a M= M - Pr e(-,t ) + Post (-,t ) =M + C(-,t )9Una sequenza di t r ansizioni o=tj 1tj 2tj r eT* abilit at a da una mar cat ur a M se: la t r ansizione tj 1 abilit at a da M e il suo scat t o por t a a M1=M+C(-,tj 1); la t r ansizione tj 2 abilit at a da M1e il suo scat t o por t a a M2=M1+C(-,tj 1); eccUna sequenza abilit at a o viene anche det t a sequenza di scat t o e ad essa cor r isponde la t r aiet t or ia:M[ tj 1) M1[ tj 2) M2 [ tj r)Mr= M[ o)MrLa sequenza vuot a c (cio la sequenza di lunghezza zer o) abilit at a da ogni mar cat ur a M e vale M[ c) M10I l compor t ament o (o linguaggio) di una r et e mar cat a (N,M0) linsieme delle sequenze di scat t o abilit at e dalla mar cat ur a iniziale:L(N,M0)={oeT*|M0[ o)}.Una mar cat ur a M r aggiungibile in (N,M0) se esist e una sequenza di scat t o o t ale che M0[ o)M.L insieme di r aggiungibilit di una r et e mar cat a (N,M0) linsieme delle mar cat ur e che possono venirr aggiunt e da M0:R(N,M0)={MeNm|- o e L(N,M0): M0[ o)M }NB: Poich M0[ c) M0, vale dunque M0 e R(N,M0)11 (a) (b) (c) t1 t3 t2 p1 p3 p2 t2 p1 p2 t1 t1 p1 t2 p2 p3 r Esempi:(a): linguaggio inf init o, insieme di r agg. f init o(b): linguaggio inf init o, insieme di r agg. inf init o(c): linguaggio f init o, insieme di r agg. f init o12Sia (N,M0) una r et e mar cat a e sia C la sua mat r ice di incidenza. Se M r aggiungibile da M0scat t ando la sequenza di t r ansizioni o vale M=M0+C Equazione di st at o ptt ptt Conf lit t o st r ut t ur ale Conf lit t o ef f et t ivoSe -t -t= CSe M > Pr e (-,t ) e M > Pr e (-,t ) ma MPr e (-,t )+ Pr e (-,t )>/13St r ut t ur e element ar i di r et i di Pet r ie1 e2 e3 par begin e1 e2 e3 e1 e2 e3 par end (a) (b) (c) (d) e1 e2 e3 Sequenzialit Par allelismoSincr onizzazioneScelt a14St r ut t ur e element ar i di r et i di Pet r iMont aggioSmont aggioMut ua esclusione 4 latte farina burro besciamellaveicolo telaio ruote (a) (b) carica M1 carica M2 robot (c) t1 t4 t2 t3 15Esempi di modellazionePr ocesso emit t ent e-r icevent e canale 2 canale 1 pronto inviare pronto ricevere attesa confermamessaggio ricevuto ricevi messaggio invia messaggio invia conferma ricevi conferma emittentericevente 16Esempi di modellazionePr ocesso let t or i-scr it t or i inattivoinattivo in lettura in scrittura leggi termina scrittura termina lettura lettoriscrittori n sscrivi n n S 17 smontaggiomontaggio Pab disponibile macchina Pa disponibile Pb disponibile lavorazione Pa lavorazione Pb Pa lavorata Pb lavorata t1 t2 t3 t5 t4 t6 t7 t8 t1 t2 t4 t3 p1 p3 p2 (a) t1 t2 p (b) t2 p k (c) t1 p t4 p2 k (d) t3 p t2 p1 t1 (e) 22 Esempi di modellazioneMacchina non af f idabileMagazz. capac.Magazz. Magazz.inf init a capac. k mult iclasse Cella di manif at t ur a18Algor it mo: I l gr af o di r aggiungibilit di una r et e mar cat a (N,M0) con mat r ice di incidenza C si cost r uisce con la seguent e pr ocedur a.1. I l nodo r adice del gr af o M0. Quest o nodo non inizialment e et ichet t at o.2. Si consider i un nodo M del gr af o senza et ichet t a.a) Perogni tabilit at a da M, cio t .c. M>Pr e(-,t ):i. Si calcoli la mar cat ur a M=M+C(-,t ) r aggiunt a da M scat t ando tii. Se gi un nodo et ichet t at o M nel gr af o, si aggiunga il nodo M al gr af o.iii. Si aggiunga un ar co t r a M ed M.Gr af o di r aggiungibilit -/19b) Si et ichet t i il nodo M vecchio.3) Se esist ono nodi senza et ichet t a si r it or ni a 2.4) Si r imuovano t ut t e le et ichet t e dai nodi.NB: Tale pr ocedur a t er mina dopo un numer o f init o di passi se e solo se la r et e mar cat a ha un insieme di r aggiungibilit f init o. I n par t icolar e, il passo 2 viene r ipet ut o t ant e volt e quant e sono le mar cat ur e r aggiungibili.20Esempio: (a) t1p1 t2 (b) t3 p3[1 1 0] [0 2 0] [1 0 1] [2 0 0] [0 1 1] [0 0 2] t1 t1t1 t3 t3t3t2 t2 t2 p2 (N,M0)Gr af o di r aggiungibilit 21Pr oposizione: Si consider i una r et e mar cat a (N,M0)e il suo gr af o di r aggiungibilit (se esist e f init o).a) La mar cat ur a M appar t iene allinsieme di r aggiungibilit R(N,M0) SE E SOLO SE M un nodo del gr af o.b) Dat a MeR(N,M0), la sequenza o=tj 1tj 2appar t iene al linguaggio L(N,M) e pu esser e gener at a con la t r aiet t or ia M[ tj 1) M1[ tj 2) M2 SE E SOLO SE esist e nel gr af o un cammino or ient at o = M tj 1M tj 2M Da quest a pr oposizione seguono i seguent i r isult at i.22Cor ollar io: Si consider i una r et e mar cat a (N,M0) e il suo gr af o di r aggiungibilit (se esist e f init o).a) La mar cat ur a M r aggiungibile da una mar cat ur a MeR(N,M0) SE E SOLO SE esist ono nel gr af o due nodi M ed M ed esist e almeno un cammino or ient at o che va da M a M.b) La t r ansizione t abilit at a da una mar cat ur a MeR(N,M0) SE E SOLO SE esist e nel gr af o un nodo M da cui esce un ar co t .NB: Se linsieme delle mar cat ur e r aggiungibili inf init o, il gr af o che r appr esent a lo spazio di st at o della r et e det t o gr af o di coper t ur a.23r aggiungibilit limit at ezzar ipet it ivit r ever sibilit vivezzaPr opr iet compor t ament ali: dipendono sia dalla st r ut t ur a della r et e sia dalla mar cat ur a iniziale.24Raggiungibilit :I l pr oblema della r aggiungibilit di una mar cat ur a M da M0pu esser e r isolt o mediant e la cost r uzione del gr af o di r aggiungibilit nel caso la r et e abbia uno spazio di st at o f init o.Limit at ezza:Un post o p k-limit at o in (N,M0) se perogni MeR(N,M0) vale M(p) s k. Un post o 1-limit at o det t o sano. Una r et e mar cat a (N,M0) k-limit at ase ogni suo post o k-limit at o. Una r et e 1-limit at a det t a sana.Una r et e limit at a se e solo se ha spazio di r aggiungibilit f init o.25Ripet it ivit :Dat a una r et e mar cat a (N,M0), sia o una sequenza di t r ansizioni non vuot a e M e R(N,M0) una mar cat ur a da cui essa abilit at a. La sequenza o r ipet it iva se essa pu esser e eseguit a un numer o inf init o di volt e da M. Rever sibilit :Una r et e mar cat a (N,M0) r ever sibile se perogni mar cat ur a M e R(N,M0) vale M0 e R(N,M), cio se da ogni mar cat ur a r aggiungibile possibile t or nar e alla mar cat ur a iniziale M0. Una r et e mar cat a (N,M0) r ipet it iva se esist e una sequenza r ipet it iva in L(N,M0).26Vivezza e bloccoDat a una r et e mar cat a (N,M0), si dice che una sua t r ansizione : mor t a, se non esist e alcuna mar cat ur a r aggiungibile M e R(N,M0)che abilit a t ale t r ansizione; quasi-viva, se esist e almeno una mar cat ur a r aggiungibile M e R(N,M0)che abilit a t ale t r ansizione; viva, se perogni mar cat ur a r aggiungibile M e R(N,M0)la t r ansizione t quasi-viva.27Una r et e mar cat a (N,M0) : mor t a, se t ut t e le t r ansizioni sono mor t e; non quasi-viva, se cont iene t r ansizioni mor t e e quasi-vive; quasi-viva, se t ut t e le sue t r ansizioni sono quasi-vive; viva, se t ut t e le sue t r ansizioni sono vive.28Si usano perla valut azione delle pr est azioni di un sist ema. Ret i di Pet r i t empor izzat e (RdPT)Sono r dP a cui associat a una st r ut t ur a di t empor izzazione.Scat t o at omico: la t empor izzazione r ealizzat a associando ad ogni t r ansizione un r it ar do che cor r isponde al t empo che deve t r ascor r er e t r a la sua abilit azione e il conseguent e scat t o. La mar che r imangono nei post i di ingr esso f ino allo scat t o, a meno che unalt r a t r ansizione le pr eveli scat t ando a sua volt a. Solo se al t er mine del r it ar do la condizione di abilit azione cont inua a sussist er e, la t r ansizione scat t a ef f et t ivament e, f acendo s che le mar che pr elevat e dai post i in ingr esso siano deposit at e nei post i di uscit a.29NB: Se due t r ansizioni che vengono abilit at e cont empor aneament e sono in conf lit t o ef f et t ivo, la t r ansizione con il r it ar do minor e scat t a perpr ima disabilit ando lalt r a.Supponiamo che una t r ansizione tir appr esent i una cer t a at t ivit che r ichiede un cer t o t empo 0iperesser e svolt a af f inch la t r ansizione possa scat t ar e, deve t r ascor r er e un t empo 0idallist ant e in cui tiviene abilit at a. 0ipu esser e cost ant e, pu cambiar e (secondo una legge not a a pr ior i) ogni volt a che la t r ansizione viene abilit at a, o pu esser e una var iabile aleat or ia con f unzione di dist r ibuzionenot a. Tempor izzazione det er minist ica o t empor izzazione st ocast ica.30Una t r ansizione tidi una RdPT det t a: immediat a (), se scat t a appena viene abilit at a, cio se 0i=0; det er minist ica ( ), se ad essa associat o un t empo di r it ar do 0iscelt o in modo det er minist ico. Esso pu esser e cost ant e, var iabile secondo una sequenza not a o r ar ament e f unzione della mar cat ur a; st ocast ica (), se il t empo di r it ar do 0i una var iabile aleat or ia con una f unzione di pr obabilit not a. Se 0iha dist r ibuzione esponenziale fi(x)= ie-ixla t r ansizione ti det t a st ocast ica esponenziale: il t empo medio di r it ar do par i allinver so della f r equenza di scat t o i, cio 0i =1/i.La t r ansizione det t a st ocast ica est esa se il suo r it ar do una v.a. con dist r ibuzione diver sa dallesponenziale.Esempi:3132Semant ica di ser vent e della RdPT Ser vent i inf init i: ogni t r ansizione r appr esent a unoper azione che pu esser e eseguit a da un numer o inf init o di unit oper at ive che lavor ano in par allelo. Ser vent e singolo: ogni t r ansizione r appr esent a unoper azione che pu esser e eseguit a da una singola unit oper at iva. Ser vent i mult ipli: ogni t r ansizione r appr esent a unoper azione che pu esser e eseguit a da un numer o f init o k di unit oper at ive che lavor ano in par allelo. NB: Nel libr o viene ut ilizzat a come nozione di base la semant ica a ser vent i inf init i: a par t ir e da quest a nozione possibile r appr esent ar e anche le alt r e due permezzo di oppor t uni post i che limit ano il massimo gr ado di abilit azione della gener ica t r ansizione.Esempi:3334Memor ia t ot ale e di abilit azioneHp: 02 < 01 < 202Da M0 (allist ant e t0) t1e t2sono ent r ambe abilit at e, quindi allist ant e t1= 02la t r ansizione t2scat t a e sir aggiunge la mar cat ur a [ 0 0 1]T. Dopo un r it ar do par i a 03, cio allist ant e t2= t1+ 03, scat t a t3e si r it or na a M0. Successivament e:1. Memor ia t ot ale: t1r icor da di esser e st at a abilit at a perun int er vallo di t empo par i a 02e scat t er dopo un r it ar do 01 -02 .2. Memor ia di abilit azione: t1ha memor ia solo dellat t uale abilit azionenon scat t er mai!!35Def inizione: Una RdPTD car at t er izzat a dalla st r ut t ur a algebr ica Nd=(N,O) dove: N=(P,T,Pr e,Post ) una r et e P/ T; O = {Oi: ti eT}, con Oi ={0i,1,0i,2,}, tieT, 0i,2 eR+ {0}, k e N+ una st r ut t ur a di or ologio (o t empor izzazione) det er minist ica. Se i r it ar di sono cost ant i, allor a il gener ico element o 0i,k indicat o con 0i, k e N+.Una RdPTD Ndcon una mar cat ur a M0allist ant e di t empo iniziale t0 det t a RdPTD mar cat a e viene indicat a come (Nd,M0).Ret i di Pet r i t empor izzat e det er minist iche (RdPTD)36Evoluzione t empor ale di una RdPTDI l gr ado di abilit azione di una t r ansizione tiabilit at a da una mar cat ur a Mj il pi gr ande numer o int er o k t ale che Mj > k Pr e(-,ti). I l gr ado di abilit azione di tida Mjviene indicat o con oi(j ).Una t r ansizione ti det t a abilit at a da una mar cat ur a Mjse ogni post o peP della r et e cont iene un numer o di mar che par i o super ior e a Pr e(p,ti), cio se Mj >Pr e(-,ti).I n ogni ist ant e di t empo ogni t r ansizione tiha associat o un numer o di or ologi par i al suo gr ado di abilit azione cor r ent e; t ale numer o cambia con il gr ado di abilit azione, quindi pu var iar e ogni volt a che la r et e evolve da una mar cat ur a ad unalt r a, cio ogni volt a che una t r ansizione scat t a.Esempi:37(c)(a) o1(j )= (t r ansiz. sor gent e)(b) o1(0)=2(c) o3(0)=038Si assume che la RdPTD abbia allist ant e tjuna det er minat a mar cat ur a Mje che siano not i i valor i minimi degli or ologi associat i alle t r ansizioni oi=min{oi,1, , oi,oi(j )}, ti eT. Levoluzione dello st at o della RdPTDavviene at t r aver so la r ipet izione dei seguent i passi:1. I ndividuar e o*=mini:t i eT {oi}come il minimo t r a i valor i di or ologio oiassociat i alle t r ansizioni abilit at e da Mj. Se o*non unico pi t r ansizioni si t r ovano a scat t ar e cont empor aneament e, secondo una sequenza che deve esser e specif icat a a pr ior i (se la r et e non per sist ent e, ossia se lo scat t o di una t r ansizione pu disabilit ar ne alt r e).Algor it mo x levoluzione di una RdPTD (mem. abilit az, ser v)392. Allist ant e tj +1= tj+o*la t r ansizione t*scat t a por t ando alla mar cat ur a Mj +1=Mj+C(-,t*).3. Raggiunt a Mj +1, lor ologio associat o a t*viene scar t at o. Gli or ologi associat i alle t r ansizioni tieT vengono aggior nat i come segue: Se oi(j +1) nella mar cat ur a r aggiunt a Mj +1 inf er ior e a oi(j ) allor a devono esser e scar t at i [ oi(j )- oi(j +1)]or ologi associat i a ti: vengono eliminat i dallinsieme {oi,1, , oi,oi(j )} gli [ oi(j )-oi(j +1)]or ologi che hanno i valor i pi alt i; Se oi(j +1) > oi(j ), [ oi(j +1) - oi(j )]nuovi or ologi sono associat i a tie impost at i ai valor i def init i da O; Se oi(j +1) = oi(j ) non f accio nulla.4. Ripet er e dal passo 1 ponendo j +1j40NB1: Se la t r ansizione tinon abilit at a in una dat a mar cat ur a, non ha or ologi associat i, ossia non ha or ologi at t ivi.NB2: Se in Mjil valor e minimo di or ologi oidi una t r ansizione ticor r isponde a k, ci signif ica che se tisar la pr ossima a scat t ar e, essa scat t er k volt e cont empor aneament e.NB3: Se consider assimo il caso di memor ia t ot alelalgor it mo andr ebbe modif icat o solo al passo 2.NB4: Se consider assimo il caso di ser vent e singolo a ogni t r ansizione sar ebbe associat o un solo or ologio. Se invece consider assimo il caso di ser vent e mult iploil numer o degli or ologi associat i sar ebbe il minimo t r a il gr ado di abilit azione e il numer o dei ser vent i.41Esempi:t101=2p1p242Esempi:t101=2p1p2p2t201=143Un gr af o mar cat o (GM) una r dP in cui ogni post o ha una sola t r ansizione in ingr esso e una sola t r ansizione in uscit a e t ut t i gli ar chi hanno peso unit ar io. Gr af i mar cat i t empor izzat i (GMT)O1t1arrivo clientep3p1p4t2 inizio serviziop2O3t3 fine servizioEsempio: sist ema a coda modellat o mediant e un GMT44Def inizione: Un gr af o mar cat o t empor izzat o det er minist ico f or t ement e connesso (GMTFC) una r dPTD Ndche soddisf a le seguent i pr opr iet : la st r ut t ur e della r et e Nd un gr af o mar cat o t empor izzat o;la r et e f or t ement e connessa, cio esist e un cammino or ient at o da un qualunque nodo a ogni alt r o nodo: ci implica che ogni post o e ogni t r ansizione della r et e appar t engono ad un ciclo or ient at o. Linsieme dei cicli or ient at i denot at o I={1, , r}. la st r ut t ur a di t empor izzazione O associat a alle t r ansizioni det er minist ica e cost it uit a da sequenze di r it ar di cost ant i.45I n un GMT il numer o di mar che in ogni ciclo r imane cost ant e perogni sequenza di scat t o.Analisi delle pr est azioni Def inizione: I l t empo di ciclo C(ti) di una t r ansizione tidi un GMT def init o sulla base del gener ico k-esimo t empo di scat t o ti,kcome,( ) limi ki kC tk=N.B: ti,k list ant e di t empo in cui tiscat t a perla k-esima volt a a par t ir e dallist ant e iniziale t046Teor ema: I n un GMT, t ut t e le t r ansizioni appar t enent i ad un ciclo i eI hanno il medesimo t empo di ciclo Cj, def init o come il r appor t o t r a la somma dei t empi di r it ar do delle t r ansizioni che f or mano je il numer o di mar che che cir colano in esso, ossia( )( )( )jjjCM =dove: ( )i jj it e= ( ) ( )k jj kpM M pe= il t empo di r it ar do di ciclo; la mar cat ur a del ciclo j.47Teor ema di Chr et ienne: I n un GMTFC in condizioni st azionar ie, t ut t e le t r ansizioni hanno il medesimo t empo di ciclo C, dat o dalla r elazione( )max maxi jjj jk jitkpC CM p eeI eIe = = ` )che ident if ica il massimo f r a i t empi di ciclo di t ut t i i cicli element ar i del GMTFC; in alt r e par ole, t ut t e le t r ansizioni hanno a r egime f r equenza di scat t o r=1/ C.Tut t i i cicli t endono a sincr onizzar si, a r egime, sul pi lent o di essi (der iva dalle car at t er ist iche st r ut t ur ali dei GMTFC).48Esempio:Consider iamo il seguent e sist ema pr odut t ivo. Vogliamo calcolar e la f r equenza delle t r ansizioni della RdPTD a r egime. 49Icicli element ar i che compongono linsieme I sono:1: p7t1p2t2p7 2: p2t2p3t3p10t1p2 3: p8t3p4t4p8 4: p9t4p5t5p9 5: p5t5p6t6p11t4p56: p1t1p2t2p3t3p4t4p5t5p6t6p1It empi di ciclo sono r ispet t ivament e:C1=11;C2=12; C3=1; C4=21; C5=22; C6=11,3.Da cui la f r equenza di scat t o a r egime r isult a:1 1 10, 045max 22j jrC C eI= = = =50Def inizione: Una RdPTS una st r ut t ur a algebr ica Ns=(N,) dove: N=(P,T,Pr e,Post ) una r et e P/ T; = [ 12 ] il vet t or e delle f r equenze di scat t o delle t r ansizioni; gli element i i= i(Mk), k eN+.Peruna RdPTS le r egole di scat t o sono uguali a quelle di una RdPe la scelt a delle pr ossima t r ansizione da scat t ar e f at t a sulla base delle pr obabilit di scat t o delle singole t r ansizioni.Ret i di Pet r i t empor izzat e st ocast iche (RdPTS)( )( )Pr{ | }( )j ki ki kj kt MMt MMeA=Pr ob. di scat t o della t r ansizione tiabilit at a da MkA(Mk):insieme delle t r ansizioni abilit at e da Mk51Teor ema 1: I n un RdPTS, i t empi di per manenza in ogni mar cat ur a sono dist r ibuit i in manier a esponenziale.Una RdPTS equivalent e ad una CMTC.Teor ema 2: Levoluzione nel t empo di una RdPTS pu esser e descr it t a da una CMTC nella quale ogni st at o cor r isponde ad una mar cat ur a r aggiungibile dalla RdPTS.52Algor it mo:Una CM equivalent e ad una RdPTS si pu ot t ener e applicando il seguent e algor it mo: 1. I ndividua una cor r ispondenza biunivoca t r a gli st at i della CMTC e linsieme di r aggiungibilit R(N,M0)f acendo cor r isponder e ad ogni mar cat ur a Mkuno st at o xk eX.2. Fissa come dist r ibuzione iniziale di pr obabilit t0(0)=1, ossia assegna max pr obabilit allo st at o x0cor r ispondent e a M0.3. I mpost a gli element i della mat r ice Q par i a:( )( )i kkk i kt Mq M eA = ( )( )i j kkj i kt Mq M eA=dove Aj(Mk) = {tieA(Mk) |MktiMj}53Esempio:Consider iamo un cent r o di lavor azione cost it uit o da una sola macchina:p1: macchina disponibilep2: macchina in lavor azionep3: macchina in r ipar azionet1: inizio lavor azione (t asso di scat t o o)t2: f ine lavor azione (t asso di scat t o |)t3: guast o della macchina (t asso di scat t o )t4: r ipar azione complet at a (t asso di scat t o )54Gli st at i in cui pu t r ovar si il sist ema sono: x0= macchina disponibile, cor r ispondent e alla mar cat ur a M0=[ 1 0 0]T; x1= macchina al lavor o, cor r ispondent e alla mar cat ur a M1=[ 0 1 0]T; x2= macchina guast a, cor r ispondent e alla mar cat ur a M2=[ 0 0 1]T. La CMTC equivalent e alla RdPTS la seguent e:55La CMTC nella pr ecedent e pagina si pu ot t ener e semplicement e dal gr af o di r aggiungibilit della RdPTSsost it uendo ad ogni mar cat ur a lo st at o cor r ispondent e nella CMTC equivalent e e ad ogni t r ansizione della RdPTS il par amet r o che car at t er izza la dist r ibuzione esponenziale dei suoi t empi di scat t o.RdPTS limit at a CMTC f init aGr af o di r aggiungibilit RdPf or t ement e connesso CMTC er godica56Sappiamo che una CMTC omogenea f init a e ir r iducibile r isult a sempr e er godica. Quindi un gr af o mar cat o di una r et e limit at a f or t ement e connesso cor r isponde a una CMTC er godica.Lanalisi di un modello RdPTS di solit o mir at a alla misur a di indici di pr est azione:1. La pr obabilit di un event o e def init o in f unzione della mar cat ur a (ad es: nessuna mar ca in un sot t oinsieme di post i, o almeno una mar ca in un post o quando in un alt r o non ce ne sono, ecc) si calcola sommando la pr obabilit di t ut t e le mar cat ur e che soddisf ano levent o:Analisi st r ut t ur ale e analisi pr est azionalePr{ }k ekMe eM= dove Me linsieme di mar cat ur e percui la def inizione di e soddisf at t a572. La pr obabilit di aver e un cer t o numer o di mar che in un post o pisi pu calcolar e consider andola come uno speciale event o; per t ant o, se def iniamo ei,jlevent o di aver e jmar che nel post o pi, il numer o medio di mar che nel post o pi dat o da:,Pr{ }i i jjn j e =3. La f r equenza di scat t o fjdi una t r ansizione tj, ossia il numer o medio di volt e che la t r ansizione scat t a nellunit di t empo in condizioni di r egime la somma pesat a dei t assi di scat t o delle t r ansizioni abilit at e in ogni mar cat ur a Mi:: ( )( )j ij j i ii t Mf M eA= 58Esempio:Consider iamo la seguent e RdPTS dove i=1 peri=1,2,3,4. Vogliamo calcolar e: 1) la pr obabilit che a r egime i post i p2e p3siano cont empor aneament e mar cat i; 2) la f r equenza di scat t o a r egime della t r ansizione t2e 3) il numer o medio di mar che nel post o p5a r egime.59Cost r uiamo il gr af o di r aggiungibilit della RdPTS:M0=[ 1 0 0 0 0]T M1=[ 0 1 1 0 0]TM2=[ 0 0 1 1 0]TM3=[ 0 1 0 0 1]TM4=[ 0 0 0 1 1]TLa RdPTS limit at a e il gr af o f or t ement e connesso, quindi la CMTC equivalent e er godica, quindi posso calcolar e le pr obabilit di st at o a r egime r isolvendo il sist ema:0{1jjx XQ e==60Risolvendo il sist ema ot t engo: t0= t4=2/ 7 e t1= t2=t3=1/ 7, da cui:1) la pr obabilit che a r egime i post i p2e p3siano cont empor aneament e mar cat i par i a t1=1/ 7.2) la f r equenza di scat t o a r egime della t r ansizione t2 : 2* (t1+ t3)= 2/ 73) il numer o medio di mar che nel post o p5a r egime par i a: 1* (t3)+1* (t4)=3/ 7