Cercetari Operationale exam
1.
Probleme de optimizare pe reţea:
o
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); constine 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. Alg. Prim – se alege un nod S initial, de la el se alege muchia
s,j si de pe muchia respectiva se alege valoarea minima Csj; muchia (i,j) unde
i € M (muchii selectate), j € M (neselectate).
o
problema drumului minim (maxim) în reţea fără
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 algoritmul Ford: se numeroteaza corect graful prin suprimarea consecutiva
a arcelor astfel incit pentru orice muchie (i,j) i
o
problema drumului minim în reţea 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 si M cu noduri neselectate. Se selecteaza pe rind
nodurile incepind cu un nod de pornire i0=S pentru care rut 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; j€M;
Uj1=min{Ui0j} => urmatorul nod. P1: se verifica pentru toate nodurile j€M
pentru Uj>Ui+Cij, i€M, j€M; daca Uj>Ui+Cij=>Uj=Ui+Cij; daca
Uj<=Ui+Cij=>Uj. P2: min{Uj}=Uj; Pr(j) pentru orice j€M; i2=j2€M;…n-1
pasi.
o
problema fluxului maximal – exista sursa de materie prima S si exista
consumatorul C; S – nod intrare, C – nod plecare. Celelalte noduri sunt
intermediare. Se cunosc capacitatile de transport Cij. Sa se determine
cantitatea maximala de materie utila care poate fi transportata in reteaua
proiectata de la S la C. Sursa fictiva S se uneste cu sursele reale S1, S2… si analogic
cu consumatorul real C si se calculeaza suma distantelor cu care se uneste S
fictiv conform arcelor care pleaca din acele noduri cu care e unit S. Modelul
matematic: Xij – cantitatea de materie utila ce va fi transportata de l j l i.
V – flux maxim = ∑ Xsj, orice (s,j) €U -> max. Pentru fiecare nod
interemediar pleac din el atita cit cine la el. ∑Xkj=∑Xik; k=[1,n], orice (k,j)
€U, orice (i,k) €U. 0<=Xij<=Cij. Daca Xij=Cij => ramura saturata, caz
contrar – ramura nesaturata. Conditiile taiturii in retea de transport cu flux
maximal: S€R, C€R, R∩R=vida; invers = s1,s2,… multimea tuturor
nodurilor. Metoda de rezolvare – ford fulkerson si ford. Ford Fulkerson – Valoarea
fluxului maximal Vmax coincide cu capacitatea taiturii minime. Vmax=min C(R,R).
Algoritmii existenti de solutionare gasesc taitura minima. Ford – initierea
matriciicapacitatilor: p1: identificam drumul care uneste S cu C astfel incit
sa fie tranasportata o cantitate pozitiva de materie. Daca drum exista =>
P2, daca nu => P3. P2: Transformam matricea initiala C0 in C1 astfel: se
calculeaza λ=min{Cij}, orice (i,j) € drumului L. Cij1=Cij0- λ;Cji1=Cji0+ λ. P3:
X*=C0-C*. C* - ultima matrice transformata.
2.
Metoda drumului critic (Critical Path of
Method) – identificam
operatiunile, consecutivitatea, durata lor. Graf
retea: Cu ajutorul nodurilor se prezinta evenimentele in retea. Arcele –
activitatile. Un singur nod de intrare si unul de iesire. Circuite interzise,
graf orientat. Fiecare activitate are un singur nod initial si unul final, nu
se permit activitati cu acelasi nod de intrare si acelasi nod de iesire, din
acest motic se introduc activitati fictive cu durata 0. Calculam caracteristicile de timp: td(i) = maxim care vine in nod
i; 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.
3.
Teoria firelor de aşteptare (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 crerilor 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. Daca repartitia e Poisson atunci fluxul e poisson, markov sau
elementar. Pentru toate sistemele fluxul de sosire a cererilor este elementar
cu proprietatile: ordinar, stationar,
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. Exista: sisteme deschise cu refuz cu sursa infinita
de statii, deschise cu refuz n,m< inf, deschise cu numar limitat de statii,
sisteme inchise in care sursa e parte componenta a sistemului de asteptare.
4.
Procese Markov continui după timp şi discrete
după stări – proces care se
poate afla in una din stari si care in orice moment de timp poate trece dintr-o
stare in alta. Pi(t) – probab ca in momentul de timp t procesul se afla in
starea Si. Pij(dt) – probab c-n intervalul de timp t procesul trece dintr-o
stare in alta. Lamda – intensitatea
de trecere a procesului din o stare in alta. Poate fi reprezentat print-un graf
marcat orientat. Sistemul de ecuaţii diferenţiale de tip Kolmogorov - Cele care
vin in S0 se iau cu + cele care pleaca – cu minus. Regim de tranziţie şi de
echilibru (staţionar). – functionarea sistemului e divizata in 2 etape. Jordan gauss pentru graf tare conex,
probab finala nu depinde de timp. Regim
stationar – daca sistemu se alfa in starea s1 40% din tot timpul de
functionare.
