CERCETRI INFORMAIONALE

1. Etapele principale ale cercetrii operaionale. Obiectivele i criteriile de eficien a problemelor decizionale.CO studiul proceselor complexe ce tin de aspecte decizionale care include solutii, strategii si factori contribuabili.Etape: 1. formularea problemei (scop, resurse, coeficienti tehnici), 2. elaborarea modelului matematic (functie scop / obiectivul, restrictii), 3. rezolvarea problmei (determinarea metodei de rezolvare), 4. verificarea, testarea modelului, validitatii (datele prelucrate / obtinute de catre decident), 5. aplicarea modelului / implementare.Problema de cercetari operationalese caracterizeaza prin: scop (maximizarea profitului, performantei, randamentului; minimizarea pierderii, costului, riscului), constrangeri (restrictii), solutii admisibile, optimale (decizii, strategii, factori de control), functia obiectiv (criterii de eficienta, performanta),decident sau grup decizional, etc.Deciziase defineste prin hotarrea de a alege o anumita varianta de actiune din mai multe posibile.Pentru ca o decizie sa fieeficientatrebuie sa ndeplineasca urmatoarele conditii:sa fie fundamentata stiintific; sa fie luata de organul sau persoana autorizata; sa fie luata la timp; sa fie simpla si clara; sa nu fie contradictorie.Criteriilede apreciere a variantelor pot fi: tehnice (consum de materii prime, durata ciclului de productie); economice (profitul, pretul, durata de recuperare a investitiilor); sociale (forta de munca, importanta produselor n cadrul pietei).Functia f e functia obiectiv a problemei de optimizare, ea reprezinta criteriul de performanta urmarit: maximizarea beneficiului, productiei marfa, gradului de incarcare al utilajelor, veniturilor, minimizarea costului productiei, timpului de tsationare a utilajelor, etc.

2. Clasificarea problemelor cercetrii operaionale: probleme decizionale de certitudine, risc i incertitudine. Regulile decizionale n condiii de incertitudine i risc.Clasificari: 1.Continut: organizarea optima a procesului de productie, gestiunea stocurilor, transport, de distribuire optima a resurselor; 2.Raport cu timpul: statice, dinamice. 3. Numarul de funcii obiectiv. 4.Caracter informational: determinist, probabilist, incertitudine.Sistem{X = (x1, x2,,xn) factori contribuabili; C = marime vectoriala / matrici marimi constante}. Q = (q1,q2,,qn) vector.De certitudine sau determinista problema e pe deplin determinata pe grupul de factori X, C; X solutia se ia in conditii de certitudine, factorii C sunt cunoscuti si nu pot fi modificati de decident.De risc sau probabilista prezenta celor 3 grupuri de factori X, C, Q. Q element aleatoriu starea naturii. Se cunoaste legea de repartitie.De incertitudine X,C ca in determinist, Q factor necunoscut (incert) care apartine unui domeniu.Cele mai cunoscuteinstrumentefolosite pentru problema de risc sunt: punctul critic, matricea rezultatelor si arborele decizional.Punctul criticsurprinde relatia dintre volumul productiei si nivelul costului, profitului si ncasarilor din vnzarea unui produs, sau a unui grup de produse. Punctul critic e cel n care costul total si ncasarile din vnzari sunt egale. Punctul critic este cel care marcheaza volumul productiei dincolo de care firma nregistreaza profit. Punctul de echilibru = prag de rentabilitate se gaseste egalnd ecuatiile costului total si a veniturilor din ncasari: V=q*p; Ct=Cf+Cd; V=Ct.Matricea rezultatelorse prezinta ca o lista bidimensionala de cifre sau simboluri aranjate pe linii si coloane care identifica starile (conditii) posibile ale naturii N, probabilitatea P si rezultatul Q fiecarei strategii S. Criteriile pe baza carora decidentul evalueaza strategiile pot fi: criteriul valorii asteptate; criteriul rationalitatii (criteriul Laplace, aplicabil deciziilor n conditii de incertitudine); criteriul probabilitatii maxime (pe baza caruia este aleasa starea naturii cu probabilitate maxima). Astfel, n cazul criteriului valorii asteptate, decidentul are de calculat valoarea asteptata a fiecarei strategii (V.A.), care este o medie aritmetica ponderata a rezultatului sau o suma a valorilor conditionale ponderate cu probabilitatea producerii lor: VA1=p1*Q11++pn*Q1n.Arborele decizionalse utilizeaza n deciziile de grup, in conditii de risc si incertitudine. Scheletul arborelui este format din noduri si linii. Nodurile sunt momente decizionale: cele care reprezinta deciziile n conditii de certitudine au forma patrata, iar cele ce sugereaza deciziile n conditii de risc sau incertitudine au forma de cerc. Liniile reprezinta activitatile sau alternativele posibile. Rezolvarea consta in calculul sperantei matematice a fiecarei consecinte si alternative decizionale, utiliznd formula: Sm = suma (pi*Ri), 1

