Rezolvarea problemei alocării resurselor folosind metoda de programare dinamică. Rezolvarea diverselor probleme practice de programare dinamică: Alocarea optimă a resurselor
Programarea dinamică (DP) este o metodă de găsire a soluțiilor optime în probleme cu o structură în mai multe etape.
Să prezentăm formularea generală a problemei DP. Se are în vedere un proces controlat (distribuirea fondurilor între întreprinderi, utilizarea resurselor pe un număr de ani etc.). Ca rezultat al controlului, sistemul (obiectul de control) este transferat din starea inițială la starea 
. Să presupunem că controlul poate fi împărțit în 
trepte. La fiecare pas, se selectează unul dintre numeroasele controale admisibile 
, transferând sistemul într-una dintre stările setului 
. Elementele setului 
Și 
sunt determinate din condiţiile unei sarcini specifice. Secvența stărilor sistemului poate fi reprezentată ca un grafic de stare prezentat în Fig. 3.1.
Fiecare pas din drum n efectul este atins 
. Să presupunem că efectul total este suma efectelor realizate la fiecare pas. Atunci problema DP se formulează astfel: determinați un astfel de control admisibil 
, care transferă sistemul de la stat 
intr-o stare 
, la care funcționează obiectivul 
ia cea mai mare (cea mai mică) valoare, adică
Rezolvarea problemelor prin metoda DP se realizează pe baza principiului optimității, care a fost formulat de omul de știință american R. Bellman: indiferent de starea sistemului ca urmare a oricărui număr de pași, la pasul următor este necesar să alegeți controlul astfel încât, în combinație cu controlul optim la toate etapele ulterioare, să ducă la câștiguri optime la toate etapele rămase, inclusiv acesta.
Să notăm prin 
valoare conditionat optima a functiei obiectiv pe intervalul de la pas n până la ultimul 
-a treaptă inclusiv, cu condiția ca înainte n La pasul al treilea, sistemul era într-una din stările setului 
, și pe n La pasul a treia, un astfel de control a fost selectat din set 
, care asigura funcția obiectiv o valoare optimă condiționat, atunci 
valoarea optimă condiționat a funcției obiectiv în intervalul de la ( n+1
)a la 
-al-lea pas inclusiv.
În notația acceptată, principiul optimității Bellman poate fi scris sub formă matematică după cum urmează
Egalitatea (3.1) se numește ecuația funcțională principală programare dinamică. Pentru fiecare sarcina specifica ecuația are o formă specială.
Procedura de calcul a metodei DP este împărțită în două etape: optimizare condiționată și necondiționată.
La scenă condiţional optimizareîn conformitate cu ecuația funcțională, se determină controale optime pentru toate stările posibile la fiecare pas, începând de la ultimul.
La scenă optimizare necondiționată pașii sunt considerați pornind de la primul. Inca din starea initiala 
cunoscut, controlul optim este selectat din set 
. Selectat control optim
aduce sistemul într-o stare foarte specifică 
. Datorită faptului că starea iniţială 
este cunoscută la începutul pasului al doilea, devine posibilă alegerea controlului optim la pasul al doilea 
etc. Astfel, se construiește un lanț de soluții de optimizare necondiționată interconectate.
3.1. Problemă de alocare optimă a resurselor
Să i se aloce asociației o anumită cantitate de resurse materiale pentru reconstrucția și modernizarea producției principale X. Disponibil Nîntreprinderi între care este necesar să se distribuie această resursă. Să notăm prin 
profitul pe care alocarea îl aduce economiei naţionale j-a întreprindere 
unități de resurse. Se presupune că marja de profit depinde atât de cantitatea de resurse alocată, cât și de întreprindere. Mai mult, profitul primit de întreprinderi se măsoară în aceleași unități, iar profitul total al asociației este format din profiturile întreprinderilor individuale. Este necesar să se găsească planul optim de alocare a resurselor între întreprinderi, în care profitul total al asociației să fie maxim.
Sarcina la îndemână trebuie considerată ca una cu mai multe etape.
La scenă optimizare condiționată vom lua în considerare eficiența investiției într-una (de exemplu, prima întreprindere), două întreprinderi împreună (prima și a doua), trei întreprinderi împreună (prima, a doua și a treia), etc. și, în final, toate N intreprinderi impreuna. Sarcina este de a determina cea mai mare valoare a funcției 
cu conditia ca 
.
Să folosim relația de recurență Bellman (3.1), care pentru această problemă conduce la următoarele ecuații funcționale pentru 
:
Iată funcția 
determină profitul maxim al primei întreprinderi la alocarea acestuia X unități de resurse, funcție 
determină profitul maxim al primei și celei de-a doua întreprinderi împreună la alocarea acestora X unități de resurse, funcție 
determină profitul maxim al primei, a doua și a treia întreprinderi împreună la alocarea acestora X unități de resurse etc. și, în sfârșit, funcția 
determină profitul maxim al tuturor întreprinderilor împreună la alocarea acestora X unități de resurse.
În etapa de optimizare necondiționată se determină planul optim de distribuire a resurselor între întreprinderi.
Exemplul 3.1.
Pentru a crește volumul producției de produse care sunt la mare căutare, au fost alocate fonduri în valoare de 50 de milioane de ruble către patru întreprinderi ale asociației de producție. Fiecare întreprindere poate fi alocată: 0, 10, 20, 30, 40 sau 50 de milioane de ruble. În același timp, creșterea anuală a producției de către fiecare dintre întreprinderi 
în funcție de investiție este cunoscută și prezentată în tabel. 3.1.
Tabelul 3.1
|
Volumul fondurilor alocate X(milioane de ruble) |
Creșterea anuală a producției de produse (milioane de ruble), în funcție de volumul fondurilor alocate |
|||
|
|
|
|
|
|
Găsiți planul optim de repartizare a fondurilor între întreprinderi, asigurând creșterea anuală maximă a producției de către asociația de producție.
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ări 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ăugări 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 astfel î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 nodurile unui grafic direcționat ponderat.
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ă, în 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 la ordine inversă Din tabel în 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 pentru acasă:
(2) clauza 5.1
Ср12: formarea și asimilarea conținutului material teoretic
Semnătura profesorului
Metoda de programare dinamică vă permite să rezolvați cu succes multe obiective 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.
Sistem controlat S in în acest caz,- fonduri sau resurse 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 sfârșit), dacă ajungem la 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 întreprindere -
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 în întreprindere întreaga sumă S. 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 remunerația optimă condiționată pe doi ultimii pași x: (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 pasul 1.
După ce investim aceste fonduri în prima întreprindere, le vom rămâne. „Citind” recomandarea pentru această valoare S, o alocăm celei de-a doua întreprinderi cantitate optimaînseamnă: etc până la capăt.
Acum să rezolvăm un exemplu numeric. Stocul inițial de fonduri (unități standard) și este necesar să îl distribuiți optim între cinci întreprinderi. Pentru simplitate, presupunem că sunt investite doar sume întregi de fonduri. Funcțiile de venit 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 astfel: 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 rezultat al optimizării secvențiale a pasilor 5, 4, 3, 2 și 1 obținem lista plina toate recomandările pentru un control 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.
Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos
Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.
postat pe http://www.allbest.ru/
Problemă de alocare a resurselor folosind metoda de programare dinamică
Pentru a extinde capacitatea de producție a trei întreprinderi A, B și C, se alocă un anumit număr de unități de energie electrică suplimentară în valoare de x 0 = 8 unități. Electricitatea poate fi eliberată sub formă de 1, 2, 3, 4, 5, 6, 7 și 8 unități. Investind x i unități de energie electrică în dezvoltarea i-a întreprindere, puteți primi venituri de la i unități la întreprindere. Exista diferite variante x i (k) alocarea de energie electrică suplimentară. Ele aduc venituri la i (k), k=1,n. Opțiuni posibile dezvoltarea întreprinderilor sunt prezentate în tabelul 1. Venitul total pentru toate întreprinderile ar trebui să fie maxim, adică y=? y i (k)>max
Masa 1. Opțiuni de dezvoltare a întreprinderii
|
Opțiunea k |
Întreprinderea A |
Întreprinderea B |
Întreprinderea C |
||||
Matematic punerea în scenă sarcini:
y=? la i (k)> max
?X i (k)?x 0
Soluţie:
Să începem să luăm în considerare procedura de rezolvare a problemei în discuție din ultima etapă (3 pași) (Tabelul 2), la care investițiile sunt alocate întreprinderii C. Se caută controlul optim condiționat în etapa a treia ca soluție a ecuației
g C(S2)=max kfc, xC(k)?S2, k=1,2,3,4
Masa 2. Soluții optime condiționat (pasul 3)
|
Stat |
Control |
|||||||
Există patru posibilități de investire a fondurilor - controale în patru etape x C (1) = 0 unități, x C (2) = 1 unitate, x C (3) = 2 unități, x C (4) = 3 unități. și nouă stări teoretic posibile ale sistemului S 2 premergătoare alocării de fonduri către întreprinderea C - volumele de investiții nedistribuite la etapa a 3-a: 0,1,2,3,4,5,6,7,8.
Să presupunem că sistemul a fost în starea S 2 = 2. Atunci, pentru controlul pasului x C (2) = 1, venitul lui C (2) va fi egal cu 3 unități. (Tabelul 3) și controlul pas x C (3) = 2 vor fi optime pentru această stare, dând un câștig maxim condiționat g c (S 2) = 5. Dacă sistemul era în starea S 2 = 3, atunci toate comenzile pasului sunt permise: x C (1) = 0 unități, x C (2) = 1 unitate, x C (3) = 2 unități, x C (4) = 3 unități. , iar controlul optim va fi x C (4) = 3, ceea ce asigură un câștig maxim condiționat g c (S 2) = 6.
Tabelul 3 distribuția dinamică a investițiilor în programare
Toate stările posibile care preced etapa a 3-a sunt completate în mod similar. Valori optime indicatorii sunt evidențiați cu caractere aldine în tabele.
În continuare, în același mod este considerată a doua etapă (Tabelul 4), care constă în alocarea investițiilor către întreprinderea A. În a doua etapă, câștigul total este suma câștigurilor primite în a treia și a doua etapă și este dat prin raportul:
g A (S 1)=max k f A + g c], x A (k)?S 1, k=1,2,3,4
Astfel, pentru starea S 1 =3 cu control în trepte x A (2) = 1 se obține:
g A (S 1)=max k f A +g c ]
Max k 4+g c =4+5=9, unde găsim din tabelul 1, și g c din tabelul 3. Toate stările sunt completate în mod similar.
Masa 4. Soluții optime condiționat (pasul 2)
|
Stat |
f A +g c |
Control |
||||||
Aici apar situații în care soluția optimă nu va fi singura.Astfel, în starea S 1 = 3, controalele trepte x A (2) = 1 și x A (3) = 2 vor fi optime condiționat, dând același câștig g A (S 1)=9
Masa 5. Soluții optime necondiționat (pasul 1)
La prima etapă (Tabelul 5) - alocarea investițiilor către întreprinderea B - există o singură stare anterioară a sistemului, corespunzătoare stării inițiale S 0 =8. Câștigul optim necondiționat este determinat de expresia:
y * = g B (S 0)= max k (f A +g A) x în (k)?S 0 =x 0, k=1,2,3,4,5
Controalele optime necondiționat care asigură venituri maxime pot fi diferite.
Schemă pentru găsirea tuturor optiuni optime distribuția investițiilor între întreprinderi (Tabelul 6) este prezentată în Figura 1.
Masa 6. Distribuția optimă a investițiilor.
Figura 1. Schema de repartizare optimă a investițiilor între întreprinderi
Concluzie: având în vedere problema alocării resurselor prin metoda de programare dinamică, au fost identificate două opțiuni pentru alocarea optimă a resurselor.
Postat pe Allbest.ru
...Documente similare
caracteristici generaleși indicatorii de performanță economică a celor trei întreprinderi studiate. Rezolvarea problemei planificării producției, precum și a distribuției investițiilor folosind programare liniară și dinamică. Analiza comparativa rezultate.
lucrare de curs, adăugată 25.04.2015
Procese în mai multe etape în sarcini dinamice. Principiul optimității și relațiilor de recurență. Metoda de programare dinamică. Probleme de alocare optimă a fondurilor pentru extinderea producției și planificarea programului de producție.
lucrare de curs, adăugată 30.12.2010
Metoda de programare dinamică și etapele sale principale. Strategia optimă de înlocuire a echipamentelor. Minimizarea costurilor pentru construcția și funcționarea întreprinderilor. Distributie optima resurse în STROYKROVLYA LLC și investiții în PKT Khimvolokno.
lucrare curs, adăugată 01.08.2015
Model matematic de planificare a producției. Întocmirea unui plan optim activitati de productie metoda intreprinderii programare liniară. Găsind cel mai bun mod repartizarea resurselor băneşti în perioada de planificare.
teză, adăugată 08.07.2013
Calculul costurilor de transport folosind metoda costuri minime. Găsirea egalității optime condiționate în procesul de programare dinamică. Liniar ecuație algebrică Kolmogorov pentru timpul mediu de non-defecțiune al unui sistem redundant.
lucrare de curs, adăugată 14.01.2011
Metoda grafica rezolvarea problemei optimizării proceselor de producţie. Aplicarea unui algoritm simplex pentru a rezolva o problemă de management al producției optimizată din punct de vedere economic. Metodă de programare dinamică pentru selectarea profilului de traseu optim.
test, adaugat 15.10.2010
Plan de distribuție optim Baniîntre întreprinderi. Elaborarea unui plan pentru fiecare întreprindere în care va fi rentabilitatea investiției cea mai mare valoare. Utilizarea metodelor de programare liniară și dinamică.
lucrare curs, adaugat 16.12.2013
Trăsături de caracter probleme de programare liniară. Formularea generală a problemei de planificare a producţiei. Construirea unui model matematic de distribuție a resurselor companiei. Analiza de sensibilitate soluție optimă. Întocmirea unui raport de sustenabilitate.
prezentare, adaugat 12.02.2014
Găsirea portofoliului optim de valori mobiliare. Revizuirea metodelor de rezolvare a problemei. Construirea unui model matematic. Problemă de programare a conului. Dependența vectorului de distribuție a capitalului inițial de unul dintre parametrii inițiali.
teză, adăugată 02.11.2017
Model de programare dinamică. Principiul optimității și ecuația Bellman. Descrierea procesului de modelare și construire a unei scheme de programare dinamică computațională. Problema minimizării costurilor de construcție și funcționare a întreprinderilor.
Instrucțiuni. Selectați numărul de afaceri.
Exemplul nr. 1. Funcționarea a două întreprinderi este planificată pentru n ani. Resurse inițiale egal cu s0. Fondurile x investite în prima întreprindere la începutul anului dau profit f1(x) la sfârșitul anului și sunt returnate în valoare de g1(x). Fondurile y investite în a 2-a întreprindere la începutul anului oferă profit f2(y) la sfârșitul anului și sunt returnate în valoare de g2(y). La sfârșitul anului, fondurile returnate sunt redistribuite între industrii. Determinați planul optim de distribuție a fondului și găsiți profitul maxim.
Să rezolvăm problema folosind metoda de programare dinamică. Operare de control proces de producție Să o împărțim în etape. Pe fiecare dintre ele vom alege controlul astfel încât acesta să conducă la câștiguri atât pe în această etapă, și pe toate cele ulterioare până la finalul operațiunii. Aceasta este principiul optimității, formulat de matematicianul american A. Bellman.
Să împărțim întreaga perioadă în trei etape pe an și să le numărăm începând de la prima.
Să notăm prin x kȘi y k suma fondurilor alocate fiecărei întreprinderi în etapa k-a și după x k + y k = un k- suma totală a fondurilor în această etapă. Apoi prima întreprindere aduce 3 în această etapă x k, iar al doilea este 4 y k unități de venit. Venitul total la a k-a etapă 3 x k + 4y k.
Să notăm prin f k ( A k) este venitul maxim pe care industria îl primește de la ambele întreprinderi la a k-a și toate cele ulterioare. Atunci ecuația funcțională care reflectă principiul optimității Bellman ia forma:
f k (a k)=max(3x k + 4y k +f k +1 (a k +1)).(1)
Deoarece x k + y k = a k , atunciy k = a k - x k și3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . De aceeaf k (a k) = max(-x k + 4a k + f k+1 (ak+1)). (2)
0 ≤ x k ≤ a k
În plus, ak este fondurile alocate întreprinderilor în etapa k-a și sunt determinate de soldul fondurilor primite în etapa anterioară (k-1). Prin urmare, în funcție de condițiile problemei, control optim în fiecare etapă
ak = 0,5x k -1 + 0,2y k -1 = 0,5x k -1 +0,2(a k -1 -x k -1) = 0,3x k -1 +0,2a k -1 . (3)
eu. Conditii de optimizare
Începem planificarea din ultima a treia etapă
La k=
3
obținem de la (2)
f 3 (a 3) = max (- x 3 + 4a 3 + f 4 (a 4))
0 ≤ x 3 ≤ a 3
Din moment ce nu există a patra etapă, atunci f 4 (a 4)=0Și
f 3 (a 3) = max (- x 3 + 4a 3 )=4a 3
0 ≤ x 3 ≤ a 3
(expresie maximă ( -
x 3 + 4a 3) va fi la x 3 =0)).
Deci pentru al treilea ultima etapă avem: f 3 (a 3) = 4un 3,x 3 = 0,y 3 =a 3 -x 3 =un 3,
Unde A 3 = 0,3x 2 + 0,2a 2, care rezultă din formula (3).
La k = 2 din (2) și (3) obținem:
f(a 2) = max (-x 2 + 4a 2 + f 3 (a 3))=
0 ≤ x ≤ a 2
=max (-x 2 + 4a 2 + 4a 3 )= max (-x 2 + 4a 2 + 4( 0,3x 2 + 0,2a 2)) max(0,2x 2 + 4,8a 2 ) 5a
0 ≤ x ≤ a 2
deoarece maximul expresiei ( 0,2
x 2 + 4,8a 2) va fi la x 2 =a 2.
Atunci pentru a doua etapă avem: f 2 (a 2) = 5a 2, x 2 = a 2, y 2 = a 2 x 2 = 0, în timp ce
a 2 = 0,3x 1 + 0,2a 1 ținând cont de (3).
La k = 1ținând cont de (2) și (3) obținem:
f 1 (a 1) = max (-x 1 + 4a 1 + f 2 (a 2))=
0 ≤ x ≤ a 1
= max (-x 1 + 4a 1 + 5a 2 )= max (-x 1 + 4a 2 + 5(0.3x 1 + 0.2a 2))= max (0.5x 1 + 5a 1 )=5, 5a 1
0 ≤ x ≤ a 1
la x 1 = a 1.
Deci pentru prima etapă f 1 (a 1) = 5,5a 1,x 1 =a 1,y 1 = 0.
Procesul s-a încheiat. În prima etapă, se cunoaște suma totală a fondurilor distribuite - a 1= 900 de unități Atunci venitul maxim primit de ambele întreprinderi în trei ani va fi f 1 (a 1) = 5,5*900 = 4950 den. unitati
II. Optimizare necondiționată
Să aflăm care ar trebui să fie managementul optim al procesului de alocare a fondurilor între prima și a doua întreprindere pentru a obține venituri maxime în valoare de 4950 den. unitati
anul 1. Deoarece x 1 =a 1Și ,
y 1 = 0, apoi toate fondurile în valoare de 900 den. unitati sunt date primei întreprinderi.
al 2-lea an. Fondurile sunt alocate a 2 = 0,3x 1 + 0,2a 1 = 0,5 a 1=450 de unități, x 2 = a 2 , y 2 = 0.
Toate sunt transferate la prima întreprindere.
al 3-lea an. Fondurile sunt alocate A 3 = 0,3x 2 + 0,2a 2 = 0,5 a 2= 225 unități, x 3 = 0,y 3 =a 3. Toate sunt transferate la a doua întreprindere.
Prezentăm rezultatele soluției sub forma unui tabel.
| Perioadă | Facilităţi | Întreprinderea nr. 1 | Întreprinderea nr. 2 | Rest | Sursa de venit |
| 1 | 900 | 900 | 0 | 450 | 2700 |
| 2 | 450 | 450 | 0 | 225 | 1350 |
| 3 | 225 | 0 | 225 | 45 | 900 |
| 4950 |
Exemplul nr. 2. Distribuția optimă în etape a fondurilor între întreprinderi în perioada de planificare.
Conducerea companiei, care are un acord de cooperare cu trei întreprinderi mici, le-a alocat capital de lucru în valoare de 100.000 USD pentru perioada anuală planificată. Pentru fiecare întreprindere sunt cunoscute funcțiile venitului trimestrial și soldului trimestrial al capitalului de lucru, în funcție de suma x alocată trimestrului. La începutul trimestrului, fondurile sunt repartizate integral între trei întreprinderi (venitul se calculează din aceste fonduri investite), iar la sfârșitul trimestrului, fondurile rămase sunt acumulate de conducerea companiei și din nou repartizate integral între întreprinderilor.
Întocmește un plan de repartizare trimestrială a fondurilor pentru anul (4 trimestre), permițându-ți să obții venitul total maxim pe an.
f1 (x)=1,2x, f2 (x)=1,5x, f3 (x)=2x; g 1 (x)=0,7x, g 2 (x)=0,6x, g 3 (x)=0,1x
