tehnici_de_simulare_1-101

8/17/2019 tehnici_de_simulare_1-101

1/123

Gheorghe BARBU Maria MIROIU

TEHNICIDE

SIMULARE

2012


2/123

CUPRINS

Prefaţă 2Cai!o"#" I$ SISTEME% MODELE% SIMULARE 4

1.1Generalităţi despre sisteme, modele, simulare 41.1.1 Sisteme 41.1.2 Modele 51.1.3 Simulare 61.1.4 Tipuri de modele de simulare 9

1.2Descrierea modelelor de simulare 121.2.1 tapele reali!ării uni model de simulare 131.2.2 "easul simulării 16

Cai!o"#" II$ SIMULAREA NUMERELOR ALEATOARE 1#

2.1$umere aleatoare uni%orme. &rocedee de 'enerare 1#2.2Simularea numerelor aleatoare uni%orme 2(

2.2.1 Metoda pătratului din mi)loc 232.2.2 Metode con'ruenţiale 23

Cai!o"#" III$ SIMULAREA &ARIABILELOR ALEATOARE 25

3.1Metoda in*ersă 253.2Metoda respin'erii 293.3Metoda compunerii 313.4+lte metode de simulare 343.5Metode particulare 3#

Cai!o"#" I&$ SIMULAREA &ECTORILOR ALEATORI 4

4.1Generarea *ectorilor aleatori prin metoda in*ersă 44.2Generarea *ectorilor aleatori a*-nd repartiţie uni%ormă 4#4.3Generarea *ectorilor aleatori a*-nd repartiţie Diriclet 534.4Generarea *ectorilor aleatori a*-nd repartiţie multinomială 564.5Generarea *ectorilor aleatori a*-nd repartiţie normală 5

Cai!o"#" &$ APLICA'II ALE SIMUL(RII 59

5.1"alculul inte'ralelor multiple prin Metoda Monte "arlo 59

5.2stimarea numărului π prin Metoda Monte "arlo 665.3Simularea unor procese de stocare 65.4Simularea unor procese de a/teptare 35.5Simularea %ia0ilităţii

