Curs9 Modelare Economica 2008_nadia Ciocoiu

CURS 9 MODELARE ECONOMICA CONF. DR. NADIA CIOCOIU

1.Teorema de optimalitate a lui Bellman 2. Modelarea proceselor de producţie-stocare cu programare dinamică (+vezi carte Modelare economica, 2007 !!!) 3. Modelarea alocării unor fonduri băneşti în funcţie de efectele economice obţinute 4. Modelul de analiză a drumului critic pentru proiecte complexe (studiu de caz la seminar)

1.Teorema de optimalitate a lui Bellman În 1951, Richard Bellman introduce termenul de „programare dinamică” pentru o nouă metodă de rezolvare secvenţială a problemelor decizionale. Pentru „programarea dinamică” propusă de Bellman nu există o formulare matematică generală a problemei, aşa cum există pentru programarea matematică liniară. Programarea dinamică reprezintă o metodă generală de abordare a problemelor complexe şi presupune un anumit grad de pricepere şi de pătrundere în structura problemei pentru a putea recunoaşte:  

când o anumită problemă poate fi rezolvată prin programare dinamică; cum poate fi făcută această rezolvare.

Programarea dinamică constă în descompunerea problemei decizionale în subprobleme mai mici.

1.Teorema de optimalitate a lui Bellman Fiecare subproblemă este numită fază sau etapă deoarece subproblemele vor fi rezolvate într-o anumită ordine. De obicei o subproblemă sau fază conţine o singură variabilă de decizie, astfel rezolvarea se poate face prin enumerare completă sau prin alte metode simple. Soluţia optimală obţinută la o etapă este apoi utilizată în etapa următoare. Prin rezolvarea tuturor subproblemelor, se obţine soluţia problemei originale. Succesiunea tuturor soluţiilor din toate etapele => politică. Orice subşir de soluţii succesive ce fac parte dintr-o politică se numeşte subpolitică. În mulţimea politicilor posibile, există cel puţin una care optimizează criteriul de eficienţă ales => politică optimală

1.Teorema de optimalitate a lui Bellman Pentru determinarea politicii optimale, Bellman a enunţat principiul de optimalitate: „O politică optimală are proprietatea că oricare ar fi starea iniţială şi decizia iniţială, deciziile care urmează a fi luate trebuie să constituie o politică optimală în raport cu starea rezultată ca urmare a alegerii primei decizii”. O consecinţă a principiului de optimalitate: Orice politică extrasă dintr-o politică optimală este ea însăşi optimală.

2. Modelarea proceselor de producţiestocare cu programare dinamică Cazul general al problemelor de aprovizionarestocare pune problema dimensionării cantităţii stocate dintr-o anumită resursă, astfel încât cererea secţiilor de producţie să fie satisfăcută atunci când solicită resurse din depozit (intervalul de timp poate fi cunoscut sau neprecizat), iar costul de stocare să fie minim. În cazul rezolvării problemelor de producţiestocare prin programarea dinamică se introduce ca variabilă de stare nivelul stocului la sfârşitul fiecărei perioade a orizontului considerat.

3.Modelarea alocării unor fonduri băneşti în funcţie de efectele economice obţinute Formularea economică a problemei:

Se doreşte repartizarea unui fond F pe cele n obiective disponibile, a.î. suma efectelor generate de cele n obiective En(F) să fie max.

Notaţii: F – fondul disponibil ce urmează a fi alocat pentru modernizarea/ reprofilarea/dezvoltarea a n obiective (secţii, unităţi etc.); xk – fondul ce se alocă pentru fiecare obiectiv k, deci k = 1, 2, ..., n obiective Ek(F) – efectul economic integral ce se obţine prin alocarea optimă a fondului F pe k obiective (reprezintă suma efectelor ce se obţin pentru diferite obiective)

E k ( F) = max{ e1 ( x1 ) + e 2 ( x 2 ) + ... + e k ( x k ) }

3.Modelarea alocării unor fonduri băneşti în funcţie de efectele economice obţinute Plecând de la principiul de optimalitate al lui Bellman se face urmatorul raţionament: Dacă pentru obiectivul k s-a repartizat un fond xk şi s-a obţinut efectul ek(xk), atunci pentru (k – 1) obiective se va aloca (F – xk) şi se va obţine efectul Ek-1(F – xk), deci efectul total va fi:

E k ( F) = max{e k ( x k ) + E k −1 ( F − x k )},

x k ∈[ 0, F]

În mod analog pentru k = n

E n ( F) = max{ e n ( x n ) + E n −1 ( F − x n )}

Se calculează efectul maxim generat de alocarea tuturor combinaţiilor posibile de fonduri pentru primele 2 obiective, apoi pentru al treilea şi celelalte două considerate împreună, apoi al patrulea obiectiv şi primele trei împreună ş.a.m.d. Citirea soluţiei se realizează începând cu efectul maxim de la ultima alocare (între obiectivul n şi restul obiectivelor) şi continuând în sens invers până la alocarea între primele două obiective. (pentru exemplificare vezi studiul de caz 13/pag. 201 din cartea Modelare economică)

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe ADC este un instrument eficient de coordonare şi conducere a lucrărilor complexe de tip proiecte. ADC presupune descompunerea lucrărilor în activităţi care se intercondiţionează din punct de vedere tehnic. Duratele activităţilor pot fi: - certe sau deterministe => metoda ADC  CPM - probabiliste => metoda PERT Prin ADC se determină: durata totală de realizare a proiectului, punând în evidenţă activităţile critice (fără rezervă de timp) pentru fiecare activitate:   

termenele de începere: minime şi maxime termenele de terminare: minime şi maxime rezervele de timp

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe Condiţionările dintre activităţi se pun în evidenţă cu ajutorul unui graf tip reţea, în care activităţile pot fi noduri sau arce. In cazul reprezentării activităţilor pe arce: nodurile reprezintă evenimente = momentele de terminare ale unor activităţi şi de începere ale altor activităţi (fig.) tmi

tM i

i

dik

dkl

k

djk

tmj

tM j

j

tm k

tM k

l

tml

tMl

m

tmm

tM m

n

tmn

tM n

dkm dkn

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe În figura, se notează: tmk = timpul minim al evenimentului k = timpul minim sau cel mai devreme de începere a activităţilor care pornesc din nodul k tmk = max{tmi + dik; tmj + djk} tMk = timpul maxim al evenimentului k = timpul maxim sau cel mai târziu de terminare a activităţilor care ajung în nodul k tMk = min{tMl - dkl; tMm – dkm; tMn – dkn } tmnod iniţial = 0 tMnod final = tm nod final

Activităţile cu rezerva totală de timp egală cu zero se numesc activităţi critice; Drumul critic = succesiune de activităţi critice care leagă nodul iniţial (începutul proiectului) cu nodul final (sfârşitul proiectului)

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe I. Analiza cost - durată (cazul duratelor deterministe) Seminar: Studiul de caz 15/ carte Modelare economica

Pentru fiecare activitate se estimează durata normală şi durata urgentată (crash time) astfel încât durata urgentată ≤ durata normală Urgentarea unei activităţi implică resurse suplimentare => creşterea costurilor, deci: Costul activităţii urgentate ≥ Costul normal

Costul unitar de urgentare al fiecărei activităţi =

Costul urgentat − Costul normal Durata normala - Durata urgentata Rezolvarea se poate face cu: ⇒WINQSB/ modulul PERT – CPM/ Deterministic CPM ⇒QM/ modulul CPM/PERT/ submodulul CPM with Crashing

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe Graficul cost-durata Cost total Cost maxim

A

Cost optim urgentat

B

C

Buget dat ?

D E

Cost minim DU

?

Dint

DN

Durata totală

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe II. Determinarea duratei totale a proiectului /cazul duratelor probabiliste Seminar: Studiul de caz 14/ carte Modelare economica

Pentru fiecare activitate se estimează: o durată optimistă (aij), una medie probabilă (mij) şi o durată pesimistă (bij). Durata unei activităţi are o distribuţie beta şi se calculează cu relaţia:

d ij =

a ij + 4m ij + bij 6

Dispersia duratei de execuţie a activităţii (i,j) se calculează cu relaţia:

 bij − a ij  2  σ ij =   6 

2

Dispersia este o măsură a gradului de nesiguranţă în evaluarea duratei unei activităţi. Metoda PERT permite calcularea timpului mediu de terminare a unei acţiuni complexe în cazul în care duratele activităţilor nu se cunosc cu exactitate. Rezolvarea se poate face cu: ⇒WINQSB/ modulul PERT – CPM/ Probabilistic CPM ⇒QM/ modulul CPM/PERT/ submodulul PERT

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe III. Algoritm euristic de alocare a resurselor Notaţii: Pentru fiecare activitate (i,j) cu durată dij, vom considera că:   

tmî este termenul minim de începere, tMt este termenul maxim de terminare, Rij rezerva totală de timp: Rij = tMt – (tmî + dij).

La un moment dat t al execuţiei proiectului se definesc următoarele mulţimi:      

Et = mulţimea activităţilor proiectului care se execută la momentul t; Tt = mulţimea activităţilor care au fost terminate până la momentul t; Nt = mulţimea activităţilor neprogramate; Ct = mulţimea activităţilor candidate, care sunt potenţial posibil să fie programate la momentul de începere t: Ct = Pt U At Pt = mulţimea activităţilor candidate, care sunt programate la momentul t; At = mulţimea activităţilor amânate.

4.Modelul de analiză a drumului critic (ADC) pentru proiecte complexe III. Algoritm euristic de alocare a resurselor Algoritmul programează la momentul t activităţile din Ct, notate Pt pentru care: ∆k = D − ck ≥ 0 t

  

k

∑

Pt ∪ E t

ij

k = resursele 1,2, ..., m Dk – disponibilul maxim din resursa K Cijk - consumul din resursa k al activitatilor programare Pt si a celor care se executa Et la momentul t.

Restul activitatilor sunt amânate (vezi carte !!!). Criteriul de programare a activitatilor poate fi:   

Ordinea crescatoare a rezervei de timp; Asigurarea la maximum a capacitatilor disponibile; Ordinea crescatoare a termenului maxim de incepere.

Vezi exemplele din cartea Modelare economica (st caz 16 si st caz 17)!!!