"Programarea dinamică în rezolvarea sarcinilor de producție". TUTORIAL: programare dinamică în sarcinile economice

2.1. Sarcina distribuției investițiilor

"Condiția sarcinii. Asociația de producție include trei întreprinderi ale PI, TI2, SH. Managementul Asociației a decis să investească 5 unități monetare condiționate în întreprinderile lor (Den. Den) în total. Cercetarea de marketing prezice suma a profiturilor așteptate ale fiecăreia dintre întreprinderi în funcție de volumul fondurilor investite. Aceste date sunt prezentate în tabelul de mai jos. Se consideră că investițiile zero sunt așteptate la zero.

Este necesar să se găsească o astfel de distribuție a investițiilor între întreprinderi, care să asigure maximul profitului total așteptat.

Decizie. În această sarcină, sistemul controlat este asociația de producție luată în considerare, un proces cu mai multe etape - procesul de alocare a fondurilor întreprinderilor. Rețineți că structura procesului pe mai multe etape în această problemă este determinată de cursul timpului, ci prin procedura de planificare a distribuției investițiilor. Efectul economic reprezintă suma totală a profitului așteptat și, în același timp, sarcina este rezolvată în căutarea unui maxim.

Pentru a rezolva sarcina, construim mai întâi modelul său economic și matematic în conformitate cu paragrafele. 1-5 sec. 1.7 ch. unu.

Numărul de pași. / V Această sarcină trebuie luată egal cu 3 corespunzătoare numărului de întreprinderi incluse în Asociația de Manufacturing: În primul pas este planificat să evidențieze fondurile companiei P, la al doilea pas - compania Ya2, în al treilea pas - Enterprise SH.

Ca o variabilă de fază X, care determină starea sistemului în timpul procesului de distribuție a investițiilor, vom lua suma totală a fondurilor alocate întreprinderilor după fiecare pas de proces. Tocmai variabila X reprezintă valoarea fondurilor alocate întreprinderilor după prima etapă a procesului (adică numai întreprinderea P), X2 - valoarea fondurilor alocate după a doua etapă (întreprinderile P și D2), X3- Schimbul de fonduri alocate după procesul al treilea pas (toate întreprinderile P, YA2 și YAZ). Deoarece în momentul inițial, cantitatea totală a mijloacelor alocate este 0, atunci starea inițială a sistemului este caracterizată de valoarea XQ \u003d 0. Prin starea problemei, cantitatea totală de instrumente de investiții este de 5 SL. Den. unități., IE, codul corespunzător este necesar: Deoarece în sensul sarcinii la fiecare etapă a procesului de valorile variabilei de fază, aceasta nu scade, atunci limitarea ZJ ^ 5. Rețineți că Selectarea variabilei de fază cu sensul economic specificat nu este singurul posibil posibil. De exemplu, în problema examinată, a fost posibilă alegerea ca o variabilă x rezoluția fondurilor nealocate.

Ca variabilă de control și să ia valoarea fondurilor alocate întreprinderilor pe fiecare dintre pașii procesului. Variabila reprezintă valoarea fondurilor alocate de întreprindere (la prima etapă a procesului) și2 - valoarea fondurilor alocate întreprinderii P2 (în etapa a 2-a), din volumul fondurilor alocate de către Întreprinderea 773 (la pasul 3). Presupunem că mijloacele pentru întreprinderi sunt alocate de sume, dar un număr întreg de condiții. Den. unități; În consecință, toate controalele iau numai valori întregi 0, 1, 2, ....

Funcția procesului XI \u003d / і (Xі-I, U), determinând legea schimbării stării sistemului, pare a fi o formulă pentru această problemă

Xі \u003d Xі-і +

și are următorul semnificație simplă: valoarea totală a fondurilor XI alocate întreprinderilor cu un rezultat tot mai mare după pasul cu numărul G este egal cu valoarea totală a fondurilor alocate întreprinderilor după pasul anterior cu numărul ii - 1 Sau la fel, la etapa actuală), plus volumul fondurilor alocate întreprinderii la pasul actual.

Funcția ZI, care determină efectul economic privat în pas cu numărul de proces, depinde numai de volumul fondurilor investite în întreprindere, adică Zi \u003d ZI (M) și este determinată de tabelul acestor sarcini pe Coloana care răspunde la această companie. De exemplu, Z (2) \u003d 4 (din coloana corespunzătoare întreprinderii PI), Z2 (3) \u003d 6, 23 (4) \u003d 9.

Cu privire la aceste acțiuni prescrise de PP. 1-5 sec. 1.7 ch. 1 efectuat, ceea ce înseamnă finalizarea formalizării matematice a sarcinii, adică construcția unei economii adecvate model matematic. Rețineți că, după formalizarea specificată, se efectuează principalele ipoteze ale metodei DP: absența unei urmăriri rezultă din formulele explicite pentru calcularea XI și ZI și aditivitatea funcției țintă

Z \u003d Zi (UI) + Z2 (și2) + 23 (m3)

datorită chiar formulării problemei.

Astfel, puteți continua direct la calcule în conformitate cu metoda DP. Aceste calcule, așa cum s-a indicat mai sus în secțiune. 1.6 ch. 1, realizat în trei etape: o etapă preliminară, o etapă de optimizare condiționată și pasul definitiv de optimizare. La etapa preliminară și în stadiul optimizării condiționate, rezultatele de calcul sunt înregistrate în tabelul auxiliar și de bază al structurii care este prezentată în secțiune. 1.7 ch. 1. La etapa de optimizare necontestabilă, soluția optimă a problemei utilizând informațiile conținute în tabelele principale este construită.

