2. Categorii ale unei teorii a controlului destul de generală În teoria controlului, este posibil să punem doar două probleme · Prima sarcină: dorim să controlăm singuri obiectul în procesul de funcționare a acestuia. Aceasta.· A doua sarcină: nu dorim să gestionăm obiectul în timp ce acesta este în curs

14. Metoda programării dinamice ca expresie algoritmică a unei teorii a controlului destul de generală În prezentarea esenței metodei programării dinamice, ne bazăm pe cartea „Curs de teoria controlului automat” (autor Palud de La Barriere: limba franceza

Mulțumiri Programul de învățare accelerată „Proiectul Renaștere” - tema principală a acestei cărți - a început să fie implementat în urmă cu 25 de ani datorită eforturilor unui număr imens de oameni, pionieri în domeniul studierii conștiinței umane, celor care au luat parte la

3. Pe drumul către Teoria Generală În același timp, Revoluția Rusă a fost percepută de el ca un avertisment serios. Cu toată atitudinea lui negativă față de ea, Keynes s-a interesat din ce în ce mai mult de problemele pe care le-a înaintat, iar acest lucru nu a putut să nu-i ascute atenția asupra unui aspect mai larg.

Programarea dinamică (altfel „planificare dinamică”) este o metodă specială de optimizare a soluțiilor, special adaptată la așa-numitele operațiuni „multi-step” (sau „multi-stage”).

Să ne imaginăm o operațiune Ơ, defalcarea într-un număr de „etape” sau „etape” succesive - de exemplu, activitatea unei industrii pe un număr de ani economici; sau un grup de aeronave care depășește mai multe zone de apărare aeriană; sau o succesiune de teste utilizate pentru controlul echipamentului. Unele operații (cum ar fi cele de mai sus) sunt împărțite în pași în mod natural; în unele, diviziunea trebuie introdusă artificial - de exemplu, procesul de îndreptare a rachetei către o țintă poate fi împărțit în etape, fiecare dintre acestea durând ceva timp.

Deci, să luăm în considerare operația Ơ , constând din T Etape (etape). Fie ca eficacitatea operațiunii să fie caracterizată de un anumit indicator W, pe care îl vom numi „câștig” pentru concizie în acest capitol. Să presupunem că câștigurile W pentru întreaga operațiune constă în câștiguri la pași individuali:

Unde Wi - câștiguri pentru eu- al-lea pas.

Dacă W are această proprietate, se numește „criteriul aditiv”.

Operațiune Oh ohîn cauză este un proces controlat, adică putem alege câțiva parametri care îi influențează cursul și rezultatul, iar la fiecare pas este selectată o soluție, pe baza căreia profitul la acest pas și profitul pentru operațiune în general. Vom numi această soluție „control în etape”. Setul tuturor comenzilor pas reprezintă controlul operației în ansamblu. Să o notăm prin literă X,și comenzile pasului - litere X1, x2, …,Xm:

X = (X1 , X2 , …, Xm). (12.2)

Trebuie avut în vedere faptul că X1, x2, …., Xmîn cazul general - nu numere, ci poate vectori, funcții etc.

Trebuie să găsim un astfel de control X, la care câştigul W se transformă la maxim:

Acel control X*, la care se atinge acest maxim se va numi control optim. Acesta constă dintr-un set de comenzi optime pentru pași:

X* =(). (12.4)

Vom nota castigul maxim care se obtine cu acest control W*:

W* = {W(X)} . (12.5)

Formula (12.5) se citește astfel: cantitate W* există un maxim de toate W{ X} sub diferite controale X(maximul este preluat peste toate controalele X, posibil în condițiile date). Uneori, acesta din urmă este specificat în formulă și scris:

Să ne uităm la câteva exemple de operații în mai multe etape și pentru fiecare dintre ele vom explica ce se înțelege prin „control” și care este „câștigul” (indicator de performanță) W.

1. Sunt planificate activitățile unui grup de întreprinderi industriale P1, P2, ..., P K pentru o perioadă de T ani de afaceri ( M-letka). La începutul perioadei au fost alocate unele fonduri pentru dezvoltarea grupului M, care trebuie cumva distribuite între întreprinderi. În timpul funcționării întreprinderii, fondurile investite în aceasta sunt parțial cheltuite (amortizate) și parțial salvate și pot fi redistribuite. Fiecare întreprindere generează venituri pe an, în funcție de câți bani sunt investiți în ea. La începutul fiecărui an de activitate, fondurile disponibile sunt redistribuite între întreprinderi. Se pune întrebarea: câți bani ar trebui alocați fiecărei întreprinderi la începutul fiecărui an, astfel încât venitul total pentru T ani a fost maximul?

Câștigând W(venitul total) este suma veniturilor la etapele individuale (ani):

Și, prin urmare, are proprietatea de aditivitate.

Control Xeu pe eu-al doilea pas este acela de la început euth an, unele fonduri sunt alocate întreprinderilor Xeu1 , Xeu2 , …, XIk (primul index este numărul pasului, al doilea este numărul întreprinderii). Astfel, controlul pasului este un vector cu K componente:

Xi = (Xi1 , Xi2 , …, Xik). (12.7)

Desigur, cantitățile Wiîn formula (12.6) depind de suma fondurilor investite în întreprindere.

Control Xîntreaga operațiune constă dintr-un set de toate comenzile pașilor:

X = (X1 , X2 , …, Xm ). (12.8)

Este necesar să se găsească o astfel de distribuție a fondurilor pe întreprindere și pe an (gestionare optimă X* ), la care valoarea W se întoarce la maxim.

În acest exemplu, controalele pasului au fost vectori; în exemplele ulterioare ele vor fi mai simple și vor fi exprimate simplu ca numere.

2. O rachetă spațială este formată din T etape, iar procesul de punere pe orbită este de la M etape, la sfârșitul fiecăreia dintre ele se resetează următoarea etapă. Toate etapele (fără a lua în considerare greutatea „utilă” a cabinei) li se alocă o anumită greutate totală:

G = G1 + G2 + … + Gmm,

Unde Gi - greutate eu etapa a.

Ca urmare eu a treptei (arderea și deversarea primei etape), racheta primește o creștere de viteză în funcție de greutatea acestei etape și de greutatea totală a tuturor celor rămase plus greutatea cabinei. Întrebarea este cum să distribuiți greutatea Gîntre etape astfel încât viteza rachetei V era la maxim când a fost lansat pe orbită?

În acest caz, indicatorul de eficiență (câștig) va fi

V = (12.9)

Unde este câștigul (creșterea vitezei) per eu- al-lea pas. Control X reprezintă un set de greutăți ale tuturor etapelor Gi:

X = (Gi, Gi, …, Gmm).

Control optim X* va fi distribuția greutăților pe trepte la care viteza V maxim. În acest exemplu, controlul pasului este un singur număr, și anume ponderea unui pas dat.

3. Proprietarul mașinii îl operează pentru T ani. La începutul fiecărui an, el poate lua una dintre cele trei decizii:

1) vindeți mașina și înlocuiți-o cu una nouă;

