Alocarea optimă a resurselor folosind metoda de programare dinamică. Principiul optimității. Ecuația Bellman. Problema ordinului înmulțirii matricelor: date matrice, ..., se cere minimizarea numărului de operații scalare pentru înmulțirea lor

ABSTRACT

Introducere

Programare dinamică- o metodă de optimizare adaptată operaţiilor în care procesul decizional poate fi împărţit în etape (etape). Astfel de operații se numesc în mai mulți pași.

Începutul dezvoltării programare dinamică datează din anii 50 ai secolului XX. și este asociat cu numele lui Richard Ernest Bellman.

Dacă modelele programare liniară poate fi folosit în economie pentru a lua decizii de planificare la scară largă în situații complexe, apoi modelele de programare dinamică sunt folosite pentru a rezolva probleme de o scară mult mai mică:

ü la elaborarea regulilor de gestionare a stocurilor;

ü la distribuirea resurselor de investiții între proiecte alternative;

ü la întocmirea planurilor calendaristice pentru curentul şi revizuire echipamente complexe și înlocuirea acestuia etc.

1. Formularea generală a problemei de programare dinamică

programarea dinamică a ecuațiilor Bellman

În considerare proces controlat, de exemplu, procesul de distribuire a fondurilor între întreprinderi, utilizarea resurselor pe un număr de ani, înlocuirea echipamentelor etc. Ca rezultat al controlului, sistemul (obiectul de control) S este transferat din starea inițială s 0a afirma s n . Lăsați controlul să fie împărțit în n pași, adică decizia se ia secvenţial la fiecare pas, iar controlul care transferă sistemul S din starea iniţială în starea finală este un set de n decizii de management pas cu pas.

Să notăm cu X k decizia managementului asupra pasul k(k=1, 2, …, n). Variabilele X k satisfac unele restricții și în acest sens sunt numite admisibile (X k poate fi un număr, un punct din spațiul n-dimensional sau o caracteristică calitativă).

Fie X=(X 1, X 2, …, X n ) - control care transferă sistemul S din starea s 0a afirma s n . Să notăm cu s k starea sistemului (caracterizat prin un anumit set parametrii și valorile lor specifice) după k-a etapă de control. Mai mult, starea sistemului s k la sfârşitul pasului k depinde numai de starea anterioară s k-1 și decizia managementului la a k-a pasă X k (adică nu depinde direct de condițiile anterioare și de deciziile de management). Această cerință se numește „nicio consecință” și poate fi exprimată prin următoarele ecuații de stare:

Astfel, obținem o succesiune de stări s0, s1, …, sk-1, sk, …, sn-1, sn. Apoi n-pas proces de management poate fi reprezentat schematic după cum urmează:

Fie ca indicatorul de eficiență al pasului k să fie exprimat printr-o funcție:

iar eficiența întregului proces în mai multe etape luat în considerare este următoarea funcție aditivă:

Apoi problema de optimizare pas cu pas (problema de programare dinamică) se formulează astfel: se determină un control admisibil X care transferă sistemul S din starea s0 în starea sn, la care funcția obiectiv Z ia cea mai mare (cea mai mică) valoare.

O problemă de programare dinamică are următoarele caracteristici:

Problema de optimizare este interpretată ca un proces de control în n pași.

Funcția obiectiv este egală cu suma funcțiilor obiectiv ale fiecărui pas.

Alegerea controlului la pasul k depinde doar de starea sistemului la acest pas și nu afectează pașii anteriori (absența părere).

Starea sk după pasul k-a de control depinde doar de starea anterioară sk-1 și de controlul Xk („fără consecințe”).

La fiecare pas, controlul Xk depinde de un număr finit de variabile de control, iar starea sk depinde de un număr finit de parametri.

2. Principiul optimității și ecuațiile Bellman

Principiul optimitățiia fost formulat pentru prima dată de Richard Ernest Bellman în 1953 (așa cum a fost interpretat de E.S. Wentzel):