3. Modele liniare ale problemelor de cercetare operaional: exemple de probleme, modele matematice ale lor.Structura generala a modelului liniar se constituie prin multimea de activitati A1An, resursele R1Rn, relatiile tehnico-economice dintre acestea. Legatura dintre activitati si resurse e determinata de tehnologia de fabricatie pentru activitatea Aj (1a11 x1 + a12 x2 + + a1n xn =0.} Forma canonica de minim: {min f = c1 x1 + + cn xn; ai1 x1 + + a1n xn >= bi, i=1,,n; x1,xn >=0.} Forma canonica de maxim: {max f = c1 x1 + + cn xn; ai1 x1 + + a1n xn =0.} Proprietatile solutiei unei astfel de probleme: verifica restrictiile 1.2, verifica restrictiile directe 1.3, optimizeaza functia obiectiv pe multimea vectorilor care indeplinesc p1 si p2.Solutie un vector x apartine Rn care verifica restrictiile 1.2;solutie admisibila un vector x apartine Rn care verifica rstrictiile 1.2, 1.3;solutie optima un vector x apartine Rn care verifica restrictiile 1.2, 1.3 si optimizeaza functia obiectiv pe multimea tuturor vectorilor cu aceasta proprietate. O soluie de baz care are toate componentele nenule strict pozitive se va numisoluie de baz admisibil.Dintre toate alegerile posibile de solutii este remarcabil (prin simplitatea ei) soluia x=0, care duce la soluia particularnumitsoluia de baz. O soluie optim care este de baz se va numisoluie optim de baz. Se observ c o soluie de baz are cel mult m componente diferite de 0. Din cauza importanei lor n rezolvarea problemei, vom evidenia soluiile de baz care au mai puin dect m componente nenule, numitesoluii degeneratei pe cele care au fix m elemente nenule, numitesoluii nedegenerate.

5. Proprietile fundamentale ale PPL (teoremele principale). Interpretarea geometric a PPL.Metoda grafic de soluionare a PPL.T1. Dac problema de programare liniar are soluii admisibile atunci are i soluii de baz admisibile. T2. Dac problema de programare liniar are soluii optime atunci are i soluii optime de baz. T3. Mulimea soluiilor admisibile (optime) este nchis i convex. Dac este i mrginit atunci punctele extremale ale acesteia sunt chiar soluiile admisibile (optime) de baz ale problemei.Restrictiile dreapta.Functiascop gradient. Domeniul de solutii estepoligonulformat de restrictii.Metoda graficaconsta in determinarea tuturor varfurilor poligonului de restrictii care e descris de relatiile 2, 3. Acest poligon reprezinta toate solutiile admisibile inclusiv si cele optimale. Se foloseste teorema fundamentala T3 in care se mentioneaza ca solutia optima a unui model liniar este unul dintre varfurile poligonului de restrictie. Daca am cunoaste toate varfurile poligonului, atunci prin calculul direct al valorilor functiei am determina aceste valori pentru toate varfurile selectand varful pe care ia maxim. Se cer reprezentari foarte exacte a desenului ce prezinta poligonul de restrictii si gradientul functiei scop.

