- 1,03 MB

Lad os give en matematisk formulering af optimalitetsprincippet. For nemheds skyld vil vi antage, at systemets initiale x 0 og sidste x T tilstande er givet. Lad os betegne med z 1 (x 0 , u 1) værdien af ​​målfunktionen i det første trin med systemets begyndelsestilstand x 0 og med kontrol u 1 , med z 2 (x 1 , u 2) den tilsvarende værdien af ​​målfunktionen først på anden fase, ..., igennem
z i (х i -1 ,u i) – tændt i-te etape, ..., gennem zN (xN-1, uN)-på N. etape. Det er indlysende

Vi skal finde den optimale kontrol u*= (; ;...;), sådan at den leverer et ekstremum objektiv funktion(1) underlagt restriktioner.

For at løse dette problem fordyber vi det i en familie af lignende. Lad os introducere noget notation. Lad være henholdsvis områderne

definitioner for lignende problemer i sidste fase, de sidste to osv.;
- domæne oprindelige problem. Lad os betegne med henholdsvis F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), den betinget optimale værdier for målfunktionen på det sidste trin, to de sidste osv., ved de k sidste osv. på alle N trin.

Lad os starte med sidste etape. Lad x N-1 være de mulige tilstande af systemet i begyndelsen af ​​det N. trin. Vi finder:

F1 (xN-1) = zN (xN-1, uN). (2)

For de sidste to etaper får vi

F2 (xN-2) = (ZN-1 (xN-2, uN-1) + F1 (x N-1)). (3)

Ligeledes:

F3 (x N-3) = (ZN-2 (x N-3, uN-2) + F2 (x N-2)). (4)

………………………………………………….

Fk (xN-k) = (zN-k+1 (xN-k, uN-k+1) + Fk-1 (xN-k+1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0, u 1) + F N-1 (x 1)). (6)

Udtryk (6) er en matematisk fremstilling af optimalitetsprincippet. Udtryk (5) – generel form registrering af den betinget optimale værdi af målfunktionen for de k resterende stadier. Udtryk (2) – (6) kaldes funktionelle Bellman-ligninger. Deres tilbagevendende (tilbagevendende) karakter er tydeligt synlig, dvs. for at finde den optimale kontrol ved N trin, skal du kende den betinget optimale kontrol ved de tidligere N – 1 stadier osv. Derfor kaldes funktionelle ligninger ofte for recurrent (tilbagevendende) Bellmans forhold.

1. Funktioner af opgaver dynamisk programmering

Baseret på ovenstående kan vi fremhæve følgende funktioner i dynamiske programmeringsproblemer.

• Vi betragter et system, hvis tilstand ved hvert trin er bestemt af vektoren x t. Yderligere ændringer i hendes tilstand afhænger kun af denne tilstand x t og afhænger ikke af, hvordan systemet kom til denne tilstand. Sådanne processer kaldes processer uden eftervirkning.
• Ved hvert trin vælges én løsning u t, under hvilken påvirkning systemet går fra tidligere tilstand x t -1 til ny x t . Denne nye tilstand er en funktion af tilstanden ved begyndelsen af ​​intervallet xt -1 og beslutningen u t vedtaget ved begyndelsen af ​​intervallet, dvs. xt = xt (xt -1,u t).
• Handlingen på hvert trin er forbundet med en bestemt gevinst (indtægt, overskud) eller tab (omkostninger), som afhænger af staten ved begyndelsen af ​​trin (stadiet) og den trufne beslutning.
• Restriktioner kan pålægges staten og kontrolvektorerne, hvis kombination udgør regionen med gennemførlige løsninger.
• Det er nødvendigt at finde en sådan tilladelig kontrol u t for hvert trin t for at opnå den ekstreme værdi af målfunktionen for alle T trin.

Enhver gyldig sekvens af handlinger for hvert trin, der overfører systemet fra den oprindelige tilstand til den endelige tilstand, kaldes en kontrolstrategi. En kontrolstrategi, der resulterer i en ekstrem værdi af den objektive funktion, kaldes optimal.