Oricare ar fi starea sistemului ca urmare a oricărui număr de pași, la pasul următor este necesar să se aleagă controlul în așa fel încât acesta, împreună cu controlul optim la toți pașii următori, să conducă la câștig optim la toți pașii rămași, inclusiv pe acesta.

RE. Bellman a formulat și condițiile în care principiul este adevărat. Cerința principală este ca procesul de control să fie fără feedback, adică. controlul la acest pas nu ar trebui să afecteze pașii anteriori.

Sa luam in considerare sarcină comună programare dinamică prezentată mai sus. La fiecare pas cu excepția ultimului pentru orice stare a sistemului s k-1 decizia managementului X k este necesar să alegeți „cu precauție”, deoarece această alegere afectează starea ulterioară a sistemului sk .

La ultimul pas, pe baza stării sistemului s n-1 decizia managementului X n poate fi planificat local în mod optim, adică bazat numai pe considerentele acestui pas.

Să luăm în considerare ultimul al n-lea pas:

s n-1 - starea sistemului la începutul pasului a n-a;

s n - starea finală a sistemului;

X n - control la pasul a n-a;

f n (s n-1 , X n ) este funcția obiectivă (recompensă) a pasului a n-a.

Conform principiului optimității, X n trebuie alese astfel încât pentru orice stări ale sistemului s n-1 obține optimul funcție obiectivă la acest pas.

Să notăm cu optimul (pentru certitudine vom lua maxim) al funcției obiectiv - un indicator al eficienței pasului a n-a, cu condiția ca la începutul ultimului pas sistemul S să fie într-o stare arbitrară sn-1 , iar la ultimul pas controlul a fost optim.

se numește maximul condiționat al funcției obiectiv la pasul a n-a și este determinat de următoarea formulă:

Maximizarea se realizează peste toate controalele admisibile Xn.

Soluția Xn la care se realizează aceasta depinde și de sn-1 și se numește soluție optimă condiționată la pasul a n-a. Să o notăm prin.

După ce am rezolvat problema de optimizare locală unidimensională folosind ecuația (5), definim două funcții și pentru toate stările posibile sn-1.

Să luăm în considerare o problemă în doi pași: adăugați (n-1) --lea la pasul n-a.

Pentru orice stări sn-2, decizii arbitrare de management Xn-1 și control optim la pasul a n-a, valoarea funcției obiectiv la doi ultimii pași x se calculează cu formula:

Conform principiului optimității lui Bellman pentru orice s n-2 solutia trebuie aleasa astfel incat, impreuna cu controlul optim la ultimul (n-a) pas, sa conduca la optimul functiei obiectiv la ultimele doua etape. Prin urmare, este necesar să se găsească optimul de exprimare (6) pentru toate deciziile de management admisibile Xn-1 :

Se numește maxim condiționat al funcției obiectiv sub control optim la ultimii doi pași. Trebuie remarcat faptul că expresia dintre paranteze în formula (6) depinde numai de sn-2 și Xn-1, deoarece sn-1 poate fi găsit din ecuația stărilor (1) cu:

Controlul corespunzător Xn-1 la pasul (n-1) este notat cu și se numește control optim condiționat la pasul (n-1).

Optimile condiționale ale funcției obiectiv sunt determinate în mod similar pentru controlul optim la (n-k+1) pași, începând de la k-a până la sfârșit, cu condiția ca la începutul k-a pas sistemul să fie în starea sk -1:

Controlul Xk la pasul k, la care se atinge maximul conform (8), este notat și numit control optim condiționat la pasul k.

Ecuațiile (5) și (8) se numesc ecuații Bellman recurente (schemă inversă). Procesul de rezolvare a acestor ecuații se numește optimizare constrânsă.

Ca urmare optimizare condiționată obținem două secvențe:

, …, - maxime condiționale ale funcției obiectiv la ultimul, ultimii doi, …, la n trepte;

, …, - controale optime condiționate la a n-a, (n-1) - a, …, la primele etape.