Etapa preliminară. Această etapă de rezolvare a problemei este efectuată într-o ordine naturală pentru і \u003d 1, 2.3 și nu este direct legată de calcularea funcțiilor Belman BI (XI). Numai primul șir al tabelului auxiliar și cele patru coloane stângi ale mesei principale sunt umplute.

Tabelul auxiliar este umplut cu starea inițială XQ \u003d 0 și are forma

Umplerea mesei principale se efectuează după cum urmează. Pentru o anumită valoare admisă XQ \u003d 0, selectați toate valorile posibile ale valorilor de control (poate lua toate valorile întregi de la 0 la 5 inclusiv) și să le introduceți în a doua coloană a tabelului. Conform formulei Xi - XQ + (următoarea formula generală XG \u003d XI-I + U la і \u003d 1), efectuăm calculul valorilor corespunzătoare ale variabilei XX și introduceți-le în a treia coloană . Pentru a umple cea de-a patra coloană, valorile profitului așteptat ZX luați din coloana sarcinii de tabel de date sursă care îndeplinește întreprinderea PI. Pentru SH - 1 pe această masă ZJ \u003d 2, pentru și \u003d 2, conform tabelului Zi-4, etc., pentru SH \u003d 0, cu starea problemei Zi \u003d 0. Obținem următorul tabel principal:

În acest sens, umplerea părții din stânga a tabelului principal este finalizată și tabelul are doar un fragment cu litere mici. Du-te la pasul următor.

i \u003d 2.

În a doua etapă, în prima linie a tabelului auxiliar, facem toate valorile variabilei x, calculate în etapa anterioară și apar în cea de-a treia coloană a tabelului principal anterior. Obținem următorul tabel auxiliar:

Pentru a umple tabelul principal în acest pas, vom, în mod analog cu pasul anterior, vom selecta succesiv toate valorile admise ale lui X, introduse într-o table subsidiară și efectuează calculele corespunzătoare. Fiecare valoare x va corespunde fragmentului său minuscular al tabelului principal; Fragmentele minuscule adiacente ale liniei orizontale sunt separate.

Pentru valoarea x \u003d 0, selectați toate valorile posibile de control U2 (poate lua toate valorile întregi de la aproximativ 5 inclusiv) și să le introduceți în a doua coloană a tabelului. De

formula X2 \u003d X + U2 (următoarea formula generală XI \u003d XI-L +

la R \u003d 2), efectuăm calculul valorilor corespunzătoare ale variabilei X2 și le introducem în coloana a treia. Pentru a umple cea de-a patra coloană, valorile profitului așteptat Z2 ia din coloana tabelului de date sursă a sarcinii corespunzătoare întreprinderii p ^. Pentru И2 \u003d 1, pentru acest tabel, Z2 \u003d 1, pentru U2 - 2, conform tabelului Z2 \u003d 2 etc. Umplerea primului fragment de linie al tabelului principal corespunzător lui X \u003d 0; acest fragment are forma următoare:

Pentru următoarea valoare admisă xi \u003d 1, construim următorul fragment cu litere mici. În același timp, controlul și2 poate lua toate valorile întregi de la 0 la 4 inclusiv (de la selectarea instrumentelor Enterprise P în cantitatea de x \u003d 1

În mod similar, se formează fragmentele de linie ale mesei și pentru X \u003d 2,3,4,5. Este clar că, cu o creștere a valorii lui X, setul de valori de control admisibile U2 este îngustat și pentru x \u003d 5, doar o singură valoare este doar o singură valoare și 2 \u003d 0. Ca rezultat, obținem După tabelul principal:

Tabelul construit este împărțit în 6 fragmente minuscule, la fel de mult cât mai multe valori diferite pot primi o variabilă XI. Du-te la următorul (ultimul) pas. .

În al treilea pas, în prima linie a tabelului auxiliar, facem toate valorile variabilei X2 calculate în etapa anterioară și apar în cea de-a treia coloană a tabelului principal anterior. Aceste valori repetă în mod repetat

Programarea dinamică este un aparat matematic conceput pentru soluție eficientă O anumită clasă de probleme de programare matematică. Această clasă se caracterizează prin posibilitatea de a diviza naturală (și, uneori) întreaga operațiune într-un număr de etape interdependente. Termenul "dinamic" din titlul metodei a apărut, aparent deoarece etapele sunt presupuse a fi separate în timp. Cu toate acestea, pașii pot fi elementele operației, în niciun fel legate între ele. Cu toate acestea, metoda de rezolvare a unor astfel de sarcini cu mai multe etape este aplicată în același timp, iar numele său a devenit general acceptat, deși în unele surse se numește programare cu mai multe etape.

Modelele de programare dinamice pot fi aplicate, de exemplu, atunci când elaborează regulile rezervelor, stabilirea momentului de reaprovizionare a stocurilor și a valorii ordinului de reaprovizionare; La elaborarea principiilor planificării calendaristice a producției și a nivelului de muncă în condițiile fluctuării cererii de produse; în distribuirea de investiții de capital deficitare între posibilele direcții de utilizare a acestora; la elaborarea planurilor de calendar pentru actualul și revizia de echipamente complexe și înlocuirea acestuia; Atunci când se dezvoltă reguli pe termen lung pentru înlocuirea funcționării activelor fixe etc.

Cea mai ușoară modalitate de a rezolva problema este o căutare completă a tuturor opțiunilor. Când numărul de opțiuni este mic, această metodă este destul de acceptabilă. Cu toate acestea, în practică, sarcina cu un număr mic de opțiuni este foarte rară, astfel încât bustul complet este, de obicei, inacceptabil din cauza costurilor excesive ale resurselor de calcul. Prin urmare, în astfel de cazuri, programarea dinamică vine la salvare.

Programarea dinamică ajută adesea să rezolve sarcina, un algoritm perknown pentru care ar necesita o mulțime de timp. Această metodă utilizează ideea optimizării pas cu pas. În această idee există o subtilitate fundamentală: fiecare pas nu este optimizat de la sine, ci cu "Lumina pentru viitor", asupra consecințelor soluției "pas cu pas" primite. Ar trebui să asigure câștigurile maxime nu la un anumit pas, ci pe întreaga întreagă a pașilor incluși în operațiune.

Metoda de programare dinamică poate fi utilizată numai pentru o anumită clasă de sarcini. Aceste sarcini ar trebui să îndeplinească astfel de cerințe:

· Sarcina de optimizare este interpretată ca un proces de gestionare a n-pas;

· Funcția țintă este egală cu suma funcțiile țintă fiecare pas;

· Selectarea managementului pe pasul K-m Depinde numai de starea sistemului la această etapă, nu afectează pașii precedenți (fără feedback);

· stat s K. După ce pasul K-Th se depinde numai de starea anterioară s k-1 și management x K. (lipsa de amerură);

· La fiecare pas, management X K. Depinde de numărul finit de variabile de control și de stat s K. - De la un număr finit de parametri.

Soluția tuturor sarcinilor de programare dinamică este principiul "optimității" lui Belman, care arată astfel:

oricare ar fi starea sistemului s ca rezultat al oricărui număr de pași, în pasul apropiat trebuie să alegeți controlul astfel încât să fie în combinație cu controlul optim la toate etapele ulterioare, a condus la câștigarea optimă a tuturor pașilor rămași, inclusiv acest lucru.

Acest principiu a fost formulat mai întâi de R. Belman în 1953. Bellman a fost formulat clar de condițiile în care principiul este credincios. Cerința de bază este procesul de gestionare trebuie să fie fără feedback, adică Managementul în această etapă nu ar trebui să afecteze pașii precedenți.

Formularea generală a sarcinii clasice de distribuție a investițiilor.

Luați în considerare formularea globală a sarcinii de distribuție dinamică a investițiilor.

Pentru dezvoltare, investițiile de capital în suma S sunt evidențiate pentru dezvoltare. Există n pe obiecte de investiții, pentru fiecare dintre care profitul așteptat (X), obținut de la atașarea unei anumite fonduri. Este necesar să se distribuie investițiile de capital între obiectele N (întreprinderi, proiecte) în așa fel încât să obțină cea mai mare valoare posibilă.

Pentru a compila un model matematic, procedăm din ipoteze:

· Profitul fiecărei întreprinderi (proiect) nu depinde de investițiile în alte întreprinderi;

· Profitul fiecărei întreprinderi (proiect) este exprimat în unele unități convenționale;

· Profitul total este egal cu valoarea profiturilor primite de la fiecare întreprindere (proiect).

Această setare este un model simplificat al procesului real de distribuție a investițiilor, iar în forma "pură" nu apare, deoarece nu ia în considerare anumiți factori, și anume:

· Prezența criteriilor "informale", adică cele care nu pot fi măsurate cantitativ (de exemplu, coerența proiectului cu strategia generală a întreprinderii, caracterul său social sau de mediu etc.) și, prin urmare, proiectele pot avea o prioritate diferită;

· Nivelul de risc al proiectelor;

· Alti factori.

Datorită necesității de înregistrare a nivelului de risc în formarea portofoliului de investiții, a apărut o programare dinamică stochastică, care se ocupă de valorile probabiliste. Acesta a fost aplicat în diverse domenii, dintre care una dintre cele mai utilizate este gestionarea investițiilor financiare de risc.

Programarea dinamică (DP) este o metodă de optimizare adaptată operațiunilor în care procesul de luare a deciziilor poate fi împărțit în pași (pași). Astfel de operațiuni sunt numite în mai multe etape. Începutul dezvoltării DP se referă la anii '50 din secolul XX. Este asociat cu numele R. Belman.

Dacă modelele de programare liniară pot fi utilizate în economie pentru realizarea de soluții planificate la scară largă în situații dificile, modelele DP sunt utilizate în rezolvarea sarcinilor unei scale semnificativ mai mici, de exemplu, atunci când se dezvoltă reguli de gestionare a rezervelor care stabilesc momentul de reaprovizionarea stocurilor și valoarea ordinului de reaprovizionare; La elaborarea principiilor planificării calendaristice a producției și a nivelului de muncă în condițiile fluctuării cererii de produse; atunci când distribuie investiții de capital limitate între posibilele direcții de utilizare a acestora; la elaborarea planurilor de calendar pentru actualul și revizia de echipamente complexe și înlocuirea acestuia; Când se dezvoltă reguli pe termen lung pentru înlocuirea fondurilor principale care pleacă de la operațiune etc.

În funcționarea efectivă a sistemelor economice mari, soluțiile microeconomice sunt necesare săptămânal. Modelele DP sunt valoroase prin faptul că acestea permit pe baza unei abordări standard folosind o intervenție minimă umană pentru a lua astfel de decizii. Și dacă fiecare luat separat o astfel de soluție este în mod inutil, atunci în agregat, aceste soluții pot avea un mare impact asupra profiturilor.

Un proces gestionat este considerat, de exemplu, procesul economic de distribuție a fondurilor între întreprinderi, utilizarea resurselor pentru mai mulți ani, înlocuirea echipamentului, reaprovizionarea rezervelor etc.

Ca rezultat al sistemului de control (obiectul de control) s este tradus din starea inițială (deci), la starea finală (SN). Să presupunem că managementul poate fi împărțit în n-pași, adică Soluția este acceptată secvențial la fiecare etapă, iar controlul care traduce sistemul S de la starea inițială în final este un proces de control N-pas.

La fiecare pas, se aplică o anumită soluție de control X K, în timp ce setul de X- (X1, X2, X, XN) se numește control. Metoda de programare dinamică se bazează pe lipsa de aftereffect și de starea adiționalității funcției țintă.

Starea lipsei de referințe. Statul S K, care a trecut la sistem pentru o singură dată, depinde numai de starea s K -1 și de controlul X K selectat și nu depinde de modul în care sistemul a venit la stat k.1:

S. k. (S. k.1, x. k.)

De asemenea, este luată în considerare faptul că alegerea controlului asupra pasului K-OM depinde numai de starea sistemului în acest pas:

x. k. (S. k. -1 )

La fiecare pas de control x k depinde de numărul finit de variabile de control. Starea sistemului la fiecare pas depinde de numărul final de parametri.

Principiul optimității.Oricare ar fi starea sistemului ca urmare a oricărui număr de pași, în pasul apropiat trebuie să alegeți controlul astfel încât să fie în combinație cu controlul optim al tuturor pașilor ulteriori la câștigarea optimă a tuturor pașilor rămași, inclusiv a acestuia . Cerința de bază în care principiul credincioșilor este procesul de gestionare trebuie să fie fără feedback, adică Managementul în această etapă nu ar trebui să afecteze pașii precedenți.

Astfel, soluția la fiecare pas se dovedește a fi cea mai bună din punct de vedere al managementului în ansamblu.

Relațiile recurente Belman.

Găsirea soluției optime a procesului gestionat poate fi făcută pe baza ratelor recurente ale lui Bellman. Lasa f. k. (S k -1, x k) - un indicator al eficienței pașilor k cu tot felul de management. Alocați modelul invers și direct al lui Bellman.

Masa6 . Valorile întreprinderilor de profit

Volumul resurselor alocate	Profitul de la proiecte

În acest tabel, sunt prezentate valorile profiturilor (F; (q)), care au fost obținute prin rezolvarea producției și a sarcinii economice a fiecărei întreprinderi investite. Aceste valori variază în funcție de volumul investițiilor.

Tabelul 7. Date privind venitul suplimentar al întreprinderilor

Resurse alocate

În acest tabel 7. Datele privind veniturile suplimentare, pe care o întreprindere de investitor primește din fiecare investiție investită, în funcție de volumul investițiilor investite.

Tabelul 8. Au fost calculate indicatori de eficiență (ZI (Q)) a întreprinderilor investite, care au fost obținute utilizând o schemă directă Belleman.

Tabelul 8. Hărți de eficiență

Resurse alocate	Venituri suplimentare din proiecte

Luați în considerare găsirea fiecărui indicator de performanță:

Pentru indicatorii eficacității unei întreprinderi Zi (0) \u003d PI (0) \u003d 0

Z1 (200'000) \u003d P1 (200 "000) \u003d 7068135.2

Z1 (400 "000) \u003d P1 (400" 000) \u003d 2567391.9

Z1 (600 "000) \u003d P1 (600" 000) \u003d 2216151.6

Z1 (800 "000) \u003d P1 (800" 000) \u003d 1222330,8

Z1 (L "OOO" OOO) \u003d P1 (L "000" 000) \u003d 122233,09 pentru indicatorii eficacității a două întreprinderi.

Z 2 (0) \u003d p 2 (0) \u003d 0

Z2 (200 "000) \u003d max (0 + 70 68135,2; 94 07519,6 + 0 )=9407519,6

Z2 (400 "000) \u003d max (0 + 25 67391,9; 94 07519,6 + 70 68135,2 ; 80 92519,9 + 0}=16475654,8

Z2 (600 "000) \u003d max (0 + 22 16151,6; 94 07519,6 +25 67391,9; 80 92519,9 +70 68135,2 ; 80 92353,6 + 0)=15160655,1

Z2 (800 "000) \u003d max (0 + 12 2233,08; 94 07519,6 + 22,16151,6; 80 92519,9 + 25,67391,9; 80 92353,6 + 70 68135,2 : 80 92353,6 + 0}=15160488,8

Z2 (L "000" 000) \u003d max (0 + 12 22330,9; 94 07519,6 + 12,22330,8; 80 92519,9 +22 16151,6; 80 92353,6 + 25 67391,9; 80 92353,6 + 70 68135,2 ; 67 38741,6 + 0}=15160488,8

Pentru eficacitatea a trei întreprinderi.

Z 3 (0) \u003d p 3 (0) \u003d 0

Z3 (200 "000) \u003d max (0 + 94 07519,6; 507 43194,2 + 0 )=50743194,2

Z3 (400 "000) \u003d max (0 + 8092519,9; 507 43194,2 + 94 07519,6 ; 272 10300,4 + 0}=60150713,8

Z 3 (600 "000) \u003d max (0 + 8092353,6; 507 43194,2 + 8092519,9 ; 272 10300,4+94 07519,6; 272 10300,4 + 0}=58835714,1

Z 3 (800 "000) \u003d max (0 + 8092353,6: 507 43194,2 + 8092353,6 ; 272 10300,4 +9407519,6; 272 10300,4 + 8092519,9; 272 10300,5 + 0}= 58835547,8

Z 3 (L "000" 000) \u003d max (0 + 6738741,6; 507 43194,2 + 8092353,6 ; 272 10300,4 + 8092353,6; 272 10300,4 + 8092519,9; 272 10300,5 + 94 07519,6; 27210300,4+0}=58835547,8

Pentru eficacitatea a patru întreprinderi.

Z 4 (0) \u003d P 4 (0) \u003d 0

Z 4 (200 "000) \u003d max ( 0 + 507 43194,2 ; 118 73132,7 + 0}= 507 43194,2

Z4 (400 "000) \u003d max (0 + 27210300,4; 118 73132,7 + 507 43194,2 ; 84 75336,3+0}=62616326,9

Z4 (600 "000) \u003d max (0 + 27210300,4; 118 73132,7 + 27210300,4; 84 75336,3 + 507 43194,2 ; 84 75336,3 + 0}= 59218530,5

Z4 (800 "000) \u003d max (0 + 27 210 300,5; 11 873 132,7 + 27,10 300,4; 8 475 336,3 + 27 210 300,4; 8 475 336,3 + 50 743 194,2 ; 71 37734,9 + 0}=59218530,5

Z4 (L "000" 000) \u003d max (0 + 27210300,4; 118 73132,7 + 27210300,5; 84 75336,3+ 27210300,4; 84 75336,3 + 27210300,4; 71 37734,9 + 507 43194,2 ; 62 83185,8+0}=57880929,1

Pentru eficacitatea a cinci întreprinderi.

Z 5 (0) \u003d P 5 (0) \u003d 0

Z 5 (200 "000) \u003d max ( 0 + 11873132,7 ; 103 07000,5 + 0}= 11873132,7

Z5 (400 "000) \u003d max (0 + 8475336,3; 103 07000,5 + 11873132 ,7; 77 36093,1+ 0}=22180133,2

Z5 (600 "000) \u003d max (0 + 8 475 336,3; 10 307 000,5 + 8 475 336,3; 7 736 093,1+11 873 132,7 ; 7 736 093,2 + 0}=19609225,8

Z5 (800 "000) \u003d max (0 + 7137734,9; 10 307000,5 + 8 4753336,3; 77 36093,1 + 8475336,3; 77 36093,2 + 11873132,7 ; 72 41299,8 + 0}= 19609225,9

Z5 (L "000000) \u003d max (0 + 6283185,8; 103 07000,5 + 7137734,9; 77 36093,1 + 8475336,3; 7736093,2+ 8475336,3; 72 41299,8+11873132,7 ; 71 67372,4+, 0}=19714432,5

După primirea ultimului indicator de performanță, puteți obține o soluție la problemă:

Z5 (1 "000" 000) \u003d 103 07000,5 + 59218530,5 \u003d 69525531.00 Q 1 \u003d 20 000 000P.

Z4 (800 "000) \u003d 118 73132,7 + 58835714.1 \u003d 70708846.80 Q 2 \u003d 20 000 000P.

Z3 (600 "000) \u003d 507 43194,2 + 16475654,8 \u003d 67218849,00 Q 3 \u003d 20 000 000 P.

Z2 (400 "000) \u003d 94 07519,6 + 7068135.2 \u003d 164756548 Q 4 \u003d 20 000 000P.

Z1 (200000) \u003d P! (200 "000) \u003d 70 68135,2 Q 5 \u003d 20 000 000 ° C.

Pentru a obține profitul maxim, resursele alocate ale investitorului (numerar în valoare de 100.000.000 de ruble) ar trebui distribuite după cum urmează - fiecare întreprindere investigată ar trebui alocată la 20.000.000 de ruble. În același timp, indicatorul maxim de performanță combinat va fi de 70 708.846,80 ruble.

Programarea dinamică (DP) este un aparat matematic menit să crească eficiența calculelor atunci când se rezolvă o anumită clasă de probleme de programare matematică prin descompunere (descompunere) pe subtașuri relativ mici și, prin urmare, mai puțin complexe. Caracteristică pentru programarea dinamică este o abordare a soluționării unei sarcini în etape, fiecare dintre care o variabilă controlată este asociată. Un set de proceduri de calculare a recurenței diferite etapeOferă obținerea unei soluții optime admise la problema în general când ultima etapă este atinsă.

Principiul fundamental bazat pe teoria DP este principiul optimității. În esență, aceasta determină procedura de decizie pe etapată prin descompunerea sarcinii (aceasta este o modalitate mai acceptabilă decât soluția imediată a problemei în formularea originală) cu ajutorul procedurilor de calcul de recurență.

Principalele prevederi ale programării dinamice împreună cu notația matematică neobișnuită generează adesea dificultăți în studiul acestei secțiuni de programare matematică. În special, acest lucru se referă la cei care se întâlnesc mai întâi cu subiectul. Cu toate acestea, experiența arată că recursul sistematic la sarcinile și metodele DP, care necesită anumite perseverență, conduce la o înțelegere completă la începutul dispozițiilor neclare. Când se întâmplă acest lucru, programele dinamice începe să pară o teorie surprinzător de simplă și subțire.

Aplicați metoda de programare dinamică pentru distribuirea investițiilor între patru evenimente. Valoarea totală a fondurilor care investesc în dezvoltare nu este de cel mult zece milioane de grivne. Pe baza calculelor tehnice și economice, sa stabilit că, ca urmare a reconstrucției, în funcție de cantitatea de fonduri cheltuite, activitățile vor avea performanța prezentată în tabelul 2.5. Este necesar să se determine distribuția optimă a fondurilor între măsuri, care asigură creșterea maximă a productivității întreprinderii. Astfel, criteriul este utilizat în această sarcină de optimizare - performanța totală a activităților.

Tabelul 2.5 - Datele pentru rezolvarea problemei

Numărul de evenimente	Fondurile investite în dezvoltare

Performanță ca rezultat al dezvoltării (TN)

Direct și, aparent, o modalitate prea simplificată de a rezolva o sarcină formulată este utilizarea procedurii de stingere completă. Sarcina are 4 x 5 \u003d 20 de soluții posibile, iar unele dintre ele nu sunt permise, deoarece este implicată la aproprierea de peste 10 milioane UAH. În procesul de forță brută completă, se calculează costurile totale asociate fiecăruia dintre cele 20 de soluții posibile. În cazul în care costul costurilor nu depășește valoarea fondurilor avansate, ar trebui calculat venitul total corespunzător. Cea mai bună soluție va fi optimă, oferind un maxim de venit total.

Observăm următoarele deficiențe ale procedurii de bustare completă.

(1) Fiecare combinație de proiecte determină o soluție a problemei în ansamblul său, de unde rezultă că bustul tuturor combinațiilor posibile în sarcinile dimensiunii medii și mari poate fi asociat cu un volum excesiv de mare de calcul.
2. Nu există o informație priori privind soluțiile care nu sunt permise, ceea ce reduce eficiența schemei de calcul computaționale.
3. Informațiile obținute ca urmare a analizei unor combinații de proiect nu sunt utilizate pentru a identifica și elimina combinațiile non-optime.

Utilizarea metodelor DP vă permite să eliminați toate defectele enumerate.

Fie x 1, x 2, x 3, x 4 - investiții în dezvoltarea primului, al doilea, al treilea, al patrulea, 0 x i 10000000, i \u003d. Denotă de F1 (x), F 2 (x), F 4 (x) - funcția de schimbare a performanței primului, al doilea, al treilea eveniment al patrulea la investiții în dezvoltarea lor x mln. UAH. Aceste funcții corespund șirurilor 1, 2, 3, 4 din Tabelul 2.5.

Definim funcția maximă a funcției

F (x 1, x 2, x 3, x 4) \u003d F1 (x) + F2 (x) + F3 (x) + F 4 (x).

În același timp, investițiile x1, x2, x3, x4 restricționate

x 1 + x 2 + x 3 + x 4 \u003d A,

Baza metodei de programare dinamică utilizată pentru rezolvarea sarcinii se bazează pe principiul optimității.

În conformitate cu acest principiu, prin alegerea unei distribuții inițiale a resurselor, efectuăm optimizarea cu mai multe etape, iar la pasul apropiat, alegem o astfel de distribuție a resurselor, astfel încât să fie combinată cu distribuția optimă a tuturor etapelor ulterioare pentru câștigul maxim pe toți pașii rămași, inclusiv acest lucru.

Evidențiați 3 pași în sarcina noastră:

- Un milion UAH. Investiți în primul, al doilea eveniment în același timp;
- Un milion UAH. Investiți în primul, al doilea eveniment al treilea împreună;

Un MLN UAH. investit în patru evenimente în același timp;

Denotă: F 1,2 (a), F 1,2,3 (a), F 1,2,3,4 (a), respectiv, distribuția optimă a fondurilor pentru primele pași, al doilea, al treilea.

Algoritmul metodei de programare dinamice constă din două etape. În prima etapă, optimizarea condiționată se efectuează în faptul că pentru fiecare dintre cele trei etape, victoria optimă condiționată F 1.2 (A), F 1,2,3 (A), F 1,2,3,4 (a ) pentru. La a doua etapă, se efectuează optimizarea necondiționată. Folosind rezultatele primei etape, valorile investițiilor se găsesc în dezvoltarea măsurilor x 1, x 2, x 3, x 4 asigurând o performanță maximă a unui grup de activități.

Prima etapă include următorii pași:

1) Calculul criteriului maxim de optimizare pentru diferite valori ale investițiilor de capital X \u003d 0, 2500000, 5000000, 7500000, 10000000, care sunt utilizate numai pentru măsurile 1 și 2. Calculul se efectuează conform formulei (2.4).

Rezultatele de calcul sunt prezentate în tabelul 2.6.

Tabelul 2.6 - Rezultatele calculelor din prima etapă

De exemplu, pentru a determina F 1.2 (5000000), este necesar să se calculeze

f 1 (500.000) + F 2 (0) \u003d 700 + 5000 \u003d 5700;

f 1 (2500000) + F 2 (2500000) \u003d 600 + 6000 \u003d 6600;

f 1 (0) + F 2 (5000000) \u003d 500 + 7000 \u003d 7500.

Restul F L, 2 (x) sunt obținuți ca cea mai mare valoare a fiecărei diagonale din tabel (aceste valori sunt subliniate în tabel):

F 2 (0) \u003d 5500; F 2 (2500000) \u003d max (5600, 6500) \u003d 6500;

F 2 (500.000,000) \u003d max (5700, 6600, 7500) \u003d 7500;

F 2 (7500000) \u003d max (5800, 6700, 7600, 9000) \u003d 9000;

F 2 (10000000) \u003d max (5900, 6800, 7700, 9100, 1500) \u003d 9100;

2) Calculul criteriului maxim de optimizare pentru diferite valori ale investițiilor de capital X \u003d 0, 2500000, 5000000, 7500000, 10000000, care sunt utilizate numai pentru activitățile 1.2 și 3.

Calculul se bazează pe formula (2.5).

Rezultatele de calcul sunt enumerate în Tabelul 2.7, care este similar cu tabelul 2.6, numai în loc de F1 (x), valorile F2 (A), A F2 (A - X) sunt înlocuite cu F3 ( A - X).

Tabelul 2.7 - Rezultatele calculelor la a doua etapă

Valorile F 1,2,3 (A) vor fi după cum urmează:

F 1,2,3 (0) \u003d 8600; F 1,2,3 (2500000) \u003d 9600; F 1,2,3 (5000000) \u003d 10600;

F 1,2,3 (7500000) \u003d 12100; F 1,2,3 (10000000) \u003d 12200.

3) Calculul criteriului maxim de optimizare pentru diferite valori ale investițiilor de capital x \u003d 0, 2500000, 5000000, 7500000, 10000000, care sunt utilizate pentru activități 1.2, 3, 4.

Calculul se bazează pe formula (2.6).

Rezultatele calculelor vor fi aduse în tabelul 2.8.

Tabelul 2.8 - Rezultatele calculelor din a treia etapă

Valorile F 1,2,3,4 (A) vor fi după cum urmează:

F 1,2,3,4 (0) \u003d 9300; F 1,2,3,4 (2500000) \u003d 10300; F 1,2,3,4 (500.000,000) \u003d 11300;

F 1,2,3,4 (7500000) \u003d 12800; F 1,2,3,4 (10000000) \u003d 12900.

În acest moment, prima etapă de rezolvare a sarcinii de programare dinamică se încheie.

Să mergem la a doua etapă de rezolvare a problemei programării dinamice - optimizarea necondiționată. În această etapă, sunt utilizate tabelele 2.6, 2.7, 2.8. Definim investiții optime în dezvoltarea întreprinderilor pentru a \u003d 0, 2500000, 5000000, 7500000, 10.000.000. Pentru a face acest lucru, vom efectua următoarele calcule:

1) Lăsați valoarea investiției alocate dezvoltării întreprinderilor, este A \u003d 10.000.000 UAH.

Definim suma investițiilor de capital pe dezvoltarea celui de-al patrulea eveniment. Pentru a face acest lucru, utilizați Tabelul 2.8. Alegeți o diagonală care corespunde lui A \u003d 10000000 este valorile lui 12900, 12900, 11500, 10550, 9600. Din aceste numere, luăm maximul F 1,2,3,4 (10000000) \u003d 12900 tone. Noi coloana în care valoarea acestei valori merită. Apoi, definim în coloana marcată a investiției în al patrulea eveniment X 4 \u003d 2500000.

Dezvoltarea primului, al doilea și al treilea eveniment rămâne

A \u003d 10000000 - x 4 \u003d 2500000 UAH.

2) Definim suma investițiilor de capital alocate dezvoltării celui de-al treilea eveniment.

Pentru a face acest lucru, utilizați Tabelul 2.7. Selectați diagonalul din acest tabel corespunzător la A \u003d 7500000 este valori de 12100, 10700, 9800, 8900. Observăm coloana în care performanța maximă (subliniată) F 1,2,3 (7500000) \u003d 12100 tone. Determinați x 3 \u003d 0 UAH. În coloana marcată.

Al treilea eveniment nu vom finanța.

3) Definim suma investiției în dezvoltarea celui de-al doilea eveniment. Pentru a face acest lucru, utilizați Tabelul 2.6. Alegem o diagonală pe ea, care corespunde lui A \u003d 75000000 - este de 5800, 6700, 7600, 9000. Din aceste numere, ia maximul F 1.2 (75000000) \u003d 9000 t. Observăm coloana în care merită această valoare. Apoi, determinăm în coloana marcată volumul investițiilor în al doilea eveniment X 2 \u003d 7500000.

Astfel, pentru investițiile de capital, A \u003d 10000000 UAH. OPTIMAL este investiția în dezvoltarea celui de-al patrulea eveniment 2500.000 UAH, al doilea - 7.500.000 UAH, dezvoltarea primului și al treilea eveniment, fondurile nu sunt alocate. În același timp, performanța totală a patru întreprinderi va fi de 12900 de tone.

Repetarea calculelor celei de-a doua etape a soluției pentru A \u003d 3, 2, 1, 0, definim investiția optimă în dezvoltarea activităților. Rezultatele vor fi după cum urmează:

F 1,2,3,4 (7500000) \u003d 12800; x 1 \u003d 0; x 2 \u003d 7500000; x 3 \u003d 0; X 4 \u003d 0

F 1,2,3,4 (5000000) \u003d 11300; x 1 \u003d 0; x 2 \u003d 5000000; x 3 \u003d 0; x 4 \u003d 0

F 1,2,3,4 (2500000) \u003d 10300; x 1 \u003d 0; X 2 \u003d 250000; x 3 \u003d 0; X 4 \u003d 0

F 1,2,3,4 (0) \u003d 9300; x 1 \u003d 0; x 2 \u003d 0; x 3 \u003d 0; X 4 \u003d 0

Programarea dinamică este un aparat matematic conceput pentru a rezolva în mod eficient o anumită clasă de sarcini de programare matematică. Această clasă se caracterizează prin posibilitatea de a diviza naturală (și, uneori) întreaga operațiune într-un număr de etape interdependente. Termenul "dinamic" din titlul metodei a apărut, aparent deoarece etapele sunt presupuse a fi separate în timp. Cu toate acestea, pașii pot fi elementele operației, în niciun fel legate între ele. Cu toate acestea, metoda de rezolvare a unor astfel de sarcini cu mai multe etape este aplicată în același timp, iar numele său a devenit general acceptat, deși în unele surse se numește programare cu mai multe etape.

Pentru a determina esența programării dinamice, luați în considerare sarcina:

Imaginați-vă o anumită operațiune pe o serie de "pași" consecutivi sau etape, de exemplu, activitățile din industrie în timpul unui număr de ani de afaceri. Lăsați numărul de pași egali cu m. Câștigarea (eficiența operației) Z pentru întreaga operațiune este alcătuită din câștiguri pe pașii individuali:

unde Zi câștigă pe pasul I-m.

Dacă Z are o astfel de proprietate, se numește un criteriu aditiv.

Operațiunea o este un proces gestionat, adică putem alege unii parametri care afectează mișcarea și rezultatul și la fiecare etapă, soluția este selectată dintre care depind câștigurile de acest pas și câștigul pentru operație ca întreg . Aceste soluții sunt numite pas cu pas.

Combinația dintre toate controalele pas cu pas este funcționarea operațiunii în ansamblu. Denotă de litera X și controalele pas cu pas ale literelor x1, x2, ..., xm: x \u003d x (x1, x2, ..., xm). Este necesar să găsiți astfel de controale x, în care câștigul este atras de maximum:

Acest control X *, în care acest maxim este atins, se numește control optim. Se compune dintr-un set de pasari optimi: x * \u003d x * (x1 *, x2 *, ..., xm *).

Câștigul maxim, care se realizează cu controlul, denotăm după cum urmează:
,

unde x-set permisibil (posibil) controale.

Cea mai ușoară modalitate de a rezolva problema este plină de toate opțiunile. Când numărul de opțiuni este mic, această metodă este destul de acceptabilă. Cu toate acestea, în practică, sarcina cu un număr mic de opțiuni este foarte rară, astfel încât bustul complet este, de obicei, inacceptabil din cauza costurilor excesive ale resurselor de calcul. Prin urmare, în astfel de cazuri, programarea dinamică vine la salvare.

Metoda de programare dinamică poate fi utilizată numai pentru o anumită clasă de sarcini. Aceste sarcini ar trebui să îndeplinească astfel de cerințe:

Sarcina de optimizare este interpretată ca un proces de gestionare a n-pas.
Funcția țintă este egală cu suma funcțiilor țintă a fiecărui pas.
Selectarea controalelor în pasul K-M depinde de starea sistemului la această etapă, nu afectează pașii precedenți (fără feedback).
Statul SK după pasul de control K depinde numai de starea anterioară a XK SK-1 (nr. După urmărire).
La fiecare pas, controlul XK depinde de numărul finit de variabile de control, iar statul SK este de la numărul final de parametri.

Soluția tuturor sarcinilor de programare dinamică se află "Principiul optimității" Bellmancare arată astfel:

Oricare ar fi starea sistemului s ca rezultat al oricărui număr de pași, în pasul apropiat trebuie să alegeți controlul astfel încât să fie în combinație cu controlul optim la toate etapele ulterioare, a condus la câștigarea optimă a tuturor pașilor rămași, inclusiv acest lucru.

Acest principiu a fost formulat mai întâi de R. Belman în 1953. Bellman a fost formulat clar de condițiile în care principiul credincioșilor. Cerința principală este procesul de gestionare trebuie să fie fără feedback, adică Managementul în această etapă nu ar trebui să afecteze pașii precedenți.

Principiul optimalității susține că, pentru orice proces fără feedback, gestionarea optimă a acestui lucru este că este optimă pentru orice subproces în raport cu starea inițială a acestei subproces. Prin urmare, soluția la fiecare pas este cea mai bună în ceea ce privește managementul în ansamblu.

"Programarea dinamică în rezolvarea sarcinilor de producție". TUTORIAL: programare dinamică în sarcinile economice

2.1. Sarcina distribuției investițiilor

Ultimul

Este necesar să știți