Den geometriske fortolkning af det dynamiske programmeringsproblem er som følger. Lad n være dimensionen af ​​tilstandsrummet. På hvert tidspunkt har systemets koordinater en meget specifik værdi. Med en ændring i tiden t kan tilstandsvektorens koordinatværdier ændre sig. Lad os kalde et systems overgang fra en tilstand til en anden for dets bevægelsesforløb i staternes rum. En sådan overgang gennemføres ved at påvirke de statslige koordinater. Det rum, hvor systemets tilstande fungerer som koordinater, kaldes faserum. Det dynamiske programmeringsproblem kan tolkes særligt klart, hvis tilstandsrummet er todimensionelt. Området med mulige tilstande i dette tilfælde vil blive afbildet af en vis figur, de indledende og endelige tilstande af systemet - med punkter x 0 (fig. 1). Kontrol er den indflydelse, der overfører systemet fra den oprindelige tilstand til den endelige tilstand. For mange økonomiske problemer er den indledende eller endelige tilstand ikke kendt, men regionen X 0 eller X T, som disse punkter tilhører, er kendt.

Billede 1

De tilladte kontroller overfører derefter punkter fra området X 0 til X T . Det dynamiske programmeringsproblem kan geometrisk formuleres som følger: find en fasebane, der starter i området X 0 og slutter i området X T, for hvilket målfunktionen når en ekstrem værdi. Hvis start- og sluttilstanden for et dynamisk programmeringsproblem er kendt, taler vi om et problem med faste ender. Hvis de indledende og endelige regioner er kendt, så taler vi om et problem med frie ender.

1. RESSOURCE DISTRIBUTION PROBLEM

2.1 Generel beskrivelse af problemet

Lad os overveje anvendelsen af ​​den dynamiske programmeringsmetode ved at bruge eksemplet på fordelingen af ​​midler mellem seks genopbygningsobjekter fra et byvandsforsyningsselskab:

1. Central pumpe- og filtreringsstation;

2. Østlig pumpe- og filtreringsstation;

3. Vandpumpestation;

4. Central beluftningsstation;

5. Østlig beluftningsstation;

6. Landbeluftningsstation.

Det samlede beløb af midler til udvikling er ikke mere end 195 tusind Hryvnia. På baggrund af tekniske og økonomiske beregninger blev det fastslået, at anlæggene som følge af ombygning, afhængig af mængden af ​​brugte midler, vil have den produktivitet, der er vist i tabel 1.1. Det er nødvendigt at bestemme den optimale fordeling af midler mellem genopbygningsobjekter, hvilket vil sikre den maksimale stigning i produktiviteten af ​​disse objekter. Dette problem bruger således et optimeringskriterium - den samlede produktivitet af virksomheder af genopbygningsobjekter.

Tabel 1.1 Inputdata for rekonstruktionsobjekters produktivitet

Objektets serienummer

Mængde af ressourcer afsat til udvikling af faciliteter (tusind UAH)

Produktivitet af objekter som et resultat af udvikling (tusind m3)

1. Blokdiagram af programmet

Figur 1. Hovedprogram

QtObj – antal objekter

QtRes – antal ressourcer

effMatrix - objektydelsesmatrix,

distVector – vektor af allokerede ressourcer

Trin 1: Betinget optimering

Trin 2. Ubetinget optimering

I = QtObj-1.0 danner vektorresultatet

Figur 2. Dataindtastning

distVector – afstandsvektor, effMatrix = ydeevnematrix

hvis alle matrixelementer er indtastet

hvis ydeevnevektoren ikke er det

negativ

Figur 3. Betinget optimering,

vi danner en outputmatrix (maksimum af målfunktionen)

outMatrix – maksimal målmatrix

QtObj – antal objekter

QtRes – antal ressourcer

Matrix – præstationsmatrix

distVect – afstandsvektor (ressourcevektor)

nej ja Hvis den første virksomhed

At finde det maksimale

ja maxItem = temp; outMatrix[i][j] = maxItem

1. Program algoritme struktur

1. Datainput – klasse DataDlg.

Variable klassemedlemmer.

//vektor til lagring af mængden af ​​ressourcer

std::vektor distVektor;

//objekt ydeevne matrix

int** effMatrix;

//funktion til at konvertere en streng til et tal

int StringToInt(CString);

//funktion til at kontrollere rigtigheden af ​​de indtastede data

BOOL FillMatrix();

//ressourcerensningsfunktion efter lukning af vinduet

virtual BOOL DestroyWindow();

//dialog initialiseringsfunktion

virtuel BOOL OnInitDialog();

1. Beregning af resultater - programmets hovedklasseWorkDlg

Variable klassemedlemmer

intVærdi; //ydelsesværdi

int MaxIndex;// maksimalt indeks i ressourcevektoren

int Facility;//enterprise

int Recource;//dedikeret ressource

Vare ** outMatrix; //maksimal målmatrix

std::vektor resVektor; //vektor af resultater

void BuildOutMatrix(int ​​​​**, std::vektor );// funktion til generering af målmatrix (betinget optimering)