6. Metoda simplex de soluionare a PPL.Se construieste o solutie initiala de baza, solutie admisibila: de regula se ia in calitate de solutie de baza punctul (0, 0) daca aceasta e admisibila. Caracter iterativ: la fiecare iteratie are loc trecerea de la o solutie de baza la alta imbunatatind de fiecare data functia scop. Fiecarei iteratii ii corespunde un tabel simplex. Trecerea de la un tabel la altul are loc conform metodei excluderii Jordan Gauss luand in considerare respectarea cirteriului de optimalitate.

7. Problema de transport: probleme echilibrate (nchise) i dezechilibrate (deschise), modele matematice. Reducerea modelelor deschise la modelul nchis.Caracteristicile unei probleme de transport clasice sunt: fiecare surs aprovizioneaz cel puin o destinaie i fiecare destinaie este aprovizionat de la cel puin o surs; pot exista perechi surs-destinaie ntre care nu se poate face transfer (rute blocate); nu exist limitri n ceea ce privete cantitatea transportat pe fiecare rut; se cunosc cantitile disponibile n fiecare surs i cantitile necesare n fiecare destinaie; fiecrei rute i s-a asociat un cost care nu depinde de sensul de parcurgere. Scopul problemei este gsirea acelor cantiti care trebuie transportate pe fiecare rut astfel nct s se asigure necesarul fiecrei destinaii, n limitele cantitilor aflate la surse, cu costul minim posibil. Datele problemei sunt: m = numrul de surse (furnizori); n = numrul de destinatari (consumatori); {Ai, i = 1,...,m} = cantitile disponibile n fiecare surs; {Bj, j = 1,...,n} = cantitile necesare la fiecare surs; {cij, i = 1,...,m; j = 1,...,n} = costurile unitare pe fiecare rut (costul transportrii unei uniti de msur de la sursa i la destinaia j). xij cantitatea care va fi transportat de la sursa i la destinaia j. Problema: Suma cij xij -> min; Suma xij =Bj (cerere totala); 1. Disponibilul > cererea; xij = Ai Bj / Suma Ai solutie admisibila; se va transporta doar necesarul pentru a avea costuri minime.Problema are soluie optim, iar cantitatea n exces fa de cerere va rmne la furnizori, fiind reprezentat de variabilele de abatere din primele m restricii. Aceste cantiti pot fi privite ca nite cereri ale unui consumator fictiv i innd cont c, de fapt, aceste cantiti nu sunt transportate nicieri, costurile unitare pe rutele care ar lega furnizorii de acest consumator sunt 0. 2. Chiar dac disponibilul este mai mic dect necesarul, nu nseamn c nu se va mai transporta nimic, ci doar c unora dintre consumatori nu li se va satisface toat cererea. Aceast cerere nesatisfcut poate fi privit ca disponibilul unui furnizor fictiv i innd cont c, de fapt, aceast cantitate nu exist, costurile unitare pe rutele care ar lega consumatorii de acest furnizor sunt 0. Orice problem poate fi transformat ntr-o problem de tipul disponibil = cerere. Acest tip va fi ales pentru formalizarea problemei. O astfel de problem se numeteproblem de transport echilibrat. Forma stadard echilibrata:Suma cij xij -> min; Suma xij =Ai, Suma cij =Bj.

8. Soluionarea problemei de transport prin metoda potenialelor.Daca modelul e neechilibrat se defineste un furnizor imaginar m+1 () cu cantitatea de cererea imaginara bn+1=ai-bj. O soluienedegeneratare m+n1 componente diferite de 0.Rezolvarea problemei de transport se face n dou etape: 1. Gsirea unei soluii iniiale de baz dupa una din metodele nord-vest, minim pe linie, minim pe coloana, costul minim, diferente maxime; 2. Gsirea soluiei optime.

9. Modele de probleme ale programrii liniare n numere ntregi (programarea discret). Exemple de probleme ale programrii discrete. Metoda Ramific i Mrginete (Branch and Baund).In CO se inainteaza cerinta ca solutia propusa sa se exprime in numere intregi. In alte cazuri o parte din componentele vectorului optim e nevoie sa fie in numere intregi, celelalte se pot exprima ca valori nenegative R. Initial au fost propuse cateva metode de rezolvare a problemelor de tip liniar in numere intregi de cercetatori Gomory, Land, Danzig. Metoda Gomory a fost propusa doar pentru rezolvare modelului liniar si se bazeaza pe metoda simplex si pe ideea definirii unor hiperplane ce sepata subdomenii admisibile care nu contin solutii exprimate in numere intregi. Tehnicile respective sunt relativ simple si dupa un numar finit de iteratii de tabele simplex se obtine solutia finala componentele careia sunt numere intregi. Al doilea tip de metode propuse de Land, Danzig initial pentru modele liniare mai tarziu generalizate pentru probleme cu caracter general. In litaratura are denumirea de ramificari si frontiere / estimatii. Exemple de probleme care se exprima in numere intregi: 1. Modelul clasic de productie cu n produse si m resurse, 4 conditii, maximizarea venitului. 2. Problema transportului minimizarea costurilor de transpoprt, ai, bj sunt numere intregi cererea si oferta in orice punct va fi un numar intreg, la fel si solutia optima cu toate componentele ei. 3. Problema determinarii unui post de lucru n specialitati, n persoane. Daca persoana i va ocupa postul j atunci castigul respectiv ca fi vij. E necesar: fiecare persoana i sa fie numit intr-un j; fiecare post j sa fie ocupat de un i; distribuire persoanelor pe posturi trebuie sa fie realizata astfel incat vij sa fie maximal. Modelul: z(x)= suma vij xij -> max; suma xij = 1, i=1n o pers ocupa un j; suma xij = 1, j=1n fiecare post sa fie ocupat de un j; xij = {1 i ocupa j; 0 i nu ocupa j}. Se rezolva problema prin metoda grafica sau simplex. Daca solutia gasita nu este din numere intregi se ia coordonata care nu este un numar intreg si se ia numaru intreg de la capetele numaruluise cauta soluti inafara acestor numere pentru ca intre ele nu exista nici un numar intreg. Xnumaru ntreg de sus acestea sunt 2 restrictii. Termenul ramifica se refera la faptul ca din problema initiala rezulta 2 probleme noi prin adaugarea la restrictii a uneia din cele 2 restrictii. Aceste 2 probleme se rezolva prin metoda simplex. Marginirea se refera la faptul ca valoarea variabilelor care nu erau numere intregi este marginita superior sau inferior. Solutia optima estea cea solutie care confera funtiei obiectiv valoarea cea mai mare la probleme.

10. Probleme multicriteriale ale programrii liniare. Metode de soluionare.Modelele cu mai multe criterii solutii pentru care s-ar realiza maximu sau minimu pentru cel putin 2 funcii scop. Venit -> max, cost -> min, profit -> max. in cazul in care toate expresiile din model reprezinta funcii liniare modelul multicriterial poarta numele de liniar multicriterial. Acelasi x va realiza val maxima in primul citeriu si minima in al doilea. Fara a limita generalizarea am putea considera ca toate sunt de maxim, simetria lui z->min in plan, solutia ramane aceeasi. Exista cateva moduri de solutionare a acestor probleme: 1. Compozitie / compunere / sinteza se determina un sir de numere numite prioritati alfa L1,,Lr care determina gradul de importanta a criteriului dat astfel incat suma lor sa fie 1. Se rezolva modelul prin metoda grafica. Se gaseste valoare maxima in ambele funcii obiectiv. Se defineste o noua functie obiectiv impreuna cu functiile obiectiv initiale si ponderile cunoscute Z(x)=Li*zi(x)->max. Se calculeaza valoarea functiei noi in punctele poligonului. Valoarea maxima va fi solutia. 2. Includerii criteriilor in restrictii criteriul de baza e cel de maxim, celelalte devin restrictii cu un plafon de considerare Zi(i)>=Zi. 3. Concesiilor / caderilor succesive z1(x)->max, fie z1* - valoarea maxima al lui z1. Se determina o cedare de la aceasta valoare de exemplu 10%: z2(x)->max, z1(x)>=z1*-cedarea. Urmatorul pas e similar cu precedentul. Solutia de la ultimal pas e considerata optima. 4. Z1(x)->max, x apartine D, fie x1* - multimea solutiilor, daca e un singur punct e sol optima. Z2(x)->max, x apartine x1*, x2*-multimea de solutiietc.