A)e*ă + IMPLEMENT(RI C,C-- ##

Bi."iografie 1((

1


3/123

PRE/A'(

ucrarea de %aţă a %ost ela0orată n cadrul &roiectului&SD561.2S326#, coordonat de Ministerul ducaţiei, "ercetării, Tineretului/i Sportului, intitulat7 8ormarea cadrelor didactice uni*ersitare /i a studenţilor ndomeniul utili!ării unor instrumente moderne de predare:n*ăţare:e*aluare pentrudisciplinele matematice, n *ederea creării de competenţe per%ormante /i practice

pentru piaţa muncii;.inanţat din ondul Social uropean /i implementat de către Ministerul

ducaţiei, "ercetării, Tineretului /i Sportului, n cola0orare cu Te ed &oint, ameni/i "ompanii, ni*ersitatea din


4/123

Cn acest conteBt, anali!a %leBi0ilităţii curriculei, nsoţită de anali!a metodelor /iinstrumentelor %olosite pentru identi%icarea /i moti*area studenţilor talentaţi lamatematică ar putea răspunde deopotri*ă cerinţelor de masă, c-t /i celor de elită.

>i!iunea pe termen lun' a acestui proiect preconi!ea!ă determinarea unor

scim0ări n a0ordarea %enomenului matematic pe mai multe planuri7 in%ormarea unuinumăr c-t mai mare de mem0ri ai societăţii n le'ătură cu rolul /i locul matematicii neducaţia de 0a!ă n instrucţie /i n descoperirile /tiinţi%ice menite să m0unătăţeascăcalitatea *ieţii, inclusi* populari!area unor mari descoperiri tenice, /i nu numai, ncare matematica cea mai a*ansată a )ucat un rol otăr-tor. De asemenea, se urmăre/tee*idenţierea a noi moti*aţii solide pentru n*ăţarea /i studiul matematicii la ni*elele de

0a!ă /i la ni*el de per%ormanţă stimularea creati*ităţii /i %ormarea la *iitoriicercetători matematicieni a unei atitudini descise %aţă de nsu/irea aspectelor speci%ice din alte /tiinţe, n scopul participării cu succes n ecipe miBte de cercetare

sau a a0ordării unei cercetări inter /i multi disciplinare identi%icarea unor %orme de pre'ătire adec*ată de matematică pentru *iitorii studenţi ai disciplinelor matematice,n scopul utili!ării la ni*el de per%ormanţă a aparatului matematic n construirea uneicariere pro%esionale.

+ceastă lucrare re%lectă e%orturile autorilor n cadrul acestui proiect /ieBperienţa lor n predarea matematicilor aplicate /i in%ormaticii, n 'eneral /i atenicilor de simulare n special, la %acultatea de matematică:in%ormatică ani*ersităţii din &ite/ti.

ucrarea m0ină n mod armonios pre!entările teoretice cu eBemple

semni%icati*e, %acilit-nd studenţilor, cadrelor didactice, matematicienilor, in'inerilor,cercetătorilor etc. cunoa/terea, apro%undarea /i utili!area tenicilor de simulare ndi%erite domenii de acti*itate.

Dispun-nd de o *astă eBperienţă n procesul de predare:n*ăţare:e*aluare,

autorii s:au străduit să reali!e!e un material de studiu unitar n domeniul simulării,

ntr:o %ormă accesi0ilă, /i speră că această lucrare ela0orată n cadrul proiectului mai

sus menţionat *a contri0ui la o mai 0ună nţele'ere /i asimilare a cuno/tinţelor de

modelare /i simulare, care pot %i de un real %olos pentru aplicarea lor n practică.

+utorii

3


5/123


6/123

n sistem deschis este caracteri!at prin7- ie/iri care corespund intrărilor n sistem- ie/irile sunt i!olate de intrări- ie/irile nu au nici o in%luenţă asupra intrărilor.

Cntr:un sistem descis, re!ultatele acţiunii trecute nu comandă acţiunea *iitoare.Sistemul nu o0ser*ă /i nu reacţionea!ă la propria:i per%ormanţă.

De eBemplu, un automo0il este un sistem descis care sin'ur nu se poate conducedupă drumul pe care l:a parcurs n trecut /i nici nu are o anumită 8ţintă;, direcţie, sprecare să mear'ă n *iitor.

=ntrări=e/iri

Si!e

i'ura 1.1. Sistem descis

n ceas este, de asemenea, un sistem descis el nu:/i o0ser*ă propria impreci!ie pentru a /i:o corecta sin'ur.

Sistemul închis (cu conexiune inversă, cu reacţie sau feed-back) estecaracteri!at prin7

- ie/iri care corespund intrărilor n sistem- ie/irile depind de intrări- ie/irile in%luenţea!ă intrările.

n sistem închis este in%luenţat de propria:i comportare trecută. a acestesisteme ie/irile pot re'la intrările. n sistem cu coneBiune in*ersă %uncţionea!ă ca o

0uclă ncisă care %olose/te re!ultatele acţiunii trecute ale sistemului pentru acomanda acţiunea *iitoare.

De eBemplu, un ceas /i posesorul lui %ormea!ă un sistem cu coneBiune in*ersă, c-ndora indicată de ceas este comparată cu ora eBactă, care este luată ca reper, ceasul este

potri*it pentru a elimina erorile.

Deci!ie +cţiune Starea sistemului =n%ormaţia

i'ura 1.2. Sistem cu coneBiune in*ersă


7/123

1$1$2 Moe"e

Modelarea este o metodă de studiu a unor procese /i %enomene care sereali!ea!ă prin su0stituirea o0iectului real al cercetării. "a metodă de cercetare estedestul de *ece, modelele %i!ice prin similitudine, apoi cele construite prin analo'ie

nlocuind de multe ori o0iectul real supus cercetării.n model presupune, n 'eneral, repre!entarea sistemului ca o mulţime de

părţi n interacţiune una cu alta.Modelul poate %i7

Ø un duplicat al sistemuluiØ o repre!entare sim0olică Ede eBemplu matematicăF a sistemuluiØ sistemul.

Modelele constituie repre!entări ale realităţii. Dacă ele ar %i tot at-t de 'reu demane*rat ca realitatea, prin utili!area lor nu s:ar o0ţine niciun a*anta). De o0icei, se

pot construi modele mult mai simple dec-t realitatea, pe 0a!a cărora putem să pre*edem /i să eBplicăm cu un nalt 'rad de acurateţe, %enomene compleBe. Bplicaţiaconstă n %aptul că, de/i pentru a descrie un %enomen este necesar un număr mare de*aria0ile, de o0icei puţine dintre acestea au rol esenţial. =mportant este să descoperimcare sunt acele *aria0ile /i relaţiile dintre ele.

Modelarea matematică ocupă un loc important n ansam0lul metodelor demodelare, n special prin %acilităţile o%erite de calculatoarele cu capacitate mare dememorare /i *ite!ă mare de lucru.

Modelele matematice au apărut din necesitatea de a descrie /i studia %ormalcomportarea unei cate'orii de sisteme reale, cu scopul de a controla /i diri)a

acti*itatea lor *iitoare.

la0orarea unei structuri matematice mpreună cu o listă de corespondenţentre sim0olurile matematice /i o0iectele situaţiei concrete considerate a condus laceea ce numim model matematic.

Cn 'eneral, un model M al unui sistem S este un alt sistem S care din anumite puncte de *edere este eci*alent cu S , dar care este mai u/or de studiat dec-t S . &rintr:un sistem S nţele'em următoarea structură de mulţimi7

S H! , " , # , $ , % , I, JK

unde- ! este timpul de 0a!ă utili!at pentru cronometrarea /i ordonarea e*enimentelor

acesta este un număr real dacă sistemul este cu timp continuu sau ntre' dacăsistemul este cu timp discret

- " repre!intă mulţimea intrărilor n sistem- # este mulţimea se'mentelor de intrare n sistem, prin se'ment de intrare n sistem

asociat %uncţiei u 7 ! & " nţele'-ndu:se 'ra%icul %uncţiei u pe un inter*al Lt (, t 1,adică7

uELt (, t 1F HEt , uEt FF N t ( O t O t 1K- $ este mulţimea stărilor sistemului. Starea este un concept de modelare a structurii

interne a sistemului, ce conţine istoria acestuia /i care:i a%ectea!ă pre!entul /i*iitorul /i mpreună cu %orma intrărilor determină n mod unic ie/irile din sistem

6


8/123

- % este mulţimea ie/irilor sistemului

- I este %uncţia de răspuns a sistemului I 7 "'$ & % dacă la o intrare uELt (, t 1F

sistemul se a%lă n starea σt ( ∈$ atunci ie/irea sistemului este

% = ϕ (u([t ( ,t 1 ]),σ t ( )- J este %uncţia de tran!iţie a stărilor ceea ce nseamnă că dacă intrarea uELt (, t 1F

'ăse/te sistemul n starea σt ( ∈$ atunci l trans%ormă pe acesta n starea σt 1 =η(u([t ( , t 1]), σt ( ).

"unoa/terea intrărilor u∈# /i a răspunsurilor corespun!ătoarea acestora ∈% repre!intă comportarea sistemului.

n model al unui sistem tre0uie să ndeplinească următoarele trei condiţii71. modelul tre0uie să re%lecte c-t se poate de %idel realitatea repre!entată2. modelul tre0uie să constituie o simpli%icare a realităţii repre!entate3. modelul este prin esenţa sa o ideali!are a realităţii repre!entate.

1$1$3 Si#"are

Cn procesul de modelare matematică, componentelor sistemului li se asocia!ăanumite *aria0ile parametri, unele cunoscute Econtrola0ileF, numite *aria0ile

parametri de intrare, altele necunoscute Enecontrola0ileF, numite *aria0ile parametride ie/ire. e'ăturile /i interacţiunile dintre componentele sistemului sau le'ăturilesistemului cu eBteriorul se transpun n modelul matematic prin relaţii %uncţionale

Eecuaţii /i sau identităţiF. Scopul modelului este de a eBprima *aria0ilelenecontrola0ile n %uncţie de *aria0ilele controla0ile, ast%el nc-t să %ie satis%ăcutecriteriile de per%ormanţă. neori nu este posi0il să se eBprime su0 %ormă de ecuaţiitoate le'ăturile, condiţionările /i interdependenţele necesare, moti* pentru care uneledintre acestea se descriu prin condiţii lo'ice sau proceduri ce pot %i manipulate numai

prin intermediul calculatorului. Modelul matematic completat cu ast%el de procedurieste un model de simulare, care pornind de la *alori ale *aria0ilelor controla0ileE'enerate cu al'oritmi specialiF, *a produce *alori ale *aria0ilelor necontrola0ile,o%erind *ariante din care se poate ale'e cea mai 0ună. De aici re!ultă că modelul desimulare produce eBperimente asupra sistemului pe care:l simulea!ă, ceea ce permiteale'erea acelor *alori ale *aria0ilelor /i parametrilor de intrare care conduc la

per%ormanţele dorite. $ecesitatea o0ţinerii unor in%ormaţii despre un anumit sistem nainte ca el să

%ie reali!at a condus la apariţia simulării.Cn proiectarea sistemelor, deose0it de importantă este o0ţinerea unor in%ormaţii

despre sistem nainte ca el să %ie reali!at concret acest lucru este posi0il aplic-ndtenica simulării.

&rin simulare numerică se nţele'e totalitatea procedeelor matematice /i decalcul destinate studiului comportării n timp a sistemelor reale cu a)utorul

calculatoarelor electronice numerice, presupun-ndu:se că n e*oluţia acestor sistemeinter*in /i elemente aleatoare.


9/123

Simularea numerică este o tenică potri*it căreia se asocia!ă sistemului real unmodel adec*at numit model de simulare, care repre!intă mulţimea interacţiunilor lo'ice ale componentelor sistemului, precum /i mecanismul scim0ării lor n timp.Modelul este %olosit apoi pentru a produce, prin intermediul calculatorului,succesiunea cronolo'ică de stări prin care trece sistemul, consider-ndu:se dată starea

sa iniţială.Deoarece n e*oluţia lor sistemele reale sunt in%luenţate de cau!e aleatoare al

căror e%ect tre0uie pus n e*idenţă n cadrul modelelor de simulare, una din pro0lemelematematice importate ale simulării numerice constă n 'enerarea simularea cucalculatorul a unor selecţii statistice asupra di%eritelor tipuri de *aria0ile aleatoare /i

procese stocastice. altă pro0lemă importantă le'ată de construirea modelelor de simulare este

aceea a cronometrării eBacte a e*enimentelor stărilor sistemului simulat %olosind o*aria0ilă numită ceasul simulării, care este supusă unui număr %init de cre/teri pe

parcursul simulării.De/i nu o%eră soluţii eBacte, simularea este o tenică e%icientă de cercetare at-t

pentru %enomenele %i!ice care nu pot %i percepute de om c-t /i pentru acelea percepute,dar imposi0il de studiat analitic. $ecesitatea simulării re!idă n %aptul că adeseorisistemele reale nu pot %i studiate n mod direct, %ie datorită di%icultăţilor de e*aluarecalitati*ă sau cantitati*ă a %enomenelor, %ie din cau!a compleBităţii Enumărul mare de*aria0ile de intrare /i de ie/ire, numărul mare de stări posi0ile, compleBitatea%uncţiilor I /i J, etc.F.

Studiul *ariantelor de deci!ie pe modele pre!intă următoarele a*anta)e7- de natură economică- scurtea!ă durata de o0ţinere a soluţiilor- permite anali!a unui număr mare de *ariante prin modi%icarea condiţiilor

iniţiale, a*-nd a*anta)ul re*enirii la *arianta de răspuns con%ormă cucerinţele utili!atorului.

olosirea unui sistem real pentru eBperimentare poate conduce la pertur0areaacti*ităţilor unui domeniu n care este studiat sistemul, anumite *ariante mai puţininspirate put-nd a*ea implicaţi impre*i!i0ile.

Cn ca!ul unor sisteme care nu eBistă ncă se poate o0ţine un plan de construirea sistemului n %uncţie de anumite criterii de optimi!are a intrărilor /isau ie/irilor sistemului repre!entat.

De eBemplu, dacă utili!ăm simularea pentru proiectarea unui 0ara),

dimensiunile /i re!istenţa acestuia se pot determina prin eBperimente cu calculatorul pe un model care pre*ede cerinţa medie de curent electric /i %actori aleatori precum*olumul precipitaţiilor n inter*alele de timp sta0ilite. Bperimentele reale nu sunt

practice, deoarece 0ara)ul odată construit nu poate %i modi%icat.Simularea presupune /i unele de!a*anta)e7- construirea modelelor de simulare cere o pre'ătire specială se spune că

simularea este mai de'ra0ă o artă dec-t o /tiinţă, care se n*aţă n timp /i prin eBperienţă

- re!ultatele simulării sunt aproBimati*e /i nu eBacte, iar uneori sunt 'reu deinterpretat

- cele mai multe ie/iri ale sistemului sunt *aria0ile aleatoare E0a!ate peintrări aleatoareF ale căror repartiţii tre0uie cunoscute sau determinate.

#


10/123

1$1$4 Ti#ri e oe"e e i#"are

Cn multe domenii /tiinţi%ice se %olosesc trei tipuri de modele de simulare7· modele imitati*e

· modele analo'ice· modele sim0olice

Modelele imitative au următoarele caracteristici7- transpun realitatea la o altă scară, mai mare sau mai mică, cu scopul

o0ser*ării comportării realităţii respecti*e- imită realitatea, ceea ce nseamnă că un model imitati* seamănă cu

%enomenul pe care:l repre!intă, dar di%eră ca mărime- repre!intă o ima'ine a realităţii.

Bemple7 proiectele unor clădiri, ărţile 'eo'ra%ice, macetele de automo0ile,

na*e a*ioane etc. Modelele imitati*e ale soarelui /i planetelor sunt mic/orate, n timpce modelele atomice Emodelul lui


11/123

Modelele de simulare mai pot %i clasi%icate ast%el7· statistice sau dinamice· deterministe sau stocastice,· discrete sau continue.

Modelele statice sunt acelea care ndeplinesc următoarele condiţii7- nu iau n mod eBplicit n considerare *aria0ila timp- re%lectă situaţii /i stări in*ariante /i atemporale- soluţiile pot %i o0ţinute /i analitic.

Modelele dinamice sunt acelea care7- ţin seamă de *ariaţia /i interacţiunea n timp a *aria0ilelor considerate- ncorporea!ă timpul ca mărime %undamentală, %iind o *aria0ilă de stare- se re!ol*ă utili!-nd tenica simulării.

Modelele deterministe sunt acelea n care7- toate *aria0ilele sunt nealeatoare- caracteristicile operati*e sunt ecuaţii de o anumită %ormă- soluţiile acestor modele se o0ţin pe cale analitică.

Modelele stochastice sunt acelea care7- conţin una sau mai multe *aria0ile de intrare aleatoare /i deci una din

caracteristicile operati*e este dată printr:o %uncţie de densitate- intrările aleatoare conduc la ie/iri aleatoare- e*enimentele nu se produc cu certitudine, ci cu o anumită pro0a0ilitate.

Cn ca!ul modelelor deterministe e*enimentele se produc sau nu se produc, iar n ca!ul producerii eBistă o certitudine 0a!ată pe re'uli clare. Cn ca!ul modelelor aleatoare e*enimentele se produc sau nu se produc, re'ulile de in%erenţă ale modeluluinu con%eră nsă certitudine producerii lor. +ceste modele, de o0icei, se re!ol*ă%olosind tenica simulării, metodele analitice %iind ine%iciente.

Modelele discrete sunt acele modele n care scim0ările stărilor *aria0ilelor se %ac la momente discrete de timp.

Modelele continue sunt acelea n care scim0ările stărilor *aria0ilelor se produc continuu.

Bemple7

1$ %a0rică poate să producă ntr:o lună trei tipuri de aparate electronice7 4aparateoră din primul tip, 2 aparateoră din al doilea tip /i 3 aparateoră din al treileatip.


12/123

"onstrucţia modelului poate %i %ăcută ast%el7

Se notea!ă cu x1, x2, x3 numărul de aparate din %iecare tip /i o0ţine74 x1 + 2 x2 + 3 x3 ≤ 16( x ≤ 25( 1

x2 ≤ 12( x ≤ #(

3

x , x 2 , x

3 ≥ (

1 +1(( x + 5 x FmaBE5( x 2 3 1

+cesta este un model static /i determinist.

2. &ro0lema *-n!ătorului de !iare.n *-n!ător de !iare tre0uie să comande !ilnic un număr de !iare ast%el nc-t

c-/ti'ul din *-n!area lor să %ie maBim. Cn %iecare !i el comandă un anumit număr de!iare, *-n!-nd o parte dintre ele sau pe toate. iecare !iar *-ndut i aduce un anumitc-/ti'. Qiarele ne*-ndute se pot napoia, dar i pro*oacă o anumită pierdere. $umărul!iarelor *-ndute este *aria0il de la o !i la alta, pro0a0ilitatea *-n!ării unui anumitnumăr de !iare ntr:o !i put-nd %i estimată pe 0a!a *-n!ărilor din perioada anterioară.

"onstrucţia modelului poate %i reali!ată consider-nd următoarele *aria0ile7n numărul !iarelor comandate n %iecare !ic c-/ti'ul o0ţinut din *-n!area unui !iarl pierderea datorată unui !iar ne*-ndutr cerereanumărul !iarelor *-ndute ntr:o !i

*Er F pro0a0ilitatea ca ntr:o !i oarecare să *-ndă r!iare + c-/ti'ul o0ţinut ntr:o !i.Dacă ntr:o !i numărul !iarelor *-ndute EcerereaF este mai mare sau e'al cu

numărul !iarelor comandate Er nF, c-/ti'ul *a %i + Er nF nc.

Dacă ntr:o !i numărul !iarelor *-ndute EcerereaF este mai mică dec-t numărul!iarelor comandate Er R nF, c-/ti'ul *a %i

+ Er R nF rc A En:r Fl ."-/ti'ul mediu !ilni* *a %i

n ∞

= ∑ *Er FLrc − En − r Fl + ∑ *Er Fnc + r =( r =n+1+cesta este un model stocastic, deoarece

n *aria0ilă controla0ilăr *aria0ilă necontrola0ilăc, l constante.

&rin re!ol*area acestui model tre0uie 'ăsit n pentru care + este maBim.


13/123

11


14/123

1$2 De5rierea oe"e"or e i#"are

Cn procesul de modelare matematică, modelul este repre!entati* pentru

sistemul %i!ic dacă se respectă condiţia de cau!alitate, ceea ce conduce la clasi%icareaelementelor n7

- elemente de intrare (cauă) care %ormea!ă *ectorul de intrare x E x1, x2,/xmF,- elemente de ie0ire (efect) care %ormea!ă *ectorul de ie/ire E 1, 2,/ nF, am0ii *ectori %iind n 'eneral aleatori.

Cn a0senţa oricăror in%ormaţii asupra structurii sistemului, acesta este descrismatematic de către dependenţa %uncţională dintre *ectorul de ie/ire /i *ectorul deintrare7 f E xF.

>aria0ilele de intrare pot %i7- variabilele deterministe, care se o0ţin după re'uli 0ine preci!ate sau se 'ăsesc

nre'istrate pe suporţi de in%ormaţie- variabilele stochastice, care sunt 'enerate cu calculatorul după al'oritmi de

'enerare per%ormanţi, 'enerarea depin!-nd de parametrii de intrare carecaracteri!ea!ă aceste *aria0ile.

+asul simulării este prin de%iniţie o etapă n care toate *aria0ilele de intrare iau*alori constante n timpul eBecutării pro'ramului.

0ser*aţii7- *aria0ilele de ie/ire depind de *aria0ilele de intrare dependenţa este determinată

de structura lo'ică a modelului de simulare considerat- o *aloare a unei *aria0ile de ie/ire este re!ultatul eBecutării unui pas al

pro'ramului de calcul asociat modelului- dacă cel puţin una din *aria0ilele de intrare este stocastică, atunci cel puţin una

din *aria0ilele de ie/ire este stocastică.

De mare importanţă n construirea modelului de simulare este procedeul de@mi/care; a sistemului n timp pentru aceasta este necesară introducerea unei*aria0ile speciale numită ceasul simulării, care să măsoare scur'erea timpului real n

care se simulea!ă sistemul, cu scopul de a menţine ordinea corectă n timp ae*enimentelor.

Modelele de simulare mai conţin7- relaţii funcţionale7 identităţi /isau ecuaţii- caracteristici o*erative, %iind utili!ate pentru a eBprima prin relaţii matematice

interacţiunile *aria0ilelor /i comportarea sistemului. caracteristică operati*ă este de o0icei o ipote!ă Estatistică sau nuF sau o

ecuaţie matematică preci!ată care lea'ă *aria0ilele de intrare ale sistemului de stărisau de *aria0ilele de ie/ire.

Dacă aceste *aria0ile sunt stocastice, caracteristicile operati*e iau %orma unor %uncţii de densitate de pro0a0ilitate, iar printre parametrii de intrare ai modelului *or

12


15/123

%i /i parametrii statistici ai caracteristicilor operati*e. +ce/ti parametri au rol demărimi de intrare n modelul de simulare /i tre0uie estimaţi n preala0il din o0ser*aţiistatistice e%ectuate asupra procesului sau sistemului ce urmea!ă a %i simulat.

După construirea modelului de simulare, simularea n sine, ca eBperiment,

constă n a *aria *alorile *aria0ilelor /i parametrilor de intrare ai sistemului /i adeduce pe 0a!a modelului, ca re!ultat al calculelor, e%ectele lor asupra *aria0ilelor deie/ire.

Deose0im două tipuri de simulare7- discretă, dacă *aria0ilele modelului pot a*ea numai anumite *alori

discrete- continuă, dacă *aria0ilele modelului pot a*ea orice *aloare pe anumite

inter*ale reale.Cn ca!ul simulării cu timp discret, ceasul simulării naintea!ă de la un

e*eniment la altul /i nu n mod continuu.Cn ca!ul simulării cu timp continuu, *aria0ilele care descriu starea sistemului

/i scim0ă *alorile n mod continuu n raport cu timpul.

1$2$1 E!ae"e rea"i6ării #)#i oe" e i#"are

"onstruirea modelelor de simulare constituie un proces amplu care n 'eneral presupune parcur'erea următoarelor etape7

1. 1efinirea *roblemei, etapă n care se sta0ilesc o0iecti*ele simulării7- ntre0ările la care tre0uie să răspundă, care tre0uie să %ie clare- ipote!ele ce tre0uiesc testate, care tre0uie să %ie nsoţite de criterii de

acceptare- e%ectele ce urmea!ă a %i estimate.

2. 2olecţionarea, analia, inter*retarea 0i *relucrarea *rimară a datelor

Cn această etapă se sta0ilesc7

- datele de o0ser*aţie necesare pentru studierea sistemului considerat- modalităţile de str-n'ere a datelor de o0ser*aţie.

+ceastă etapă este esenţială deoarece colecţionarea unor date eronate are mariconsecinţe n o0ţinerea re!ultatelor %inale, moti* pentru care este necesară o anali!ă

preliminară /i o interpretare a lor pentru a depista e*entualele neconcordanţe curealitatea. Se e%ectuea!ă o prelucrare primară, apoi se %ace con*ersia /i transmiterealor, n *ederea or'ani!ării n %i/iere pentru a putea %i utili!ate de calculator. Datele deo0ser*aţie sunt necesare pentru estimarea parametrilor caracteristicilor operati*e alemodelului ce *a %i construit, iniţiali!area *aria0ilelor de intrare ale modelului /i*alidarea lui.

13


16/123

3. 3ormularea modelului de simulare

&entru a construi un model matematic de simulare a unui sistem, componentelor saleli se asocia!ă anumite *aria0ile /i parametri, unele dintre acestea %iind7- cunoscute Econtrola0ileF numite *aria0ile sau parametri de intrare

- necunoscute Enecontrola0ileF numite *aria0ile sau parametri de ie/ire.=nteracţiunile dintre componentele sistemului sau le'ăturile sistemului cu eBteriorul sere'ăsesc n modelul matematic su0 %orma unor relaţii %uncţionale. &rintre relaţiilemodelului eBistă una sau mai multe %uncţii care lea'ă di%erite *aria0ile /i care măsoară

per%ormanţa sistemului. Deoarece n e*oluţia lor sistemele reale sunt in%luenţate de%actori aleatori al căror e%ect este pus n e*idenţă n cadrul modelului de simulare, o

parte din *aria0ilele de intrare ale modelului sunt *aria0ile aleatoare a*-nd %uncţii derepartiţie cunoscute. De aici apare necesitatea ca modelul de simulare să conţină rutinecare să 'enere!e aceste *aria0ile de intrare.

Modelul de simulare tre0uie să conţină7- *aria0ile care să descrie stările componentelor sistemului E*aria0ile de stareF- o a'endă care să memore!e e*enimentele care se produc n sistem- rutine pentru producerea E'enerareaF di%eritelor tipuri de e*enimente.

"onstruirea unui model de simulare di%eră de la o pro0lemă la alta, moti* pentru care nu pot %i sta0ilite ni/te re'uli 'eneral *ala0ile. "u toate acestea se potindica c-te*a re'uli de care tre0uie să se ţină seama n construirea modelului desimulare. na dintre acestea se re%eră la numărul de *aria0ile pe care le %olose/temodelul un număr prea mare ar crea di%icultăţi n ceea ce pri*e/te sta0ilirea relaţiilor %uncţionale, ar %ace ca modelul să %ie mai puţin %leBi0il, iar timpul de calcul ar %i maimare. $u tre0uie să se a)un'ă nici la cealaltă eBtremă a simpli%icării eBa'erate amodelului prin %olosirea unui număr mic de *aria0ile, deoarece n acest ca! ar putea

pierde o parte din aspectele esenţiale ale pro0lemei. elaţiile %uncţionale alemodelului tre0uie să ai0ă o %ormă c-t mai simplă, %iind u/or de calculat /i e*aluat na/a %el nc-t erorile de calcul induse să %ie c-t mai mici, asi'ur-nd n acest %el o c-tmai 0ună preci!ie a modelului.

De mare importanţă n reali!area modelelor de simulare este o0ţinerea unuitimp de calcul redus, %apt ce permite simularea di%eritelor *ariante de sistem cu costuriEe%orturiF re!ona0ile.

altă cerinţă de care tre0uie să se ţină seama la construirea modelelor de

simulare se re%eră la mi)loacele prin care poate %i *eri%icată corectitudinea modelului/i *ariantele ce urmea!ă a %i simulate cu a)utorul calculatorului electronic.

4. 4stimarea *arametrilor de intrare ai modelului

&arametrii de intrare ai modelului matematic de simulare se estimea!ă prin metodestatistice, %olosind datele colecţionate En prima etapăF despre sistemul real."aracteristicile operati*e pot a*ea %orma unor ecuaţii sau sisteme de ecuaţii depin!-ndde anumiţi parametri care pot %i estimaţi cu a)utorul tenicilor speci%ice anali!eire'resiei.

14


17/123

5. 4valuarea *erformanţelor modelului 0i testarea *arametrilor

+ceastă etapă are ca scop *eri%icarea modelului nainte ca el să %ie pro'ramat7- se *eri%ică dacă parametrii de intrare ai modelului au %ost 0ine estimaţi, %olosind

teste statistice

- se *eri%ică dacă modelul conţine toate *aria0ilele /i parametrii esenţiali precum /irelaţiile %uncţionale necesare repre!entării interdependenţelor esenţiale alesistemului real.

Cn ca!ul c-nd caracteristicile operati*e iau %orma unor ipote!e statisticere%eritoare la repartiţiile *aria0ilelor de intrare, atunci se aplică testele de concordanţă

Etestul ℵ 2, olmo'oro*:Smirno*F pentru *eri%icarea acestor ipote!e.Dacă n urma acestor *eri%icări se constată că o ntre0are sau o ipote!ă nu este

corect %ormulată, nseamnă că %ie *aria0ilele /i parametrii nu au %ost 0ine ale/i, %ie parametrii de intrare nu au %ost 0ine estimaţi. Dacă pe l-n'ă acestea se constată /i alteneconcordanţe n cadrul modelului, atunci toate etapele precedente *or %i reluate n*ederea corectării lor.

6. 1escrierea aloritmului de simulare 0i scrierea *roramului de calcul

&e 0a!a re!ultatelor etapelor precedente se construie/te al'oritmul de calcul carerepre!intă succesiunea lo'ică a e*enimentelor ce urmea!ă a %i reproduse cucalculatorul electronic. &entru a %i mai u/or de pro'ramat, al'oritmul este repre!entat

printr:o scemă lo'ică urmea!ă scrierea pro'ramului care se poate %ace %ie %olosindun lim0a) de pro'ramare de ni*el nalt7 " ", %ie un lim0a) special de simulare, de

eBemplu G&SS.+le'erea lim0a)ului de pro'ramare depinde de mai mulţi %actori, dintre care

amintim7 timpul de calcul necesar simulării, %orma su0 care tre0uie imprimatere!ultatele simulării, eBperienţa ca pro'ramator etc.

im0a)ele de simulare Especiali!ateF %ac mult mai u/oară descrierea unuisistem /i a comportării lui n timp. le pot u/ura mult modelarea, ceea ce %ace să %ienet superioare din acest punct de *edere lim0a)elor 'enerale de pro'ramare.

. $alidarea modelului

>alidarea modelului, adică sta0ilirea adec*ării lui la realitate, este de o0icei o sarcinăcompleBă /i di%icilă. >aloarea unui model n raport cu contri0uţia sa la studiul situaţieiconcrete modelate este determinată de 'radul său de adec*are, adică de modul n care

predicţiile concordă cu o0ser*aţiile.Metodele de *alidare a modelelor matematice de simulare nu sunt unice.

>alidarea modelului se poate %ace prin7- testarea modelului ntr:un ca! particular, n care soluţia se cunoa/te sau poate %i

dedusă cu u/urinţa pe cale analitică- compararea re!ultatelor simulării cu datele o0ţinute prin o0ser*area unor sisteme

similare sau prin comparaţie cu e*oluţia trecută a sistemului real care a %ostsimulat.

15


18/123

>ariantele modelului care se do*edesc neadec*ate sunt modi%icate p-nă se

a)un'e la soluţii care concordă cu realitatea.

#. +lanificarea ex*erienţelor de simulare

Cn această etapă se %ace atri0uirea *aria0ilelor /i parametrilor de intrare a *alorilor care să acopere situaţiile reale n care s:ar putea a%la sistemul n *ederea selectării*ariantei care satis%ace cerinţele utili!atorului.

9. 5nalia datelor simulate

e!ultatele simulării ne pre!intă care este @reacţia; sistemului la modi%icarea *alorilor *aria0ilelor de intrare /i mai mult, n ele *om căuta răspunsurile la ntre0ările%ormulate la nceput. +cest lucru este posi0il colecţion-nd datele simulate,

prelucr-ndu:le calcul-nd statisticile pentru testele de semni%icaţie /i apoi interpret-nd

doar re!ultatele.

1$2$2 Cea#" i#"ării

&rin intermediul modelului de simulare calculatorul electronic producesuccesi* di%erite e*enimente care repre!intă scim0ările ce au loc n timp n cadrulsistemului. &entru a putea menţine ordinea corectă a acestor e*enimente /i pentru

putea preci!a, după %iecare pas al simulării care este inter*alul de timp n care s:a

simulat e*oluţia sistemului la pasul respecti*, este necesar să se introducă n modelulde simulare o *aria0ilă specială numită ceas. a %iecare pas al simulării tre0uie să se'enere!e o @cre/tere; a ceasului care să se adau'e mărimii ceasului la pasul anterior.

Bistă două tipuri de ceas7· ceas cu cre/tere %iBă EconstantăF· ceas cu cre/tere *aria0ilă.

Simularea 0a!ată pe metoda ceasului constant, constă n a 'enera de %iecaredată o cre/tere constantă c a ceasului /i a anali!a apoi starea di%eritelor elemente ale

sistemului 'ener-nd toate e*enimentele posi0ile a se produce n inter*alul de timp delun'ime c. După aceea se *a 'enera o nouă cre/tere care se *a adău'a ceasului /i se *arepeta anali!a menţionată.

Scema lo'ică a modelului de simulare tre0uie n acest ca! să descrie n modcomplet e*oluţia sistemului pe un inter*al de timp de lun'ime c simularea sistemului

pe un inter*al mare EoarecareF de timp se *a o0ţine repet-nd de un număr de orisu%icient de mare al'oritmul re%eritor la inter*alul de timp de lun'ime c. Deci pentrumodelele de simulare cu ceas constant mărimea ceasului ! este de %orma7

! c67 E 7(,1,2,/Funde 7 este un ntre' care repre!intă numărul de iteraţii ale al'oritmului de simulare.

16


19/123

Cn ca!ul ceasului *aria0il, *aloarea E*aria0ilăF a cre/terii ceasului este e'ală culun'imea inter*alului de timp dintre apariţiile a două e*enimente consecuti*e. "u altecu*inte, mărimea cre/terii ceasului este e'ală cu inter*alul de timp de la starea actualăla momentul apariţiei celui mai apropiat e*eniment *iitor.

Cn ca!ul modelului cu ceas constant, a*em7

e1 e2 e3 e4 T

T1 T2 T3

Cn ca!ul modelului cu ceas *aria0il, a*em7

e1 e2e3e4 T

T1 T2 T3 T4

Metoda ceasului *aria0il presupune n mod ri'uros considerarea ordinii tuturor apariţiilor de e*enimente succesi*e, ast%el nc-t la %iecare nouă apariţie corespunde ocre/tere a ceasului.

Cn ca!ul modelelor cu ceas constant, dacă de eBemplu *aloarea ceasului la unmoment dat este ! c6k , atunci n această %a!ă al'oritmul de simulare *a 'enerae*enimentele care urmea!ă să se producă n inter*alul de timp L c6Ek :1F, c6k F /i dupăaceea *a a*ansa ceasul la *aloarea ! c6Ek81F.

n model de simulare 0a!at pe metoda ceasului constant consideră 'rupul dee*enimente produse n inter*alul Lc6Ek :1F, c6k F ca /i cum s:ar %i produs la momentul ck .

Cn consecinţă, procedeul 0a!at pe metoda ceasului constant, spre deose0ire de

cel 0a!at pe ceas *aria0il, %ace ca 'rupul de e*enimente care apar pe un inter*al detimp de lun'ime c să %ie sincroni!ate la momentul terminării acelui inter*al. Din acestmoti* este recomanda0il să se alea'ă constanta c c-t mai mică. +ceasta *a conduce lacre/terea timpului de calcul. &e de altă parte, mărirea constantei c datorită sincroni!ăriiunor e*enimente ce se petrec la momente de timp ndepărtate, *a mări 'radul deaproBimaţie al modelului /i *a reduce timpul de calcul.

Metoda 0a!ată pe ceasul constant este de pre%erat celei 0a!ată pe ceasul cucre/tere *aria0ilă, mai ales din punctul de *edere al u/urinţei cu care se poate construial'oritmul simulării.

1


20/123

CAPITOLUL II

SIMULAREA NUMERELOR ALEATOARE

2$1 N#ere a"ea!oare #)ifore$ Pro5eee e ge)erare$

$umerele care sunt @alese la înt9m*lare; numite )#ere a"ea!oare seutili!ea!ă7- n aplicaţii n care reali!ea!ă nlocuirea *alorilor *aria0ilei aleatoare cu o mulţime

de *alori care au proprietăţile statistice ale acesteia- n simularea numerică pentru a reproduce n mod realist anumite elemente ale

sistemului simulat, precum /i pentru re!ol*area unor pro0leme numerice cua)utorul metodelor Monte "arlo

- n cercetarea statistică pentru a produce selecţii nt-mplătoare n cadrul unei populaţii statistice, selecţii cărora li se pot aplica, apoi procedee de prelucrare /iinterpretare speci%ice statisticii matematice

- n testarea pro'ramelor pe calculator.

Se nume/te şir de numere aleatoare independente cu o repartiţie de pro0a0ilitate speci%icată, /irul care ndepline/te condiţiile7- numerele /irului au %ost o0ţinute la nt-mplare- %iecare număr nu este n nici un %el le'at de celelalte numere ale /irului- are o anumită proprietate de a se a%la ntr:un anumit inter*al.

n /ir de numere aleatoare independente cu o repartiţie speci%icată este oselecţie nt-mplătoare e%ectuată asupra unei *aria0ile aleatoare a cărei repartiţie estecea speci%icată.

Dacă ntr:un /ir de numere putem pre*edea unul din termenii /irului n %uncţiede termenii precedenţi atunci /irul nu este aleator. Cn cadrul /irurilor de numerealeatoare de lun'ime %oarte mare este posi0il ca unele numere să se repete, dar elendeplinesc anumite cerinţe care le apropie de cele nt-mplătoare ele se numesc

numere pseudo-aleatoare.

Bistă mai multe procedee de a produce numere nt-mplătoare /i anume7

1. !abele cu numere înt9m*lătoare, care conţin numere ntre'i uni%orm

reparti!ate pe un inter*al.

2. +rocedee fiice, %iind construite ma/ini sau dispo!iti*e %i!ice pentru producerea de numere nt-mplătoare. le se 0a!ea!ă pe principii %i!ice,%olosind de eBemplu !'omotul electronic sau radioacti*. &rocedeul radioacti*constă dintr:un detector de particule radioacti*e care nre'istrea!ă ntr:o

perioadă de timp Ut un număr par sau impar de particule emise de sursă.

1#


21/123

n alt procedeu %i!ic este cel al intensităţii unui curent măsurat la momente

distincte ast%el nc-t *alorile *olta)elor # Et 1F, # Et 2F,V, # Et nF,V să poată %iconsiderate ca independente. Cn ca!ul n care un ast%el de dispo!iti* se%olose/te pentru 'enerarea de numere aleatoare cu o anumită repartiţie,dispo!iti*ul este conectat la calculator ast%el nc-t el să poată produce numerealeatoare la ne*oie.

:. +rocedee aritmetice

&entru 'enerarea numerelor aleatoare cu a)utorul calculatoarelor electronicenumerice se %olosesc relaţii de recurenţă de %orma7

" n1 f E " n, " n:1,V, " n-mF,

nWm, mX(, unde E " n Fn∈ ; , sunt numere naturale, presupun-ndu:se că*ectorul *alorilor iniţiale " (, " 1,V, " m este dinainte %iBat.

n procedeu aritmetic de o0ţinere a numerelor aleatoare 0a!at pe o relaţie de

recurenţă de %orma de mai sus se nume/te enerator. Yin-nd seama de %aptul cănumerele 'enerate n acest mod ele nu sunt nt-mplătoare, dar pentru anumite ale'eriale lui f se pot o0ţine numere cu proprietăţi statistice apropiate de cele nt-mplătoare,un asemenea 'enerator *a produce numere *seudo-aleatoare sau cvasi-aleatoare.

&entru ca un procedeu aritmetic să poată %i numit generator de numere

pseudo-aleatoare, tre0uie să ndeplinească următoarele condiţii7

1. Generatorul tre0uie să %ie sim*lu 0i ra*id , ceea ce nseamnă că el tre0uie să %ie

u/or de pro'ramat, să ocupe memorie puţină /i să solicite timp de calcul redus.

2. Generatorul tre0uie să producă /iruri de numere de lun'ime oric-t de mare,%ără ca numerele /irului să se repete. +ceasta ar nsemna să nu producă /iruricu perioadă %inită. Yin-nd seama că mărimea cu*-ntului unui calculator estelimitată, ceea ce nseamnă că orice calculator poate lucra numai cu numerentre'i mai mici dec-t un număr dat, re!ultă că nu putem construi 'eneratori cu

perioadă in%inită. De aceea, cerinţa ca un 'enerator să producă /iruri oric-t delun'i de numere se reduce la %aptul că 'eneratorul tre0uie să ai0ă *erioadă c9t mai mare *osibilă.

3. Generatorul tre0uie să *roducă numere inde*endente stocastic unul %aţă de

altul. &ractic acest lucru nu este reali!a0il cu calculatorul, dar un 'enerator esteacceptat dacă produce numere care sunt %oarte puţin dependente stocastic sau%oarte puţin corelate. Gradul de independenţă stocastică se *eri%ică cu a)utorultestelor statistice.

4. Generatorul tre0uie să producă numere a căror re*artiţie să %ie uniformă, ceea

ce se poate *eri%ica cu a)utorul testelor de concordanţă Etestul ℵ2 , testul

olmo'oro* etc.F.

Datorită simplităţii lor, 'eneratorii cel mai %rec*ent utili!aţi sunt aceia care

produc numere pseudo:aleatoare ntre'i.

19


22/123

=deea %olosirii procedeelor aritmetice pentru 'enerarea al'oritmică de numerecare au calităţi apropiate de cele nt-mplătoare aparţine lui ?on *on $eumann. l a

propus o metodă particulară cunoscută su0 numele de metoda *ărţii de la mi7locul *ătratului.

2$2 Si#"area )#ere"or a"ea!oare #)ifore

ie HZ, [, + K un c-mp de pro0a0ilitate /i " 7 Z \ R o *aria0ilă aleatoare.ie 3 7 R \ L(,1, 3 E xF + E " R xF H + H] " E]FR xKK. + 'enera cu calculatorul

o *aria0ilă aleatoare nseamnă a ale'e un număr de e*enimente elementare ]1, ]2, V,]n /i a determina *alorile " i " E]iF ale *aria0ilei aleatoare.

>alorile " 1, ..., " n repre!intă o selecţie asupra *aria0ilei aleatoare " . 'enerare este un al'oritm care este capa0il să producă un " i, /i iter-nd acel

al'oritm el să %ie n stare să producă " (, " 1, ..., " n ast%el ca ele să %ie independente

stocastic /i identic reparti!ate.>aria0ilele " 1, " 2, ..., " n sunt inde*endente stochastic dacă^

n

3 E x1, x2,V, xnF ∏ 3 i ( xi ), i=1

unde

3 E x1, x2,V, xnF + E " 1R x1, " 2R x2,V, " nR xnF.>aria0ilele " 1, " 2, ..., " n sunt identic re*artiate dacă toate au aceea/i

repartiţie 3 iE xF 3 7E xF, pentru i k = 1 Eb − aF−∞ a

/i o %uncţie de repartiţie uni%ormă7

2

0


23/123

(, x ≤ a 3 ( x)=

( x − a) (b − a), a


24/123

+ro*oiţie7 Dacă " ∈R 2 este *ector uni%orm pe un inter*al = La, b `Lc, d , " E " 1, " 2F, atunci " 1 este uni%orm pe La, b /i " 2 este uni%orm pe Lc, d , iar " 1 esteindependent de " 2.

1emonstraţie7

uncţia de repartiţie a lui " este7 ( x1 ≤ a, x2 ≤ c

3 ( x , x 2 ) = ( x − a)( x 2 − c) (b − a)(d − c) ( x , x 2)∈ = 1 1 1

1 x1 ≥ b, x2 ≥ d iar

3 1( x1 ) = 3 ( x1, ∞) este %uncţie de repartiţie uni%ormă pe La, b, 3 2( x2 ) = 3 ( x2 , ∞) este %uncţie de repartiţie uni%ormă pe Lc, d .

+tunci7

f 1( x1 ) = 1 (b − a), x1 ∈ [a, b] f 2 ( x2 ) = 1 (d − c), x2 ∈ [c, d] f ( x1, x2 ) = 1 (b − a)(d − c)

+ceastă proprietate arată că dacă *rem să o0ţinem puncte uni%orme n

domeniu, putem 'enera puncte uni%orme pe componente.

d

=

c

a b

>bservaţie7 &ropo!iţia este ade*ărată numai pe inter*ale /i nu pe domeniioarecare.

"onstruirea unui 'enerator de numere aleatoare este destul de di%icilă, pe de o parte datorită periodicităţii mari, iar pe de altă parte datorită cerinţelor statistice deindependenţă stocastică /i uni%ormitate.

nut, 0a!-ndu:se pe procedeul lui ?on *on $eumann /i pe alte operaţiinumerice care n mod intuiti* a*eau caracter aleatoriu, a construit un 'enerator de

numere super:aleatoare, pe care c-nd l:a utili!at a constatat n mod surprin!ător căreproduce un anumit număr.

"onclu!ia lui nut a %ost că 'eneratoarele de numere aleatoare nu tre0uieconstruite prin metode intuiti*e, ele tre0uie să ai0ă la 0a!ă teorii matematiceri'uroase.

Cn 'eneral, producerea de numere aleatoare se 0a!ea!ă pe metode recurente, iar cele care au %ost ri'uros studiate /i au produs re!ultate 0une sunt metodelecon'ruenţiale. le au %ost iniţiate de emer.

22


25/123

2$2$1 Me!oa ă!ra!#"#i i) i7"o5

Să presupunem că %olosim o repre!entare n 0a!a b a numerelor ntre'i cu carelucrăm, care de o0icei este 2 sau 1(.

&resupunem că toate aceste numere au 2a ci%re, a 1, 2, .... Cn ca! contrar, secompletea!ă n %aţa numărului cu !erouri.

" n7 n 0a!a b, cu 2a ci%re E ( ≤ " n ≤ b2a

Fa a

" n2 7

a a a a

" n+1

iind dat numărul aleator ntre' " n, următorul număr pseudo:aleator " n1 se

de%ine/te după *on $eumann ca %iind %ormat din ci%rele părţii din mi)loc a pătratuluilui " n. +st%el, ridic-nd pe " n la pătrat se o0ţine un număr cu 4a ci%re lu-nd cele 2a

ci%re de la mi)locul /irului de 4a ci%re ale lui " n2 se o0ţine numărul " n1. +cest

procedeu poate %i eBprimat prin relaţia de recurenţă7

" n +1

" n

2 " n2 ×b

2a

= − ba b3a

+ceastă metodă s:a do*edit a %i o sursă sla0ă de numere pseudo:aleatoare

deoarece anumite numere se repetă.De eBemplu pentru a2 /i b1(, numărul 3922 se repetă deoarece 3922

1439264.

2$2$2 Me!oe 5o)gr#e)ţia"e

+ceste metode constau n a determina numărul " n1 din " n pe 0a!a relaţiei

con'ruenţiale de recurenţă7

" n+1 = (a" n + c)mod M , n = (, 1, 2.K

unde a, c, M sunt ntre'i nene'ati*i.&entru o0ţinerea unui /ir de numere ntre'i pseudo:aleatoare este necesar să

se alea'ă de la nceput n mod con*ena0il numerele " (, a, c, M . $umărul ntre'

po!iti* " ( este termenul iniţial al /irului de numere pseudo:aleatoare. +cest 'enerator se mai nume/te enerator mixt-conruenţial , deoarece parante!a din mem0rul dreptconţine o nmulţire /i o adunare.

23


26/123

Se pune pro0lema ale'erii constantelor a /i c care dau o perioadă maBimă,urm-nd ca din clasa 'eneratorilor respecti*i să ale'em pe aceia care produc numere

pseudo:aleatoare de 0ună calitate din punct de *edere statistic.

!eoremă7 Pirul de numere de%init de relaţia con'ruenţială liniară are o perioadă

maBimă de mărime M dacă /i numai dacă71. c este prim cu M 2. b a:1 este multiplu de *, pentru orice di*i!or prim al lui M 3. b este un multiplu de 4 dacă M este un multiplu de 4.

De eBemplu, se pot ale'e7 M 235, a 223 214 22 1, c 1, " ( (, a

3141592621.

?eneratorul multi*licativ - conruenţial de *erioadă maximă

+cest 'enerator se o0ţine din cel miBt A con'ruenţial, lu-nd c

(7 " n+1 = a" n Emod M F+cest 'enerator nu poate a*ea perioada de lun'ime maBimă, ceea ce:l %ace mai puţinutili!at dec-t precedentul.

&entru calculatoare cu lun'imea cu*-ntului de 32 0iţi, se poate lua M 231 A 1 cel

mai mare număr ntre' repre!enta0il pe un cu*-nt de memorie, iar a 5 16#(.

24


27/123

CAPITOLUL III

SIMULAREA &ARIABILELOR ALEATOARE

ie 2 o %amilie de *aria0ile aleatoare pentru care se cunosc al'oritmi de'enerare. Se pune pro0lema să determinăm un al'oritm ! care să trans%orme omulţime de *aria0ile aleatoare 2 ∈C ntr:o mulţime de *aria0ile aleatoare " , " ! E2 1, 2 2, ..., 2 nF.

"u alte cu*inte, pornind de la o %amilie de *aria0ile aleatoare pentru carecunoa/tem al'oritmi e%icienţi de 'enerare din punct de *edere al calcula0ilităţii, sădeterminăm al'oritmul care 'enerea!ă *aria0ile aleatoare mai di%icil de 'enerat.

&entru 'enerarea *aria0ilelor aleatoare se utili!ea!ă următoarele metode71. Metoda in*ersă2. Metoda respin'erii3. Metoda compunerii EamestecăriiF4. +lte metode de 'enerare a *aria0ilelor aleatoare5. Metode particulare de 'enerare a *aria0ilelor aleatoare

3$1 Me!oa i)8eră

@ema lui Aincin-Smirnov7 Dacă " este o *aria0ilă aleatoare oarecare a*-nd%uncţia de repartiţie 3 E xF, iar # este un număr aleator uni%orm pe E(,1F, atunci

*aria0ila aleatoare % = 3 −1

(# ) are %uncţia de repartiţie 3 E xF. 1emonstraţie. ie " o *aria0ilă aleatoare a*-nd %uncţia de repartiţie E xF. +tunci7

3 E xF = + (%


28/123

2. Metoda in*ersă poate induce multe erori de calcul datorită pre!enţei unor %uncţii ca ln, ex* etc. care se calculea!ă după *alori aproBimati*e.

3. Cn multe ca!uri %uncţia de repartiţie nu poate %i in*ersată /i atunci seapelea!ă la metode numerice care de asemenea pot induce erori de calcul.

Metoda in*ersă poate %i aplicată pentru simularea *aria0ilelor aleatoare de tipcontinu, discret /i a *ectorilor aleatori.

&resupunem că dispunem de un 'enerator de numere aleatoare R andomNum0ers Generation E$GF pentru 'enerarea de numere aleatoare uni%orme pe E(,1F/i independente stocastic. Cn aceste condiţii, al'oritmul de simulare a unei *alori deselecţie a unei *aria0ile aleatoare pentru care se cunoa/te %uncţia de repartiţie 3 E " F, seo0ţine aplic-nd lema bincin:Smirno* pentru ca!ul discret /i continuu.

Si#"area 8aria.i"e"or a"ea!oare e !i i5re! x x 2 K x n

1 n ÷ , (


29/123

Si#"area 8aria.i"e"or a"ea!oare e !i 5o)!i)##

5loritm de simulare a unei variabile aleatoare continue7

(. =niţiali!are $G.

=ntrare parametri.=niţiali!area in*ersării %uncţiei 3 E " F.

1. Se 'enerea!ă cu $G un număr aleator # uni%orm pe E(, 1F.

2. =e/ire " = 3 −1(# ).

&entru o0ţinerea *alorilor de selecţie ale unei *aria0ile aleatoare se reiterea!ă

acest al'oritm.

&entru *eri%icarea al'oritmului se poate aplica cel mai simplu test care constă

n calculul mediei /i dispersiei de selecţie. >eri%icarea se %ace pentru un *olum de'enerări nW1(((, ceea ce nseamnă reiterarea acestui al'oritm se %ace de cel puţin de1((( de ori. Se calculea!ă7

1 n: media de selecţie = ∑ " im

ni=1

∑n ( " i −: dispersia de selecţie = 1 )2 s 2 mn −1

i =1

unde " 1, " 2, ..., " n sunt n *alori o0ţinute prin reiterarea al'oritmului.Se compară aceste *alori cu media /i dispersia teortetice /i cu c-t erorile sunt

mai mici, re!ultă că al'oritmul este mai 0un.+l'oritmul mai poate %i *eri%icat aplic-nd testul ℵ2 sau testul olmo'oro*.

Me!oa i)8eră e)!r# o"#ţii )#eri5e

Metoda in*ersă poate %i aplicată /i n ca!ul c-nd nu putem calcula eBplicitin*ersa %uncţiei 3 . Cn aceste ca!uri, tre0uie re!ol*ată ecuaţia 3 E " F # numeric, ceeace cere un *olum mult mai mare de timp c-nd 3 este continuă. Desi'ur că aceastaconduce la un al'oritm care are o preci!ie scă!ută.

Cn cele ce urmea!ă " este necunoscută, %iind soluţia eBactă a ecuaţiei 3 E " F

# , iar " C este *aloarea o0ţinută prin al'oritmul de calcul al in*ersei.

"ondiţia de oprire a al'oritmului N " : " CN R D pentru un D W ( mic, n anumitesituaţii este este posi0il să nu ne satis%acă deoarece pentru *alori mai mari ale lui " aceasta ar putea să implice ca numărul de ci%re semni%icati*e cerut să depă/eascăcu*-ntul calculatorului.

a doua condiţie de oprire poate %i dată prin N 3 E " F − 3 E " F NR , unde

W( este un număr mic.

2


30/123

"ei mai cunoscuţi al'oritmi numerici pentru calculul in*ersei 3 E " F # sunt7

Metoda bisecţiei7

=ntrare7 un inter*al Ea, bF care să conţină soluţia7

repetă " Ea bF 2dacă 3 E " F O #

atunci a " alt%el b "

p-nă c-nd b A a R 2D.=e/ire7 " .

Metoda secantei7

=ntrare7 un inter*al Ea, bF care să conţină soluţia7repetă

" ¬ a + Eb − aF # − 3 EaF 3 EbF − 3 EaF

dacă 3 E " F O # atunci a " alt%el b "

p-nă c-nd b A a R D.=e/ire7 " .

Metoda lui ;eEton-Fa*hson7

=ntrare7 o *aloare iniţială pentru " .repetă

¬ − 3 E " F −#

" " f E " F

p-nă c-nd condiţia de oprire estesatis%acută. =e/ire7 " .

>bservaţie. &entru primele două metode a*em ne*oie de un inter*al Ea, bF caresă conţină soluţia. Metoda lui $efton A apson con*er'e dacă este con*eBă sauconca*ă.

2#


31/123

3$2 Me!oa rei)gerii

ie " o *aria0ilă aleatoare a cărei 'enerare dorim să o simulăm, cu condiţia să:

i putem asocia următoarele elemente7· S HS 1, S 2, V, S n, VK o %amilie de *aria0ile aleatoare pe care /tim să le

'enerăm.

· ; o *aria0ilă aleatoare discretă, ; ∈ N, + E ; < ∞F = 1, pe care /tim, deasemenea să o 'enerăm.

· + o proprietate E*aria0ilă lo'ică ce poate lua două *alori F ce se poate *eri%ica prin calcul.

· g o %uncţie măsura0ilă, g 9 R n → R .

1efiniţie . Dacă unei *aria0ile aleatoare " i se poate asocia un sistem de patru elemente

HS , ; , + , gK,

ast%el nc-t pentru orice n∈N + , %iind date S 1, S 2, V, S n, V∈ S , care satis%ac proprietatea + , *aria0ila aleatoare g ES 1, S 2, V, S nF are aceea/i %uncţie de repartiţie cu " , atunci am de%init un *rocedeu de res*inere pentru 'enerarea lui " .

5loritm de enerare (metoda res*inerii)7

(. =niţiali!ări+l'oritmul pentru 'enerarea lui ; .+l'oritmul pentru 'enerarea lui S 1, S 2, V,S n. +l'oritmul pentru *eri%icarea proprietăţii

+ . +l'oritmul pentru calculul lui g.1. Generea!ă o *aloare de selecţie n ∈ N-.2. Generea!ă S 1, S 2, V, S n .3. Dacă S 1, S 2, V, S n nu satis%ac proprietatea + Erespin'ereF

trans%er la 1.4. "alculea!ă " g ES 1, S 2, V, S nF E*aloarea 'eneratăF.

>bservaţii.1. +l'oritmul se nume/te de respin'ere deoarece n &asul 3 se decide dacă

are loc o respin'ere sau o acceptare.

2. $otăm cu *a pro0a0ilitatea de acceptare /i cu *r pro0a0ilitatea derespin'ere al'oritmul este per%ormant dacă *a este mare, iar *r este mică.

3. ; poate %i o *aria0ilă aleatoare sau o constantă.4. amilia S tre0uie să /tim să o 'enerăm simplu /i rapid.5. &roprietatea + tre0uie să %ie u/or de *eri%icat.6. uncţia g să %ie simplă /i u/or de e*aluat.

29


32/123

@ema 1 E Prima lemă de respingereF$

ie : un *ector aleator a cărui densitate de repartiţie este f E*F, *∈R k /i pe care*rem să:l 'enerăm.

ie ; un *ector aleator a cărui densitate de repartiţie este hE


33/123

3(


34/123

3$3 Me!oa 5o#)erii

ie " o *aria0ilă aleatoare a cărei %uncţie de repartiţie este 3 E xF de %orma7m

3 E xF = ∑ *i?i E xF , i =1unde

( R *i R 1, E ∀ F 1 O i O m, cu mW1 m

å *i = 1i=1

unde ?iE xF sunt %uncţii de repartiţie. Se spune n acest ca! că 3 E xF este amestecarea%amiliei H?1 ,?2 ,.....,?m K de %uncţii de repartiţie după *aria0ila aleatoare discretă ;

pentru care + E ; = iF = *i ,1 ≤ i ≤ m sunt cunoscute.

Se o0ser*ă că %uncţiile de repartiţie H? ; E xFK,1 ≤ ; ≤ m , depind de indicelealeator ; , iar 3 E xF este media n raport cu ; a *aria0ilelor aleatoare H? ; E xFK.

Dacă notăm cu I ; *aria0ila aleatoare care are %uncţia de repartiţie H? ; E xFK ,

atunci " = I i cu pro0a0ilitatea *i = + E ; = iF.

>bservaţie7 Dacă 3 E xF /i ?iE xF au densităţile de repartiţie f E xF /i respecti* iE xF,

atuncim

f E xF = ∑ *i i E xFi=1

Pro5ee#" e ae!e5are i5re!ă

Dacă eBistă un al'oritm pentru 'enerarea *aria0ilelor I ; , 1 O ; O m, , atunci

al'oritmul de 'enerarea *aria0ilei aleatoare " se pre!intă ast%el7

5loritm J de enerare *rin amestecare discretă7


=niţiali!area al'oritmului pentru 'enerarea unei *aria0ile din %amilia H I ; K.i

=ntrare ?i = ∑ *α ,1 ≤ i ≤ mα =1

7 (1. Se 'enerea!ă un număr # uni%orm pe E(,1F.2. 7 7 1

3. Dacă # R ? 7 trans%er la 2.4. =e/ire " I 7.

sau

31


35/123

5loritm B de enerare *rin amestecare discretă7

(. =niţiali!ări.1. Se 'enerea!ă un indice aleator Eo *aria0ilă aleatoare discretăF.

1 2 ... m

* ... *÷

i → = 7 * 2 ÷ 1 m 2. =e/ire " I i.

4xem*lu7a un ser*ice sosesc pentru *eri%icare periodică automo0ile de k tipuri7

1 2 ... i ... k * ... * ... * ÷ K 7

*

2 i ÷ 1 k

unde *i , 1 ≤ i ≤ k repre!intă procentul de

ma/ini de tipul i. Durata I i , 1 ≤ i ≤ k

dintre două sosiri de acela/i tip este o *aria0ilă aleatoare eBponenţială ne'ati*ă de

parametru λ i , 1 ≤ i ≤ k . =nter*alul de timp " dintre două sosiri oarecare are ca %uncţie

de repartiţie amestecarea %uncţiilor de de repartiţie ?i E xF = 1− e−λ i

x , x > (,1 ≤ i ≤ k ,

ceea ce nseamnă că %uncţia de repartiţie a lui " este dată dek

3 E xF = ∑ *i E1− e−λ i x Fi

=1

5loritm de enerare *rin amestecare7

(. =niţiali!ea!ă $G.

=ntrare λ i , 1 ≤ i ≤ k i

=ntrare ?i = ∑ *α ,1 ≤ i ≤ k α =1

7 (1. Se 'enerea!ă # cu $G.

2. 7 7 13. Dacă # R ? 7 trans%er la pasul 2.4. Se 'enerea!ă un nou # cu $G.

3. =e/ire " = − 1

ln# . λ 7

32


36/123

Pro5ee#" e ae!e5are 5o)!i)#ă

uncţia de repartiţie 3 E xF constituie compunerea unei %amilii de %uncţii de

repartiţie H?E x, F, ∈R Kdupă %uncţia de repartiţie A E F, de %orma7+∞

3 E xF = ∫ ?E x, FdA E F−∞Se o0ser*ă că 3 E xF este *aloarea medie a %uncţiei de repartiţie ?E x,% F, unde % este un

parametru aleator care are %uncţia de repartiţie A E F.Cn acest ca!, al'oritmul de 'enerare a *aria0ilei aleatoare " c-nd se cunosc

al'oritmi de 'enerare pentru % Ea*-nd %uncţia de repartiţie A E FF /i pentru I Ecu%uncţia de repartiţie ?E x,% FF se pre!intă ast%el7

5loritm de enerare *rin amestecare continuă7

(. =niţiali!are $G.=niţiali!area al'oritmului pentru 'enerarea lui % .=niţiali!area al'oritmului pentru 'enerarea lui I .

1. Se 'enerea!ă % .

2. Se 'enerea!ă I .3. =e/ire " I .

4xem*lu7 ie ?E x, λ F = 1 − e−λ x

, x > (, λ > ( unde L este un parametru aleator

care are repartiţie eBponenţială A Eλ F = 1 − e− µλ , µ > ( . +plic-nd procedeul deamestecare continuă, %uncţia de repartiţie 3 E xF se o0ţine ast%el7

3 E xF = ∞∫ E1 − e−λ x F µ e− µλ d λ = 1 − x +

µ µ (

/i repre!intă %uncţia de repartiţie &earson de tipul =.Soluţie7 +l'oritmul de 'enerare a *aria0ilei aleatoare " ce corespunde amestecării

%amiliei de repartiţii eBponenţiale H?E x, λ F, λ > (K după repartiţia eBponenţială A E LFeste următorul7

5loritm de enerare (variabila +earson "=)7

(. =niţiali!ea!ă $G.1. Se 'enerea!ă # cu $G.

2. Se calculea!ă Λ = − µ 1

ln# .

3. Se 'enerea!ă un alt # cu $G.

4. =e/ire " = − Λ1

ln# .

+cest al'oritm poate %i utili!at pentru 'enerarea unor *alori de selecţie urm-ndrepartiţia &earson de tipul =.

33


37/123

k

>bservaţie7 Dacă n eBpresia 3 E xF = ∑ *i?i E xF , unele pro0a0ilităţi *i sunt i=1

mari, iar *aria0ilele aleatoare corespun!ătoare I i se 'enerea!ă u/or, atunci al'oritmulde 'enerare este per%ormant.

3$4 A"!e e!oe e i#"are

Simularea variabilelor aleatoare normale N(m,σ ba!ată pe teorema limită

centrală

>aria0ila aleatoare " cu repartiţie normală ; Em, F are densitatea de repartiţiede forma:

1 −( x − m )2

2σ 2

f ( x) =σ e2π cu m G M E " F, 2 G 12E " F, W (.

&entru m ( /i 1 se o0ţinede repartiţie

, x∈R

repartiţia normală redusă ; (0,1) cudensitatea

( x)= 1 e− x2

2 , x∈R 2π

e'ătura dintre *aria0ila aleatoare I a*-nd repartiţie normală redusă I N ; E(,1F /i *aria0ila aleatoare " care are repartiţie normală " N ; Em, F este dată de

trans%ormarea " m I .

Generarea *aria0ilei aleatoare ; E(,1F se poate %ace %olosind teorema limităcentrală7

!eoremă7 Dacă " 1 , " 2 ,...., " n este o selecţie e%ectuată asupra unei *aria0ile

aleatoare " , ast%el nc-t media M E " F m /i dispersia 12E " F 2, atunci

I = " 1 + " 2 + .....+ " n − nmσ

n

are asimptotic Ec-nd n \ F repartiţia ; E(,1F.

Dacă # 1, # 2, ..., # n este o selecţie de numere aleatoare uni%orme pe E(,1F,

independente, atunci *aria0ila % # 1 # 2 ... # n are asimptotic repartiţie normalăcu media n 2 /i dispersia n 12.

Teorema limită centrală poate %i %olosită pentru 'enerarea unei *aria0ile

normale ; E(,1F.

34


38/123

S:a constatat că dacă *olumul de selecţie n satis%ace condiţia n W 1(, atunci*aria0ila

% − n

I = 2 poate aproBima o *aria0ilă ; E(,1F.n

12

&entru n 12 se o0ţine I # 1 # 2 ... # 12 : 6, care este o metodă rapidă de'enerare, dar aproBimati*ă.

5loritm de enerare a unei variabile aleatoare ;(O,J) folosind teorema

limită centrală7


1. Se 'enerea!ă cu $G 12 numere aleatoare # 1, # 2, ..., # 12 uni%orme /iindependente pe E(,1F.

2. =e/ire I # 1 # 2 ... # 12 : 6.

Metoda polară

Metoda polară se 0a!ea!ă pe teorema lui


39/123

35


40/123

Simularea reparti"iei gama

*aria0ilă aleatoare " cu repartiţie 'ama ?EG, L, PF are densitatea de repartiţiede %orma7

λ ν E x

− α F

ν −1e−λ E x−α

F , x

> α

f E xF = Γ Eν F(, x ≤ α

unde G∈R este parametru de locaţie, L W ( este parametru de scală, P W ( este parametru de %ormă, iar

∞

ΓEν F = ∫ ν −1

e−

d(

*aria0ilă aleatoare % are repartiţia ?E(, 1, PF dacă are densitatea de repartiţiede %orma7

1 xν −1e− x , x > ( f E (F = Γ Eν F

(, x ≤ (

Cntre cele două *aria0ile aleatoare eBistă relaţia " = α + % ,

λ ceea ce nseamnă că 'enerarea lui " se reduce la 'enerarea lui % .

ie " o *aria0ilă aleatoare a*-nd repartiţie 'ama cu densitatea de repartiţie de

%orma7

1 xν −1e− x , x > ( f E xF = Γ Eν F ,ν > (

(, x ≤ (

/i % o *aria0ilă aleatoare a*-nd o repartiţie jei0ull7 ν −1 − xν , x > (ν x e

hE xF = ,ν > (

(, x ≤ (

>om 'enera *aria0ila " /tiind că % este o *aria0ilă jei0ull /i se 'enerea!ă mai u/or.&entru aceasta *om utili!a prima lemă de respin'ere /i *om determina pe G ast%el nc-t

f E xF = 1 e xν − x

hE xF ν × ΓEν F

"onsiderăm ca!ul c-nd ( R k R 1 /i se o0ţine71

e xν − x <

1


41/123

5loritm de enerare a unei variabile aleatoare ama ?EG, L, PF, ( R k R 17

(. =niţiali!are $G.=ntrare k, h.

1. Se 'enerea!ă % hEkF.2. Se 'enerea!ă # # E(,1F.

3. Dacă # > f

E%

F trans%er 2.

α hE% F4. =e/ire " % .

Cn ca!ul k W 1 se poate ale'e k Lk HkK /i se 'enerea!ă prin metodacompunerii pentru Lk cu rlan', ca sumă de eBponenţiale. epartiţia rlan' are%uncţia de densitate de %orma7

1 xk −1e− x , x > (, k ∈ Ν + f E xF = Γ Ek F

(, x ≤ (

k

iar 'enerarea se %ace după %ormula " = −ln ∏# i .i =1

Mai departe se aplică metoda compunerii7

f E xF *1 f 1E xF *2 f 2E xF,unde

1 f E xF, x > ( f E xF = * pentru k ∈ ?-%

1 1

(, x ≤ (iar

k

*1 = ∫ f E xFdx /i *2 1 A *1.(

Simularea reparti"iei beta

Dacă *aria0ila aleatoare " are repartiţie 0eta de parametri * /i Q, atuncidensitatea sa de repartiţie este de %orma7

1 x *−1

E1− xF

Q −1

,(


42/123

Simularea repartiţiei 0eta se 0a!ea!ă pe următorul re!ultat7

!eoremă. Dacă " 1, " 2 sunt două *aria0ile aleatoare a*-nd repartiţie 'ama de parametri * /i respecti* Q, atunci *aria0ila " = " 1 este o *aria0ilă 0eta de

" 1 + " 2 parametri * /i Q.

5loritm de enerare a unei variabile aleatoare beta7

(. =niţiali!are $G.=niţiali!are al'oritm pentru 'enerarea *aria0ilei aleatoare'ama. =ntrare *, Q.

1. Se 'enerea!ă " 1 'ama E *F.Se 'enerea!ă " 2 'ama EQF.

2. =e/ire " = " 1 . " 1 + " 2

3$@ Me!oe ar!i5#"are

nul din principiile 'enerale de 'enerare a *aria0ilelor aleatoare constă n areduce pro0lema la 'enerarea *aria0ilelor aleatoare mai simplu de 'enerat /i dacă este

posi0il la *aria0ile aleatoare uni%orme.>om pre!enta o metodă particulară de 'enerare a *aria0ilelor aleatoare 0a!ată

pe principiul respin'erii, %olosind *ectorii aleatori uni%ormi pe un domeniu

1 = {(u, v) γ (u, v)≤ (},unde este %rontiera domeniului 1.

5loritm de enerare (metodă *articulară)7

(7 =niţiali!are $G.=ntrare parametrii.

Se determină = Lu1, u2`Lv1, v2 ast%el nc-t 1 ⊂ = , u1 X (.17 Se 'enerea!ă # ′,$ ′ două numere aleatoare independente,

uni%orme pe E(,1F. ∗= u + (u − u )×# ′

27 Se calculea!ă # 2 1 1 ′ ∗ = v1 + (v2 − v1 )×$ $

37 Dacă (# ∗ ,$ ∗ )∉ 1 trans%er la 1.47 =e/ire " = h(# ∗ ,$ ∗ ).

38


43/123

>bservaţii71. &rocedeul pre!entat este un procedeu de respin'ere, deoarece la pasul 3

sunt respinse punctele care nu aparţin domeniului 1.2. &er%ormanţa al'oritmului este dată de pro0a0ilitatea de acceptare

*a =aria 1 .

aria = 3. +l'oritmul este considerat per%ormant dacă *a este mare, adică 1 ≤ *a


44/123

B. Metoda tanentelor

Se consideră tan'entele la domeniul 1 de %orma u const., respecti* v const. Se determină punctele

+ (u1, v∗ ), R(u2 , v∗∗ ), F(u∗ , v1 ), S (u∗∗, v2 )

"um 1 HEu,vF Eu,vF O (K /i d γ = ∂

∂γ u du +

∂∂γ v dv

re!ultă că panta tan'entei estedv ∂γ

m(u, v) = = − ∂u

du ∂γ ∂v

>alorile u1 /i u2 se determină din condiţiile

u1 7lim

m(u, v) = ∞, γ

(u1, v

∗

)= (

u →u1

v→v∗

m(u, v) = ∞, γ (u2 , v∗∗ )= (u2 7 lim

u →u2

v→v∗∗

iar *alorile v1 /i v2 se determină din condiţiile

v1 7lim

m(u, v) = (, γ (u∗, v1 )= (u →u ∗

v→v1m(u, v) = (, γ (u∗∗, v2 )= (

v2 7 lim

u →u ∗∗

v→v2 @emă. ie " o *aria0ilă aleatoare a cărui densitate de repartiţie este este de

%orma

f ( x) = 1 ( x), x∈R K

unde K = ∫ ( x)dx . F

ie E# , $ F un *ector aleator uni%orm pe domeniul măr'init v 1 = (u, v)( ≤ u ≤ 1 2 ÷

u


45/123

4(


46/123

+tunci, " = $ are %uncţia de repartiţie 3 E xF, unde 3 E xF este %uncţia de repartiţie#

corespun!ătoare densităţii de repartiţie f E xF. 1emonstraţie.

>ectorul E# , $ F este uni%orm pe 1 atunci7

1 , (u, v)∈ 1 (u, v) =

aria 1

(, n rest

aria 1 = ∫∫ dudv = ∫∫ dudv 1 v

(≤u ≤ 1 2 ÷ u

Dacă se %ace trans%ormareav u = t = x ⇒ ,u u = t v = tx

al cărui ?aco0ian este

1(u, v) ∂u ∂u 1 (= ∂t ∂ x = = t

1(t , x) ∂v ∂v x t +tunci ∂t ∂ x

dudv = 1 (u , v ) dtdx W du dv t dt dx

1 (t , x )∞ ) 1 2 E xF ∞ t 2 ) 1 2 E xF 1 ∞ K

∫∫ tdtdx = ∫ ∫ tdt ÷ ∫ ∫ E xFdx =aria 1 = ÷dx = ( dx =2 2 2(≤t ≤ 1 2E xF −∞ ( ÷ −∞ −∞

/i se poate calcula %uncţia de repartiţie a *aria0ilei aleatoare " $ # 7 $

1 x 1 2(ω ) 2 x t

2 ) 1 2 Eω F 1 x ÷

+ ( "


47/123

4xem*lu ( generarea variabilei aleatoare #eibull )

ie " *aria0ilă aleatoare jei0ull de parametru W(. +tunci %uncţia de densitateare %orma

ν −1 − xν

f E xF e , x > (,ν > (ν x(, x ≤ (

ν −1 −1 v ν ν v ÷ ν − − 2

+ici K k, E xF x 1e x /i 1 = (u,v)( ≤ u ≤ ÷ e 2 u

u Domeniul 1 se mai poate scrie7 1 v ν ν −1

÷

v

2

1 = (u, v) ( ≤ ue 2 u ÷ ≤ 1 .

u

1 v ν ν −1 ÷ v 2

$ot-nd cu γ (u, v) = ln ue 2 u se o0ţine7 ÷ u

γ (u, v)= ln u + 1 v ν − ν −1 v ≤ ( ÷ ln ÷

2 2 u u /i 1 = {(u, v)Dγ (u, v)≤ (}

Cn plus,

v ν −1 udv − vdu

d γ = du + ν udv − vdu − ν −1 × u 2 ÷

u 2 u2 2 v u

de unde u

du ν dv − v du v ν −1 ν −1 dv − v du

+ u − u = ( ÷u 2 u 2 v u

vu

$ot-nd cu = Q , a*emu du ν dv − Qdu ν −1 dv − Qdu

ν −1+ Q − = ( ×uu 2 u 2 Q

=> du + ν (dv − Qdu)Qν −1 − ν −1 dv − Qdu = ( 7 du

2 2 Q


48/123

4

2


49/123

ν dv

ν −1 dv − Qν −1 d

u=> 1 + − Q÷Q − = (

2 Q2 du dv ν −1 ν −1

d v

ν −1 −ν +1 ν Q ν Q

=> − Q÷ − ÷ = −1 ⇒ ÷= −12 2

Q2Q

du ÷ du ÷

=> dv = Q − 2Q => dv=

Q(ν Qν −ν −1)du ν Q

ν −ν +1 du ν Q

ν −ν +1

dv ν

aF >alorile u1 /i u2 se determină din condiţiile → ∞ ⇔ Q → ∞ sau ν Q −ν +1 = (duQ = u → ∞ W u → ( . "um u ≥ ( ⇒ u = ( .

v 1

ν Qν −ν +1 = ( W Q = ν −1 1 ν . "um γ (u, v) = ( W ÷

ν ln u + 1 ν −1 ν −1 ν −1 1 ν u 1 ν −1

− ln ÷ = ( W ln = −2 ν 2 ν ν −1 2 ν ν −1

2ν ÷

ν ν −1 ν −1

ν −1 2ν W u2 e 2ν = ÷ν

Q(ν Qν −ν −1)= ( 0F >alorile u1 /i u2 se determină din condiţia W WQ → ( sau ν Q

ν −ν −1 = (

Q → ( ⇒ v → ( ⇒ v = (u 1

ν ν +1 1ν

ν Q −ν −1 = ( ⇒ Q = ÷ .ν

"um γ

(u, v

) = ( re!ultă că

1ν ν −1 ν +1

1 ν +1 ν −1 ν +1 u ν +1 ν +1 −2ν 2ν ln u + − ln ÷ = ( ⇒ ln = − ⇒ u = ÷ e

2 ν 2 ν ν −1 2ν

ν

ν +1 2ν ÷

ν Q = v ⇒ v2 = uQ

u

ν −1 ν +1 ν +1 ν +1

ν +1 1ν ν +1 − ν +1 −2ν 2ν 2ν 2ν

W v2 = ÷ ÷ e = ÷ eν ν ν


50/123

43


51/123

5loritm de enerare a unei variabile aleatoare eibull 7

(7 =niţiali!ări $G ν −1 ν −1 ν −1

=ntrare kW1, u1 (, u2 2ν e 2ν

=

ν

÷

ν +1 ν +1

−ν +1v1 (, v2

2ν e= ν ÷ 2ν

17 Se 'enerea!ă # ′,$ ′ uni%orme pe E(, 1F /i independente.

27 Se calculea!ă # ∗ = u2# ′,$

∗ = v2$ ′ .

37 Dacă ln # ∗ + 1

$

∗ ν − ν −1 ln $ ∗ > ( trans%er la pasul 1

÷

∗2 ∗ ÷ 2 # # 47 =e/ire " = $

∗ .

#∗

@emă$

ie " o *aria0ilă aleatoare a cărei densitate de repartiţie este

f ( x) = 1 ) ( x), ) ( x) ≥ (, x ∈ . ie E# , $ F un *ector aleator pe domeniul 1, K

2 v

1 = (u, v)7 ( ≤ u ≤ 3 ÷ ,

u

cu aria 1 R . +tunci densitatea de repartiţie a lui " = $ este f E xF.#

Ge)erarea 8aria.i"e"or a"ea!oare N 0%1

eamintim că " ; Em, F dacă %uncţia de densitate este1 − ( x − m )2

2σ 2

, x∈R . f E xF σ e2π

1e− x 2

Cn ca!ul particular " ; E(,1F se o0ţine f E xF 2 .2π

&entru aplicarea lemei a*em

, ) ( x) = e− x2

K = 22π


52/123

4

4


53/123

1 v 2 1 v2 − ÷ ÷

u(u, v)7 ( ≤ ue 3 u ≤ 1

1 = (u, v)7 ( ≤ u ≤ e 3 =

$ot-ndγ (u, v) = ln u +1 v2 .

3 u

se o0ţine 1 = {(u, v)7 γ (u, v) ≤ (}.Cn continuare,

3 (u, v) = u + λγ (u, v) = u + λ ln u + 1 λv2 .1 3 u

∂ 3 λ 1 λv 2 3u 2 + 3λ u − λ v2W 1 =1 + − = .

u 3 u 2 3u 2

+poi, ∂u

∂ 3 1 = ( ⇒ 3u 2 + 3λ u − λ v

2 = ( (1).

∂u

∂ 3 1= 2 λv = ( ⇒ v = ( (2)

3 u∂vDin relaţiile E1F /i E2F se %ormea!ă sistemul7

2 + 3λ u − λ v

2 = ( u = −λ 3u ⇔ v = ( v = (

"omplet-nd sistemul anterior7∂ 3 = ( 1 u = −λ ∂u ∂ 3 = ( ⇔ v = ( 1 ∂v 1

v

2γ

(u, v) = ( ln u + = (3 u

Deci lnE: LF ( W L A1. e!ultă /i că u1 ( /i u1 1.

3 (u, v) = v + λγ (u, v) = v + λ ln u + λ v22 3u

GW ∂ 3 = λ − λv2 .2 u

3u 2

∂u∂ 3 3λ u − λ v2 v 2 3 (∗)

Din 2 = ( ⇒ = ( ⇒ λ ≠ ( ⇒ =3u

2∂u u 2

Cn continuare,∂ 3 2 =1 + 2λ v

.

∂v 3u


54/123

4

5


55/123

Din∂ 3 2

= ( ⇒1 + 2λ v = ( ⇒ (∗) ⇒1 + 2λ

3 = ( ⇒ v =−λ

∂v 3 u 3 2v

"omplet-nd sistemul deri*atelor parţiale7

∂ 3 2 = ( v2

v2

v2

∂u = 3 = 3 = 3 u u u ∂ 3 2 = ( ⇔ v = −λ ⇔ v = −λ ⇔ v = −λ

∂v

v2 1 3

γ (u, v) = ( ln u + 1 = ( u = v2 =e e 3 u

de unde se o0ţin *alorile v1 /i v27

v = − 3

1 e

3

v2

=e

5loritm de enerare a unei variabile aleatoare ;(O,J)7

(7 =niţiali!are $G=ntrare7 v1 = − 3 e, v2 = 3 e

17 Se 'enerea!ă # ′ # E(,1F .

Se calculea!ă # = # ′ (# = u1 + (u2 − u1 )# ′) # ((,1)

27 Se 'enerea!ă $ # E(,1FSe 'enerea!ă$

= v1 + (v2 − v1 )$ ′ GW $

# (v1, v2 )

37 Dacă ln #

+ 1 3$ 2

# > ( trans%er la 1.

Eperecea (# ,$ ) 'enerată nu este n domeniuF47 =e/ire " =

$ .

#

&ro0a0ilitatea de acceptare este7

aria 1 ∫∫ dudv v = x

*a = 1 = = ... = + a ≈ (,5uaria = (u2 − u1)× (v2 − v1 ) u = t


56/123

46


57/123

CAPITOLUL I&

SIMULAREA &ECTORILOR ALEATORI

&ro0lema 'enerării *ectorilor aleatori este de mare importanţă n construireamodelelor de simulare, 'enerarea unor procese stocastice, n aplicarea metodeiMonte "arlo la inte'rale multiple.

&entru a 'ăsi metode de 'enerare a *ectorilor aleatori s:a ncercat

'enerali!area unor metode %olosite la 'enerarea *aria0ilelor aleatoare datoritădi%icultăţii de calcul puţine dintre acestea au condus la re!ultate scontate.

&entru calculul inte'ralelor multiple = = ∫ f E$ Fd$ , 1 ⊂ Fk , se poate %olosi 1

următorul procedeu Monte "arlo7

: se 'enerea!ă o selecţie $ 1, $ 2, ..., $ n de *ectori aleatori independenţi identicreparti!aţi cu repartiţie uni%ormă pe 1

1 n

: se estimea!ă = prin = n = ∑ f ($ i ) .n i =1Dacă f ∈ @2E 1F atunci M E = nF=

a0solut corectă pentru = .

/i lim 1 2 ( = n )= ( , adică = n este o estimaţie

n→∞


58/123

"alculul inte'ralei = n c-nd n este su%icient de mare cu a)utorul calculatorului prin metoda Monte "arlo este uneori mai e%icientă dec-t prin mi)loacele anali!einumerice.

4$1 Ge)erarea 8e5!ori"or a"ea!ori ri) e!oa i)8eră

@emă .

ie " E " 1,..., " k F ∈ R k *ector aleator cu %uncţia de repartiţie 3 E x1, x2, ..., xk F.ie următoarele notaţii7

3 1( x1 )= + ( " 1


59/123

% 1 = 3 1−1(# 1 )

% 2 = 3 2−1(% 1,# 2 )

LLLLLLLL

% k = 3 k −1

(% 1,% 2 ,K,% k −1,# k )are %uncţia de repartiţie 3 E x1, x2, ..., xk F, unde 3 i

−1( x1,K, xi−1, ) este in*ersa lui 3 iE x1, x2, ..., xiF. 1emonstraţieT

&entru simpli%icarea scrierii se *a da demonstraţia n ca!ul k 2. &entru k W 2demonstraţia se poate reali!a prin inducţie.

3 E x1, x2F PE " 1 R x1, " 2 R x2F PE " 1 R x1F _ P E " 2 R x2 " 1 R x1F 3 1E x1F _ 3 2E x1, x2F

epartiţia comună a *ectorului E% 1, % 2F este7

+ (% 1


60/123

5loritm de simulare a unui vector aleator uniform *e (a,b)k 7

(. =niţiali!are $G.=ntrare k (, i(.

1. Se 'enerea!ă *aria0ila aleatoare # uni%ormă peE(,1F i i81

2. $ i ai 8 Ebi - aiF_# 3. Dacă i O k trans%er la pasul 1.

4. =e/ire $ E$ 1,..., $ k F.

&entru a 'enera un *ector aleator $ care are repartiţie uni%ormă pe un domeniu

oarecare 1 ⊂ R k , notăm cu = inter*alul care conţine domeniul 1. Dacă 1 domeniusimplu coneB /i f E " F ( este ecuaţia %rontierei care delimitea!ă acest domeniu, f %iindo %uncţie de k *aria0ile, atunci al'oritmul de 'enerare 0a!at pe metoda respin'erii se

pre!intă ast%el7

5loritm de simulare a unui vector aleator uniform *e 17

(. =niţiaţi!are $G.

=ntrare = Eai, bi, 1 O i O k F.1. Se 'enerea!ă un *ector # uni%orm pe = .2. Dacă f E# FW( trans%er la pasul 1.

Ese presupune că # ∈ 1 dacă f E# FR(F3. =e/ire $ # .

"ele mai simple /i rapide metode de 'enerare a *ectorilor aleatori constau n areduce pro0lema 'enerarea *ectorilor aleatori uni%ormi, care sunt cei mai u/or de'enerat.

@emă .

ie " E " 1,..., " k F un *ector aleator cu *alori n R k a cărui densitate de

repartiţie este

f ( " ) =1 ,

A × ) ( " )cu

( " ) ≥ (, " ∈ R k /i

A = ∫ ( " )d " . F

k

ie E$ (, $ 1,..., $ k F un *ector aleator uni%orm pe domeniul 1 ⊂ R k 17 v v

k

1 = (v ( , v ,...,v k )

∈ R k

+1

, ( ≤ v ( ≤ 1 k +11

,...,

÷

v 1 v ( ( ÷

49


61/123

presupus măr'init Eadică aria 1 R F.

+tunci densitatea de repartiţie a lui " E " 1,..., " k F, unde

" i = $ i $ ( , i = 1 ,2 ,...,k este f E " F.

1emonstraţie. Dacă *ectorul aleator E$ (, $ 1,..., $ k F are repartiţie uni%ormă pe D, atunci densitatea sa de repartiţie este dată de

1 , dacă (v( ,v1 ,...,vk )W ∈ 1 ,

(v( ,v1 ,...,vk )= aria 1

( , n rest

undearia 1 = 1

∫ K∫ dv(dv1...dvk v v

k

(≤ k +1 1 ,..., ÷

v

÷

v( ( acem trans%ormarea de coordonate7

x = v v ( v = tx 1 1 1 1

x

2=

v

2v

( v

2=

tx

2 ...... W ......

= vk v(

= tx( xk vk t = v ( v( = t

al cărui ?aco0ian este

1 ( ( ... (

1(v ( ,v1 ,...,vk ) x1 t ( ... ( = t k = x2 ( t ... (

1(t,x1 ,....,xk ) ... ... ... ... ... xk ( ( ... t

+tunci1 ( x ,..., x )

k +1 k

∫ ...

∫ t k dtdx

1...dx

k =

∫ K

∫

1

aria 1 = ∫

tk dtdx1...dxk =

1 123 (

( x ,..., x ) F k (≤t ≤ k +1 k 1

= 1 ∫ K∫ ( x1,..., xk )dx1...dxk = A

k +1 k +1123 F

k

+cum se o0ţine7

+ ( " 1


62/123

5

0


63/123

1 ( x ,..., x ) x xk ) k +1 k

= (k +1) A 1 1

tk ∫ K ∫ ∫ dtdx ...dx k =

1

− ∞ −∞ (

1 x1 xk ( x K x )dx ...dx = 3 ( " ),= ∫ K ∫ A 1 k 1 k −∞ −∞

unde 3 E " F este %uncţia de repartiţie a lui f E " F, " ∈R k /i lema este demonstrată.

5loritm de simulare a unui vector aleator 7

(. =niţiali!ea!ă al'oritmul $G pentru 'enerarea unor numerealeatoare uni%orme pe E(,1F

=ntrare parametri.Se determină un inter*al = , 1 ⊂ = , de %orma7

= = Lv1

( , v(2 ×Lv1

1, v1

2 ×K×Lv

1k , vk

2

1. Se 'enerea!ă *ectorul aleator E$ (,$ 1

,...,$ k

F uni%orm pe = , ast%el7$

= v

1 + Ev2 − v1F# i , i =1,2,...,k unde # i sunt numerei i i i

aleatoare independente, uni%orme pe E(,1F.

2. Dacă ($ (,$ 1,...,$ k ) ∉ 1 trans%er la pasul 1, alt%el la pasul 3.3. =e/ire "

i =

h

($

(

,$

1

,...,$

k

), i

= 1,2,..., n .

>bservaţii7

1. &unctele E$ (, $ 1

, ..., $ k

F sunt uni%orm reparti!ate pe domeniul măr'init 1, al'oritmul descris mai sus %iind un al'oritm de respin'ere.

2. &er%ormanţa al'oritmului este caracteri!at de pro0a0ilitatea de acceptareEpro0a0ilitatea de trecere de la pasul 2 la pasul 3F dată de

*a =aria 1 .

∏k

(vi2 − vi1 )

i=1

3. +l'oritmul este per%ormant dacă *a este mare.

Di%icultatea aplicării acestui al'oritm constă n determinarea inter*alului

minimal = care:l conţine pe 1. &entru aceasta l putem scrie pe 1 su0 %orma7

1 = {(v( ,...,vk ) γ (v( ,...,vk )≤ (}/i procedeul de determinare a lui = re*ine la a re!ol*a pro0lemele de optim

v1i = min vi , vi

2 = maB vi , ( ≤ i ≤ k .

1 1


64/123

51


65/123

+plic-nd metoda multiplicatorilor lui a'ran'e pentru re!ol*area pro0lemelor deoptim, *om 'ăsi pe v(, v1,/,vk ast%el ca7

3 i (v( , v1,..., vk ) = min 3 i (v( , v1,..., vk ) = maB , i = 1,2,...,n

unde 3 i (v( , v1,...,vk ) = vi + λγ (v( , v1,...,vk )

cu restricţia

γ (v( , v1,..., vk ) = (.

Cn continuare aplicăm lema /i al'oritmul pentru 'enerarea *ectorilor

aleatori a*-nd repartiţie Diriclet /i multinomială.

4$3 Ge)erarea 8e5!ori"or a"ea!ori a8) rear!iţie Diri5h"e!

Date post:	06-Jul-2018
Category:	Documents
Upload:	biancamihalache
View:	221 times
Download:	0 times

tehnici_de_simulare_1-101

Documents