Programarea dinamică

Programarea dinamica constituie una dintre cele mai eficiente metode de rezolvare a problemelor de optimizare , indiferent de domeniul de aplicare.

Aplicarea programarii dinamice presupune rezolvarea succesiva a unui numar de N subprobleme , incepand cu una corespunzatoare primelor doua etape si sfarsind cu ultima, ce va da solutia problemei initiale.[Cartina ‘89].

Modelul problemei de programare dinamica consta in gasirea extremului unei functii de N variabile , definite pe domeniul determinat de restrictiile modelului:

maxF(x1,x2,…xN)=g1(x1)+g2(x2)+…+gN(xN)

x1+x2+…xN=x

x1+x2+…xN>=0

Metoda programarii dinamice se bazeaza pe principiul de optimalitate.Conform acestui principiu, o strategie optima are proprietatea ca , oricare ar fi starea initiala si decizia initiala, deciziile ramase trebuie sa constituie o strategie optima in raport cu starea care rezulta din prima strategie.

Conform principiului de optimalitate avem:

Etapele ce trebuie parcurse, intr-o problema de programare dinamica, pentru aflarea solutiei optimale sunt

• Se intocmeste tabelul de venituri optimale:

• Apoi, din tabelul de venituri optimale , obtinem tabelul de stratedii:

• Din tabelul de strategii, printr-o tehnica de retrosubstitutie, se obtin pe rand xN, xN-1, xN-2,…pana la x1,ceea ce reprezinta si solutia optimala a problemei respective.

Modelul matematic

In repartizarea optimala a sarcinilor intre grupurile unei centrale termoelectrice, modelul de optimizare corespunzator are forma generala:

In aceste relatii puterea active totala ceruta Pc , include, pe langa puterea ceruta de sistem si puterea consumata in serviciile proprii ale centralei respective.

Pentru un grup oarecare, plecand de la expresia consumului de combutibil:

B(P)=B2P2+B1P+B0

se poate obtine costul combustibilului consumat, prin inmultire cu c0 ($/tcc):

C(P)=C2P2+C1P+C0F

Facand o translatie de simboluri : x-Pc, xN-PN, xk-Pk, gN(xN)-BN(PN) pentru repartizarea economica a puterii pe cele N=NG=ng grupuri ale centralei considerate, ecuatia fundamentala a programarii dinamice devine:

Exemplu:

Daca se cunoaste puterea ceruta unei centrale termoelectrice cu doua grupuri si caracteristicile de functionare ale acestora, sa se determine impartirea sarcinii intre grupuri astfel incat pe total sa avem u consum minim corespunzator unei cereri de putere de 400,600,800 respectiv 1000MW.

Caracteristicile de functionare si limitele tehnice corespunzatoare celor doua grupuri sunt:

B1(P1)=P12*0.00107+P1*7.74+793.22, 100<=P1<=600MW

B2(P2)=P22*0.00072+P2*7.72+1194.6, 100<=P2<=800MW

Pc=600MW

a) discretizarea resursei totale (Pc) in mai multe valori:

Pc B1(P1) B2(P2)

0 793.22 1194.6

50 1182.895 1582.4

100 1577.92 1973.8

150 1978.295 2368.8

200 2384.02 2767.4

250 2795.095 3169.6

300 3211.52 3575.4

350 3633.295 3984.8

400 4060.42 4397.8

450 4492.895 4814.4

500 4930.72 5234.6

550 5373.895 5658.4

600 5822.42 6085.8