11. Probleme de optimizare pe reea: problema arborelui minim , problema drumului minim (maxim) n reea fr circuite; problema drumului minim n reea cu circuite i metode de soluionare.Problema arborelui minim avem n orase care trebuie unite intre ele si cunoastem costul Cij; sa selectam graful pentru care costul este minim (lungimea totala a muchiilor sa fie minima); contine n-1 muchii si nu are cicluri; metoda de solutionare este algoritmul Kruskal si algoritmul Prim. Alg.Kruskal initierea matricii costurilor; urmeaza n-1 pasi: la fiece pas se selecteaza cite o muchie, astfel incit costul selectat s fie minim din celelalte din matrice si sa nu formeze ciclu. Alg.Prim se alege un nod S initial, de la el se alege muchia s, j si de pe muchia respectiva (coloana) se alege valoarea minima Csj; muchia (i,j) unde i M (muchii selectate), j M (neselectate).Problema drumului minim (maxim) n reea fr circuite se da un graf orientat (cu arce) fara circuite, fiecarui arc i se asociaza un numar Cij. Nodul 1 este nod cu gradul de incidenta 0 si este nod de intrare in graf; nodul final are doar arce de sisire. Sa identificam toate retelele d lungime minima ce pornesc de la nodul 1 pina la toate celelalte noduri. Metoda de solutionare este algoritmulFord: se numeroteaza corect graful prin suprimarea consecutiva a arcelor astfel incit pentru orice muchie (i,j) iProblema drumului minim n reea cu circuite metode de rezolvare: alg. Ford (imperfect), alg. Dijkstra (rezolva si problema drum in retea fara circuite). Alg.Dijkstra se da un graf cu circuite, cu arce in ambele sensuri; sa se selecteze rute de lungime minima ce pornesc dintr-un nod arbitrar S. Se constituie 2 multimi: M cu noduri selectate siMcu noduri neselectate. Se selecteaza pe rind nodurile incepind cu un nod de pornire i0=S pentru care ruta optima a fost selectata: P0: i0=S M; Ui0=0; Pr(j)=i0; orice j=[1,n]; Ui=Uj, i=j, - distanta optima; min {Ui0,j}, orice j=[1,n]; j ! M, j!=S; MuM=|Un|=n; jM; Uj1=min{Ui0j} => urmatorul nod. P1: se verifica pentru toate nodurile jMpentru Uj>Ui+Cij, iM, jM; daca Uj>Ui+Cij=>Uj=Ui+Cij; daca UjUj. P2: min{Uj}=Uj; Pr(j) pentru orice jM; i2=j2M;n-1 pasi.

