- 1,03 MB

La oss gi en matematisk formulering av optimalitetsprinsippet. For enkelhets skyld vil vi anta at de initiale x 0 og siste x T-tilstandene til systemet er gitt. La oss betegne med z 1 (x 0 , u 1) verdien av målfunksjonen i det første trinnet med starttilstanden til systemet x 0 og med kontroll u 1 , med z 2 (x 1 , u 2) den tilsvarende verdien av målfunksjonen bare på andre trinn, ..., gjennom
z i (х i -1 ,u i) – på i-te trinn, ..., gjennom z N (x N-1, u N) -på N. trinn. Det er åpenbart det

Vi må finne den optimale kontrollen u*= (; ;...;), slik at den leverer et ekstremum objektiv funksjon(1) underlagt restriksjoner.

For å løse dette problemet fordyper vi det i en familie med lignende. La oss introdusere litt notasjon. La være henholdsvis områdene

definisjoner for lignende problemer på siste stadium, de to siste osv.;
- domene originalt problem. La oss betegne med henholdsvis F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), det betinget optimale verdier av målfunksjonen på det siste stadiet, to de siste osv., på de k siste osv., på alle N stadier.

La oss begynne med siste etappe. La x N-1 være de mulige tilstandene til systemet ved begynnelsen av det N-te trinnet. Vi finner:

Fi (x N-1) = zN (x N-1, uN). (2)

For de to siste etappene får vi

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

Like måte:

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

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