afx_msg void OnBnClickedButton1(); // handler for at klikke på knappen "Beregn", som starter beregningsprocessen.

virtuel BOOL DestroyWindow();//rydder programressourcer

1. Udskrivende resultatklasserapport

Formålet med denne klasse er at udlæse resultatvektoren i tabelform.

2.4 Resultater af programmet

Indledende dataindtastning

1. Indtastning af data om produktiviteten af ​​rekonstruktionsobjekter

1. Hvis ikke alle felter er udfyldt

1. Hvis der indtastes et forkert tegn

Korrekt dataindtastning

Vis resultat

1. Data input

Resultatet af programmet

Indledende dataindtastning

Indtastning af objektproduktivitet

Ansøgning.

Programoversigt

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// er alle felter udfyldt?

BOOL DataDlg::FillMatrix()

bool flag = sand;

for (int i = 0; i< Cells.GetSize(); i ++){

for (int j = 0 ; j< Cells.GetAt(i)->Edits.GetSize(); j++)(

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

if (temp->m_hWnd != NULL)(

temp->GetWindowText(str);

if (str.IsEmpty())(

MessageBox(L"Du skal udfylde alle felter", L"Fejl", MB_ICONERROR | MB_OK);

Beskrivelse af arbejdet

Formålet med dette arbejde er at implementere på en computer en løsning på problemet med optimal tildeling af midler til udvidelse af produktionen.
Kursusmål:
Overveje teoretiske aspekter løsning af dynamiske programmeringsproblemer; opgavers tilbagevendende karakter af denne type; Bellmans principper om optimalitet.
Algoritme udvikling. Blokdiagrammer. Algoritme struktur.
Computerimplementering af den udviklede algoritme i det valgte programmeringssprog.

Indhold

INDLEDNING………………………………………………………………2
Dynamisk programmering
Grundlæggende begreber…………………4
Principper for dynamisk programmering. Bellmans funktionelle ligninger………………………….5
Funktioner ved dynamiske programmeringsproblemer……………….10
Ressourceallokeringsproblem………………………12
Generel redegørelse for problemet………………………….13
Blokdiagram af programmet
Program algoritme struktur
Resultatet af programmet
Konklusion
Bibliografi

Send dit gode arbejde i videnbasen er enkel. Brug formularen nedenfor

Godt arbejde til webstedet">

Studerende, kandidatstuderende, unge forskere, der bruger videnbasen i deres studier og arbejde, vil være dig meget taknemmelig.

opslået på http://www.allbest.ru/

Ressourceallokeringsproblem ved hjælp af dynamisk programmeringsmetode

For at udvide produktionskapaciteten for tre virksomheder A, B og C tildeles et vist antal enheder ekstra elektricitet i mængden af ​​x 0 = 8 enheder. Elektricitet kan frigives i form af 1, 2, 3, 4, 5, 6, 7 og 8 enheder. Ved at investere x i enheder elektricitet i udviklingen af ​​den i-te virksomhed kan du få indtægter fra i-enheder på virksomheden. Eksisterer forskellige varianter x i (k) tildeling af yderligere elektricitet. De bringer indkomst til i (k), k=1,n. Mulige muligheder virksomhedsudvikling er angivet i tabel 1. Den samlede indkomst for alle virksomheder bør være maksimal, dvs. y=? y i (k)>max

Bord 1. Virksomhedsudviklingsmuligheder

Mulighed k	Virksomhed A	Virksomhed B	Virksomhed C

Matematisk iscenesættelse opgaver:

y=? på jeg (k)> max

?X jeg (k)?x 0

Løsning:

Lad os begynde at overveje proceduren for løsning af det aktuelle problem fra det sidste (3 trin) trin (tabel 2), hvor investeringer allokeres til virksomhed C. Betinget optimal kontrol på tredje trin søges som en løsning på ligningen

g C (S 2) = maks. k f c, x C (k)? S 2, k=1,2,3,4

Bord 2. Betinget optimale løsninger (trin 3)

Stat		Styring

Der er fire muligheder for at investere midler - fire trins kontroller x C (1) = 0 enheder, x C (2) = 1 enhed, x C (3) = 2 enheder, x C (4) = 3 enheder. og ni teoretisk mulige tilstande af systemet S 2 forud for allokeringen af ​​midler til virksomhed C - mængderne af investeringer, der ikke er fordelt til 3. trin: 0,1,2,3,4,5,6,7,8.

Lad os antage, at systemet var i tilstanden S 2 = 2. Så, for trinstyring x C (2) = 1, vil indkomsten af ​​C (2) være lig med 3 enheder. (Tabel 3), og trinstyring x C (3) = 2 vil være optimal for denne tilstand, hvilket giver en betinget maksimal forstærkning g c (S 2) = 5. Hvis systemet var i tilstanden S 2 =3, er alle trinstyringer tilladt: x C (1) = 0 enheder, x C (2) = 1 enhed, x C (3) = 2 enheder, x C (4) = 3 enheder. , og den optimale kontrol vil være x C (4) = 3, hvilket giver en betinget maksimal forstærkning g c (S 2) = 6.

Tabel 3 dynamisking

Alle mulige tilstande forud for 3. trin udfyldes på samme måde. De optimale værdier af indikatorerne er fremhævet med fed skrift i tabellerne.

Dernæst betragtes anden fase på samme måde (tabel 4), som består i at allokere investeringer til virksomhed A. På anden fase er den samlede gevinst summen af ​​de modtagne gevinster i tredje og anden fase, og gives ved forholdet:

g A (S 1)=max k f A + g c], x A (k)? S 1, k=1,2,3,4

For tilstanden S 1 =3 med trinstyring x A (2) = 1 opnår vi således:

g A (S 1) = max k f A + g c ]

Max k 4+g c =4+5=9, hvor vi finder fra tabel 1, og g c fra tabel 3. Alle tilstande er udfyldt ens.

Bord 4. Betinget optimale løsninger (trin 2)

Stat	f A +g c	Styring

Her opstår situationer, hvor den optimale løsning ikke vil være den eneste. I tilstanden S 1 = 3 vil trinstyringerne x A (2) = 1 og x A (3) = 2 således være betinget optimale, hvilket giver det samme forstærkning g A (S 1) = 9

Bord 5. Ubetinget optimale løsninger (trin 1)

I den første fase (tabel 5) - allokeringen af ​​investeringer til virksomhed B - er der kun én tidligere tilstand af systemet, svarende til starttilstanden S 0 =8. Den ubetinget optimale gevinst bestemmes af udtrykket:

y * = g B (S 0) = max k (f A + g A) x in (k)? S 0 = x 0, k=1,2,3,4,5

Ubetinget optimale kontroller, der sikrer maksimal indkomst, kan være anderledes.

Ordning for at finde alle optimale muligheder fordeling af investeringer mellem virksomheder (tabel 6) er vist i figur 1.

Bord 6. Optimal fordeling af investeringer.

Figur 1. Ordning for optimal fordeling af investeringer mellem virksomheder

Konklusion: Efter at have overvejet problemet med ressourceallokering ved hjælp af den dynamiske programmeringsmetode, er der identificeret to muligheder for optimal ressourceallokering.

Udgivet på Allbest.ru

...

Lignende dokumenter

generelle karakteristika og økonomiske præstationsindikatorer for de tre undersøgte virksomheder. Løsning af problemet med produktionsplanlægning, samt investeringsfordeling ved hjælp af lineær og dynamisk programmering. Komparativ analyse af resultater.

kursusarbejde, tilføjet 25/04/2015


Flertrinsprocesser i dynamiske opgaver. Princippet om optimalitet og gentagelsesforhold. Dynamisk programmeringsmetode. Problemer med optimal tildeling af midler til produktionsudvidelse og produktionsprogramplanlægning.

kursusarbejde, tilføjet 30-12-2010


Dynamisk programmeringsmetode og dens hovedstadier. Optimal strategi for udskiftning af udstyr. Minimering af omkostninger til opførelse og drift af virksomheder. Optimal fordeling af ressourcer i STROYKROVLYA LLC og investeringer i PKT Khimvolokno.

kursusarbejde, tilføjet 01/08/2015


Matematisk model for produktionsplanlægning. Udarbejdelse af en optimal plan for en virksomheds produktionsaktiviteter ved hjælp af metoden lineær programmering. Finde den bedste måde fordeling af pengeressourcer i planlægningsperioden.

afhandling, tilføjet 08/07/2013


Beregning af transportomkostninger ved hjælp af metoden minimumsomkostninger. At finde betinget optimal lighed i processen med dynamisk programmering. Lineær algebraisk ligning Kolmogorov for gennemsnitlig tid problemfri drift redundant system.

kursusarbejde, tilføjet 14/01/2011


Grafisk metode løsning af problemet med optimering af produktionsprocesser. Anvendelse af en simpleksalgoritme til at løse et økonomisk optimeret produktionsstyringsproblem. Dynamisk programmeringsmetode til valg af den optimale stiprofil.

test, tilføjet 15/10/2010


Optimal plan fordeling af midler mellem virksomheder. Udvikling af en plan for hver virksomhed, hvor investeringsafkastet vil være højeste værdi. Brug af lineære og dynamiske programmeringsmetoder.

kursusarbejde, tilføjet 16-12-2013


Karakteristiske træk ved lineære programmeringsproblemer. Generel formulering af produktionsplanlægningsproblemet. Konstruktion af en matematisk model for fordelingen af ​​virksomhedens ressourcer. Følsomhedsanalyse af den optimale løsning. Udarbejdelse af en bæredygtighedsrapport.

præsentation, tilføjet 12/02/2014


At finde den optimale værdipapirportefølje. Gennemgang af metoder til løsning af problemet. Konstruktion af en matematisk model. Kegleprogrammeringsproblem. Afhængighed af startkapitalfordelingsvektoren af ​​en af ​​startparametrene.

afhandling, tilføjet 02/11/2017


Dynamisk programmeringsmodel. Optimitetsprincippet og Bellman-ligningen. Beskrivelse af processen med at modellere og konstruere et beregningsdynamisk programmeringsskema. Problemet med at minimere omkostningerne ved opførelse og drift af virksomheder.

Lektionsplan

Akademisk disciplin MATEMATISKE METODER OG MODELLER I ØKONOMI

Lektionens emne Løsning af forskellige praktiske problemer DP ved hjælp af matematiske metoder.

Lektionens mål

Udvikle færdigheder i at løse dynamiske programmeringsproblemer.

Udvikling af kvaliteten af ​​sind, opmærksomhed og akademiske arbejdsevner hos eleverne.

At give eleverne disciplin og beslutsomhed.

Lektionsudstyr Forelæsningsnotater, V.P. Agaltsov "Matematiske metoder i programmering."

Under undervisningen:

Organiseringstid:

kontrollere fravær, udfylde loggen.

Opdatering af referenceviden: svar på sikkerhedsspørgsmål

Hvilke opgaver kaldes multi-step?

Hvilket matematisk apparat bruges til at løse flertrinsproblemer?

Hvad er optimal kontrol u*?

Hvad er metodens algoritme successive tilnærmelser i to cirkler?

Giv eksempler på optimale ressourceallokeringsproblemer.

At lære nyt materiale:

Klassiske dynamiske programmeringsproblemer

• Længste fælles undersekvensproblem: Givet to sekvenser skal du finde den længste fælles undersekvens.

• Problem med at finde den længst stigende undersekvens: givet en sekvens, skal du finde den længst stigende undersekvens.

• Redaktionelt afstandsproblem (Levenshtein-afstand): givet to strenge skal du finde det mindste antal sletninger, udskiftninger og tilføjelser af tegn, der omdanner en streng til en anden.

• Problemet med at beregne Fibonacci-tal

• Problemet med rækkefølgen af ​​matrix multiplikation: givet matricer, ..., er det nødvendigt at minimere antallet af skalaroperationer for deres multiplikation.

• Problem med banevalg

• Problem med sekventiel beslutningstagning

• Problem med arbejdsudnyttelse

• Problem med lagerstyring

• Rygsækproblemet: fra et ubegrænset sæt af objekter med egenskaberne "cost" og "weight" er det nødvendigt at vælge et bestemt antal objekter på en sådan måde, at man opnår den maksimale samlede pris med en begrænset totalvægt.

• Floyd-Warshall-algoritme: find de korteste afstande mellem alle hjørner af en vægtet rettet graf.

• Bellman-Ford algoritme: find den korteste vej i en vægtet graf mellem to givne hjørner.

• Maksimalt uafhængigt sæt af hjørner i et træ: givet et træ, find det maksimale sæt hjørner, således at ikke to af dem er forbundet med en kant.

Eksempel: Optimal ressourceallokering

Kapital 40 millioner rubler. investor skal investere i fire investeringsprojekter for at opnå maksimal indtjening. Rentabiliteten af ​​projekter er angivet i tabellen (investeringer er multipla på 8 millioner rubler)

u

Udbytte af implementering

f4(u)

f3(u)

f2(u)

f1(u)

55

39

120

115

10 0

120

135

134

14 0

145

158

147

Løsning:

Dette er et dynamisk programmeringsproblem. Løsningen består af to faser. I det første trin (fra slutningen til begyndelsen) leder vi efter en betinget optimal løsning, i den anden (fra slutningen til slutningen) leder vi efter den optimale løsning på problemet.

Scene 1.

Vi fordeler kapital mellem fire projekter og beregner det modtagne overskud L (jeg ), jeg = 8,16,24,32,40.

1 trin: Kontanter investerer i det fjerde projekt.

L(8)= 55

L(16)=58

L(24)=90

L(32)=100

L(40)=140

Trin 2: Der investeres midler i det fjerde og tredje projekt.

u

Udbytte af implementering

1 trin

f3(u)

55

39

10 0

120

14 0

145

Trin 3: Der investeres midler i det fjerde, tredje (trin 2) og andet projekt.

u

Udbytte af implementering

Trin 2

f 2(u)

94

108

120

135

135

175

158

175

134

214

147

Fase 2:

På det fjerde trin vælger vi maksimum af de opnåede overskudsværdier L (40) = 214.

Og vender tilbage til omvendt rækkefølge Fra tabel til tabel (fra 4 trin til 1) vælger vi sådanne indkomstværdier, hvor værdien 214 opnås.

Maksimal indkomst 214 millioner rubler. fra de investerede midler kan modtages med følgende fordeling af midler:

1 projekt – 0 millioner rubler.

2 projekt – 24 millioner rubler.

3. projekt – 8 millioner rubler.

4 projekt – 8 millioner rubler.

Konsoliderer nyt materiale:

5. Opsummering af lektionen: konklusioner, vurderinger, lektier:

(2) paragraf 5.1

Ср12: dannelse og assimilering af indholdet af teoretisk materiale

Lærerens underskrift

Ledig en vis mængde ressourcer s 0, som skal fordeles på n forretningsenheder for løbende aktiviteter i den pågældende periode (måned, kvartal, halvår, år osv.) for at opnå den samlede maksimal profit. Størrelsen af ​​ressourceinvesteringer x i (;) i hver økonomisk enheds aktiviteter er et multiplum af en vis værdi h. Det er kendt, at hver økonomisk enhed, afhængigt af mængden af ​​anvendte midler x i i den undersøgte periode, genererer et overskud på størrelsen fi (xi) (afhænger ikke af investering af ressourcer i andre økonomiske enheder).

Lad os forestille os processen med ressourcefordeling mellem økonomiske enheder som en n-trins ledelsesproces (trintallet falder sammen med betinget nummerøkonomisk enhed). Lad s k () være en tilstandsparameter, dvs. mængden af ​​tilgængelige midler efter det k. trin til fordeling blandt de resterende (n - k) forretningsenheder. Så kan tilstandsligningerne skrives på følgende form:

Lad os tage funktionen i betragtning - det betinget optimale samlede overskud modtaget fra de k-th, (k+1) - th, ..., n-th økonomiske enheder, hvis ressourcer i mængden af ​​s k-1 () var optimalt fordelt mellem dem. Mange mulige ledelsesbeslutninger i forhold til størrelsen af ​​distribuerede ressourcer på det k-te trin kan repræsenteres som følger: .

Så de tilbagevendende ligninger af R.E. Bellman (omvendt diagram) vil se sådan ud:

Eksempel. Der er en vis mængde ressourcer s 0 =100, som skal fordeles på n=4 forretningsenheder til løbende aktiviteter i den pågældende periode (måned) for at opnå det samlede maksimale overskud. Størrelsen af ​​investeringen af ​​ressourcer x i (;) i aktiviteterne i hver økonomisk enhed er et multiplum af værdien h = 20 og er specificeret af vektoren Q. Det er kendt, at hver økonomisk enhed, afhængigt af mængden af ​​anvendte midler x i for den undersøgte periode giver et overskud på fi (x i) () (afhængigt ikke af ressourceinvesteringer i andre økonomiske enheder):

Det er nødvendigt at bestemme, hvor mange ressourcer der skal tildeles hver virksomhed, for at det samlede overskud er størst.

Løsning. Lad os skabe Bellmans tilbagevendende ligninger (omvendt skema):

Lad os bestemme de betingede maksimum i overensstemmelse med (13); beregningsresultaterne er vist i tabel 1.

Tabel 1. Beregning af betingede optima

		22+20=42
		22+33=55		17+42=59
		22+46=68		17+55=72		14+59=73
		67+20=87

Ifølge resultaterne betinget optimering Lad os bestemme den optimale allokering af ressourcer:

Den optimale ressourceallokering er således:

hvilket vil give det største overskud i mængden af ​​87 konventionelle enheder. hule. enheder

Svar: optimal ressourceallokering: som giver det største overskud af 87 konventionelle enheder. hule. enheder

Konklusion

Dynamisk programmering er et felt matematisk programmering, herunder et sæt af teknikker og midler til at finde den optimale løsning, samt optimering af hvert trin i systemet og udvikling af en ledelsesstrategi, det vil sige, at ledelsesprocessen kan repræsenteres som en flertrinsproces. Dynamisk programmering, ved hjælp af trin-for-trin planlægning, gør det ikke kun muligt at forenkle løsningen af ​​problemet, men også at løse de problemer, som metoder ikke kan anvendes til matematisk analyse. Forenkling af løsningen opnås ved at reducere antallet af undersøgte muligheder markant, da trin-for-trin planlægningsmetoden i stedet for at løse et komplekst multivariat problem én gang involverer flere løsninger vedr. simple opgaver. Når vi planlægger et trin-for-trin proces, tager vi udgangspunkt i hele processens interesser som helhed, dvs. Når du træffer en beslutning på et bestemt tidspunkt, er det altid nødvendigt at huske det endelige mål. Dynamisk programmering har dog også sine ulemper. I modsætning til lineær programmering, hvor simpleks metode er universel; der er ingen sådan metode i dynamisk programmering. Hver opgave har sine egne vanskeligheder, og i hvert tilfælde er det nødvendigt at finde den bedst egnede løsningsmetode. Ulempen ved dynamisk programmering er også kompleksiteten ved at løse multidimensionelle problemer. Et dynamisk programmeringsproblem skal opfylde to betingelser. Den første betingelse kaldes normalt betingelsen om fravær af eftervirkning, og den anden er betingelsen om additivitet af problemets objektive funktion. I praksis er der planlægningsproblemer, hvor tilfældige faktorer spiller en væsentlig rolle, som både påvirker systemets tilstand og gevinsten. Der er forskel på deterministiske og stokastiske dynamiske programmeringsproblemer. I et deterministisk problem er den optimale kontrol unik og er på forhånd specificeret som hårdt program handlinger. I et stokastisk problem er den optimale kontrol tilfældig og vælges under selve processen, afhængig af den tilfældige situation. I et deterministisk skema, der går gennem processen i trin fra ende til begyndelse, er det også på hvert trin hele linjen betingede optimale kontroller, men af ​​alle disse kontroller blev kun én i sidste ende implementeret. Dette er ikke tilfældet i en stokastisk ordning. Hver af de betingede optimale kontroller kan faktisk implementeres, hvis det forrige træk tilfældig proces vil bringe systemet i den rette tilstand. Princippet om optimalitet er grundlaget for den trinvise løsning af dynamiske programmeringsproblemer. Typiske repræsentanter for økonomiske problemer med dynamisk programmering er de såkaldte problemer med produktion og opbevaring, problemer med distribution af kapitalinvesteringer, problemer med kalender produktions planlægning og andre. Dynamiske programmeringsproblemer bruges til at planlægge en virksomheds aktiviteter under hensyntagen til ændringer i behovet for produkter over tid. I den optimale fordeling af ressourcer mellem virksomheder i retning eller tid. Beskrivelsen af ​​karakteristika ved dynamisk programmering og de typer problemer, der kan formuleres inden for dens rammer, må nødvendigvis være meget generel og noget vag, da der er en enorm variation forskellige opgaver, der passer ind i det dynamiske programmeringsskema. Kun undersøgelse stort antal Eksemplerne giver en klar forståelse af strukturen i dynamisk programmering.

1. Grundlæggende begreber

1.1. Dynamisk programmeringsmodel

1.2. Princippet om optimalitet. Bellmans ligning

2. Optimal ressourceallokering

2.1 Problemstilling

2.2 Todimensionel ressourceallokeringsmodel

2.3 Diskret dynamisk model optimal ressourceallokering

2.4 Tager hensyn til eftervirkninger i problemer med optimal ressourceallokering

Konklusion

Liste over anvendte kilder

Bilag 1. Programliste til løsning af problemet med optimal ressourceallokering med givne parametre. Program resultater

Introduktion

Gennem historien har folk tyet til komplekse ritualer, når de står over for beslutninger. De holdt højtidelige ceremonier, ofrede dyr, fortalte lykke ved stjernerne og så fuglenes flugt. De stolede på folkelig overtro og forsøgte at følge primitive regler, der gjorde den vanskelige opgave at træffe beslutninger lettere for dem. I øjeblikket bruges et nyt og tilsyneladende mere videnskabeligt "ritual" til at træffe beslutninger baseret på brugen af ​​en elektronisk computer. Uden moderne tekniske midler Det menneskelige sind kan formentlig ikke tage højde for de mange og forskellige faktorer, man støder på i at drive en virksomhed, designe en raket eller regulere trafikken. Der findes mange i øjeblikket matematiske metoder optimeringer er allerede ret udviklede, hvilket gør det muligt effektivt at bruge mulighederne for digital og hybrid computere. En af disse metoder er matematisk programmering, som omfatter begge dele særlig situation dynamisk programmering.

De fleste praktiske problemer har flere (og nogle måske endda uendeligt antal) løsninger. Målet med optimering er at finde den bedste løsning blandt mange potentielt mulige i overensstemmelse med et eller andet kriterium om effektivitet eller kvalitet. Et problem, der kun tillader én løsning, kræver ikke optimering. Optimering kan opnås ved hjælp af mange strategier, lige fra meget komplekse analytiske og numeriske matematiske procedurer til intelligent brug af simpel aritmetik.

Dynamisk programmering er en optimeringsmetode tilpasset operationer, hvor beslutningsprocessen kan nedbrydes i separate stadier (trin). Sådanne operationer kaldes flere trin.

Som en gren af ​​matematisk programmering begyndte dynamisk programmering (DP) at udvikle sig i 50'erne af det 20. århundrede. takket være R. Bellmans og hans medarbejderes arbejde. For første gang blev problemer med optimal lagerstyring løst ved hjælp af denne metode, derefter udvidedes klassen af ​​problemer betydeligt. Hvordan praktisk metode optimering blev den dynamiske programmeringsmetode kun mulig ved brug af moderne computerteknologi.

Den dynamiske programmeringsmetode er baseret på princippet om optimalitet formuleret af Bellman. Dette princip og ideen om at inkludere et specifikt optimeringsproblem i en familie af lignende flertrinsproblemer fører til gentagelsesrelationer - funktionelle ligninger - mht. optimal værdi målfunktion. Deres løsning giver os mulighed for konsekvent at opnå optimal kontrol over det oprindelige optimeringsproblem.

1. Grundlæggende begreber

1.1 Dynamisk programmeringsmodel

Lad os give generel beskrivelse dynamiske programmeringsmodeller.

Under overvejelse kontrolleret system, som under indflydelse af kontrol bevæger sig fra starttilstanden

til den endelige tilstand. Lad os antage, at systemstyringsprocessen kan opdeles i P trin. Lad , ,..., være systemets tilstande efter den første, anden,..., P-trin. Dette er vist skematisk i fig. 1.

Billede 1

Stat

systemer efter kth trin ( k = 1,2 …,n) er kendetegnet ved parametre , ,..., som kaldes fasekoordinater. Tilstanden kan repræsenteres af et punkt i det s-dimensionelle rum kaldet fase rum. Konsekvent transformation af systemet (trin for trin) opnås ved hjælp af visse aktiviteter, ,..., , som udgør systemstyring , hvor er kontrollen på k-trin, overførsel af systemet fra tilstand til tilstand (fig. 1). Ledelse på k Det trin er at vælge værdierne for visse kontrolvariabler.

Vi antager fremover, at systemets tilstand i slutningen kth trin afhænger kun af den tidligere tilstand af systemet

og ledelse videre dette trin(fig. 1). Denne egenskab kaldes ingen eftervirkning. Lad os betegne denne afhængighed som , (1.1)

Ligheder (1.1) kaldes tilstandsligninger. Funktioner

vi antager givet.

Varierende kontrol U , vi vil opnå forskellige "effektiviteter" af processen, som vi vil vurdere kvantitativt ud fra den objektive funktion Z , afhængigt af systemets oprindelige tilstand

og fra den valgte kontrol U : . (1.2)

Præstationsindikator kth trin i kontrolprocessen, som afhænger af staten

i begyndelsen af ​​dette trin og den kontrol, der er valgt på dette trin, vil blive betegnet med det pågældende problem trin-for-trin optimering objektivfunktionen (1.2) skal være additiv, dvs. . (1.3)

Hvis additivitetsegenskaben for den objektive funktion Z ikke er opfyldt, kan dette nogle gange opnås ved nogle transformationer af funktionen. For eksempel, hvis Z er en multiplikativ funktion givet som

, så kan vi overveje en funktion, der er additiv.

Typisk styres procesbetingelserne ved hvert trin

nogle begrænsninger gælder. Kontroller, der opfylder disse begrænsninger kaldes tilladte .

Trin-for-trin optimeringsproblemet kan formuleres som følger: Bestem sættet af gennemførlige kontroller