12. Metoda drumului critic (Critical Path of Method). Graful-reea i regulile principale de construire.Drumul critic i determinarea lui. Calcularea caracteristicilor de timp al grafului-reea. Semnificaia i importana caracteristicilor de timp pentru analiza grafului-reea.Principiul analizei drumului critic const n divizarea unui proiect (aciuni complexe) n pri componente. Ia natere un tabel care conine activitile proiectului, intercondiionrile ntre activiti i duratele acestora. Un astfel de tabel trebuie s conin cel puin urmtoarele elemente: activiti; condiionri: se precizeaz, pentru fiecare activitate, activitile imediat precedente, prin simbolurile lor; durata: pentru fiecare activitate se precizeaz durata de execuie, ntr-o anumit unitate de msur. Durata unei activiti este o constant. Modelele de analiz a drumului critic se bazeaz pe reprezentarea proiectului printr-un graf, elementele tabelului asociat acestuia fiind suficiente pentru a construi graful corespunztor. Metoda CPM este un procedeu de analiz a drumului critic n care singurul parametru analizat este timpul i n reprezentarea graficului reea se ine seama de urmtoarele convenii: fiecrei activiti i se asociaz un segment orientat numit arc, definit prin capetele sale, astfel fiecare activitate identificndu-se printr-un arc; fiecrui arc i se asociaz o valoare egal cu durata activitii pe care o reprezint; condiionarea a dou activiti se reprezint prin succesiunea a dou arce adiacente. Nodurile grafului vor reprezenta momentele caracteristice ale proiectului, reprezentnd stadii de realizare a activitilor (adic terminarea uneia sau mai multor activiti i/sau nceperea uneia sau mai multor activiti). Pentru reprezentarea corect a proiectului, ct i pentru o standardizare a reprezentrii n desenarea grafului se respect urmtoarele reguli: fiecare activitate se reprezint printr-un arc a crui orientare indic, pentru activitate, desfurarea ei n timp; un arc este limitat prin dou noduri care simbolizeaz momentele de nceput i de sfrit ale executrii activitii corespunztoare; lungimea fiecrui arc, n general, nu este proporional cu lungimea activitii; deoarece respectarea tuturor regulilor nu se poate face doar cu arce care corespund doar activitilor proiectului, vor exista i arce care nu corespund nici unei activiti, care vor fi reprezentate punctat i care, pentru unitatea prezentrii, vor fi numite activiti fictive, ele neconsumnd resurse i avnd durata 0.In graf nu sunt admise. Nodurile vor fi numerotate, numerotarea fcndu-se n aa fel nct, pentru fiecare activitate, numrul nodului de nceput s fie mai mic dect numrul nodului de final al activitii.graful are un singur nod iniial ("nceperea proiectului") i un singur nod final ("sfritul proiectului");orice activitate trebuie s aib cel puin o activitate precedent i cel puin una care i succede, exceptnd bineneles activitile care ncep din nodul iniial al proiectului i pe cele care se termin n nodul final al proiectului;dei exist activiti care se execut n paralel, care pot ncepe n acelai moment i se pot termina n acelai moment, este interzis ca cele dou arce corespunztoare s aib ambele extremiti comune; nu trebuie introduse dependene nereale. s se foloseasc, pe ct posibil, numrul minim de activiti fictive, pentru a nu complica excesiv desenul. Analiza grafului retea: Calculam caracteristicile de timp: cel mai devreme termen de realizare a evenimentului i: td(i) = maxim care vine in nod i; cel mai tarziu termen de realizare a ev j: tt(j) = minim care pleaca din j. SD = td; FT = tt; ST = tt-tij; FD = td+tij; rezerve de timp: Rtot = FT-FD=ST-SD; Ri = td(j)-tt(i)-tij. Durata critica = termen de realizare cel mai devreme a ultimului eveniment n, - cel mai mic interval de timp necesar pentru realizarea intregului proiect. Daca td=tt se alege drumul critic. Activitatile drumului critic sunt numite activitati critice. Caracteristicile de timp sunt importante in analiza grafului retea pentru ca ele duc la determinarea drumului critic.

13. Teoria firelor de ateptare (teoria cozilor). Clasificarea sistemelor de servire (ateptare). Exemple. Fluxul de sosire al cererilor (comenzilor). Fluxul elementar, testul Pearson(x2) de validare a legii de repartiie a probabilitilor de tip exponenial (Poisson) a fluxului de sosire a cererilor i a timpului de servire.Teoria firelor de ateptare (teoria cozilor) scop: abonatii sa nu astepte prea mult. Pentru analiza acestor sisteme se utilizeaza: caracteristicile fluxului de cereri solicitate sistemului, timpul de servire. Flux de sosire a cererilor variabila x(t) numarul cererilor solicitate sistemului in intervalul de timp t variabila aleatoare discreta. Tabelul pentru reprezentare: x(t): 0,1,,k,; p. Legea de distribuire / repartitie a probabilitatii este diferita pentru fiecare sistem. Distingem: Sisteme deschise: cu surs infinit de staii unde n-numrul staiilor, iar m numrul locurilor de ateptare=0(cu refuz). Sisteme deschise unde ninf. Sisteme nchise, n care sursa este partea component a sitemului de ateptare, n numrul staiilor de servire. Pentru toate sistemele, fluxul de sosire a cererilor este elementar, adic satisface urmtoarele proprieti: 1) ordinar; 2) staionar; 3) independent. Ordinar probab solicitarii mai mult de o cerere intr-un interval mic de timp este infinit mica de ordin superior. Stationar probab ca in intervalul de timp t vor sosi k cereri depinde numai de marimea k si t. Independent probab nu depinde de nr de cereri solicitate pina la momentul inceperii intervalului t. Fluxul elementar se mai numete flux de tip Poisson exprima probabilitatea intimplarii unui numar de evenimente intr-un interval fixat de timp daca aceste evenimente se intimpla cu o frecventa stiuta si independent de timpul de la ultimul eveniment. Lambda intensitatea fluxului de solicitare a sistemului. O variabila aleatoare discreta are distributie Poisson cu parametrul lambda>0 daca pntru orice k=0,1,2 probabilitatea ei este definita de formula: f(k; lamda) = P(X=k) = (lambda^k * e^-lambda)/k!.

14. Procese Markov continui dup timp i discrete dup stri. Sistemul de ecuaii difereniale de tip Kolmogorov. Regim de tranziie i de echilibru (staionar).In cazul in care sistemul analizat are un numar finit de stari, iar timpul de observare este continuu, se obtine un proces markov. Probabilitatea tranzitiei dintr-o stare in alta la un anumit moment de timp este nula. Deoarece variabila aleatoare de timp este continua se utilizeaza densitati ale probabilitatii de tranzitie.Proces care se poate afla in una din stari S1Sn si care in orice moment de timp T poate trece dintr-o stare in alta. Pi(t) probab ca in momentul de timp t procesul poate trece din orice stare Si in starea Sj a procesului fiind influientat de un flux de evenimente. Pij(t) probab ca-n momentul de timp t procesul se afla in starea Si.Pi(dt) probab ca in intervalul de timp dt procesul va trece din Si in Sj. Pi(dt) = lambdaij * dt (elementar Poisson). Lamda intensitatea de trecere a procesului din o stare in alta; = nr de treceri / unitate de timp. Procesul Markov poate fi reprezentat print-un graf marcat orientat. Nodurile grafului sunt starile, trecerile dintr-o stare in alta sunt sagetile. De exemplu: daca avem o retea de 2 calculatoare sunt posibile starile: S0 ambele calc lucreaza; S1 s-a defectat primul; S2 s-a defectat al doilea; S3 s-au defectat ambele. Variabila lambda in acest caz este intensitatea de defectare a compului; miu intensitatea de reparare. Sagetile care pleaca dintr-o stare sunt lambda, cele care vin spre ele e Miu.Sistemul de ecuaii difereniale de tipKolmogorovderivata probabilitatilor care conduc de la orice stare in starea considerata din care se scade suma tuturor probabilitatilor care conduc din starea considerata in alte stari. pentru fiecare stare se alcatuieste o ecuatie. Cele care vin in S0 se iau cu + cele care pleaca cu minus.Po(t)=P1Miu1+P2Miu2-P0Lambda1-P0Lambda2. Se egaleaza cu 0. Po+P1+P2+P3=1; Teoria de rezolvare a sistemului demonstreaza ca Pk(t) e suma a 2 solutii fk(t) solutia ecuatiilor omogene si fik(t) solutia particulara care verifica conditiile intitiale (solutia de echilibru). Functionarea sistemului e divizata in 2 etape: de tranzitie si finala de stabilitate. O stare Si e neesentiala sau de tranzitie daca exista o stare Sj si un numar n astfel incat Pij(n)>0, Pji(m)=0, pentru orice m. Cand timpul este continuu in locul numarului de pasi n se poate considera intervalul de timp dt. O stare neesentiala poate fi atinsa in sistem dar cand este parasita nu se mai revine in ea. O stare Si e esentiala daca nu exista o alta stare Sj in care sa se ajunga pe un drum oarecare din Si fara ca sistemul sa mai poate reveni in Si. Daca Si si Sj sunt esentiale, pentru cazul discret, exista 2 numere naturale m si n pentru care Pij(n)>0, Pji(m)>0, atunci starile se numesc comunicate. Aceasta relatie e tranzitiva. Ergodic sistem pentru care exista limitele probabilitatilot starilor pentru t tinzand la infinit. Pentru un sistem cu numar finit de stari conditia necesara si suficienta pentru ergodicitate este ca toate starile esentiale sa fie comunicante. Pentru starile neesentiale limitele probab starilor sunt 0. Daca un sistem e ergodic limitele starilor se pot obtine din ecuatiile Kolmogorov in care toate derivatele se anuleaza. Se obtine un sistem liniar de n ecuatii cu n necunoscute si suma probabilitatile = 1.Jordan gauss un algoritm de rezolvare a sistemelor de ecuatii liniare. Este inteles ca o secventa de operatii efectuate asupra unei matrici de coeficienti. Sunt 3 tipuri de operatii elementare efectuate asupra liniei: schimbare cu locul a doua linii, multiplicarea unei linii cu un numar diferit de zero, adunarea unui multiplu a unei linii la alta linie pana cand matricea nu contine cat mai multe zerouri. Sau se foloseste pivotul pentru transformare.

