Programare dinamică. Problema alocării optime a resurselor. Alocarea resurselor folosind metoda de programare dinamică
Planul lecției
Disciplina academica METODE ȘI MODELE MATEMATICE ÎN ECONOMIE
Subiectul lecției Rezolvarea diverselor probleme practice DP folosind metode matematice.
Obiectivele lecției
Dezvoltați abilitățile de rezolvare a problemelor de programare dinamică.
Dezvoltarea calității minții, a atenției și a abilităților de lucru academice ale studenților.
Insuflarea disciplinei si determinarii elevilor.
Echipamentul de lecție Note de curs, V.P. Agaltsov „Metode matematice în programare”.
În timpul orelor:
Timp de organizare:
verificarea absentelor, completarea jurnalului.
Actualizarea cunoștințelor de referință: răspunsuri la întrebările de securitate
Ce sarcini se numesc în mai mulți pași?
Ce aparat matematic este folosit pentru a rezolva probleme cu mai multe etape?
Care este controlul optim u*?
Care este algoritmul pentru metoda de aproximare succesivă cu două cercuri?
Dați exemple de probleme de alocare optimă a resurselor.
Învățarea de materiale noi:
Probleme clasice de programare dinamică
Problemă cu cea mai lungă subsecvență comună: Având în vedere două secvențe, trebuie să găsiți cea mai lungă subsecvență comună.
Problema găsirii celei mai lungi subsecvențe crescătoare: dată fiind o secvență, trebuie să găsiți cea mai lungă subsecvență crescătoare.
Problemă de distanță editorială (distanța Levenshtein): având în vedere două șiruri, trebuie să găsiți numărul minim de ștergeri, înlocuiri și adăugiri de caractere care transformă un șir în altul.
Problema calculării numerelor Fibonacci
Problema ordinului înmulțirii matricelor: date matrice, ..., se cere minimizarea numărului de operații scalare pentru înmulțirea lor.
Problemă de selecție a traiectoriei
Problemă de luare a deciziilor secvenţiale
Problema utilizării forței de muncă
Problema de gestionare a stocurilor
Problema rucsacului: dintr-un set nelimitat de obiecte cu proprietățile „cost” și „greutate”, este necesară selectarea unui anumit număr de obiecte în așa fel încât să se obțină costul total maxim cu o greutate totală limitată.
Algoritmul Floyd-Warshall: găsiți cele mai scurte distanțe dintre toate vârfurile unui grafic ponderat direcționat.
Algoritmul Bellman-Ford: găsiți calea cea mai scurtă dintr-un grafic ponderat între două vârfuri date.
Setul maxim independent de vârfuri dintr-un arbore: dat fiind un arbore, găsiți setul maxim de vârfuri astfel încât să nu fie conectate două dintre ele printr-o muchie.
Exemplu: Alocarea optimă a resurselor
Capital 40 de milioane de ruble. investitorul trebuie să investească în patru proiecte de investiții pentru a obține venituri maxime. Rentabilitatea proiectelor este dată în tabel (investițiile sunt multipli de 8 milioane de ruble)
u
Profit din implementare
f4(u)
f3(u)
f2(u)
f1(u)
55
39
120
115
10 0
120
135
134
14 0
145
158
147
Soluţie:
Aceasta este o problemă de programare dinamică. Soluția constă din două etape. În prima etapă (de la capăt la început) căutăm o soluție optimă condiționată, la a doua (de la început până la sfârșit) căutăm soluția optimă a problemei.
Etapa 1.
Distribuim capitalul între patru proiecte și calculăm profitul primit L (i ), i = 8,16,24,32,40.
1 pas: Fondurile sunt investite în al patrulea proiect.
L(8)= 55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
Pasul 2: Fondurile sunt investite în al patrulea și al treilea proiect.
u
Profit din implementare
1 pas
f3(u)
55
39
10 0
120
14 0
145
Pasul 3: Fondurile sunt investite în al patrulea, al treilea (pasul 2) și al doilea proiect.
u
Profit din implementare
Pasul 2
f 2(u)
94
108
120
135
135
175
158
175
134
214
147
Etapa 2:
La al patrulea pas, selectăm valoarea maximă a profitului obținut L (40) = 214.
Și revenind în ordine inversă de la tabel la tabel (de la 4 pași la 1) selectăm astfel de valori ale veniturilor la care se obține valoarea 214.
Venitul maxim 214 milioane de ruble. din fondurile investite pot fi primite cu următoarea distribuție de fonduri:
1 proiect – 0 milioane de ruble.
2 proiect – 24 de milioane de ruble.
Al treilea proiect – 8 milioane de ruble.
4 proiect – 8 milioane de ruble.
Consolidarea materialului nou:
5. Rezumatul lecției: concluzii, aprecieri, teme:
(2) clauza 5.1
Ср12: formarea și asimilarea conținutului materialului teoretic
Semnătura profesorului
- 1,03 MBSă dăm o formulare matematică a principiului optimității. Pentru simplitate, vom presupune că sunt date stările inițiale x 0 și x T finale ale sistemului. Să notăm cu z 1 (x 0 , u 1) valoarea funcției de obiectiv la prima etapă cu starea inițială a sistemului x 0 și cu controlul u 1 , cu z 2 (x 1 , u 2) corespunzătoare valoarea funcţiei de obiectiv numai la a doua etapă, .., prin
z i (x i -1 ,u i) - în stadiul I, ..., prin z N (x N -1 , u N) - în stadiul N. Este evident că
Este necesar să se găsească controlul optim u*= (; ;...;), astfel încât să livreze extremul funcției obiectiv (1) sub restricții.
Pentru a rezolva această problemă, o scufundăm într-o familie de altele asemănătoare. Să introducem o notație. Fie, respectiv, zonele
definiții pentru probleme similare la ultima etapă, ultimele două etc.;
– domeniul de definire a problemei originale. Să notăm cu F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), respectiv optimul condiționat valorile funcției de obiectiv la ultima etapă, două ultimele etc., la ultimele k, etc., la toate cele N etape.
Să începem de la ultima etapă. Fie x N-1 stările posibile ale sistemului la începutul etapei a N-a. Găsim:
F 1 (x N -1) = z N (x N -1, u N). (2)
Pentru ultimele două etape obținem
F2 (x N -2) = (Z N -1 (x N -2, uN -1) + F1 (x N -1)). (3)
De asemenea:
F3 (x N -3) = (Z N -2 (x N -3, u N -2) + F2 (x N -2)). (4)
………………………………………………….
Fk (x N-k) = (z N-k +1 (x N-k, u N-k +1) + Fk-1 (x N-k +1)). (5)
…………………………………………………..
F N (x 0) = (z 1 (x 0, u 1) + F N -1 (x 1)). (6)
Expresia (6) este o reprezentare matematică a principiului optimității. Expresia (5) este forma generală de scriere a valorii optime condiționat a funcției obiectiv pentru k etape rămase. Expresiile (2) – (6) se numesc ecuații funcționale Bellman. Natura lor recurentă (recurentă) este clar vizibilă, adică, pentru a găsi controlul optim la N trepte, trebuie să cunoașteți controlul optim condiționat la N – 1 etape anterioare etc. Prin urmare, ecuațiile funcționale sunt adesea numite recurente (recurente) Relațiile Bellman.
- Caracteristicile problemelor de programare dinamică
Pe baza celor de mai sus, putem evidenția următoarele caracteristici ale problemelor de programare dinamică.
- Considerăm un sistem a cărui stare la fiecare pas este determinată de vectorul x t. O schimbare suplimentară a stării sale depinde numai de starea dată x t și nu depinde de modul în care sistemul a ajuns în această stare. Astfel de procese sunt numite procese fără efect secundar.
- La fiecare pas este selectată o soluție u t, sub influența căreia sistemul trece din starea anterioară x t -1 în starea nouă x t . Această nouă stare este o funcție a stării de la începutul intervalului x t -1 și a deciziei u t adoptată la începutul intervalului, adică x t = x t (x t -1 ,u t).
- Actiunea la fiecare pas este asociata cu un anumit castig (venit, profit) sau pierdere (costuri), care depind de starea de la inceputul pasului (etapa) si de decizia luata.
- Pot fi impuse restricții asupra vectorilor de stare și de control, a căror combinație constituie regiunea soluțiilor fezabile.
- Este necesar să se găsească un astfel de control admisibil u t pentru fiecare pas t pentru a obține valoarea extremă a funcției obiectiv pentru toți T pașii.
Orice succesiune validă de acțiuni pentru fiecare pas care transferă sistemul din starea inițială în starea finală se numește strategie de control. O strategie de control care are ca rezultat o valoare extremă a funcției obiectiv se numește optimă.
Interpretarea geometrică a problemei de programare dinamică este următoarea. Fie n dimensiunea spațiului stărilor. În fiecare moment de timp, coordonatele sistemului au o valoare foarte specifică. Cu o modificare a timpului t, valorile coordonatelor vectorului de stare se pot schimba. Să numim tranziția unui sistem de la o stare la alta traiectoria mișcării sale în spațiul stărilor. O astfel de tranziție se realizează prin influențarea coordonatelor de stat. Spațiul în care stările sistemului servesc drept coordonate se numește spațiu fazelor. Problema de programare dinamică poate fi interpretată mai ales clar dacă spațiul de stare este bidimensional. Zona stărilor posibile în acest caz va fi descrisă printr-o anumită cifră, stările inițiale și finale ale sistemului - prin puncte x 0 (Fig. 1). Controlul este influența care transferă sistemul din starea inițială în starea finală. Pentru multe probleme economice, starea inițială sau finală nu este cunoscută, dar regiunea X 0 sau X T căreia îi aparțin aceste puncte este cunoscută.
Poza 1
Apoi controalele admisibile transferă punctele din regiunea X 0 la X T . Problema de programare dinamică poate fi formulată geometric astfel: găsiți o traiectorie de fază care începe în regiunea X 0 și se termină în regiunea X T pentru care funcția obiectiv atinge o valoare extremă. Dacă se cunosc stările inițiale și finale ale unei probleme de programare dinamică, atunci vorbim de o problemă cu capete fixe. Dacă se cunosc regiunile inițiale și finale, atunci vorbim de o problemă cu capete libere.
- PROBLEMA DE DISTRIBUIREA RESURSELOR
2.1 Expunerea generală a problemei
Să luăm în considerare aplicarea metodei de programare dinamică folosind exemplul distribuirii fondurilor între șase obiecte de reconstrucție ale unei companii de utilități de apă din oraș:
1. Stație centrală de pompare și filtrare;
2. Statie de pompare si filtrare estica;
3. Stație de pompare a apei;
4. Stație centrală de aerare;
5. Statie de aerare estica;
6. Stație de aerare de țară.
Suma totală a fondurilor prevăzute pentru dezvoltare nu este mai mare de 195 mii grivne. Pe baza calculelor tehnice și economice s-a stabilit că în urma reconstrucției, în funcție de suma fondurilor cheltuite, instalațiile vor avea productivitatea prezentată în Tabelul 1.1. Este necesar să se determine distribuția optimă a fondurilor între obiectele de reconstrucție, ceea ce va asigura creșterea maximă a productivității acestor obiecte. Astfel, această problemă folosește un criteriu de optimizare - productivitatea totală a întreprinderilor de obiecte de reconstrucție.
Tabelul 1.1 Date de intrare pentru productivitatea obiectelor de reconstrucție
Numărul de serie al obiectului |
Volumul resurselor alocate pentru dezvoltarea instalațiilor (mii UAH) |
|||||||||||||
Productivitatea obiectelor ca rezultat al dezvoltării (mii m3) |
||||||||||||||
- Schema bloc a programului
Figura 1. Programul principal
QtObj – numărul de obiecte
QtRes – numărul de resurse
effMatrix - matricea performanței obiectului,
distVector – vector al resurselor alocate
Pasul 1: Optimizarea condiționată
Pasul 2. Optimizare necondiționată
I = QtObj-1.0 formează rezultatul vectorial
Figura 2. Introducerea datelor
distVector – vector de distanță, effMatrix = matrice de performanță
dacă sunt introduse toate elementele matricei
dacă vectorul de performanță nu este
negativ
Figura 3. Optimizare condiționată,
formăm o matrice de ieșire (maximul funcției obiectiv)
outMatrix – matrice maximă țintă
QtObj – numărul de obiecte
QtRes – numărul de resurse
Matrice – matrice de performanță
distVect – vector de distanță (vector de resurse)
nu da Dacă prima întreprindere
Găsirea maximului
da maxItem = temp; outMatrix[i][j] = maxItem
- Structura algoritmului programului
- Intrare date – clasa DataDlg.
Membri variabili ai clasei.
//vector pentru stocarea cantității de resurse
std::vector
//matricea performanței obiectului
int** effMatrix;
//funcție pentru a converti un șir într-un număr
int StringToInt(CString);
//funcție de verificare a corectitudinii datelor introduse
BOOL FillMatrix();
//funcția de curățare a resurselor după închiderea ferestrei
virtual BOOL DestroyWindow();
//funcția de inițializare a dialogului
virtual BOOL OnInitDialog();
- Calculul rezultatelor - clasa principală a programului courseWorkDlg
Membri variabili ai clasei
intValue; //valoarea performanței
int MaxIndex;// index maxim în vectorul resursă
int Facilitate;//întreprindere
int Resurse;//resursa dedicata
Item**outMatrix; //matricea țintă maximă
std::vector
void BuildOutMatrix(int **,std::vector
afx_msg void OnBnClickedButton1(); // handler pentru a face clic pe butonul „Calculate”, care începe procesul de calcul.
virtual BOOL DestroyWindow();// ștergerea resurselor programului
- Ieșirea rezultatelor clasa Raport
Scopul acestei clase este de a scoate vectorul rezultat în formă tabelară.
2.4 Rezultatele programului
Introducerea inițială a datelor
- Introducerea datelor privind productivitatea obiectelor de reconstrucție
- Dacă nu sunt completate toate câmpurile
- Dacă este introdus un caracter incorect
Introducerea corectă a datelor
Arată rezultatul
- Introducere a datelor
Rezultatul programului
Introducerea inițială a datelor
Introducerea productivității obiectului
Aplicație.
Lista de programe
int DataDlg::StringToInt(CString str)
const wchar_t* s = T2CW(str);
int val = _wtoi(s);
// toate câmpurile sunt completate?
BOOL DataDlg::FillMatrix()
steag bool = adevărat;
pentru (int i = 0; i< Cells.GetSize(); i ++){
pentru (int j = 0; j< Cells.GetAt(i)->Edits.GetSize(); j++)(
CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;
dacă (temp->m_hWnd != NULL)(
temp->GetWindowText(str);
dacă (str.IsEmpty())(
MessageBox(L „Trebuie să completați toate câmpurile”, L „Eroare”, MB_ICONERROR | MB_OK);
Descrierea muncii
Scopul acestei lucrări este de a implementa pe computer o soluție la problema alocării optime a fondurilor pentru extinderea producției.
Obiectivele cursului:
Luați în considerare aspectele teoretice ale rezolvării problemelor de programare dinamică; natura recurentă a problemelor de acest tip; Principiile optimității lui Bellman.
Dezvoltarea algoritmului. Diagrame bloc. Structura algoritmului.
Implementarea computerizată a algoritmului dezvoltat în limbajul de programare selectat.
Conţinut
INTRODUCERE…………………………………………………………………2
Programare dinamică
Concepte de bază…………………………4
Principiile programării dinamice. Ecuații funcționale Bellman………….5
Caracteristicile problemelor de programare dinamică……………….10
Problema de alocare a resurselor………………………………12
Expunerea generală a problemei………………………….13
Schema bloc a programului
Structura algoritmului programului
Rezultatul programului
Concluzie
Bibliografie
Aceste tipuri de sarcini se bazează pe Funcțiile Bellman iar soluția folosește metoda de baleiaj înapoi (vezi. Sarcini tipice). De asemenea, puteți utiliza serviciul Procedura de trecere directă.
Instrucțiuni. Selectați numărul de întreprinderi și numărul de linii (numărul de opțiuni de investiții efective), faceți clic pe Următorul (vezi. Exemplu de umplere). Dacă veniturile și soldurile întreprinderilor sunt date sub forma funcțiilor f(x) și g(x), problema rezolvat folosind acest calculator.
Exemplul nr. 1. Determinați planul optim de extindere a producției a trei întreprinderi, dacă profitul lor anual este cunoscut în absența investițiilor și cu o investiție de 1, 2, 3 sau 4 milioane Stabiliți care investiție va avea ca rezultat creșterea procentuală maximă a profitului.
| f1 | f2 | f3 | x i |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
Etapa I. Optimizare conditionata.
primul pas. k = 3.
| e 2 | tu 3 | e 3 = e 2 - u 3 | f 3 (u 3) | F* 3 (e 3) | u 3 (e 3) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
al 2-lea pas. k = 2.
| e 1 | tu 2 | e 2 = e 1 - u 2 | f 2 (u 2) | F* 2 (e 1) | F 1 (u 2 ,e 1) | F* 2 (e 2) | u 2 (e 2) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
al 3-lea pas. k = 1.
| e 0 | tu 1 | e 1 = e 0 - u 1 | f 1 (u 1) | F* 1 (e 0) | F 0 (u 1 ,e 0) | F* 1 (e 1) | u 1 (e 1) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Notă: Coloanele 1 (fonduri investite), 2 (proiect) și 3 (sold fond) sunt aceleași pentru toate cele trei tabele, așa că ar putea fi făcute comune. Coloana 4 este completată pe baza datelor inițiale privind funcțiile de venit, valorile din coloana 5 sunt preluate din coloana 7 din tabelul precedent, coloana 6 este completată cu suma valorilor coloanelor 4 și 5 (în tabelul pasului 3 lipsesc coloanele 5 și 6).
Coloana 7 înregistrează valoarea maximă a coloanei precedente pentru o stare inițială fixă, iar coloana 8 înregistrează controlul din coloana 2, care ajunge la maximum 7.
Etapa II. Optimizare necondiționată.
Din tabelul pasului 3 avem F* 1 (e 0 = 4 milioane de ruble) = 780 de mii de ruble, adică profitul maxim din investiție e 0 = 4 milioane de ruble. egal cu 780 de mii de ruble.
Din același tabel aflăm că prima întreprindere ar trebui să i se aloce u* 1 (e 0 = 4 milioane de ruble) = 0 milioane de ruble.
În acest caz, soldul fondurilor va fi: e 1 = e 0 - u 1, e 1 = 4 - 0 = 4 milioane de ruble.
Din tabelul pasului 2 avem F* 2 (e 1 = 4 milioane de ruble) = 740 de mii de ruble, i.e. profitul maxim la e 1 = 4 milioane de ruble. egal cu 740 de mii de ruble.
Din același tabel aflăm că a doua întreprindere ar trebui să i se aloce u* 2 (e 1 = 4 milioane de ruble) = 1 milion de ruble.
În acest caz, soldul fondurilor va fi: e 2 = e 1 - u 2, e 2 = 4 - 1 = 3 milioane de ruble.
Ultima întreprindere primește 3 milioane de ruble. Deci, o investiție de 4 milioane de ruble. trebuie distribuită după cum urmează: prima întreprindere nu trebuie să i se aloce nimic, a doua întreprindere ar trebui să i se aloce 1 milion de ruble, a treia întreprindere ar trebui să i se aloce 3 milioane de ruble, ceea ce va asigura un profit maxim de 780 de mii de ruble.
Exemplul nr. 2. Există 4 întreprinderi, între care este necesar să se distribuie 100 de mii de unități convenționale. unitati fonduri. Valorile creșterii producției la întreprindere, în funcție de fondurile alocate X, sunt prezentate în tabel. Elaborați un plan optim de alocare a fondurilor pentru a maximiza creșterea globală a producției.
Metoda de programare dinamică vă permite să rezolvați cu succes multe probleme economice (vezi, de exemplu,). Să luăm în considerare una dintre cele mai simple astfel de probleme. Avem la dispozitie o rezerva de fonduri (resurse) K, care trebuie distribuita intre intreprinderi. Fiecare dintre întreprinderi, atunci când unele fonduri sunt investite în ea, generează venituri care depind de , adică reprezentând un fel de funcție Toate funcțiile sunt date (desigur, aceste funcții sunt nedescrescătoare).
Întrebarea este cum ar trebui să fie distribuite fondurile K între întreprinderi, astfel încât acestea să genereze venituri maxime?
Această problemă este ușor de rezolvat folosind metoda de programare dinamică. Deși în formularea sa nu conține nicio mențiune despre timp, este totuși posibilă desfășurarea mentală a operațiunii de distribuire a fondurilor într-o anumită secvență, considerând că primul pas este investirea fondurilor în întreprindere, al doilea - la etc.
Sistemul gestionat S în acest caz este fondurile sau resursele care sunt distribuite. Starea sistemului S înainte de fiecare pas este caracterizată de un număr S - stocul disponibil de fonduri neinvestit încă. În această sarcină, „managementul în etape” reprezintă fondurile alocate întreprinderilor. Este necesar să se găsească controlul optim, adică un astfel de set de numere pentru care venitul total este maxim:
Să rezolvăm această problemă mai întâi în formă generală, formulă și apoi pentru date numerice specifice. Să găsim pentru fiecare pas câștigul optim condiționat (de la acest pas până la final), dacă am abordat acest pas cu o rezervă de fonduri S. Să notăm câștigul optim condiționat , și controlul optim condiționat corespunzător - fondurile investite în intreprinderea -
Să începem optimizarea de la ultimul pas. Să abordăm acest pas cu un sold de fonduri S. Ce ar trebui să facem? Evident, investiți întreaga sumă S în întreprindere. Prin urmare, controlul optim condiționat la pasul al treilea: acordați ultimei întreprinderi toate fondurile disponibile S, adică.
și câștigul optim condiționat
Având în vedere un întreg interval de valori ale lui S (localizându-le destul de aproape), vom ști pentru fiecare valoare a lui S . Ultimul pas este optimizat.
Să trecem la penultimul pas. Să o abordăm cu o rezervă de fonduri S. Să notăm câștigul optim condiționat la ultimii doi pași: (care este deja optimizat). Dacă alocam fonduri întreprinderii la pas, atunci vor rămâne pentru ultimul pas câștigurile noastre la ultimii doi pași vor fi egale cu
și trebuie să găsiți unul la care acest câștig să fie maxim:
Semnul înseamnă că valoarea maximă este preluată peste toate valorile posibile (nu putem pune mai mult de S), din expresia dintre paranteze. Acest maxim este câștigul optim condiționat pentru ultimii doi pași, iar valoarea la care se atinge acest maxim este controlul optim condiționat la pas.
iar controlul optim condițional corespunzător este valoarea la care se atinge acest maxim.
Continuând în acest fel, vom ajunge în sfârșit la întreprindere. Aici nu va fi nevoie să variem valorile lui S; știm cu siguranță că stocul de fonduri înainte de primul pas este egal cu K:
Deci, a fost găsit câștigul (venitul) maxim din toate întreprinderile. Acum nu mai rămâne decât să „citești recomandările”. Valoarea la care se atinge maximul (13,4) este controlul optim la primul pas.
După ce investim aceste fonduri în prima întreprindere, le vom rămâne. „Citind” recomandarea pentru această valoare a lui S, alocăm suma optimă de fonduri celei de-a doua întreprinderi: și așa mai departe până la sfârșit.
Acum să rezolvăm un exemplu numeric. Stocul inițial de fonduri (unități standard) și este necesar să îl distribuiți în mod optim între cinci întreprinderi Pentru simplitate, presupunem că sunt investite doar sume întregi de fonduri. Funcțiile venitului sunt date în Tabelul 13.1.
Tabelul 13.1
În fiecare coloană, pornind de la o anumită sumă de investiție, veniturile încetează să crească (în realitate, aceasta corespunde faptului că fiecare întreprindere este capabilă să „stăpânească” doar o cantitate limitată de fonduri).
Să efectuăm optimizarea condiționată așa cum este descris mai sus, pornind de la ultimul pas. De fiecare dată când ne apropiem de pasul următor, având o rezervă de fonduri?, încercăm să alocăm una sau alta sumă de fonduri pentru acest pas, luăm câștigurile la acest pas conform tabelului 13.1, le adăugăm cu câștigurile deja optimizate la toate ulterioare. pași până la final (ținând cont că avem deja mai puține fonduri, doar pentru suma de fonduri pe care am alocat-o) și găsim investiția la care această sumă atinge maximul. Această investiție este controlul optim condiționat la acest pas, iar maximul în sine este câștigul optim condiționat.
Tabelul 13.2 prezintă rezultatele optimizării condiționate pentru toți pașii. Tabelul este construit după cum urmează: prima coloană prezintă valorile stocului de fonduri S cu care abordăm acest pas. Tabelul este împărțit în continuare în cinci perechi de coloane, corespunzătoare numărului pasului.
Tabelul 13.2
Prima coloană a fiecărei perechi dă valoarea controlului optim condiționat, a doua - câștigul optim condiționat. Tabelul este umplut de la stânga la dreapta, de sus în jos. Decizia la al cincilea - ultimul - pas este forțată: toate fondurile sunt alocate; La toți ceilalți pași, soluția trebuie optimizată. Ca urmare a optimizării secvențiale a pasilor 5, 4, 3, 2 și 1, vom primi o listă completă a tuturor recomandărilor pentru controlul optim și câștigul optim necondiționat W pentru întreaga operațiune - în acest caz este egal cu 5,6 . În ultimele două coloane din Tabelul 13.2, este completat un singur rând, deoarece știm exact starea sistemului înainte de începerea primului pas: . Comenzile optime la toate etapele sunt evidențiate cu un cadru. Astfel, am primit concluzia finală: trebuie să alocăm două unități din zece primei întreprinderi, cinci unități celei de-a doua, două celei de-a treia, niciuna celei de-a patra și o unitate celei de-a cincea. Cu această distribuție, venitul va fi maxim și egal cu 5,6.