Folosind aceste secvențe, putem găsi o soluție la problema de programare dinamică dată n și s0:

Ca rezultat, obținem soluția optimă a problemei de programare dinamică: .

Folosind un raționament similar, putem construi o schemă de optimizare condiționată directă:

Soluția optimă a problemei în în acest caz, este situat după următoarea schemă:

Astfel, construirea unui model de programare dinamică și rezolvarea unei probleme pe baza acestuia în vedere generala poate fi reprezentat sub forma următoarelor etape:

Alegeți o metodă de împărțire a procesului de management în pași.

Definiți parametrii de stare s k și variabilele de control X k La fiecare pas se scriu ecuații de stare.

3. Introduceți funcțiile obiectiv ale pasului k-a și funcția obiectiv totală, precum și optima condiționată și controlul optim condiționat la pasul k-a ().

Ecuațiile recurente Bellman sunt scrise în conformitate cu schema inversă sau directă și, după efectuarea optimizării condiționate, se obțin două secvențe: () și ().

Se determină valoarea optimă a funcției obiectiv și soluția optimă.

3. Problema de alocare a resurselor

Există o anumită cantitate de resurse s0 care trebuie distribuită între n entități de afaceri pentru activitățile curente în perioada analizată (lună, trimestru, semestru, an etc.) pentru a obține un profit maxim total. Mărimea investițiilor în resurse xi (;) în activitățile fiecărei entități economice este multiplu al unei anumite valori h. Se știe că fiecare entitate economică, în funcție de volumul fondurilor utilizate xi pentru perioada analizată, aduce un profit în valoare de fi(xi) (nu depinde de investiția de resurse în alte entități economice).

Să ne imaginăm procesul de distribuție a resurselor între entitățile de afaceri ca un proces de management în n pași (numărul pasului coincide cu numărul condiționat al entității de afaceri). Fie sk() un parametru de stare, i.e. suma fondurilor disponibile după pasul k pentru distribuire între restul (n - k) entități de afaceri. Atunci ecuațiile de stare pot fi scrise în urmatoarea forma:

Sa introducem in considerare functia - profitul total conditionat optim primit de la k-a, (k+1) --a, ..., n-a entitate economica, daca resurse in valoare de sk-1 () au fost repartizate optim între ele. Setul de decizii de management posibile privind mărimea resurselor alocate la pasul k-a poate fi prezentat astfel: .

Apoi ecuațiile recurente ale lui R.E. Bellman (diagrama inversă) va arăta astfel:

Exemplu. Există o anumită cantitate de resurse s0=100, care trebuie distribuită între n=4 entități de afaceri pentru activitățile curente în perioada analizată (lună) pentru a obține profitul maxim total. Mărimea investiției de resurse xi (;) în activitățile fiecărei entități economice este un multiplu al valorii h=20 și este specificată de vectorul Q. Se știe că fiecare entitate economică, în funcție de volumul fondurilor utilizate xi pentru perioada analizată, aduce un profit în valoare de fi(xi) () (nu depinde de investiția de resurse în alte entități economice):

Este necesar să se determine câte resurse trebuie alocate fiecărei întreprinderi pentru ca profitul total să fie cel mai mare.

Soluţie.Să creăm ecuațiile recurente ale lui Bellman (schema inversă):

Să determinăm maximele condiționate în conformitate cu (13); rezultatele calculului sunt prezentate în tabelul 1.

Tabelul 1. Calculul optimelor condiționale

s k-1 X k s k k=3k=2k=1 123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61Pe baza rezultatelor optimizării condiționate, vom determina alocarea optimă a resurselor:

Astfel, alocarea optimă a resurselor este:

care va asigura cel mai mare profit în valoare de 87 de unităţi convenţionale. den. unitati

Răspuns: alocarea optimă a resurselor: care oferă cel mai mare profit de 87 de unități convenționale. den. unitati

Concluzie

Programarea dinamică este o zonă de programare matematică care include un set de tehnici și instrumente pentru găsirea soluție optimă, precum și optimizarea fiecărui pas din sistem și dezvoltarea unei strategii de management, adică procesul de management poate fi reprezentat ca un proces în mai multe etape. Programarea dinamică, folosind planificarea pas cu pas, permite nu numai simplificarea soluționării problemei, ci și rezolvarea acelor probleme pentru care metodele nu pot fi aplicate analiză matematică. Simplificarea soluției se realizează prin reducerea semnificativă a numărului de opțiuni studiate, deoarece în loc să rezolve o singură problemă complexă multivariată, metoda de planificare pas cu pas presupune soluții multiple privind sarcini simple. Atunci când planificăm un proces pas cu pas, pornim de la interesele întregului proces în ansamblu, adică. Atunci când luați o decizie într-o anumită etapă, este întotdeauna necesar să aveți în vedere scopul final. Cu toate acestea, programarea dinamică are și dezavantajele sale. Spre deosebire de programarea liniară, în care metoda simplex este universal; nu există o astfel de metodă în programarea dinamică. Fiecare sarcină are propriile sale dificultăți și în fiecare caz este necesar să se găsească cea mai potrivită metodă de rezolvare. Dezavantajul programării dinamice este și complexitatea rezolvării problemelor multidimensionale. O problemă de programare dinamică trebuie să îndeplinească două condiții. Prima condiție este de obicei numită condiția de absență a efectului secundar, iar a doua este condiția de aditivitate a funcției obiective a problemei. În practică, există probleme de planificare în care factorii aleatori joacă un rol semnificativ, influențând atât starea sistemului, cât și câștigul. Există o diferență între problemele de programare dinamică deterministă și stocastică. Într-o problemă deterministă, controlul optim este unic și este specificat în prealabil ca program dur actiuni. Într-o problemă stocastică, controlul optim este aleatoriu și este selectat în timpul procesului în sine, în funcție de situația aleatorie. Într-o schemă deterministă, parcurgând procesul în etape de la sfârșit la început, se află și în fiecare etapă întreaga linie controale optime condiționate, dar dintre toate aceste controale, doar unul a fost implementat în cele din urmă. Acesta nu este cazul într-o schemă stocastică. Fiecare dintre controalele optime condiționate poate fi implementat de fapt dacă cursul anterior al procesului aleatoriu conduce sistemul la starea corespunzătoare. Principiul optimității stă la baza soluționării pas cu pas a problemelor de programare dinamică. Reprezentanți tipici sarcini economice programarea dinamică sunt așa-numitele probleme de producție și stocare, probleme de distribuție a investițiilor, probleme de programare a producției și altele. Problemele de programare dinamică sunt utilizate în planificarea activităților unei întreprinderi, ținând cont de modificările nevoii de produse în timp. În repartizarea optimă a resurselor între întreprinderi în direcție sau timp. Descrierea caracteristicilor programării dinamice și a tipurilor de probleme care pot fi formulate în cadrul acesteia trebuie să fie neapărat foarte generală și oarecum vagă, deoarece există o varietate imensă diverse sarcini, încadrându-se în schema de programare dinamică. Studiază doar un numar mare exemplele oferă o înțelegere clară a structurii programării dinamice.

Bibliografie

Modele și metode economice și matematice. Programare liniară: Tutorial pentru studenții specialităților economice / Alcătuit de: Smirnov Yu.N., Shibanova E.V., Naberezhnye Chelny: Editura KamPI, 2004, 81 p.
Cercetare operațională în economie: manual. manual pentru universități / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Ed. prof. N.Sh. Kremer. - M.: UNITATEA, 2000. - 407 p.
Kuznetsov A.V. si altele.Matematica superioara: Mat. programare: Manual/A.V. Kuznetsov, V.A. Sakovich, N.I. Rece; Sub general ed. A.V. Kuznetsova. - Mn.: Mai sus. şcoală, 1994. - 286 p.: ill.

Îndrumare

Ai nevoie de ajutor pentru a studia un subiect?

Specialiștii noștri vă vor consilia sau vă vor oferi servicii de îndrumare pe teme care vă interesează.
Trimiteți cererea dvs indicând subiectul chiar acum pentru a afla despre posibilitatea de a obține o consultație.

Există o anumită cantitate de resurse s 0 care trebuie distribuită între n entități de afaceri pentru activitățile curente în perioada analizată (lună, trimestru, semestru, an etc.) pentru a obține profitul maxim total. Mărimea investițiilor în resurse x i (;) în activitățile fiecărei entități economice este un multiplu al unei anumite valori h. Se știe că fiecare entitate economică, în funcție de volumul fondurilor utilizate x i pentru perioada analizată, generează un profit în valoare de f i (x i) (nu depinde de investiția de resurse în alte entități economice).

Să ne imaginăm procesul de distribuție a resurselor între entitățile de afaceri ca un proces de management în n pași (numărul pasului coincide cu numărul condiționat al entității de afaceri). Fie s k () un parametru de stare, i.e. suma fondurilor disponibile după pasul k pentru distribuire între restul (n - k) entități de afaceri. Atunci ecuațiile de stare pot fi scrise sub următoarea formă:

Sa introducem in considerare functia - profitul total conditionat optim primit de la k-a, (k+1) --a, ..., n-a entitate economica, daca resurse in valoare de s k-1 () au fost repartizate optim între ele. Setul de decizii de management posibile privind mărimea resurselor alocate la pasul k-a poate fi prezentat astfel: .

Apoi ecuațiile recurente ale lui R.E. Bellman (diagrama inversă) va arăta astfel:

Exemplu. Există o anumită cantitate de resurse s 0 =100, care trebuie distribuită între n=4 entități de afaceri pentru activitățile curente în perioada analizată (lună) pentru a obține profitul maxim total. Mărimea investiției de resurse x i (;) în activitățile fiecărei entități economice este un multiplu al valorii h = 20 și este specificată de vectorul Q. Se știe că fiecare entitate economică, în funcție de volumul fondurilor utilizate x i pentru perioada analizată, aduce un profit în valoare de f i (x i) () (nu depinde de investiția de resurse în alte entități economice):

Este necesar să se determine câte resurse trebuie alocate fiecărei întreprinderi pentru ca profitul total să fie cel mai mare.

Soluţie. Să creăm ecuațiile recurente ale lui Bellman (schema inversă):

Să determinăm maximele condiționate în conformitate cu (13); rezultatele calculului sunt prezentate în tabelul 1.

Tabelul 1. Calculul optimelor condiționale







22+20=42


22+33=55	17+42=59



22+46=68	17+55=72	14+59=73







67+20=87

Pe baza rezultatelor optimizării condiționate, vom determina alocarea optimă a resurselor:

Astfel, alocarea optimă a resurselor este:

care va asigura cel mai mare profit în valoare de 87 de unităţi convenţionale. den. unitati

Răspuns: alocarea optimă a resurselor: care oferă cel mai mare profit de 87 de unități convenționale. den. unitati

Concluzie

Programarea dinamică este o zonă de programare matematică care include un set de tehnici și instrumente pentru găsirea soluției optime, precum și optimizarea fiecărui pas din sistem și dezvoltarea unei strategii de control, adică procesul de control poate fi reprezentat ca un proces în mai multe etape. Programarea dinamică, folosind planificarea pas cu pas, permite nu numai simplificarea soluționării problemei, ci și rezolvarea acelor probleme care nu pot fi aplicate folosind metode de analiză matematică. Simplificarea soluției se realizează prin reducerea semnificativă a numărului de opțiuni studiate, deoarece în loc să rezolve o singură problemă complexă multivariată, metoda de planificare pas cu pas presupune rezolvarea de mai multe ori a unor probleme relativ simple. Atunci când planificăm un proces pas cu pas, pornim de la interesele întregului proces în ansamblu, adică. Atunci când luați o decizie într-o anumită etapă, este întotdeauna necesar să aveți în vedere scopul final. Cu toate acestea, programarea dinamică are și dezavantajele sale. Spre deosebire de programarea liniară, în care metoda simplex este universală, nu există o astfel de metodă în programarea dinamică. Fiecare sarcină are propriile sale dificultăți și în fiecare caz este necesar să se găsească cea mai potrivită metodă de rezolvare. Dezavantajul programării dinamice este și complexitatea rezolvării problemelor multidimensionale. O problemă de programare dinamică trebuie să îndeplinească două condiții. Prima condiție este de obicei numită condiția de absență a efectului secundar, iar a doua este condiția de aditivitate a funcției obiective a problemei. În practică, există probleme de planificare în care factorii aleatori joacă un rol semnificativ, influențând atât starea sistemului, cât și câștigul. Există o diferență între problemele de programare dinamică deterministă și stocastică. Într-o problemă deterministă, controlul optim este unic și este specificat în prealabil ca un program rigid de acțiuni. Într-o problemă stocastică, controlul optim este aleatoriu și este selectat în timpul procesului în sine, în funcție de situația aleatorie. Într-o schemă deterministă, parcurgând procesul în etape de la capăt la început, există și o serie întreagă de controale optime condiționate în fiecare etapă, dar dintre toate aceste controale, doar unul a fost efectuat în cele din urmă. Acesta nu este cazul într-o schemă stocastică. Fiecare dintre controalele optime condiționate poate fi implementat de fapt dacă cursul anterior al procesului aleatoriu conduce sistemul la starea corespunzătoare. Principiul optimității stă la baza soluționării pas cu pas a problemelor de programare dinamică. Reprezentanții tipici ai problemelor economice ale programării dinamice sunt așa-numitele probleme de producție și stocare, probleme de distribuție a investițiilor de capital, probleme de programare a producției și altele. Problemele de programare dinamică sunt utilizate în planificarea activităților unei întreprinderi, ținând cont de modificările nevoii de produse în timp. În repartizarea optimă a resurselor între întreprinderi în direcție sau timp. Descrierea caracteristicilor programării dinamice și a tipurilor de probleme care pot fi formulate în cadrul acesteia trebuie neapărat să fie foarte generală și oarecum vagă, deoarece există o varietate imensă de probleme diferite care se încadrează în schema de programare dinamică. Doar studierea unui număr mare de exemple oferă o înțelegere clară a structurii programării dinamice.

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 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 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 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: . Controale optime Toți pașii sunt evidențiați 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.

- 1,03 MB

Să 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 țintă 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 (х i -1 ,u i) – on i-a etapă, ..., prin z N (x N -1 , u N) -on Etapa a N-a. 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.

Sa incepem cu 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 Bellman funcționale. 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. Modificările ulterioare ale stării ei depind doar de această stare 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 pleacă sistemul starea anterioară x t -1 la 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.
Se pot impune 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 de 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 complet valoare specifică. Odată cu schimbarea 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 stări 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 nu se cunoaște starea inițială sau finală, dar se cunoaște regiunea X 0 sau X T căreia îi aparțin aceste puncte.

Poza 1

Apoi controalele admisibile transferă puncte 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 DISTRIBUȚIE A 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. Stație de pompare și filtrare de Est;

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)

Diagrama 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 distanță (vector resursă)

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 distVector;

//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 resVector; //vector de rezultate

void BuildOutMatrix(int **,std::vector );//funcție de generare a matricei obiective (optimizare condiționată)

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);

if (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:
Considera aspecte teoretice rezolvarea problemelor de programare dinamică; caracterul recurent al sarcinilor 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
Problemă de alocare a resurselor………………………………12
Expunerea generală a problemei………………………….13
Diagrama bloc a programului
Structura algoritmului programului
Rezultatul programului
Concluzie
Bibliografie

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. Distribuția optimă a resurselor î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întreprinderile care utilizează metoda programării liniare. 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 unei probleme de optimizare Procese 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. Constructie model matematic distribuirea resurselor companiei. Analiza de sensibilitate a soluției optime. Î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.