15. Procese moarte i renatere. Formulele Eurlang.Caz particular Kolmogorov. Lant Markov. Se considera un sistem care poate avea un nr finit de stari S0Sn In intervalul de timp unic dt, sistemul aflat in starea Sk poate trece in starea Sk+1 cu probabilitatea Lambdak dt, poate trece in starea Sk-1 cu probabilitatea miuk dt sau poate ramane in starea Sk cu probabilitatea 1-(lambdak+miuk)dt. Robabilitatea ca sistemul sa treaca in alte stari dect cele specificate e neglijabila. E un proces Markov. Lambdak si miuk sunt dependenti de k, independenti de t, ceea ce inseamna ca e un proces markov omogen. Acest proces poarta numele de moarte renastere. Daca starea Sk reprezinta o nastere, iar o tranzitie in starea Sk-1 reprezinta o moarte. Miui = 0 atunci e un proces de nastere pura. Lambda i = 0 atunci proces de moarte. Forumele lui Eurlang 1903 P1 = 01/10 * P0.P1 = 12/21 * P1.Pn= P0 * (01 * 12 * * n-1 n)/ (10 * 21 * * n n-1).Po=[(1+01/10)++( 01 * 12 * * n-1 n)/( 10 * 21 * * n n-1)^(-1).

16-17. Sisteme de servire (ateptare) deschise cu coad finit i infinit; caracteristicile principale necesare pentru analiza acestor sisteme.

De obicei,sistemele de asteptaresunt studiate analitic, adica, pentru anumite repartitii ale timpilor dintre doua sosiri consecutive si timpilor de servire, precum si anumite politici de servire ale clientilor, sunt deduse formule matematice ale factorilor de eficienta ai sistemului. Exista numeroase situatii cnd astfel de formule nu exista sau sunt extrem de complicate. n aceste situatii, se recomanda utilizarea unor algoritmi de simulare cu ajutorul calculatorului.Analiza sistemelor de ateptarecu n staii de servire i m=0(locuri la coad).Fluxul de sosire a cererilor este elementar(de tip Poisson).Timpul de servire are repartiia exponenial.F(t)=, unde cte cereri n unitatea de timp t vor fi servite de staie.Fluxul de sosire: f(t)=Dac cererea solicitat sosete n momentul cnd cel puin o staie este liber, ea va fi servit. Dac toate staiile sunt ocupat, ea va fi respins. Toate staiile de servire posed aceeai capacitate.S0starea cnd cererile lipsesc i deci toate n fire de ateptare(staii) sunt libere.S1n sistem se afl o cerere, adic 1 staie e ocupat i n-1 libere.Sntpate staiile sunt ocupate cu servirea.Fie intenisatea de ocupare, iar intensitatea de eliberare.

Pentru calculul probabilitilor finale vom utiliza formulele:Notm, atunciAvnd probabilitile finale, putem calcula o serie de caracteristici:probabilitatea cnd cererea va fi refuzat:capacitatea relativ de servire:capacitatea absolut de servire:numrul mediu de staii ocupate cu servirea: saunumrul de staii libere, ce funcioneaz neproductiv, disponibile:coeficientul de utilizare a staiei:coeficientul de staionare neproductiv:Dac pierderea clienilor este costisitoare, pentru ameliorare se va mri numrul de staii.

Analiza sistemelor de ateptarecu n staii de servire i m