Fk (xN-k) = (z N-k+1 (xN-k, uN-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)

Uttrykk (6) er en matematisk representasjon av optimalitetsprinsippet. Uttrykk (5) – generell form registrering av den betinget optimale verdien av målfunksjonen for de k gjenværende stadiene. Uttrykk (2) – (6) kalles funksjonelle Bellman-ligninger. Deres tilbakevendende (tilbakevendende) natur er tydelig synlig, dvs. for å finne den optimale kontrollen ved N trinn, må du kjenne til den betinget optimale kontrollen ved de forrige N – 1-stadiene, osv. Derfor kalles funksjonelle ligninger ofte tilbakevendende (tilbakevendende) Bellman-relasjoner.

1. Funksjoner ved oppgaver dynamisk programmering

Basert på ovenstående kan vi fremheve følgende funksjoner ved dynamiske programmeringsproblemer.

• Vi tar for oss et system hvis tilstand ved hvert trinn bestemmes av vektoren x t. Ytterligere endringer i tilstanden hennes avhenger bare av denne staten x t og er ikke avhengig av hvordan systemet kom til denne tilstanden. Slike prosesser kalles prosesser uten ettervirkning.
• Ved hvert trinn velges én løsning u t, under påvirkning av hvilken systemet går fra tidligere tilstand x t -1 til ny x t . Denne nye tilstanden er en funksjon av tilstanden ved begynnelsen av intervallet x t -1 og avgjørelsen u t vedtatt ved begynnelsen av intervallet, dvs. x t = x t (x t -1 ,u t).
• Handlingen på hvert trinn er forbundet med en viss gevinst (inntekt, fortjeneste) eller tap (kostnader), som avhenger av staten ved begynnelsen av trinnet (stadiet) og beslutningen som er tatt.
• Restriksjoner kan pålegges staten og kontrollvektorene, og kombinasjonen av disse utgjør regionen med gjennomførbare løsninger.
• Det kreves å finne en slik tillatt kontroll u t for hvert trinn t for å oppnå ekstremverdien til målfunksjonen for alle T-trinn.

Enhver gyldig sekvens av handlinger for hvert trinn som overfører systemet fra starttilstanden til slutttilstanden kalles en kontrollstrategi. En kontrollstrategi som resulterer i en ekstremverdi av objektivfunksjonen kalles optimal.

Den geometriske tolkningen av det dynamiske programmeringsproblemet er som følger. La n være dimensjonen til tilstandsrommet. I hvert øyeblikk av tiden har koordinatene til systemet en veldig spesifikk verdi. Med en endring i tid t kan koordinatverdiene til tilstandsvektoren endres. La oss kalle overgangen til et system fra en stat til en annen banen for dets bevegelse i staters rom. En slik overgang gjennomføres ved å påvirke de statlige koordinatene. Rommet der tilstandene til systemet fungerer som koordinater kalles faserom. Det dynamiske programmeringsproblemet kan tolkes spesielt tydelig hvis tilstandsrommet er todimensjonalt. Området med mulige tilstander i dette tilfellet vil bli avbildet av en viss figur, de første og siste tilstandene til systemet - med poeng x 0 (fig. 1). Kontroll er påvirkningen som overfører systemet fra den opprinnelige tilstanden til den endelige tilstanden. For mange økonomiske problemer er den opprinnelige eller endelige tilstanden ikke kjent, men regionen X 0 eller X T som disse punktene tilhører er kjent.

Bilde 1

Deretter kontrollerer tillatte overføringspunkter fra området X 0 til X T . Det dynamiske programmeringsproblemet kan formuleres geometrisk som følger: finn en fasebane som starter i området X 0 og slutter i området X T som målfunksjonen når en ekstremverdi for. Hvis start- og slutttilstanden til et dynamisk programmeringsproblem er kjent, snakker vi om et problem med faste ender. Hvis de første og siste regionene er kjent, snakker vi om et problem med frie ender.

1. RESSURSFORDELING PROBLEM

2.1 Generell beskrivelse av problemet

La oss vurdere bruken av den dynamiske programmeringsmetoden ved å bruke eksemplet på fordeling av midler mellom seks gjenoppbyggingsobjekter til et byvannsverk:

1. Sentral pumpe- og filtreringsstasjon;

2. Østlig pumpe- og filtreringsstasjon;

3. Vannpumpestasjon;

4. Sentral luftestasjon;

5. Østlig luftestasjon;

6. Landsluftestasjon.

Den totale mengden av midler til utvikling er ikke mer enn 195 tusen hryvnia. Basert på tekniske og økonomiske beregninger ble det fastslått at anleggene som følge av rekonstruksjon, avhengig av hvor mye midler som brukes, vil ha produktiviteten vist i tabell 1.1. Det er nødvendig å bestemme den optimale fordelingen av midler mellom gjenoppbyggingsobjekter, noe som vil sikre maksimal økning i produktiviteten til disse objektene. Dermed bruker dette problemet et optimaliseringskriterium - den totale produktiviteten til foretak av gjenoppbyggingsobjekter.

Tabell 1.1 Inndata for produktiviteten til gjenoppbyggingsobjekter

Objektets serienummer

Volum av ressurser tildelt for utvikling av anlegg (tusen UAH)

Produktivitet av objekter som et resultat av utvikling (tusen m3)

1. Blokkdiagram av programmet

Figur 1. Hovedprogram

QtObj – antall objekter

QtRes – antall ressurser

effMatrix - objektytelsesmatrise,

distVector – vektor av tildelte ressurser

Trinn 1: Betinget optimalisering

Trinn 2. Ubetinget optimalisering

I = QtObj-1.0 danner vektorresultatet

Figur 2. Dataregistrering

distVector – avstandsvektor, effMatrix = ytelsesmatrise

hvis alle matriseelementer er lagt inn

hvis ytelsesvektoren ikke er det

negativ

Figur 3. Betinget optimalisering,

vi danner en utdatamatrise (maksimum av målfunksjonen)

outMatrix – maksimal målmatrise

QtObj – antall objekter

QtRes – antall ressurser

Matrise – ytelsesmatrise

distVect – avstandsvektor (ressursvektor)

nei ja Hvis den første bedriften

Finne maksimum

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

1. Programalgoritmestruktur

1. Datainndata – klasse DataDlg.

Variable klassemedlemmer.

//vektor for å lagre mengden ressurser

std::vektor distVektor;

//objektytelsesmatrise

int** effMatrise;

//funksjon for å konvertere en streng til et tall

int StringToInt(CSstring);

//funksjon for å kontrollere riktigheten av de angitte dataene

BOOL FillMatrix();

//ressursrensefunksjon etter lukking av vinduet

virtuell BOOL DestroyWindow();

//dialog initialiseringsfunksjon

virtuell BOOL OnInitDialog();

1. Beregning av resultater - hovedklassen i programmets kursWorkDlg

Variable klassemedlemmer

intVerdi; //ytelsesverdi

int MaxIndex;// maksimal indeks i ressursvektoren

int Facility;//enterprise

int Recource;//dedikert ressurs

Vare ** outMatrix; //maksimal målmatrise

std::vektor resVektor; //vektor av resultater

void BuildOutMatrix(int ​​​​**, std::vektor );//funksjon for å generere målmatrisen (betinget optimalisering)

afx_msg void OnBnClickedButton1(); // handler for å klikke på "Calculate"-knappen, som starter beregningsprosessen.

virtuell BOOL DestroyWindow();//tømmer programressurser

1. Utdata klasserapport

Hensikten med denne klassen er å gi ut resultatvektoren i tabellform.

2.4 Resultater av programmet

Innledende datainntasting

1. Legge inn data om produktiviteten til gjenoppbyggingsobjekter

1. Hvis ikke alle feltene er fylt ut

1. Hvis et feil tegn er skrevet inn

Riktig datainntasting

Vis resultat

1. Datainput

Resultatet av programmet

Innledende datainntasting

Gå inn i objektproduktivitet

Applikasjon.

Programliste

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// er alle felt fylt ut?

BOOL DataDlg::FillMatrix()

bool flagg = sant;

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 må fylle ut alle felt", L"Feil", MB_ICONERROR | MB_OK);

Arbeidsbeskrivelse

Formålet med dette arbeidet er å implementere på en datamaskin en løsning på problemet med optimal tildeling av midler til utvidelse av produksjonen.
Arbeidsmål:
Ta i betraktning teoretiske aspekter løse dynamiske programmeringsproblemer; gjentakende karakter av oppgaver av denne typen; Bellmans prinsipper om optimalitet.
Algoritmeutvikling. Blokkdiagrammer. Algoritmestruktur.
Datamaskinimplementering av den utviklede algoritmen i det valgte programmeringsspråket.

Innhold

INNLEDNING………………………………………………………………2
Dynamisk programmering
Grunnleggende konsepter…………………4
Prinsipper for dynamisk programmering. Bellman funksjonelle ligninger………………………….5
Funksjoner ved dynamiske programmeringsproblemer……………….10
Ressursfordelingsproblem………………………12
Generell beskrivelse av problemet………………………….13
Blokkdiagram av programmet
Programalgoritmestruktur
Resultatet av programmet
Konklusjon
Bibliografi

Send ditt gode arbeid i kunnskapsbasen er enkelt. Bruk skjemaet nedenfor

Godt jobba til nettstedet">

Studenter, hovedfagsstudenter, unge forskere som bruker kunnskapsbasen i studiene og arbeidet vil være deg veldig takknemlig.

postet på http://www.allbest.ru/

Ressursallokeringsproblem ved bruk av dynamisk programmeringsmetode

For å utvide produksjonskapasiteten til tre foretak A, B og C, tildeles et visst antall enheter ekstra elektrisitet i mengden x 0 = 8 enheter. Elektrisitet kan frigjøres i form av 1, 2, 3, 4, 5, 6, 7 og 8 enheter. Ved å investere x i enheter elektrisitet i utviklingen av det i-te foretaket kan du få inntekter fra i-enheter ved foretaket. Eksistere forskjellige varianter x i (k) tildeling av ekstra elektrisitet. De bringer inntekt til i (k), k=1,n. Mulige alternativer utvikling av foretak er gitt i tabell 1. Den totale inntekten for alle foretak skal være maksimal, dvs. y=? y i (k)>maks

Bord 1. Bedriftsutviklingsalternativer

Alternativ k	Enterprise A	Enterprise B	Enterprise C

Matematisk iscenesettelse oppgaver:

y=? på Jeg (k)> maks

?X Jeg (k)?x 0

Løsning:

La oss begynne å vurdere prosedyren for å løse det aktuelle problemet fra det siste (3 trinn) stadiet (tabell 2), hvor investeringer tildeles virksomhet C. Betinget optimal kontroll på tredje trinn søkes 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 (trinn 3)

Stat		Kontroll

Det er fire muligheter for å investere midler - fire trinns kontroller x C (1) = 0 enheter, x C (2) = 1 enhet, x C (3) = 2 enheter, x C (4) = 3 enheter. og ni teoretisk mulige tilstander av systemet S 2 før tildeling av midler til bedrift C - volumene av investeringer som ikke er distribuert til tredje trinn: 0,1,2,3,4,5,6,7,8.

La oss anta at systemet var i tilstanden S 2 = 2. Så, for trinnkontroll x C (2) = 1, vil inntekten til C (2) være lik 3 enheter. (Tabell 3), og trinnkontroll x C (3) = 2 vil være optimal for denne tilstanden, og gir en betinget maksimal forsterkning g c (S 2) = 5. Hvis systemet var i tilstand S 2 =3, er alle trinnkontroller tillatt: x C (1) = 0 enheter, x C (2) = 1 enhet, x C (3) = 2 enheter, x C (4) = 3 enheter. , og den optimale kontrollen vil være x C (4) = 3, som gir en betinget maksimal forsterkning g c (S 2) = 6.

Tabell 3 dynamisking

Alle mulige tilstander før 3. trinn fylles ut på samme måte. De optimale verdiene til indikatorene er markert med fet skrift i tabellene.

Deretter vurderes det andre trinnet på samme måte (tabell 4), som består i å allokere investeringer til foretak A. På det andre trinnet er den totale gevinsten summen av gevinstene mottatt i tredje og andre trinn, og gis etter forholdet:

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

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

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

Maks k 4+g c =4+5=9, hvor vi finner fra tabell 1, og g c fra tabell 3. Alle tilstander er fylt ut på samme måte.

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

Stat	f A +g c	Kontroll

Her oppstår det situasjoner hvor den optimale løsningen ikke vil være den eneste. I tilstanden S 1 = 3 vil trinnkontroller x A (2) = 1 og x A (3) = 2 være betinget optimal, og gir det samme forsterkning g A (S 1) = 9

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

På det første trinnet (tabell 5) - allokering av investeringer til bedrift B - er det bare en tidligere tilstand av systemet, tilsvarende starttilstanden S 0 =8. Den ubetinget optimale gevinsten bestemmes av uttrykket:

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

Ubetinget optimale kontroller som sikrer maksimal inntekt kan være annerledes.

Opplegg for å finne alle optimale alternativer fordeling av investeringer mellom foretak (tabell 6) er presentert i figur 1.

Bord 6. Optimal fordeling av investeringer.

Figur 1. Ordning med optimal fordeling av investeringer mellom foretak

Konklusjon: etter å ha vurdert problemet med ressursallokering ved bruk av dynamisk programmeringsmetode, er det identifisert to alternativer for optimal ressursallokering.

Skrevet på Allbest.ru

...

Lignende dokumenter

generelle egenskaper og økonomiske resultatindikatorer for de tre foretakene som studeres. Løse problemet med produksjonsplanlegging, samt investeringsdistribusjon ved hjelp av lineær og dynamisk programmering. Komparativ analyse av resultater.

kursarbeid, lagt til 25.04.2015


Flertrinns prosesser i dynamiske oppgaver. Prinsippet om optimalitet og gjentakelsesforhold. Dynamisk programmeringsmetode. Problemer med optimal tildeling av midler til produksjonsutvidelse og produksjonsprogramplanlegging.

kursarbeid, lagt til 30.12.2010


Dynamisk programmeringsmetode og dens hovedstadier. Optimal strategi for utskifting av utstyr. Minimere kostnader for bygging og drift av virksomheter. Optimal fordeling av ressurser i STROYKROVLYA LLC og investeringer i PKT Khimvolokno.

kursarbeid, lagt til 01.08.2015


Matematisk modell for produksjonsplanlegging. Utarbeide en optimal plan for produksjonsaktivitetene til en bedrift ved hjelp av metoden lineær programmering. Finne den beste måten fordeling av pengeressurser i planperioden.

avhandling, lagt til 08.07.2013


Beregning av transportkostnader ved hjelp av metoden minimumskostnader. Finne betinget optimal likhet i prosessen med dynamisk programmering. Lineær algebraisk ligning Kolmogorov for gjennomsnittlig tid problemfri drift redundant system.

kursarbeid, lagt til 14.01.2011


Grafisk metode løse problemet med optimalisering av produksjonsprosesser. Anvendelse av en simpleksalgoritme for å løse et økonomisk optimalisert produksjonsstyringsproblem. Dynamisk programmeringsmetode for valg av optimal baneprofil.

test, lagt til 15.10.2010


Optimal plan fordeling av midler mellom virksomheter. Utvikle en plan for hver bedrift hvor avkastningen på investeringen vil være høyeste verdi. Bruk av lineære og dynamiske programmeringsmetoder.

kursarbeid, lagt til 16.12.2013


Karakteristiske trekk ved lineære programmeringsproblemer. Generell formulering av. Konstruksjon av en matematisk modell for fordeling av selskapets ressurser. Sensitivitetsanalyse av den optimale løsningen. Utarbeide en bærekraftsrapport.

presentasjon, lagt til 12.02.2014


Finne den optimale verdipapirporteføljen. Gjennomgang av metoder for å løse problemet. Konstruksjon av en matematisk modell. Kjegleprogrammeringsproblem. Avhengighet av spå en av startparametrene.

avhandling, lagt til 02.11.2017


Dynamisk programmeringsmodell. Optimalitetsprinsippet og Bellman-ligningen. Beskrivelse av prosessen med å modellere og konstruere et beregningsdynamisk programmeringsskjema. Problemet med å minimere kostnadene ved bygging og drift av bedrifter.

Timeplan

Akademisk disiplin MATEMATISKE METODER OG MODELLER I ØKONOMI

Leksjonens tema Løsning av ulike praktiske problemer DP ved hjelp av matematiske metoder.

Leksjonens mål

Utvikle ferdigheter i å løse dynamiske programmeringsproblemer.

Utvikling av kvaliteten på sinnet, oppmerksomheten og akademiske arbeidsferdighetene til studentene.

Innføre disiplin og besluttsomhet hos elevene.

Leksjonsutstyr Forelesningsnotater, V.P. Agaltsov "Matematiske metoder i programmering."

I løpet av timene:

Organiseringstid:

sjekke fravær, fylle ut loggen.

Oppdatering av referansekunnskap: svar på sikkerhetsspørsmål

Hvilke oppgaver kalles flertrinn?

Hvilket matematisk apparat brukes til å løse flertrinnsoppgaver?

Hva er optimal kontroll u*?

Hva er metodens algoritme påfølgende tilnærminger i to sirkler?

Gi eksempler på optimale ressursallokeringsproblemer.

Lære nytt materiale:

Klassiske dynamiske programmeringsproblemer

• Lengste vanlige undersekvensproblem: Gitt to sekvenser, må du finne den lengste vanlige undersekvensen.

• Problem med å finne den lengste økende undersekvensen: gitt en sekvens, må du finne den lengste økende undersekvensen.

• Redaksjonelt avstandsproblem (Levenshtein-avstand): gitt to strenger, må du finne minimum antall slettinger, erstatninger og tillegg av tegn som forvandler en streng til en annen.

• Problemet med å beregne Fibonacci-tall

• Problemet med rekkefølgen av matrisemultiplikasjon: gitte matriser, ..., er det nødvendig å minimere antall skalaroperasjoner for deres multiplikasjon.

• Problem med banevalg

• Sekvensielt beslutningstakingsproblem

• Arbeidsutnyttelsesproblem

• Problem med lagerstyring

• Ryggsekkproblemet: fra et ubegrenset sett med objekter med egenskapene "kostnad" og "vekt", er det nødvendig å velge et visst antall objekter på en slik måte at man oppnår maksimal totalkostnad med begrenset totalvekt.

• Floyd-Warshall-algoritme: finn de korteste avstandene mellom alle toppunktene i en vektet rettet graf.

• Bellman-Ford-algoritme: finn den korteste veien i en vektet graf mellom to gitte hjørner.

• Maksimalt uavhengig sett med toppunkter i et tre: gitt et tre, finn det maksimale settet med toppunkter slik at ikke to av dem er forbundet med en kant.

Eksempel: Optimal ressursallokering

Kapital 40 millioner rubler. investor må investere i fire investeringsprosjekter for å oppnå maksimal inntekt. Lønnsomheten til prosjekter er gitt i tabellen (investeringer er multipler på 8 millioner rubler)

u

Fortjeneste på gjennomføring

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 av to trinn. På det første stadiet (fra slutt til begynnelse) ser vi etter en betinget optimal løsning, på det andre (fra begynnelse til slutt) ser vi etter den optimale løsningen på problemet.

1. stadie.

Vi fordeler kapital mellom fire prosjekter og beregner mottatt overskudd L (Jeg ), Jeg = 8,16,24,32,40.

1 trinn: Penger investerer i det fjerde prosjektet.

L(8)= 55

L(16)=58

L(24)=90

L(32)=100

L(40)=140

Steg 2: Det investeres midler i fjerde og tredje prosjekt.

u

Fortjeneste på gjennomføring

1 trinn

f3(u)

55

39

10 0

120

14 0

145

Trinn 3: Det investeres midler i det fjerde, tredje (trinn 2) og andre prosjekt.

u

Fortjeneste på gjennomføring

Steg 2

f 2(u)

94

108

120

135

135

175

158

175

134

214

147

Trinn 2:

På det fjerde trinnet velger vi maksimum av de oppnådde profittverdiene L (40) = 214.

Og tilbake til omvendt rekkefølge Fra tabell til tabell (fra 4 trinn til 1) velger vi slike inntektsverdier der verdien 214 oppnås.

Maksimal inntekt 214 millioner rubler. fra de investerte midlene kan mottas med følgende fordeling av midler:

1 prosjekt - 0 millioner rubler.

2 prosjekt – 24 millioner rubler.

Tredje prosjekt - 8 millioner rubler.

4 prosjekt - 8 millioner rubler.

Konsoliderer nytt materiale:

5. Oppsummering av leksjonen: konklusjoner, vurderinger, hjemmelekser:

(2) klausul 5.1

Ср12: dannelse og assimilering av innholdet i teoretisk materiale

Lærerens signatur

Tilgjengelig en viss mengde ressurser s 0, som må fordeles på n virksomhetsenheter for løpende aktiviteter i løpet av den aktuelle perioden (måned, kvartal, halvår, år osv.) for å få totalsummen maksimal fortjeneste. Størrelsen på ressursinvesteringene x i (;) i aktivitetene til hver økonomisk enhet er et multiplum av en viss verdi h. Det er kjent at hver økonomisk enhet, avhengig av volumet av midler brukt x i for perioden under vurdering, genererer et overskudd i mengden fi (xi) (avhenger ikke av investeringen av ressurser i andre økonomiske enheter).

La oss forestille oss prosessen med ressursfordeling mellom økonomiske enheter som en n-trinns styringsprosess (trinntallet sammenfaller med betinget nummerøkonomisk enhet). La s k () være en tilstandsparameter, dvs. mengden tilgjengelige midler etter kth trinn for fordeling blant de gjenværende (n - k) forretningsenhetene. Da kan tilstandsligningene skrives i følgende form:

La oss introdusere funksjonen - den betinget optimale totale fortjenesten mottatt fra k-th, (k+1) - th, ..., n-th økonomiske enheter, hvis ressurser i mengden s k-1 () var optimalt fordelt mellom dem. Mange mulige ledelsesbeslutninger i forhold til størrelsen på distribuerte ressurser på k-te trinn kan representeres som følger: .

Så de tilbakevendende ligningene til R.E. Bellman (omvendt diagram) vil se slik ut:

Eksempel. Det er en viss mengde ressurser s 0 =100, som må fordeles på n=4 forretningsenheter for løpende aktiviteter i løpet av den aktuelle perioden (måned) for å oppnå maksimalt overskudd. Størrelsen på investeringen av ressurser x i (;) i aktivitetene til hver økonomisk enhet er et multiplum av verdien h = 20 og spesifiseres av vektoren Q. Det er kjent at hver økonomisk enhet, avhengig av volumet av midler som brukes x i for perioden under vurdering, gir et overskudd i mengden f i (x i) () (avhenger ikke av investeringen av ressurser i andre økonomiske enheter):

Det er nødvendig å bestemme hvor mye ressurser som skal tildeles hver virksomhet for at det totale overskuddet skal være størst.

Løsning. La oss lage Bellmans tilbakevendende ligninger (inverst skjema):

La oss bestemme de betingede maksimumene i samsvar med (13); beregningsresultatene er presentert i tabell 1.

Tabell 1. Beregning av betingede optima

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

I følge resultatene betinget optimalisering La oss bestemme den optimale ressursfordelingen:

Dermed er den optimale ressursallokeringen:

som vil gi størst fortjeneste i mengden av 87 konvensjonelle enheter. hi. enheter

Svar: optimal ressursallokering: som gir størst fortjeneste av 87 konvensjonelle enheter. hi. enheter

Konklusjon

Dynamisk programmering er et felt matematisk programmering, inkludert et sett med teknikker og midler for å finne den optimale løsningen, samt optimalisere hvert trinn i systemet og utvikle en styringsstrategi, det vil si at styringsprosessen kan representeres som en flertrinnsprosess. Dynamisk programmering, ved hjelp av trinn-for-trinn-planlegging, gjør det ikke bare mulig å forenkle løsningen av problemet, men også å løse de problemene som metoder ikke kan brukes for matematisk analyse. Forenkling av løsningen oppnås ved å redusere antall alternativer som studeres betydelig, siden i stedet for å løse et komplekst multivariat problem én gang, innebærer trinn-for-trinn planleggingsmetoden flere løsninger mht. enkle oppgaver. Når vi planlegger en trinnvis prosess går vi ut fra interessene til hele prosessen som helhet, dvs. Når du tar en beslutning på et bestemt stadium, er det alltid nødvendig å huske på det endelige målet. Dynamisk programmering har imidlertid også sine ulemper. I motsetning til lineær programmering, der simpleks metode er universell; det er ingen slik metode i dynamisk programmering. Hver oppgave har sine egne vanskeligheter, og i hvert tilfelle er det nødvendig å finne den mest passende løsningsmetoden. Ulempen med dynamisk programmering er også kompleksiteten ved å løse flerdimensjonale problemer. Et dynamisk programmeringsproblem må tilfredsstille to betingelser. Den første tilstanden kalles vanligvis tilstanden for fravær av ettervirkning, og den andre er tilstanden for additivitet av den objektive funksjonen til problemet. I praksis er det planleggingsproblemer der tilfeldige faktorer spiller en vesentlig rolle, og påvirker både systemets tilstand og gevinsten. Det er en forskjell mellom deterministiske og stokastiske dynamiske programmeringsproblemer. I et deterministisk problem er den optimale kontrollen unik og er spesifisert på forhånd som tøft program handlinger. I et stokastisk problem er den optimale kontrollen tilfeldig og velges under selve prosessen, avhengig av den tilfeldige situasjonen. I et deterministisk opplegg, som går gjennom prosessen i trinn fra slutt til begynnelse, er det også på hvert trinn hele linjen betingede optimale kontroller, men av alle disse kontrollene ble til slutt bare én implementert. Dette er ikke tilfelle i et stokastisk opplegg. Hver av de betingede optimale kontrollene kan faktisk implementeres hvis forrige trekk tilfeldig prosess vil bringe systemet i riktig tilstand. Prinsippet om optimalitet er grunnlaget for trinn-for-trinn-løsningen av dynamiske programmeringsproblemer. Typiske representanter for økonomiske problemer med dynamisk programmering er de såkalte problemene med produksjon og lagring, problemer med distribusjon av kapitalinvesteringer, problemer med kalender produksjonsplanlegging og andre. Dynamiske programmeringsproblemer brukes i planlegging av virksomheten til en virksomhet, med hensyn til endringer i behovet for produkter over tid. I optimal fordeling av ressurser mellom virksomheter i retning eller tid. Beskrivelsen av egenskapene til dynamisk programmering og hvilke typer problemer som kan formuleres innenfor dens ramme, må nødvendigvis være veldig generell og noe vag, siden det er en enorm variasjon ulike oppgaver, som passer inn i det dynamiske programmeringsskjemaet. Kun studier stort nummer eksempler gir en klar forståelse av strukturen til dynamisk programmering.

1. Grunnleggende begreper

1.1. Dynamisk programmeringsmodell

1.2. Prinsippet om optimalitet. Bellman-ligningen

2. Optimal ressursallokering

2.1 Problemstilling

2.2 Todimensjonal ressursallokeringsmodell

2.3 Diskret dynamisk modell optimal ressursallokering

2.4 Ta hensyn til ettervirkninger i problemer med optimal ressursallokering

Konklusjon

Liste over kilder som er brukt

Vedlegg 1. Programoppføring for å løse problemet med optimal ressursallokering med gitte parametere. Programresultater

Introduksjon

Gjennom historien har folk tydd til komplekse ritualer når de står overfor avgjørelser. De holdt høytidelige seremonier, ofret dyr, fortalte lykke ved stjernene og så på fuglenes flukt. De stolte på folkelig overtro og prøvde å følge primitive regler som gjorde den vanskelige oppgaven med å ta beslutninger lettere for dem. For tiden brukes et nytt og tilsynelatende mer vitenskapelig "ritual" for å ta avgjørelser, basert på bruk av en elektronisk datamaskin. Uten moderne tekniske midler Det menneskelige sinnet kan sannsynligvis ikke ta hensyn til de mange og varierte faktorene man møter ved å drive en virksomhet, designe en rakett eller regulere trafikken. Det er mange eksisterende matematiske metoder optimaliseringer er allerede ganske utviklet, noe som gjør det mulig å effektivt bruke evnene til digital og hybrid datamaskiner. En av disse metodene er matematisk programmering, som inkluderer begge deler spesielt tilfelle dynamisk programmering.

De fleste praktiske problemer har flere (og noen kanskje til og med uendelig antall) løsninger. Målet med optimalisering er å finne den beste løsningen blant mange potensielt mulige i samsvar med et eller annet kriterium for effektivitet eller kvalitet. Et problem som bare tillater én løsning krever ikke optimalisering. Optimalisering kan oppnås ved hjelp av mange strategier, alt fra svært komplekse analytiske og numeriske matematiske prosedyrer til intelligent bruk av enkel aritmetikk.

Dynamisk programmering er en optimaliseringsmetode tilpasset operasjoner der beslutningsprosessen kan brytes ned i separate stadier (trinn). Slike operasjoner kalles flertrinn.

Som en gren av matematisk programmering begynte dynamisk programmering (DP) å utvikle seg på 50-tallet av det 20. århundre. takket være arbeidet til R. Bellman og hans medarbeidere. For første gang ble optimale lagerstyringsproblemer løst ved hjelp av denne metoden, deretter utvidet klassen av problemer seg betydelig. Hvordan praktisk metode optimering ble den dynamiske programmeringsmetoden bare mulig ved bruk av moderne datateknologi.

Den dynamiske programmeringsmetoden er basert på optimalitetsprinsippet formulert av Bellman. Dette prinsippet og ideen om å inkludere et spesifikt optimaliseringsproblem i en familie med lignende flertrinnsproblemer fører til gjentakelsesrelasjoner - funksjonelle ligninger - mht. optimal verdi målfunksjon. Deres løsning lar oss konsekvent oppnå optimal kontroll for det opprinnelige optimaliseringsproblemet.

1. Grunnleggende begreper

1.1 Dynamisk programmeringsmodell

La oss gi generell beskrivelse dynamiske programmeringsmodeller.

Under vurdering kontrollert system, som under påvirkning av kontroll beveger seg fra den opprinnelige tilstanden

til den endelige tilstanden. La oss anta at systemadministrasjonsprosessen kan deles inn i P trinn. La , ,..., være tilstandene til systemet etter den første, andre,..., P-trinn. Dette er vist skjematisk i fig. 1.

Bilde 1

Stat

systemer etter kth steg ( k = 1,2 …,n) er preget av parametere , ,..., som kalles fasekoordinater. Tilstanden kan representeres av et punkt i det s-dimensjonale rommet kalt faserom. Konsekvent transformasjon av systemet (trinn for trinn) oppnås ved hjelp av visse aktiviteter , ..., , som utgjør systemadministrasjon , hvor er kontrollen på k-trinn, overføring av systemet fra stat til stat (fig. 1). Ledelse på k Det tredje trinnet er å velge verdiene til visse kontrollvariabler.

Vi antar heretter at tilstanden til systemet på slutten kth trinnet avhenger bare av den forrige tilstanden til systemet

og ledelse på dette trinnet(Figur 1). Denne egenskapen kalles ingen ettervirkning. La oss betegne denne avhengigheten som , (1.1)

Likheter (1.1) kalles tilstandsligninger. Funksjoner

vi antar gitt.

Varierende kontroll U , vi vil oppnå forskjellige "effektiviteter" av prosessen, som vi vil vurdere kvantitativt av den objektive funksjonen Z , avhengig av den opprinnelige tilstanden til systemet

og fra den valgte kontrollen U : . (1.2)

Ytelsesindikator kth trinn i kontrollprosessen, som avhenger av staten

i begynnelsen av dette trinnet og kontrollen valgt på dette trinnet vil bli betegnet med problemet under vurdering trinn-for-trinn-optimalisering objektivfunksjonen (1.2) må være additiv, dvs. . (1.3)

Hvis additivitetsegenskapen til objektivfunksjonen Z ikke er tilfredsstilt, kan dette noen ganger oppnås ved noen transformasjoner av funksjonen. For eksempel, hvis Z er en multiplikativ funksjon gitt som

, så kan vi vurdere en funksjon som er additiv.

Vanligvis kontrolleres prosessforholdene ved hvert trinn

noen restriksjoner gjelder. Kontroller som tilfredsstiller disse begrensningene kalles godkjent .

Trinn-for-trinn optimaliseringsproblemet kan formuleres som følger: Bestem settet med gjennomførbare kontroller