Principiul optimalității a fost formulat pentru prima dată de Richard Ernest Bellman în 1953 (în interpretarea lui ES Venttsel):
Indiferent de starea sistemului, ca urmare a unui număr de pași, la următorul pas este de a selecta control, astfel încât acesta este cuplat cu un control optim la toate etapele ulterioare care conduc la optim câștiga toate etapele rămase, inclusiv aceasta.
RE Bellman a formulat condițiile în care principiul este adevărat. Principala cerință este ca procesul de gestionare să nu aibă un feedback, adică Gestionarea la acest pas nu trebuie să influențeze pașii anteriori.
Să luăm în considerare problema generală de programare dinamică dată mai sus. La fiecare pas, cu excepția ultima pentru orice sk-1 soluție de management al sistemului de stat Xk ar trebui să fie ales „cu prudență“, deoarece această alegere afectează sistemul ulterior sk de stat.
La ultima etapă, pe baza stării sistemului sn-1, soluția de administrare Xn poate fi planificată la nivel local optim, adică pe baza motivelor pentru această etapă.
Luați în considerare ultimul pas n:
sn-1 - starea sistemului la începutul etapei n;
sn este starea finală a sistemului;
Xn - controlul asupra etapei n;
Conform principiului optimalității, Xn trebuie ales în așa fel încât pentru orice stare a sistemului sn-1 să obțină optimul funcției obiective la acest pas.
Notăm optimă (pentru o decolare maximă certitudine) funcția obiectiv - un indicator al eficienței pas n-lea, cu condiția ca începutul ultimului sistem pas S era într-o stare de arbitrar sn-1. iar la ultimul pas controlul a fost optim.
numit maximul condițional al funcției obiective în etapa n și determinat de următoarea formulă:
Maximizarea se efectuează asupra tuturor controalelor admisibile Xn.
Soluția Xn. la care se realizează. De asemenea depinde de sn-1 și se numește soluția optimă condiționată la pasul n. Indicăm asta prin.
Rezolvind problema unidimensională a optimizării locale prin ecuația (11.5), definim pentru două stări posibile sn-1 două funcții u.
Luați în considerare problema în două etape: atașați la pasul n (n-1) -th.
Pentru orice state sn-2. decizii administrative arbitrare XN-1 și un control optim la n-lea pas valoarea functiei obiectiv pe ultimele două etape se calculează după cum urmează:
În conformitate cu principiul optimalității Bellman pentru orice soluție sn-2 ar trebui să fie alese astfel încât să, împreună cu controlul optim în ultimul (n th) pas ar duce la optimul funcției obiectiv pe ultimele două etape. Prin urmare, este necesar să se găsească optimul expresiei (11.6) pentru toate soluțiile administrative admisibile Xn-1:
- numit maximul condițional al funcției obiectiv cu control optim în ultimii doi pași. Trebuie notat că expresia în paranteze curbate din formula (11.6) depinde numai de sn-2 și Xn-1. deoarece sn-1 poate fi găsit din ecuația stărilor (11.1) pentru:
Xn-1 management corespunzător (n-1) th pas este notat și denumit control optim condiționată (n-1) th.
condiționată a optima funcției obiectiv sunt definite în mod similar, pentru controlul optim (n + 1) -k etape, începând cu k -lea până la sfârșit, cu condiția ca începutul k-lea pas sistem este în stare sk-1:
management k xk-lea pas, la care, se indică maximul (11,8) și se numește un control optim condiționată k-lea pas.
Ecuațiile (11.5) și (11.8) sunt numite ecuații Bellman recursive (schema inversă). Procesul de rezolvare a acestor ecuații se numește optimizare condiționată.
Ca urmare a optimizării condiționale, se obțin două secvențe:
. . .... - maximele condiționate ale funcției obiective pe ultimele, ultimele două, ..., n pași;
. . .... - Controale optime condiționate pe n-a, (n-1) -th, ..., la pașii 1-a.
Folosind aceste secvențe, găsim soluția problemei de programare dinamică pentru n și s0 date date:
Ca rezultat, obținem soluția optimă a problemei de programare dinamică :.
În mod similar, argumentând, se poate construi și o schemă directă de optimizare condiționată:
Soluția optimă a problemei în acest caz este conformă cu următoarea schemă:
Astfel, construirea modelului dinamic de programare și soluționarea problemei pe baza sa în formă generală pot fi reprezentate sub forma următoarelor etape:
1. Alegeți cum să împărțiți procesul de control în pași.
2. Definiți parametrii de stare sk și variabilele de control Xk la fiecare pas, scrieți ecuațiile de stare.
3. Introduceți funcția țintă k pas și funcția obiectiv totală, precum și gestionarea optimă și condiționată condiționată valori optime la k etapa ().
4. Scrieți în conformitate cu schema inversă sau directă ecuațiile Bellman de recurență și după efectuarea optimizării condiționale primiți două secvențe: <> și <>.
5. Determinați valoarea optimă a funcției obiectiv și soluția optimă.
Articole similare
Trimiteți-le prietenilor: