Ce este programarea dinamică. Ideea de programare dinamică. Să ne uităm la un exemplu de i pași

Secțiunea Programare dinamică este reprezentată de următoarele calculatoare:

Problemă de alocare a investițiilor. Pentru reconstrucția și modernizarea producției la patru întreprinderi, alocate bani gheata C = 80 den. unitati Pentru fiecare întreprindere, este cunoscută posibila creștere f i (x) (i = 1, 4) a producției, în funcție de suma alocată.

În sarcini programare dinamică proces economic depinde de timp (sau de mai multe perioade de timp), prin urmare se găsesc o serie de soluții optime (secvențial pentru fiecare etapă) care asigură desfășurarea optimă a întregului proces în ansamblu. Programarea dinamică este un aparat matematic care permite planificarea optimă a proceselor controlate și a proceselor dependente de timp. Efectuarea optimizării pas cu pas se numește proces decizional în mai multe etape. Un proces economic se numește controlat dacă este posibil să influențeze cursul dezvoltării sale.

Metoda programarii dinamice (DP) se bazeaza pe principiul optimizarii secventiale: solutie problema initiala optimizarea dimensională înaltă este înlocuită cu rezolvarea unei secvențe de probleme de optimizare dimensională joasă. Condiția principală pentru aplicabilitatea metodei DP este posibilitatea împărțirii procesului decizional într-un număr de pași sau etape similare, fiecare dintre acestea fiind planificată separat, dar ținând cont de rezultatele obținute la alte etape. De exemplu, activitatea unei industrii de-a lungul unui număr de ani de activitate, sau o succesiune de teste utilizate în controlul echipamentelor etc. Unele procese (operații) sunt împărțite în etape în mod firesc, dar există operațiuni care trebuie împărțite în etapează artificial, de exemplu, procesul de ghidare a rachetelor la țintă.
Acest principiu asigură că controlul ales la orice pas nu este cel mai bun la nivel local, ci cel mai bun din punct de vedere al procesului în ansamblu, deoarece acest control este ales luând în considerare consecințele în etapele următoare.

Sa luam in considerare descriere generala probleme de programare dinamică.
Lăsați procesul de luare a deciziilor în mai multe etape să fie împărțit în n trepte. Să notăm cu ε 0 starea inițială a sistemului, cu ε 1, ε 2, … ε n– starea sistemului după primul, al doilea, n- al-lea pas. ÎN caz general stat ε k– vector (ε k 1, …, ε k s).
managementîntr-un proces în mai multe etape, se numește un set de soluții (variabile de control). Regatul Unit = (Regatul Unit 1 , ..., u k r) luate la fiecare pas kși transferarea sistemului din starea ε k-1 = (ε k- 1 1 , …, ε k -1 s) pentru a afirma ε k = (ε k 1, …, ε k s).
În procesele economice, managementul constă în distribuirea și redistribuirea fondurilor în fiecare etapă. De exemplu, producția de produse de către orice întreprindere este un proces controlat, deoarece este determinat de modificări în compoziția echipamentelor, volumul livrărilor de materii prime, valoarea finanțării etc. Un set de decizii luate la început a anului, perioada de planificare, pentru a furniza întreprinderii cu materii prime, înlocuirea echipamentelor, precum și suma de finanțare etc este management. S-ar părea că pentru a obține volumul maxim de producție, cel mai simplu mod este să investești cea mai mare sumă posibilă de fonduri și să folosești echipamentul la capacitate maximă. Dar acest lucru ar duce la uzura rapidă a echipamentelor și, în consecință, la o scădere a producției. Prin urmare, eliberarea produsului trebuie planificată astfel încât să se evite efectele nedorite. Este necesar să se ia măsuri pentru a se asigura că echipamentul este completat pe măsură ce se uzează, adică pe perioade de timp. Acesta din urmă, deși duce la o scădere a volumului inițial al producției, oferă posibilitatea extinderii producției în viitor. Astfel, procesul economic de producție poate fi considerat a fi format din mai multe etape (etape), fiecare dintre acestea influențând dezvoltarea sa.
Începutul etapei (pasul) proces controlat se are în vedere momentul luării deciziilor (cu privire la valoarea investițiilor de capital, la înlocuirea echipamentelor anumit tip etc.). O etapă este de obicei înțeleasă ca un an de afaceri.
De obicei, pe control la fiecare pas Regatul Unit se aplică unele restricții. Se apelează controalele care îndeplinesc aceste restricții acceptabil.
Presupunând că indicatorul de performanță k a treia etapă a procesului depinde de starea inițială la acest pas k-1 și de la control la acest pas Regatul Unit, obținem funcția obiectivă a întregului proces în mai multe etape sub forma:
.