2) reparați-l și continuați funcționarea;

3) continuați funcționarea fără reparații.

Controlul pasului - alegerea uneia dintre aceste trei soluții. Ele nu sunt exprimate direct în numere, dar puteți atribui valoarea numerică 1 primului, 2 celui de-al doilea și 3 celui de-al treilea Ce decizii trebuie luate pe an (adică, cum să alternați controalele 1, 2, 3) astfel încât costurile totale de operare, reparare și achiziție de mașini noi să fie minime?

Indicatorul de eficiență (în acest caz nu este „câștig”, ci „pierdere”, dar asta nu contează) este egal cu

W = (12.10)

Unde Wi - cheltuieli în eu- al-lea an. mărimea W trebuie redusă la minimum.

X = (3, 3, 2, 2, 2, 1, 3, …),

Ceea ce înseamnă: operați mașina fără reparații în primii doi ani, reparați-o în următorii trei ani, vindeți-o la începutul celui de-al șaselea an, cumpărați una nouă, apoi utilizați-o din nou fără reparații etc. Orice control este un vector (un set de numere):

X = (J1 , J2 , …; Jm), (12.11)

Unde sunt fiecare dintre numere J1 , J2 , …, Jm are una dintre cele trei valori: 1, 2 sau 3. Este necesar să se selecteze un set de numere (12.11) pentru care valoarea (12.10) este minimă.

4. O porțiune de cale ferată este așezată între puncte A și B (Fig. 12.1). Terenul este accidentat, incluzând zone împădurite, dealuri, mlaștini și un râu peste care trebuie construit un pod. Se cere trasarea drumului din A și B, astfel încât costurile totale ale construcției șantierului să fie minime.

În această problemă, spre deosebire de cele trei anterioare, nu există o împărțire naturală în pași: trebuie introdusă artificial, pentru care, de exemplu, puteți utiliza un segment. ABîmparte la T părți, trageți linii drepte perpendiculare pe punctele de diviziune AB,și socotiți drept „pas” trecerea de la o astfel de linie dreaptă la alta. Dacă le apropiați suficient unul de celălalt, atunci la fiecare pas puteți considera că secțiunea de cale este dreaptă. Controlul pasului la pasul i este un unghi care formează o secțiune a căii cu o linie dreaptă AB. Controlul întregii operațiuni constă dintr-un set de comenzi pași:

X = ().

Este necesar să alegeți un astfel de control (optim). X*, la care costurile totale pentru construcția tuturor secțiunilor sunt minime:

W = => Min . (12.12)

Până acum am analizat câteva exemple de probleme de cercetare operațională în mai multe etape. Acum să vorbim despre cum poți rezolva acest tip de problemă?

Orice problemă cu mai mulți pași poate fi rezolvată în moduri diferite: fie căutați toate elementele soluției simultan pentru totdeauna M pași, sau construiți controlul optim pas cu pas, optimizând doar un pas la fiecare etapă a calculului. De obicei, a doua metodă de optimizare se dovedește a fi mai simplă decât prima, mai ales cu un număr mare de pași.

Această idee de optimizare graduală, pas cu pas, stă la baza metodei de programare dinamică. Optimizarea unui pas, de regulă, este mai simplă decât optimizarea întregului proces: se dovedește că este mai bine să rezolvi o problemă relativ simplă de mai multe ori decât să rezolvi o singură dată una complexă.

La prima vedere, ideea poate părea destul de banală. De fapt, ceea ce ar părea mai simplu:

Dacă este dificil să optimizați operațiunea în ansamblu, împărțiți-o într-o serie de pași. Fiecare astfel de pas va fi o operațiune mică, separată, care nu este greu de optimizat. Este necesar să alegeți un astfel de control la acest pas încât eficiența acestui pas să fie maximă. Nu-i așa?

Nu, deloc așa! Principiul programării dinamice nu implică deloc ca fiecare pas să fie optimizat separat, independent de ceilalți. Dimpotrivă, controlul pasului trebuie ales cu prevedere, ținând cont de toate consecințele sale în viitor. Ce rost are dacă alegem la acest pas un control care să maximizeze eficiența acestui pas, dacă acest pas ne lipsește de oportunitatea de a câștiga bine la pașii ulterioare?

Să fie planificată, de exemplu, activitatea unui grup de întreprinderi industriale, dintre care unele sunt angajate în producția de bunuri de larg consum, iar restul produc mașini pentru ele. Obiectivul operației este obținerea T ani volumul maxim de producție de bunuri de larg consum. Să presupunem că investițiile de capital sunt planificate pentru primul an. Pe baza intereselor înguste ale acestui pas (an), ar trebui să investim toate fondurile disponibile în producția de bunuri de larg consum. Dar o astfel de decizie va fi corectă din punct de vedere al eficacității operațiunii în ansamblu? Evident nu. Această decizie este risipitoare și miop. Având în vedere viitorul, este necesar să se aloce o parte din fonduri pentru producția de mașini. Acest lucru va reduce, desigur, volumul producției în primul an, dar se vor crea condiții pentru creșterea acesteia în anii următori.

Alt exemplu. Să presupunem că în sarcina 4 (așezarea unei căi ferate din A V ÎN) suntem sedusi de ideea de a ne repezi imediat in directia cea mai usoara (cea mai ieftina). La ce folosește economisirea la primul pas dacă în viitor ne va conduce (la propriu sau la figurat) într-o „mlaștină”?

Mijloace, Atunci când planificați o operațiune în mai multe etape, este necesar să alegeți controlul la fiecare pas, ținând cont de toate consecințele sale viitoare la pașii care urmează. Management activat eu Al treilea pas este ales nu astfel încât câștigurile la acest pas anume să fie maxime, ci astfel încât suma câștigurilor la toate etapele rămase până la final plus aceasta să fie maximă.

Cu toate acestea, există o excepție de la această regulă. Printre toți pașii, există unul care poate fi planificat simplu, fără a ține cont de viitor. Ce pas este acesta? Evident, ultimul! Acest pas, singurul dintre toate, poate fi planificat astfel încât el însuși, ca atare, să aducă cel mai mare beneficiu.

Prin urmare, procesul de programare dinamică se desfășoară de obicei de la sfârșit la început: în primul rând, ultimul este planificat, M- al-lea pas. Cum îl putem planifica dacă nu știm cum s-a terminat penultimul? Adică nu știm condițiile în care începem ultimul pas?

Aici începe cel mai important lucru. Când planificați ultimul pas, trebuie să faceți ipoteze diferite despre modul în care s-a încheiat penultimul, (T - Pasul 1) și pentru fiecare dintre aceste ipoteze găsiți controlul optim condiționat pe M-a treaptă („condițională” pentru că se alege pe baza condiției ca penultimul pas să se încheie într-un fel și așa).

Să presupunem că am făcut acest lucru și, pentru fiecare dintre rezultatele posibile ale penultimului pas, cunoaștem controlul optim condiționat și profitul optim condiționat corespunzător pe M- al-lea pas. Grozav! Acum putem optimiza controlul pe penultimul, (T- 1) pasul. Din nou, să facem toate ipotezele posibile despre cum s-a terminat precedenta, ( M- al 2-lea pas, iar pentru fiecare dintre aceste ipoteze găsim un astfel de control asupra ( M— 1) al-lea pas, în care plata pentru ultimii doi pași (din care M-a este deja optimizată!) este maximă. Deci găsim pentru fiecare rezultat ( M— 2)- pas condițional control optim pe (T - Pasul 1) și recompensa optimă condiționată la ultimii doi pași. În continuare, „în spate”, optimizăm controlul prin ( M- al 2-lea pas etc., până ajungem la primul.

Să presupunem că cunoaștem toate controalele optime condiționate și plățile optime condiționate pentru întreaga „coadă” a procesului (la toți pașii, începând de la cel dat până la sfârșit). Aceasta înseamnă: știm ce trebuie făcut, cum să ne descurcăm în acest pas și ce vom obține pentru el la „coadă”, indiferent de starea în care se afla procesul la începutul pasului. Acum putem construi nu un control optim condiționat, ci pur și simplu un control optim X*și nu găsiți optimul condiționat, ci pur și simplu câștigul optim W*.

Într-adevăr, spune-ne în ce stare S0 exista un sistem controlat (obiect de control S) la începutul primului pas. Apoi putem alege controlul optim în primul pas. Prin aplicarea acestuia, vom schimba starea sistemului cu una nouă; în această stare ajungem la a doua etapă. Apoi cunoaștem și controlul optim condiționat , care până la sfârșitul celui de-al doilea pas transferă sistemul în starea , etc. În ceea ce privește câștigul optim W* pentru întreaga operațiune, atunci ne este deja cunoscut: la urma urmei, pe baza maximului ei am ales managerul la primul pas.

Astfel, în procesul de optimizare a controlului folosind metoda de programare dinamică, procesul în mai multe etape este „traversat” de două ori: prima dată - de la sfârșit la început, în urma căruia controale optime condiționate și plăți optime condiționate pentru restul „ se găsesc coada” procesului; a doua oară - de la început până la sfârșit, când tot ce trebuie să facem este să „citim” recomandări gata făcute și să găsim controlul optim necondiționat X*, constând din controale optime în trepte

Prima etapă - optimizarea condiționată - este incomparabil mai dificilă și mai lungă decât a doua. A doua etapă nu necesită aproape niciun calcul suplimentar.

Autorul nu se măgulește cu speranța că dintr-o astfel de descriere a metodei de programare dinamică, un cititor care nu l-a întâlnit până acum va înțelege cu adevărat ideea lui. Adevărata înțelegere apare atunci când luăm în considerare exemple specifice, la care vom trece mai departe.

Printre problemele rezolvate folosind programarea matematică, se poate distinge o clasă separată de probleme care necesită optimizarea proceselor în mai multe etape (mai multe etape). Astfel de probleme se disting prin posibilitatea de a împărți soluția în mai multe etape interconectate. Pentru a rezolva astfel de probleme, se folosește programarea dinamică sau, așa cum se mai numește, programarea în mai multe etape. Metodele sale sunt optimizate pentru a găsi soluția optimă la problemele cu mai multe etape care pot fi împărțite în mai multe etape, pași etc.

Originea termenului

Folosirea cuvântului „dinamic” în nume a implicat inițial că împărțirea în subsarcini ar avea loc în primul rând în timp. Când se utilizează metode dinamice pentru a rezolva probleme de producție, economice și de altă natură în care apare factorul timp, împărțirea lui în etape separate nu este dificilă. Dar este posibil să se utilizeze tehnici de programare dinamică în sarcini în care etapele individuale nu sunt legate în timp. Într-o problemă cu mai mulți pași, puteți selecta oricând un parametru sau o proprietate care poate fi folosită pentru a o împărți în pași separati.

Algoritm (metodă) pentru rezolvarea problemelor în mai multe etape

Algoritmul sau metoda de programare dinamică se bazează pe principiul optimizării secvențiale a unei probleme, atunci când soluția unei probleme generale este împărțită într-un număr de soluții la subprobleme individuale și apoi combinată într-o singură soluție. Foarte des, subproblemele individuale se dovedesc a fi aceleași, iar o soluție generală reduce semnificativ timpul de calcul.

O caracteristică a metodei este autonomia de rezolvare a problemei în fiecare etapă individuală, adică indiferent de modul în care procesul a fost optimizat și rezolvat în etapa anterioară, în calculul curent sunt utilizați doar parametrii procesului care o caracterizează în prezent. De exemplu, un șofer care se deplasează de-a lungul drumului ia o decizie cu privire la virajul curent, indiferent de cât și cât timp a condus înainte.

Metoda de sus și metoda de jos

În ciuda faptului că, atunci când se calculează într-o etapă separată de rezolvare a unei probleme, sunt utilizați parametrii procesului în momentul actual, rezultatul optimizării din etapa anterioară afectează calculele etapelor ulterioare pentru a obține cel mai bun rezultat în ansamblu. Programarea dinamică numește acest principiu de soluție metoda optimității, care determină ca strategia optimă de rezolvare a unei probleme, indiferent de deciziile și condițiile inițiale, trebuie urmată de decizii ulterioare în toate etapele pentru a crea o strategie optimă în raport cu starea inițială. După cum putem vedea, procesul de rezolvare a unei probleme este o optimizare continuă a rezultatului în fiecare etapă individuală de la prima până la ultima. Această metodă se numește metoda de programare de sus în jos. Figura prezintă schematic algoritmul soluției de sus în jos. Dar există o clasă de probleme cu mai multe etape în care efectul maxim la ultima etapă este deja cunoscut, de exemplu, am ajuns deja de la punctul A la punctul B și acum vrem să aflăm dacă am condus corect la fiecare precedent stadiu sau dacă ceva ar fi putut fi făcut mai optim. Apare o succesiune recursivă de etape, adică mergem, parcă, „din direcția opusă”. Această metodă de soluție se numește „metoda de programare de jos în sus”.

Uz practic

Programarea dinamică poate fi utilizată în orice domeniu de activitate în care există procese care pot fi împărțite într-un număr de etape mici identice în funcție de un anumit parametru (timp, cantitate, temperatură etc.). Metodele de soluție dinamică sunt cele mai utilizate în teoria controlului și în dezvoltarea sistemelor informatice.

Găsirea căii optime

Folosind optimizarea dinamică, este posibil să se rezolve o clasă largă de probleme de găsire sau optimizare a căii celei mai scurte și alte probleme în care metoda „clasică” de enumerare a posibilelor opțiuni de soluție duce la o creștere a timpului de calcul și uneori este complet inacceptabilă. Problema clasică de programare dinamică este problema rucsacului: dat fiind un anumit număr de obiecte cu o anumită masă și cost, și este necesar să se selecteze un set de obiecte cu costul și masa maximă care să nu depășească volumul rucsacului. O căutare clasică a tuturor opțiunilor în căutarea soluției optime va dura considerabil, dar cu ajutorul metodelor dinamice problema este rezolvată într-un interval de timp acceptabil. Problemele de găsire a celei mai scurte căi pentru logistica transportului sunt de bază, iar metodele de soluții dinamice sunt optim potrivite pentru rezolvarea acestora. Cel mai simplu exemplu al unei astfel de sarcini este construirea celui mai scurt traseu folosind un navigator GPS pentru mașină.

Productie

Programarea dinamică este utilizată pe scară largă în rezolvarea unei varietăți de probleme de producție, cum ar fi gestionarea stocurilor pentru a menține numărul necesar de componente la un moment dat, programarea procesului de producție, rutina și revizia echipamentelor, volumul de lucru uniform al personalului, cea mai eficientă distribuție. a fondurilor de investiții, etc. Pentru a rezolva problemele de producție folosind metode de programare dinamică, au fost dezvoltate pachete speciale de software care sunt integrate în sistemele populare de management al întreprinderilor, cum ar fi SAP.

Domeniul stiintific

Metodele de programare dinamică sunt utilizate pe scară largă în diverse cercetări științifice. De exemplu, sunt utilizați cu succes în algoritmii de recunoaștere a vorbirii și a imaginilor, atunci când procesează cantități mari de date în sociologie și

ABSTRACT

„Metode de dinamică

programare”.

INTRODUCERE

În zilele noastre, știința acordă o atenție din ce în ce mai mare problemelor de organizare și management, ceea ce duce la necesitatea analizei proceselor complexe cu scop din punctul de vedere al structurii și organizării lor. Nevoile practicii au dat naștere unor metode speciale care sunt combinate convenabil sub denumirea de „cercetare operațională”. Acest termen se referă la utilizarea metodelor matematice, cantitative pentru a justifica deciziile în toate domeniile activității umane intenționate.

Scopul cercetării operaționale este de a identifica cel mai bun curs de acțiune pentru a rezolva o anumită problemă. Rolul principal în acest caz este dat modelării matematice. Pentru a construi un model matematic, este necesar să aveți o înțelegere strictă a scopului funcționării sistemului studiat și să aveți informații despre restricțiile care determină intervalul de valori admisibile. Scopul și constrângerile trebuie reprezentate ca funcții.

În modelele de cercetare operațională, variabilele de care depind constrângerile și funcția obiectivă pot fi discrete (cel mai adesea întregi) sau continue (continue). La rândul lor, restricțiile și funcțiile obiective sunt împărțite în liniare și neliniare. Există diverse metode de rezolvare a acestor modele, cele mai cunoscute și eficiente dintre ele sunt metodele de programare liniară, când funcția obiectiv și toate constrângerile sunt liniare. Pentru rezolvarea altor tipuri de modele matematice se urmăresc metode de programare dinamică, programare cu numere întregi, programare neliniară, optimizare multicriterială și metode de model de rețea.

Aproape toate metodele de cercetare operațională generează algoritmi de calcul care sunt de natură iterativă. Aceasta presupune că problema se rezolvă secvenţial (iterativ), când la fiecare pas (iteraţie) obţinem o soluţie care converge treptat către soluţia optimă.

Natura iterativă a algoritmilor duce de obicei la calcule mari, repetitive. Acesta este motivul pentru care acești algoritmi sunt dezvoltați în primul rând pentru implementarea computerului.

CONCEPTE ȘI NOTAȚII DE BAZĂ ALE PROGRAMĂRII DINAMICE

Programarea dinamică este o metodă matematică de găsire a controlului optim, adaptată special proceselor în mai multe etape. Să ne uităm la un exemplu de astfel de proces.

Să fie planificate activitățile unui grup de întreprinderiNani. Aici pasul este de un an. La începutul anului I sunt alocate fonduri pentru dezvoltarea întreprinderilor, care trebuie cumva repartizate între aceste întreprinderi. În procesul de funcționare a acestora, fondurile alocate sunt parțial cheltuite. Fiecare întreprindere generează un anumit venit pe an, în funcție de fondurile investite. La începutul anului, fondurile disponibile pot fi redistribuite între întreprinderi: fiecăreia dintre ele i se alocă o anumită cotă din fonduri.

Se pune întrebarea: cum se distribuie fondurile disponibile între întreprinderi la începutul fiecărui an, astfel încât venitul total din toate întreprinderile pentruNani a fost maximul?

Ne confruntăm cu o problemă tipică de programare dinamică, care are în vedere un proces controlat - funcționarea unui grup de întreprinderi. Managementul procesului constă în distribuirea (și redistribuirea) fondurilor. Acțiunea de control (IC) este alocarea unor fonduri către fiecare dintre întreprinderi la începutul anului.

HC la fiecare pas trebuie selectat luând în considerare toate consecințele sale în viitor. HC trebuie să gândească înainte, ținând cont de viitor. Nu are rost să alegeți cel mai bun CS la pasul luat în considerare dacă în viitor acest lucru va interfera cu obținerea celor mai bune rezultate din alte etape. La fiecare pas trebuie selectat HC „cprivind în viitor”, altfel sunt posibile greșeli grave.

Într-adevăr, să presupunem că în grupul de întreprinderi luate în considerare, unele sunt angajate în producția de bunuri de larg consum, în timp ce altele produc mașini în acest scop. Mai mult, scopul este de a primiNani de producție maximă de bunuri de larg consum. Să planificăm investițiile de capital pentru primul an. Pe baza intereselor lor înguste ale acestui pas (an), ar trebui să investim toate resursele în producția de bunuri de larg consum, să punem mașinile existente la capacitate maximă și să atingem volumul maxim de producție până la sfârșitul anului. Dar o astfel de decizie va fi corectă în general? Evident nu. Ținând cont de viitor, este necesar să se aloce o parte din fonduri pentru producția de mașini. În același timp, volumul producției pentru primul an va scădea în mod firesc, dar se vor crea condiții care să permită creșterea producției sale în anii următori.

În formalismul rezolvării problemelor prin metoda programării dinamice se vor folosi următoarele notații:

N– numărul de pași.

– vector care descrie starea sistemului lak- al-lea pas.

– starea inițială, adicăcStarea la primul pas.

– starea finală, adică starea din ultimul pas.

X k – zona stărilor permise pek- al-lea pas.

– Vector HC activatk-al-lea pas, asigurarea trecerii sistemului de la statX k -1 intr-o stareX k .

U k – zona undelor de șoc permise lak- al-lea pas.

W k – suma câștigului primit ca urmare a vânzăriik- al-lea pas.

S– câștiguri totale pentruNtrepte.

– vector de strategie optimă de control sau OCS pentruNtrepte.

S k +1 ( ) – câștigul maxim obținut la trecerea din orice stare la starea finală cu o strategie de control optimă începând de la (k+1) al-lea pas.

S 1 ( ) – câștigurile maxime primite ptNpași când sistemul trece de la starea inițială până la capăt la implementarea unei strategii optime de control . Este evident căS = S 1 ( ), Dacă -fix.

Metoda de programare dinamică se bazează pe condiția absenței efectelor secundare și condiția aditivității funcției obiectiv.

Fără condiție ulterioară. Stat , la care sistemul s-a mutat într-unulk-al-lea pas, depinde de stat și HC selectat și nu depinde de modul în care sistemul a ajuns la stat , acesta este

La fel, suma câștigurilorW k depinde de stare și HC selectat , acesta este

Condiție de aditivitate a funcției obiectiv.Câștiguri totale pentruNpașii se calculează prin formula

Definiție. Strategia optimă de management numit un set de unde de șoc , acesta este , ca urmare a implementării căreia sistemulNtrepte se deplasează din starea inițială până la capăt și în același timp câștigul totalSia cea mai mare valoare.

Condiția absenței efectelor secundare ne permite să formulăm principiul optimității Belman.

Principiul optimității.

Oricare ar fi starea acceptabilă a sistemului înainte de următoruli-pas, trebuie să selectați o undă de șoc acceptabilă la acest pas astfel încât câștigurileW i pei-al-lea pas plus plata optimă la toți pașii următori a fost maximă.

Ca exemplu de înființare a unei probleme de control optim, vom continua să luăm în considerare problema gestionării finanțării unui grup de întreprinderi. Să fie la începutian grup de întreprinderi fondurile sunt alocate în mod corespunzător: totalitatea acestor valori poate fi considerată control pei- al-lea pas, adică . Control procesul în ansamblu este un set de control al tuturor etapelor, adică .

Managementul poate fi bun sau rău, eficient sau ineficient. Eficiența managementului este evaluat de indicatorS. Apare întrebarea: cum să alegeți controalele pas , astfel încât valoareaStransformat la maxim?

Problema enunțată este o problemă de control optim, iar controlul în care indicatorulSatinge un maxim si se numeste optim. Control optim procesul în mai multe etape constă dintr-un set de controale optime pentru pași:

Astfel, ne confruntăm cu sarcina de a determina controlul optim la fiecare pas(i=1,2,... N ) și, prin urmare, controlul optim al întregului proces .

IDEI DE METODA DE PROGRAMARE DINAMICĂ

Am observat că atunci când planificați un proces în mai multe etape, este necesar să selectați HC la fiecare pas, ținând cont de consecințele sale viitoare în pașii care urmează. Cu toate acestea, există o excepție de la această regulă. Printre toți pașii, există unul care poate fi planificatfără a privi în viitor. Ce pas este acesta? Evident, ultimul estenu mai sunt alti pasi dupa el. Acest pas, singurul dintre toate, poate fi planificat astfel încât să aducă cel mai mare beneficiu ca atare. După ce ați planificat în mod optim acest ultim pas, îl puteți adăuga pe penultimul, penultimul penultimul etc.

Prin urmare, procesul de programare dinamică din prima etapă se desfășoară de la sfârșit la început, adică ultima este planificată mai întâi,

N- al-lea pas. Cum îl putem planifica dacă nu știm?cum s-a terminat penultimul? Evident, trebuie să facem toate ipotezele posibile despre cum s-a încheiat penultima,( N - pasul 1) și pentru fiecare dintre ele găsiți un control astfel încât câștigul (venitul) la ultimul pas să fie maxim. După rezolvarea acestei probleme, vom găsi controlul optim condiționat (COC) peN-a treaptă, adică control care trebuie aplicat dacă (N - Pasul 1) sa încheiat într-un anumit fel.

Să presupunem că această procedură este efectuată, adică pentru fiecare rezultat( N - 1) pasul pe care îl cunoaștem UOUN-m pas și câștigul optim condiționat corespunzător (COP). Acum putem optimiza controlul pe penultimul, (N- 1) pasul. Să facem toate ipotezele posibile despre cum s-a terminat penultima, adică( N - al 2-lea pas, iar pentru fiecare dintre aceste ipoteze găsim un astfel de control pe(N- al 1-lea pas, astfel încât câștigul pentru ultimii doi pași (dintre care ultimul este deja optimizat) să fie maxim. În continuare, controlul este optimizat pentru(N-2) pasul etc.

Intr-un cuvant, la fiecare pas se cauta un control care sa asigure continuarea optima a procesului fata de starea curenta atinsa. Acest principiu al selecției controlului se numește principiul optimității. Autocontrolul, care asigură continuarea optimă a procesului în raport cu o anumită stare, se numește unitate de control în acest pas.

Acum să presupunem că cunoaștem COU la fiecare pas: știm ce să facem în continuare, indiferent de starea în care se află procesul la începutul fiecărui pas. Apoi putem găsi control nu „condițional”, ci cu adevărat optim la fiecare pas. |

Într-adevăr, spuneți-ne starea inițială a procesului. Acum știm deja ce să facem la primul pas: trebuie să aplicăm COU găsit pentru primul pas și starea inițială. Ca urmare a acestui control, după primul pas, sistemul va trece la o altă stare; dar pentru această stare cunoaștem UOU etc. Astfel, vom găsi controlul optim al procesului care să conducă la câștigul maxim posibil.

Astfel, în procesul de optimizare a controlului folosind metoda de programare dinamică, procesul în mai multe etape este „trecut” de două ori:

- prima dată - de la sfârșit până la început, în urma căreia UO la fiecare pas și câștigul optim (de asemenea condiționat) se găsesc la toate etapele, de la aceasta până la sfârșitul procesului;

a doua oară - de la început până la sfârșit, în urma căreia se găsesc controale optime la toate etapele procesului.

Putem spune că procedura de construire a controlului optim

Metoda de programare dinamică este împărțită în două etape:

Preliminar;

Cel final.

În etapa preliminară, pentru fiecare pas, se determină SOE, în funcție de starea sistemului (realizată ca urmare a pașilor anteriori), și câștigul optim condiționat la toate etapele rămase, începând de la aceasta, tot în funcție de stat. În etapa finală, se determină controlul optim (necondiționat) pentru fiecare pas. Optimizarea preliminară (condițională) se realizează pas cu pas în ordine inversă: de la ultimul pas la primul; optimizare finală (necondiționată) - tot în trepte, dar într-o ordine firească: de la primul pas la ultimul. Dintre cele două etape de optimizare, prima este incomparabil mai importantă și consumatoare de timp. După parcurgerea primei etape, parcurgerea celei de-a doua nu prezintă nicio dificultate: nu rămâne decât să „citești” recomandările deja pregătite la prima etapă.

Exemple de probleme de programare dinamică

Majoritatea metodelor de cercetare operațională sunt asociate în primul rând cu sarcini cu un conținut foarte specific. Aparatul clasic al matematicii s-a dovedit a fi de puțin folos pentru rezolvarea multor probleme de optimizare care implică un număr mare de variabile și/sau constrângeri sub formă de inegalități. Nu există nicio îndoială că ideea de a împărți o problemă de dimensiuni mari în subprobleme de dimensiuni mai mici, incluzând doar câteva variabile, și apoi de a rezolva problema generală în părți este atractivă.

Pe această idee se bazează metoda de programare dinamică.

Programarea dinamică (DP) este o metodă matematică a cărei creare și dezvoltare îi aparține în primul rând lui Bellman. Metoda poate fi utilizată pentru a rezolva o gamă foarte largă de probleme, inclusiv probleme de alocare a resurselor, de înlocuire și de gestionare a stocurilor și probleme de încărcare. Caracteristica programării dinamice este abordarea rezolvării unei probleme în etape, fiecare dintre acestea fiind asociată cu o variabilă controlată. Kitproceduri de calcul recurente,conectarea diferitelor etape, asigura obtinerea unei solutii optime acceptabile la problemaVîn generalla atingerea ultimei etape.

originea numeluiprogramare dinamică, se datorează probabil utilizării metodelor DP în probleme de luare a deciziilor la intervale de timp fixe (de exemplu, în problemele de gestionare a stocurilor). Cu toate acestea, metodele DP sunt folosite cu succes și pentru a rezolva probleme în care factorul timp nu este luat în considerare. Din acest motiv, pare mai potrivit să folosim termenulprogramare în mai multe etape,reflectând natura pas cu pas a procesului de rezolvare a problemelor.

Principiul fundamental care stă la baza teoriei DP esteprincipiul optimității.În esență, determină procedura pentru o soluție pas cu pas a unei probleme care permite descompunerea (aceasta este o modalitate mai acceptabilă decât rezolvarea directă a problemei în formularea originală) folosind proceduri de calcul recurente.

Programarea dinamică permite planificarea optimă a proceselor controlate. Prin „controlat” înțelegem procesele al căror curs îl putem influența într-o măsură sau alta.

Să se desfășoare un anumit eveniment sau o serie de evenimente („operațiune”), urmărind un anumit scop. Întrebarea este: cum ar trebui să fie organizată (planificată) operațiunea pentru ca aceasta să fie cât mai eficientă? Pentru ca sarcina să dobândească un caracter cantitativ, matematic, este necesar să se ia în considerare un criteriu numericW, pe care îl vom folosi pentru a caracteriza calitatea, succesul și eficiența operațiunii. Criteriul de eficacitate în fiecare caz specific este selectat pe baza orientării țintă a operațiunii și a sarcinii de cercetare (ce element de control este optimizat și pentru ce).

Să formulăm principiul general care stă la baza soluției tuturor problemelor de programare dinamică („principiul optimității”):

„ Indiferent de starea sistemuluiSÎnainte de următorul pas, trebuie să alegem un control la acest pas, astfel încât profitul la acest pas plus rentabilitatea optimă la toți pașii următori să fie maximă.”

Programarea dinamică este planificarea pas cu pas a unui proces în mai multe etape în care doar un pas este optimizat la fiecare pas. Managementul la fiecare pas trebuie ales ținând cont de toate consecințele sale în viitor.

Când stabiliți probleme de programare dinamică, trebuie să vă ghidați după următoarele principii:

Selectați parametrii (coordonatele fazei) care caracterizează stareaSsistem controlat înainte de fiecare pas.

Împărțiți operația în etape (etape).

Aflați setul de comenzi de pas xi pentru fiecare pas și restricțiile impuse acestora.

Determinați ce aduce controlul câștigului xi la pasul i, dacă înainte de aceasta sistemul era în starea S, adică. notează „funcția de plată”:

Determinați modul în care starea S a sistemului S se modifică sub influența controlului xi la pasul i: acesta intră într-o stare nouă

. (1.1)

Notați ecuația de bază de programare dinamică recurentă care exprimă câștigul optim condiționatW i ( S) (incepand cuipasul și până la final) printr-o funcție deja cunoscutăW i +1 ( S):

. (1.2)

Acest câștig corespunde controlului optim condiționat pei- al-lea pasX i ( S) (și în funcția deja cunoscutăW i +1 ( S) nevoie în schimbSînlocuirea starea schimbată

Rețineți că, dacă starea sistemului la momentul inițial este cunoscută (și acesta este de obicei cazul), atunci la primul pas nu este nevoie să variam starea sistemului - găsim direct câștigul optim pentru o anumită inițială. statS 0 . Acesta este câștigul optim pentru întreaga operațiune

Aceste etape au fost luate în considerare pentru probleme aditive în care profitul pentru întreaga operațiune este egal cu suma plăților la pașii individuali. Metoda de programare dinamică este aplicabilă și problemelor cu așa-numitul criteriu „multiplicativ”, care are forma unui produs:

(dacă doar câștiguriw i sunt pozitive). Aceste probleme sunt rezolvate exact în același mod ca și problemele cu criteriu aditiv, cu singura diferență că în ecuația principală (1.2) în loc de semnul „plus”, se plasează semnul „înmulțire”:

3.1. Problemă de planificare a forței de muncă

În unele proiecte, numărul de muncitori necesari pentru a finaliza un proiect este controlat prin angajarea și concedierea acestora. Întrucât atât angajarea, cât și concedierea lucrătorilor implică costuri suplimentare, este necesar să se determine modul în care numărul de lucrători ar trebui să fie reglementat în perioada proiectului.

Să presupunem că proiectul va fi finalizat în termennsăptămâni și cerințe minime de muncă pentruia-a săptămână va fib i muncitorii. In conditii ideale as dorii-săptămânile au exactb i muncitorii. Cu toate acestea, în funcție de indicatorii de cost, poate fi mai profitabil să devii numărul de forță de muncă în orice direcție de la cerințele minime.

DacăX i iîn a-a săptămână, atunci sunt posibile două tipuri de costuri: 1) C 1 ( X i - b i ) - costuri asociate cu necesitatea mentinerii excedentuluiX i - b i forța de muncă și 2) C 2 ( X i - X i -1 ) - costuri asociate cu necesitatea de angajare suplimentară (X i - X i -1 ) muncitorii.

Elementele modelului de programare dinamică sunt definite după cum urmează:

Etapăі reprezentată de numărul de serie al săptămâniiі , і =1,2,… n.

Opțiuni de soluție pentruі -a etapă sunt valorileX i – numarul de angajati in perioadaі- a saptamana.

Stare activatăSuntetapa esteX i -1 – numărul de angajați în perioada (і- 1) a-a săptămână (etapa).

Ecuația de programare dinamică recurentă este reprezentată ca:

Unde

Calculele încep cu etapanlaX n = b n și se termină în etapa 1.

3.2. Problemă de înlocuire a echipamentului

Cu cât un mecanism este utilizat mai mult timp, cu atât costul de întreținere al acestuia este mai mare și performanța acestuia este mai scăzută. Când durata de viață a unui mecanism ajunge la un anumit punct, poate fi mai rentabilă înlocuirea acestuia. Sarcina înlocuirii echipamentelor se rezumă astfel la determinarea duratei optime de viață a mecanismului.

Să presupunem că înlocuim mecanismele pe tot parcursulnani. La începutul fiecărui an se ia decizia fie de a funcționa mecanismul încă un an, fie de a-l înlocui cu unul nou.

Să notăm prinr( t) Șic( t) profit din exploataret-mecanismul vechi de ani pe tot parcursul anului și costurile de întreținere a acestuia pentru aceeași perioadă. Următoarea lasăs( t) – costul vânzării mecanismului care a fost utilizattani. Costul achiziționării unui nou mecanism rămâne neschimbat de-a lungul anilor și este egal cul.

Elementele modelului de programare dinamică sunt:

Etapăі reprezentată de numărul de ordine al anuluii, i=1,2,...n.

Opțiuni de soluție pentruі -a etapă (adică pentru i-Wowani) sunt alternativele: continuarea funcționării sau înlocuirea mecanismului la începutі- Wow.

Stare activatăі -etapa este durata de viațăt(vechimea) mecanismului până la începutі al-lea an.

Lăsaf i ( t) - profitul maxim primit de-a lungul anilor de laі inainte dencu condiţia ca la începutі- există un mecanismt-ani de varsta.

Ecuația recurenței are următoarea formă:

(1) - dacă acționați mecanismul,

(2) - dacă înlocuiți mecanismul.

3.3. Problema investitiei

Să presupunem că la începutul fiecăreia dintre următoarelenani trebuie să facă o investițieP 1 , P 2 ,…, P n respectiv. Ai ocazia să investești în două bănci: prima bancă plătește anual dobândă compusăr 1 și al doilea -r 2 . Pentru a încuraja depozitele, ambele bănci plătesc bonusuri noilor investitori ca procent din suma investită.

Bonusurile variază de la an la an și pentruі al-lea an sunt egaleq i 1 Șiq i 2 în prima și respectiv a doua bancă. Acestea sunt plătite la sfârșitul anului în care se efectuează depozitul și pot fi investite într-una din două bănci pentru anul următor. Aceasta înseamnă că doar dobânda specificată și banii noi pot fi investiți într-una dintre cele două bănci. Depozitul plasat în bancă trebuie să rămână acolo până la sfârșitul perioadei analizate. -1) thal anului.

Lăsaf i (X i ) - suma optimă a investiției pentru intervalul de la1inainte den-anul al-lea, cu condiţia ca la început1an există o sumă de baniX i nal-lea an fac parte din numerarul acumulat din investiții, în expresii pentrus n adăugatq n 1 Șiq n 2 .

Deci, în acest caz, ecuația recurentă pentru măturarea înapoi în algoritmul de programare dinamică are forma

UndeX i +1 exprimat prinX i conform formulei de mai sus șif n +1 (X n +1 )=0.

4. Structura generală a programării dinamice

Găsirea strategiei optime pentru luarea unui set de decizii secvențiale, în cele mai multe cazuri, se face astfel: mai întâi, se selectează ultima soluție în timp, apoi, deplasându-se în direcția opusă curgerii timpului, toate celelalte soluții sunt selectate. la cea inițială.

Pentru implementarea acestei metode, este necesar să se afle toate situațiile în care poate apărea alegerea ultimei soluții. De obicei, condițiile în care se ia o decizie sunt numite „starea” sistemului. Starea unui sistem este o descriere a sistemului care permite, având în vedere deciziile viitoare, să prezică comportamentul acestuia. Nu este nevoie să aflăm cum a apărut cutare sau cutare condiție sau care au fost deciziile anterioare. Acest lucru vă permite să selectați în mod constant o singură soluție la un moment dat. Indiferent dacă soluțiile optime sunt găsite folosind o metodă tabelară și căutarea ulterioară sau analitic, este de obicei mai rapid și mai profitabil să selectați o soluție la un moment dat, apoi să treceți la momentul următor etc. Din păcate, nu toate procesele de luare a deciziilor pot fi studiate folosind această metodă. O condiție necesară pentru aplicarea metodei de programare dinamică este aditivitatea prețurilor tuturor soluțiilor, precum și independența rezultatelor viitoare din preistoria unui anumit stat.

Dacă numărul de soluții este foarte mare, atunci este posibil să se construiască estimări relative ale stărilor, astfel încât estimările corespunzătoare fiecărei perechi de decizii succesive să difere unele de altele printr-o valoare constantă, care este „venitul” mediu pe decizie. De asemenea, puteți reduce veniturile din deciziile viitoare. Necesitatea acestui lucru apare uneori atunci când deciziile sunt luate rar, să zicem o dată pe an. Atunci nu mai trebuie să luați în considerare 1,2,3...soluții succesiv pentru a obține o soluție cu un număr mai mare. În schimb, se poate opera direct pe ecuația funcțională, care de obicei oferă un beneficiu semnificativ în ceea ce privește calcularea redusă.

CONCLUZIE

Putem distinge cel puțin patru aspecte ale utilizării metodelor dinamice în rezolvarea problemelor practice.

1. Îmbunătățirea sistemului informațional economic. Metodele dinamice fac posibilă eficientizarea sistemului de informații economice, identificarea deficiențelor informațiilor existente și dezvoltarea cerințelor pentru pregătirea de noi informații sau ajustarea acestora. Dezvoltarea și aplicarea modelelor economice și matematice indică modalități de îmbunătățire a informațiilor economice care vizează rezolvarea unui sistem specific de probleme de planificare și management. Progresul în suportul informațional pentru planificare și management se bazează pe dezvoltarea rapidă a instrumentelor tehnice și software ale informaticii.

2. Intensificarea si cresterea acuratetii calculelor economice. Formalizarea problemelor economice și utilizarea computerelor accelerează foarte mult calculele standard, de masă, măresc precizia și reduc intensitatea muncii și fac posibilă realizarea unor justificări economice multivariate pentru activități complexe care sunt inaccesibile sub dominația tehnologiei „manuale”.

3. Aprofundarea analizei cantitative a problemelor economice. Datorită utilizării metodei de programare dinamică, capacitățile de analiză cantitativă specifică, studiul multor factori care influențează procesele economice, evaluarea cantitativă a consecințelor modificărilor condițiilor de dezvoltare a obiectelor economice etc. sunt îmbunătățite semnificativ.

Sfera de aplicare practică a acestor metode este limitată de capacitățile și eficacitatea formalizării problemelor și situațiilor economice, precum și de starea informațiilor, a suportului matematic și tehnic al modelelor utilizate. Dorința de a aplica cu orice preț un model matematic poate să nu dea rezultate bune din cauza lipsei măcar a unor condiții necesare.

În conformitate cu ideile științifice moderne, sistemele de dezvoltare și luare a deciziilor de afaceri ar trebui să combine metode formale și informale, care se întăresc reciproc și se completează unele cu altele. Metodele formale sunt, în primul rând, un mijloc de pregătire bazată științific a materialului pentru acțiunile umane în procesele de management. Acest lucru face posibilă utilizarea productivă a experienței și intuiției unei persoane, a capacității sale de a rezolva probleme slab formalizate.