Să formulăm acum problema de programare dinamică: „Determinați setul de controale admisibile ( u 1 , …, u n), transferând sistemul din starea inițială ε 0 în starea finală ε nși maximizarea sau minimizarea indicatorului de eficiență F».
Control care realizează maximul (minimul) funcției F numit control optim u * = (u 1* ,…, u n *).
Dacă variabilele de control Regatul Unit iau valori discrete, atunci se numește modelul DP discret. Dacă variabilele Regatul Unit se modifică continuu, apoi se numește modelul DP continuu.
În funcţie de numărul de parametri de stare sși numărul de variabile de control r diferențiați unidimensionalȘi multidimensionale Sarcini DP.
Numărul de pași dintr-o sarcină poate fi final sau fără sfârşit.

Probleme aplicate de programare dinamică

problema de planificare a construcţiei de facilităţi.

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 împărțirii soluției î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 căutare soluție optimă sarcini în 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. Atunci 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 acestuia î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 problemei, când soluţia sarcină comună este împărțit într-un număr de soluții pentru subsarcini individuale și apoi combinat într-o singură soluție. Foarte des, subsarcinile individuale se dovedesc a fi aceleași și una decizie comună 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 doar parametrii procesului care îl caracterizează în acest moment. 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 realiza cel mai bun rezultatîn general. 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 efect maxim pe ultima etapă se știe deja, de exemplu, am ajuns deja din punctul A în punctul B și acum vrem să aflăm dacă am condus corect la fiecare etapă anterioară sau dacă s-ar fi putut face ceva 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.). Cele mai multe aplicații s-au obţinut soluţii dinamice î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ă” a forței brute opțiuni posibile soluțiile 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 exemplu simplu O astfel de sarcină este construirea celui mai scurt traseu folosind un navigator GPS pentru mașină.

Productie

Programarea dinamică este utilizată pe scară largă în rezolvarea diverselor sarcini de producție cum ar fi gestionarea stocurilor pentru a menține cantitatea necesară componente în orice moment, programare proces de producție, reparații curente și majore ale echipamentelor, volumul de muncă uniform al personalului, distribuția cât mai eficientă a fondurilor de investiții etc. Pentru a rezolva problemele de producție folosind metode de programare dinamică, pachete software, integrat in sisteme populare sisteme de management al întreprinderii, 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

În modelele de sarcini de management discutate mai sus, timpul nu a fost luat în considerare. Acestea sunt așa-numitele modele cu o singură etapă care vă permit să analizați procese statice, independente de timp, de exemplu, atunci când modificările procesului studiat în timp pot fi neglijate. O decizie de management asupra unei astfel de modelări are sens fie în condiții de stabilitate a sistemului, fie pentru o perioadă scurtă în viitor.

În realitate, toate procesele și fenomenele economice funcționează și se dezvoltă în timp, adică sunt de natură dinamică. Acest lucru presupune ca managerii să decidă probleme practice, în care este necesar să se țină cont de eventualele modificări ale proceselor economice în timp, cu condiția ca procesul să poată fi controlat, adică să poată fi influențat cursul dezvoltării acestuia.

Programarea dinamică este un aparat matematic cu ajutorul căruia se rezolvă probleme în mai multe etape control optim. Într-o astfel de programare, pentru a controla procesul, dintre ansamblul tuturor soluțiilor fezabile, se caută cea optimă în sensul unui anumit criteriu, adică o soluție care dă valori extreme (mai mult sau mai puțin) funcție obiectivă- unele caracteristici numerice ale procesului. Multigradul este înțeles fie ca o structură în mai multe etape a unui proces, fie distribuția controlului într-un număr de etape succesive, corespunzătoare, de regulă, diferitelor momente în timp. Astfel, cuvântul „programare” înseamnă luarea deciziilor de management, iar cuvântul „dinamic” indică importanța esențială a timpului și a ordinii operațiilor în procesele și metodele care sunt luate în considerare.

Problemele de programare dinamică includ probleme programare, distribuția investițiilor, gestionarea stocurilor, curente și revizuire, alegând metode de publicitate și altele asemenea.

În unele probleme de programare dinamică proces de management se descompune în mod natural în etape, de exemplu o lună, un sfert, un an. În alte situații, împărțirea în etape poate avea caracter condiționat. Particularitatea tuturor problemelor de programare dinamică este că în fiecare etapă este posibil să se ia în considerare modificările anterioare, să se controleze cursul evenimentelor, evaluând în același timp calitatea unui astfel de control. Deci, programarea dinamică vă permite să luați o serie de decizii de management și asigură dezvoltarea optimă a sistemului în ansamblu.

Să luăm în considerare formularea generală a problemei acestei programări. Să investigăm un proces economic care are n etape succesive. La fiecare a 7-a etapă, procesul poate fi activ diferite state fiecare dintre acestea fiind caracterizat de un set finit de parametri. Fiecare etapă a sarcinii este asociată cu adoptarea unei anumite decizii de management, care transferă sistemul dintr-un stat în altul. Se presupune că starea si a sistemului la sfârșitul etapei a 7-a este determinată numai de starea anterioară si_1 și de controlul xi la etapa a 7-a și nu depinde de stările anterioare si managementuri. Atunci starea si a sistemului se scrie ca dependenta

Si = f (în, _!, Xi), i = 1, P.

Eficacitatea întregului proces de management poate fi prezentată ca suma eficacității deciziilor de management la etapele individuale, adică

În condițiile de mai sus, problema programării dinamice se formulează astfel: să se determine o astfel de succesiune admisibilă de decizii de management X = (x1, x2, xn), care transferă sistemul din starea inițială 50 în starea finală sn și la care se atinge eficienţa maximă a managementului.

La planificarea unui proces de management în mai multe etape, în problemele de programare dinamică este necesară în fiecare etapă selectarea unei decizii de management, ținând cont de consecințele acesteia în acele etape care urmează să vină. Abia în ultima etapă se poate lua o decizie de management care să dea efect maxim, de vreme ce urmatorul pas nu exista pentru el. Prin urmare, problemele de programare dinamică sunt rezolvate de la final.

Maximul funcției obiectiv la p-m final stadiul este egal cu

^ n-O = verifica / n ^ n-i xn).

În consecință, în stadiul (n - 1) avem

r * n-1 (5n-2) = ShaX ((fn-1 (sn-2, xn-1) + r * n ^ n-1)).

Ținând cont de acest model, pentru o etapă k arbitrară putem scrie dependența recurentă

g * (al cincilea-1) = Shahi (L (ik-1, xk) + g * + 1)).

Această dependență recurentă este o reprezentare matematică a principiului optimității lui Bellman.

După ce au determinat efectul optim condiționat în etapa inițială folosind dependențe recurente, ei efectuează optimizarea necondiționată a managementului în direcția „inversă”, în urma căreia se găsește o succesiune de decizii de management, asigurând eficienta maxima sisteme ca un întreg.

Principalele caracteristici ale metodei de programare dinamică

1. Ideea și metoda de programare dinamică sunt mai potrivite pentru problemele discrete, care în cele mai multe cazuri sunt probleme de control.

2. Metoda de programare dinamică poate fi utilizată cu orice metodă de specificare a funcției obiectiv și cu orice set admisibil de stări și comenzi. Metodele clasice de optimizare și altele nu au acest avantaj. metode de calcul programare matematică.

3. Scheme de calcul ale metodei de programare dinamică în cazul discret asociat cu bulkheading valori optime indicator de performanță și management pe pasul k pentru toate valorile posibile ale variabilei de stare, dar volumul calculelor este semnificativ mai mic decât cu selecția directă a opțiunilor. Acest lucru se datorează faptului că la scenă optimizare condiționată opțiuni proaste sunt imediat aruncate și sunt reținute numai cele care sunt optime condiționat în această etapă.

4. Metoda de programare dinamică face posibilă analizarea sensibilității la modificările datelor inițiale ale stărilor sk și ale numărului lor n. De fapt, aici la fiecare pas nu se rezolvă o problemă, ci multe probleme similare pentru diferite stări sk și diferite. k (1<к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

concluzii

1. Apariția modelelor neliniare este asociată cu necesitatea de a lua în considerare și demonstra modelele neliniare care afectează luarea optimă a deciziilor. Astfel de modele sunt incluse în constrângerile problemei și funcția obiectiv.

2. După natura funcţiilor şi constrângerilor care descriu problemele de programare neliniară, acestea pot fi clasificate astfel: probleme clasice de optimizare; probleme cu funcția obiectiv neliniară și constrângeri liniare; probleme de programare convexă, pătratică, separabilă.

3. Spre deosebire de problemele de programare liniară, nu există o metodă universală pentru rezolvarea problemelor neliniare. În fiecare caz specific, este necesar să alegeți cea mai bună metodă.

4. Programarea dinamică este un aparat matematic cu ajutorul căruia se rezolvă probleme de control optim în mai multe etape. Multigradul este înțeles fie ca o structură în mai multe etape a unui proces, fie distribuția controlului într-un număr de etape succesive, corespunzătoare, de regulă, diferitelor momente în timp.

5. Sarcinile de programare dinamică includ sarcini de programare, distribuție de investiții, gestionare a stocurilor, reparații curente și majore, selectarea metodelor de publicitate și altele asemenea. Particularitatea tuturor problemelor de programare dinamică este că în fiecare etapă este posibil să se ia în considerare modificările anterioare și să se controleze cursul evenimentelor, evaluând în același timp calitatea unui astfel de control.

6. Rezolvarea problemelor de programare dinamică se bazează pe principiul optimității Bellman. În procesul de optimizare a controlului de programare dinamică, un proces în mai multe etape este efectuat de două ori. Prima dată este de la sfârșit până la început, în urma căreia se găsesc controale optime condiționat. Al doilea este de la început până la sfârșit, în urma căruia se găsește controlul optim al procesului în ansamblu.

Pentru a selecta soluția optimă atunci când efectuați sarcini de programare, uneori este necesar să sortați un număr mare de combinații de date, ceea ce încarcă memoria unui computer personal. Astfel de metode includ, de exemplu, metoda de programare „împărțiți și cuceriți”. În acest caz, algoritmul prevede împărțirea sarcinii în subsarcini mici separate. Această metodă este utilizată numai în cazurile în care subsarcinile mici sunt independente unele de altele. Pentru a evita efectuarea unor lucrări inutile dacă subsarcinile sunt interdependente, se utilizează metoda de programare dinamică propusă de americanul R. Bellman în anii 50.

Esența metodei

Programarea dinamică implică determinarea soluției optime pentru o problemă n-dimensională prin împărțirea acesteia în n pași separate. Fiecare dintre ele este o subsarcină în raport cu o variabilă.

Principalul avantaj al acestei abordări este că dezvoltatorii se confruntă cu probleme de optimizare unidimensională a subsarcinilor în loc de o problemă n-dimensională, iar soluția la problema principală este asamblată „de jos în sus”.

Este recomandabil să folosiți programarea dinamică în cazurile în care subsarcinile sunt interconectate, de ex. au module comune. Algoritmul prevede rezolvarea fiecăreia dintre sarcinile secundare o dată, iar răspunsurile sunt stocate într-un tabel special. Acest lucru face posibilă să nu se recalculeze răspunsul atunci când întâlniți o subsarcină similară.

Problemă de optimizare a programării dinamice. Autorul acestei metode, R. Bellman, a formulat principiul optimității: oricare ar fi starea inițială la fiecare dintre pași și soluția determinată la acest pas, toate cele ulterioare sunt alese optime în raport cu starea pe care o ia sistemul la sfarsitul pasului.

Metoda va îmbunătăți execuția problemelor rezolvate folosind enumerarea opțiunilor sau recursiile.

Construirea algoritmului problemei

Programarea dinamică presupune construirea unui algoritm de problemă în care problema este împărțită în două sau mai multe subsarcini, astfel încât soluția sa să constea în soluția optimă a tuturor subsarcinilor incluse în ea. În continuare, este nevoie de a scrie o relație de recurență și de a calcula valoarea optimă a parametrului pentru problema în ansamblu.

Uneori, la pasul 3, trebuie să vă amintiți suplimentar câteva informații auxiliare despre progresul fiecărei sarcini secundare. Aceasta se numește inversare.

Aplicarea metodei

Programarea dinamică este utilizată atunci când sunt prezente două caracteristici:

optimitate pentru subsarcini;
prezența unor subsarcini suprapuse într-o sarcină.

Când rezolvați folosind programarea dinamică, mai întâi trebuie să descrieți structura soluției. O problemă este optimă dacă soluția problemei constă în soluții optime la subproblemele sale. În acest caz, este recomandabil să folosiți programarea dinamică.

A doua proprietate a problemei, care este esențială pentru această metodă, este numărul mic de subsarcini. O soluție recursivă a unei probleme folosește aceleași subprobleme suprapuse, al căror număr depinde de dimensiunea informațiilor de intrare. Răspunsul este stocat într-un tabel special; programul economisește timp utilizând aceste date.

Utilizarea programării dinamice este deosebit de eficientă atunci când deciziile privind esența problemei trebuie luate pas cu pas. De exemplu, luați în considerare un exemplu simplu al problemei de înlocuire și reparare a echipamentului. Să presupunem că mașina de turnare a unei turnări de anvelope produce anvelope în două forme diferite în același timp. Dacă una dintre matrițe eșuează, mașina trebuie dezasamblată. Este clar că uneori este mai profitabilă înlocuirea celei de-a doua matrițe pentru a nu dezasambla mașina în cazul în care această matriță se dovedește a fi nefuncțională în etapa următoare. În plus, poate fi mai ușor să înlocuiți ambele forme de lucru înainte de a începe să cedeze. Metoda de programare dinamică determină cea mai bună strategie pentru înlocuirea unor astfel de matrițe, ținând cont de toți factorii: beneficiile continuării exploatării matrițelor, pierderile din timpul de nefuncționare a mașinii, costul anvelopelor refuzate și multe altele.