Dynamisk programmeringsmetode i ledelsen. Dynamisk programmeringsmetode

For valg optimal løsning Når du utfører programmeringsoppgaver, må du noen ganger iterere et stort nummer av kombinasjoner av data som laster minne personlig datamaskin. Slike metoder inkluderer for eksempel programmeringsmetoden «del og hersk». I i dette tilfellet Algoritmen sørger for å dele opp oppgaven i separate små underoppgaver. Denne metoden brukes kun i tilfeller der små deloppgaver er uavhengige av hverandre. For å unngå å utføre unødvendig arbeid dersom deloppgaver er gjensidig avhengige, brukes den dynamiske programmeringsmetoden som amerikaneren R. Bellman foreslo på 50-tallet.

Essensen av metoden

Dynamisk programmering innebærer å bestemme den optimale løsningen på et n-dimensjonalt problem ved å dele det inn i n separate trinn. Hver av dem er en deloppgave med hensyn til én variabel.

Den største fordelen med denne tilnærmingen er at utviklere håndtere endimensjonale optimaliseringsoppgaver delproblemer i stedet for et n-dimensjonalt problem, og løsningen hovedoppgave samlet nedenfra og opp.

Det er tilrådelig å bruke dynamisk programmering i tilfeller der deloppgaver henger sammen, dvs. ha vanlige moduler. Algoritmen sørger for å løse hver av deloppgavene én gang, og svarene lagres i en spesiell tabell. Dette gjør det mulig å ikke beregne svaret på nytt når du møter en lignende deloppgave.

Dynamiskblem. Forfatteren av denne metoden, R. Bellman, formulerte prinsippet om optimalitet: uansett starttilstand ved hvert av trinnene og løsningen bestemt på dette trinnet, velges alle etterfølgende optimal i forhold til tilstanden systemet inntar ved slutten av trinnet.

Metoden vil forbedre utførelsen av problemer løst ved å bruke oppregning av alternativer eller rekursjoner.

Konstruksjon av problemalgoritmen

Dynamisk programmering innebærer å konstruere en problemalgoritme der problemet er delt inn i to eller flere deloppgaver slik at løsningen består av den optimale løsningen av alle deloppgavene som er inkludert i den. Deretter er det behov for å skrive en gjentakelsesrelasjon og beregne optimal verdi parameter for oppgaven som helhet.

Noen ganger på det tredje trinnet må du i tillegg huske litt tilleggsinformasjon om fremdriften til hver deloppgave. Dette kalles reversering.

Anvendelse av metoden

Dynamisk programmering brukes når to karakteristiske funksjoner er tilstede:

optimalitet for deloppgaver;
tilstedeværelsen av overlappende deloppgaver i en oppgave.

Når du løser ved hjelp av dynamisk programmering, må du først beskrive løsningens struktur. Et problem er optimalt hvis løsningen på problemet består av optimale løsninger på underproblemene. I dette tilfellet er det tilrådelig å bruke dynamisk programmering.

Den andre egenskapen til problemet, som er viktig når denne metoden, - lite antall deloppgaver Rekursiv løsning oppgaver bruker de samme overlappende underoppgavene, hvor antallet avhenger av størrelsen på kildeinformasjonen. Svaret lagres i en spesiell tabell; programmet sparer tid ved å bruke disse dataene.

Bruken av dynamisk programmering er spesielt effektiv når beslutninger om essensen av problemet må tas steg for steg. Tenk for eksempel på et enkelt eksempel på problemet med å bytte ut og reparere utstyr. La oss si at støpemaskinen til et dekkstøperi produserer dekk i to forskjellige former samtidig. Hvis en av formene svikter, må maskinen demonteres. Det er klart at noen ganger er det mer lønnsomt å erstatte den andre formen for ikke å demontere maskinen i tilfelle denne formen også viser seg å være ute av drift i neste trinn. Dessuten kan det være lettere å erstatte begge arbeidsformene før de begynner å svikte. Den dynamiske programmeringsmetoden bestemmer den beste strategien for å erstatte slike støpeformer, og tar alle faktorer i betraktning: fordelene ved å fortsette å betjene støpeformene, tap fra maskinstans, kostnadene for avviste dekk og mer.

Dynamisk programmering er en optimaliseringsmetode der beslutningsprosessen kan brytes ned i trinn. Hvert trinn flytter kontrollobjektet fra tilstand til tilstand gjennom kontroll. Hvis det totale antallet trinn er , så kan vi snakke om sekvensen av tilstander til systemet som det tar som et resultat av påvirkning av ulike kontroller. Målfunksjonen til systemet avhenger av den opprinnelige tilstanden og kontrollen

Det antas at systemets tilstand ved slutten av det -th trinnet bare avhenger av den forrige tilstanden og kontrollen ved -th trinnet. Da har tilstandsligningen til systemet formen

Hvis vi vurderer den objektive funksjonsadditivet fra effektivitetsindikatoren for hvert trinn, så på trinnet Og objektiv funksjon ser ut som

Løsningen på det dynamiske programmeringsproblemet er å bestemme en slik kontroll , som overfører systemet fra stat til stat med den største (minste) verdien.

For å løse det dynamiske programmeringsproblemet ble det såkalte optimalitetsprinsippet formulert. Dens betydning koker ned til følgende: uansett tilstanden til systemet som et resultat av å utføre et hvilket som helst antall trinn, må kontroll ved nærmeste trinn velges slik at det, sammen med optimal kontroll ved alle påfølgende trinn, fører til maksimal gevinst på alle gjenværende trinn, inkludert.

La oss se på det siste trinnet. Tilstanden til systemet i begynnelsen av trinnet, kontroll, og er den objektive funksjonen. I henhold til optimalitetsprinsippet må kontroll velges slik at det for enhver tilstand oppnås et betinget maksimum av den objektive funksjonen

Løsningen der dette oppnås kalles betinget optimal kontroll på trinnet. Det betingede maksimum for objektivfunksjonen er funnet for alle mulige tilstander i systemet ved siste trinn. Deretter vurderes siste og nest siste trinn sammen. Den objektive funksjonen i dette tilfellet har formen

En betinget optimal kontroll søkes for to siste trinn x for alle mulige tilstander i systemet på nest siste trinn

Tilstanden til systemet under kjent kontroll er definert som , og derfor avhenger målfunksjonen kun av tilstanden ved forrige trinn og gjeldende kontroll. Deretter vurderes tre, fire osv.. siste trinn. I det generelle tilfellet er trinnligningen oppnådd av Belman, som først utviklet den dynamiske programmeringsmetoden.

Som et resultat betinget optimalisering sekvenser av verdier for kriteriefunksjonen og betingede kontroller kan oppnås

Løsningen på et dynamisk programmeringsproblem oppnås ved å erstatte en spesifikk verdi i uttrykket for løsningen i det første trinnet og . Deretter bestemmes tilstanden til det første trinnet

og så videre for alle trinn. Den optimale løsningen på problemet oppnås ved å sekvensielt beregne optimale løsninger og nye tilstander .

Ved den praktiske implementeringen av den dynamiske programmeringsmetoden på en datamaskin oppstår det en rekke vanskeligheter, spesielt knyttet til metoder for å beskrive tilstanden til kontrollobjektet. Som regel vurderes et begrenset antall tilstander til kontrollobjektet ved hvert trinn. Den største interessen er imidlertid i tilfelle å finne den optimale tilstanden til et objekt fra uendelig antall mulige tilstander, for eksempel ved metoden matematisk programmering. Det er ingen slike materialer i tilgjengelig litteratur; i tillegg er det ingen informasjon om programvareimplementeringen av den dynamiske programmeringsmetoden, selv om behovet for å løse slike problemer er ganske stort. Av ovenstående følger det at å bringe dynamiske programmeringsmetoder til praktisk bruk representerer et aktuell og viktig forskningsproblem.

Blant problemene som er løst ved hjelp av matematisk programmering, kan vi trekke frem egen klasse oppgaver som krever optimalisering av flertrinns (flertrinns) prosesser. Slike problemer kjennetegnes ved muligheten for å dele løsningen i flere sammenkoblede stadier. For å løse slike problemer brukes dynamisk programmering eller, som det også kalles, flertrinnsprogrammering. Metodene er optimalisert for å finne den optimale løsningen på flertrinnsproblemer som kan deles inn i flere stadier, trinn osv.

Opprinnelsen til begrepet

Bruken av ordet "dynamisk" i navnet antydet opprinnelig at inndelingen i deloppgaver først og fremst ville skje i tid. Når du bruker dynamiske metoder for å løse produksjons-, økonomiske og andre problemer der tidsfaktoren dukker opp, er det ikke vanskelig å bryte den ned i separate stadier. Men det er også mulig å bruke dynamiske programmeringsteknikker i oppgaver der enkeltstadier ikke henger sammen i tid. I et flertrinnsproblem kan du alltid velge en parameter eller egenskap som kan brukes til å dele den inn i separate trinn.

Algoritme (metode) for å løse flertrinnsproblemer

Algoritmen eller metoden for dynamisk programmering er basert på prinsippet om sekvensiell optimalisering av problemet, når løsningen felles oppgave er delt inn i en rekke løsninger på individuelle deloppgaver og deretter kombinert til en enkelt løsning. Svært ofte viser individuelle deloppgaver seg å være de samme, og en felles vedtak reduserer beregningstiden betydelig.

Et trekk ved metoden er autonomien til å løse problemet på hvert enkelt trinn, dvs. uavhengig av hvordan prosessen ble optimalisert og løst på forrige trinn, i gjeldende beregning kun prosessparametrene som kjennetegner den i dette øyeblikket. For eksempel tar en sjåfør som beveger seg langs veien en beslutning om gjeldende sving uavhengig av hvordan og hvor lenge han kjørte før.

Metode ovenfra og metode nedenfra

Til tross for det faktum at når man beregner på et eget trinn for å løse et problem, brukes prosessparametrene i det nåværende øyeblikket, påvirker resultatet av optimalisering på forrige trinn beregningene av påfølgende stadier for å oppnå det beste resultatet som helhet. Dynamisk programmering kaller dette løsningsprinsippet for optimalitetsmetoden, som bestemmer at den optimale strategien for å løse et problem, uavhengig av de innledende beslutningene og betingelsene, må følges av påfølgende beslutninger i alle ledd for å lage en optimal strategi mht. original tilstand. Som vi kan se, er prosessen med å løse et problem en kontinuerlig optimalisering av resultatet på hvert enkelt trinn fra første til siste. Denne metoden kalles ovenfra-ned programmeringsmetoden. Figuren viser skjematisk top-down løsningsalgoritmen. Men det er en klasse med flertrinnsproblemer der maksimal effekt er på siste etappe er allerede kjent, for eksempel har vi allerede kommet fra punkt A til punkt B og nå ønsker vi å finne ut om vi kjørte riktig på hver forrige etappe eller om noe kunne vært gjort mer optimalt. En rekursiv sekvens av stadier oppstår, det vil si at vi går så å si «fra motsatt retning». Denne løsningsmetoden kalles "bottom-up-programmeringsmetoden."

Praktisk bruk

Dynamisk programmering kan brukes i ethvert aktivitetsfelt der det er prosesser som kan deles inn i en rekke identiske små stadier i henhold til en eller annen parameter (tid, mengde, temperatur osv.). Dynamiske løsningsmetoder er mest brukt i kontrollteori og i utvikling av datasystemer.

Å finne den optimale veien

Ved å bruke dynamisk optimalisering er det mulig å løse en lang rekke problemer med å finne eller optimalisere den korteste veien og andre problemer der den "klassiske" brute-force-metoden mulige alternativer løsninger fører til økt beregningstid, og noen ganger er det helt uakseptabelt. Klassisk problem Dynamisk programmering er et problem med en ryggsekk: et visst antall objekter med en viss masse og kostnad er gitt, og det er nødvendig å velge et sett med objekter med maksimal kostnad og masse som ikke overstiger volumet til ryggsekken. Et klassisk søk av alle alternativer på jakt etter den optimale løsningen vil ta mye tid, men ved hjelp av dynamiske metoder løses problemet i en akseptabel tidsramme. Oppgavene med å finne korteste vei for transportlogistikk er grunnleggende, og dynamiske metoder løsninger er optimalt egnet for å løse dem. Mest enkelt eksempel En slik oppgave er å bygge den korteste ruten ved hjelp av en bil GPS-navigator.

Produksjon

Dynamisk programmering er mye brukt for å løse ulike produksjonsoppgaver, for eksempel lagerstyring for å opprettholde det nødvendige antallet komponenter til enhver tid, planlegging produksjonsprosess, nåværende og større renovering utstyr, ensartet arbeidsmengde av personell, den mest effektive fordelingen av investeringsmidler osv. For å løse produksjonsproblemer ved hjelp av dynamiske programmeringsmetoder, spesielle programvarepakker, integrert i populære systemer bedriftsstyringssystemer som SAP.

Vitenskapelig felt

Dynamiske programmeringsmetoder er mye brukt i ulike Vitenskapelig forskning. For eksempel brukes de med hell i tale- og bildegjenkjenningsalgoritmer, ved behandling av store datamengder i sosiologi og

4.1. Optimalitetsprinsipp

Vurder systemet

og funksjonalitet

(4.2)

som må minimeres. Høyre ende av fasekoordinatene er fri.

Sammen med dette variasjonsproblemet vurderer vi et hjelpeproblem, når prosessen vurderes i intervallet
og funksjonalitet er minimert

. (4.3)

La minimum bli funnet først (4.2) og den tilsvarende optimale kontrollen (fig. 14a):

og deretter - minimum (4.3) og optimal kontroll (fig. 14b):

I sistnevnte tilfelle er det antatt at pt prosessen starter fra staten
, oppnådd innen tidens øyeblikk ved optimalisering av prosessen i intervallet
.

Generelt sett, ledelse
Og
varierer i intervall og verdier. Optimalitetsprinsippet sier at optimal kontrollerer
Og
i den generelle delen av intervallet
sammenfaller, uavhengig av bakgrunnen for prosessen og er helt bestemt av staten
i øyeblikket
.

I tilfellet med fri høyre ende er optimalitetsprinsippet bevist. Faktisk, la oss anta det på nettstedet
ledelse
Og
samsvarer ikke og

(4.6)

Ris. 14 EN Fig.14 b

Så for det første problemet introduserer vi kontrollen

(4.7)

og beregne funksjonelle

Ved kjøring (4.7) funksjonell (4.2) tar en mindre verdi enn med (4.4). Men kontroll er optimal. Derfor er antakelse (4.6) feil.

Et Gjett

motsier hva
- ledelse som minimerer
(4.3).

Dermed forblir det det

og hvis det bare er én optimal kontroll, da

Kort fortalt kan prinsippet om optimalitet formuleres som følger: den siste delen av den optimale banen er optimal uavhengig av prosessens historie.

4.2. Grunnleggende ligning for den dynamiske programmeringsmetoden

La oss anvende prinsippet om optimalitet på løsningen av variasjonsproblemet (4.1), (4.2). For å gjøre dette må du først vurdere funksjonaliteten (4.3). La oss betegne dens minste verdi under forbindelser (4.1):

. (4.8)

Hvis
- optimal kontroll, altså

Optimal kontroll
avhenger av starttilstanden
i øyeblikket
. Derfor, er en funksjon av Og :
, og fra kontroll og dens variasjonsfunksjon
er ikke avhengig. Det er helt bestemt av verdiene
.

Intervall
dele inn i to intervaller
Og
og vi skriver uttrykk (4.8) i formen:

I henhold til prinsippet om optimalitet er den siste delen også optimal:

(4.9)

La oss betegne:

, (4.10)

Hvor
- økning av fasekoordinatvektoren over tid
. Den bestemmes i henhold til bevegelsesligningene (4.1). Erstatter
fra (4.10) til likhet (4.9), får vi:

Selv om funksjonen
avhenger kun av fasekoordinater og tid, den kan ikke tas ut av fortegn
. Øk verdi
i løpet av
avhenger av intervallkontroll
. Men
er ikke avhengig av kontroll i intervallet
og det kan være med under skiltet
. La oss introdusere
under minimumstegnet og del med
:

Vurderer

;

vi får den grunnleggende ligningen for den dynamiske programmeringsmetoden:

(4.11)

Dette forholdet består av to utsagn:

Hvis
- kontroll som minimerer uttrykk
, deretter den grunnleggende ligningen for den dynamiske programmeringsmetoden

(4.12)

Her
avhenger av kontroll per definisjon, funksjonen
er ikke avhengig av ham. Imidlertid derivatet avhenger av ledelsen. Dette kan verifiseres dersom det er representert i skjemaet

Og erstatte i henhold til system (4.1):

.(4.13)

Ved å erstatte (4.13) med (4.12) får vi R. Bellmans ligning:

. (4.14)

Dette er en partiell differensialligning mht
, som etter bytte
blir ikke-lineær. I følge definisjonen (4.8) kl
den endelige betingelsen må være oppfylt

Ved et uendelig intervall på
prosessen må være asymptotisk stabil, dvs.
.

I tilfellet når Boltz-funksjonen vurderes

(4.15)

Ligning (4.12) forblir gyldig, funksjonen v i øyeblikket
må tilfredsstille betingelsen

. (4.16)

4.3. To optimale kontrollproblemer

I teorien om optimal kontroll skilles problemer av to typer: programkontroll og syntese. I det første problemet, optimal kontroll konstruert som en funksjon av tid for spesifikke start- og sluttforhold, hvis spesifisert. Avhengighet
betraktet som et program.

I det andre problemet, optimal kontroll er bygget for hvert øyeblikk i tid som en funksjon av fasekoordinatvektoren de. som

. (4.17)

Konstruksjonen av en slik avhengighet er målet for synteseproblemet. Betydningen av den andre oppgaven er at avhengigheten
gir ligningen tilbakemelding eller en optimal regulator som lukker systemet. Den brukes for optimal kontroll av den forbigående prosessen.

Programkontroll og tilbakemeldingskontroll fungerer på teknisk forskjellige måter. Den første kan utføres av en programvareklokkemekanisme, i henhold til en streng lov, som en funksjon av tiden . Denne kontrollen reagerer ikke på noen måte på mulige avvik i objektets tilstander fra den ideelle, ønskede tilstanden. Tilbakemeldingskontroll utføres ved hjelp av en regulator, som, basert på resultatene av måling av den virkelige tilstanden til fasekoordinatene, genererer et signal i henhold til hvilket kontrollelementet avbøyes.

Begge oppgavene henger sammen. Løsningen på den ene kan uttrykkes gjennom den andre. Imidlertid bemerker vi at maksimumsprinsippet vanligvis fører til representasjon av kontroll i form av et program, og den dynamiske programmeringsmetoden - i form av syntese.

Problemet med å syntetisere optimal kontroll av prosesser beskrevet av et lineært system av differensialligninger mens man minimerer integrerte kvadratiske funksjoner har fått betydelig utvikling. Det kalles problemet med analytisk design av optimale kontrollere (ACOR), eller problemet med A.M. Letov.

4.4. Problemet med analytisk design av optimale kontrollere

La oss anta at likningene for den forstyrrede bevegelsen til systemet har formen

(4.18)

Matriser
, dimensjoner
Og
, følgelig har kjente funksjoner som sine elementer
.

Det antas også at tilstanden til systemet (4.18) i hvert øyeblikk av tiden kjent.

Den kvadratiske Boltz-funksjonen betraktes som et optimalitetskriterium

Hvor
- symmetriske ikke-negative bestemte matriser,
- positiv bestemt matrise; *) - transposisjonsindeks.

Det er nødvendig å finne den optimale (minimere funksjonell 4.19) kontroll, som er en funksjon av gjeldende tilstand
.

For å løse dette problemet kan du bruke maksimalprinsippet, men den korteste veien er den dynamiske programmeringsmetoden.

I henhold til denne metoden må du finne funksjonen
, som tilfredsstiller ligningen

. (4.20)

Generelt er dette vanskelig oppgave, for lineære systemer med et kvadratisk optimalitetskriterium funksjonen
kan søkes i form av en annen kvadratisk form.

(4.21)

Hvor
- det er noen, foreløpig ukjent, kvadratisk form som i kraft av (4.16) tilfredsstiller den endelige betingelsen

. (4.22)

Altså for lineære systemer oppgaven handler om å finne funksjonen
. Å differensiere (4.21) tar hensyn til (4.18) får vi

Minimering (4,23) ved
, vi får

(4.24)

Fordi
, så gir kontroll (4.24) faktisk et minimum til uttrykket
.

Ved å erstatte (4.24) med (4.23), får vi

Den kvadratiske formen (4.25) er lik null for enhver
bare i tilfellet når matrisen som danner den er lik null. Dermed får vi ligningen for å bestemme matrisen

(2.26)

med grensebetingelse (4.22).

Ved å integrere ligning (4.26) i motsatt retning får vi
, og dermed de optimale kontrollparametrene (4.24). Det er lett å vise at matrisen
- symmetrisk matrise. For å gjøre dette er det nok å transponere ligning (4.26). Deretter

hvorfra, tatt i betraktning symmetrien til matrisene følger det
.

Merknad 1. I tilfellet når systemet (4.18) er stasjonært (matriser EN Og B– numeriske matriser), matriser - numeriske matriser,
(steady state vurderes). Matrise er også numerisk og tilfredsstiller den algebraiske ligningen

Notat 2. Fra uttrykk (4.24) følger det at for å implementere optimal kontroll kreves fullstendig og nøyaktig informasjon om tilstanden til den kontrollerte prosessen
. I de tilfellene hvor denne informasjonen ikke kan innhentes, brukes statlige estimater innhentet på grunnlag av tilgjengelig ufullstendig informasjon for å implementere optimal kontroll.

4.5. Syntese av lokalt optimal kontroll

Ved utforming av kontrollsystemer er det ofte nødvendig at oppførselen til systemet er optimal i en eller annen forstand til enhver tid.

La oss vurdere en kontinuerlig kontrollert prosess beskrevet av et system av differensialligninger (4.18).

La en funksjonell (funksjon) gis
parametrisk tidsavhengig og definert på et sett med funksjoner
Og
.

Vi må finne ligningen
, minimere
, Hvor - gjeldende øyeblikk i tid. Slik kontroll kalles lokalt optimal.

Som et optimalitetskriterium anser vi det funksjonelle

matrise tilfredsstiller de samme kravene som i punkt 4.4.

Det er lett å vise at den lokalt optimale ligningen
tilfredsstiller nødvendigvis betingelsen

. (4.28)

La oss bruke denne tilstanden.

Deretter, ved å differensiere (4.27) i kraft av (4.18), finner vi et uttrykk for å bestemme den deriverte

fra tilstanden
la oss finne lokalt optimal kontroll

Den funnet kontrollen leverer faktisk derivatet
, fordi

Fra uttrykk (4.30) følger det at lokalt optimal kontroll er fullstendig bestemt av matrisene
, og for å implementere det, kreves det fullstendig informasjon om tilstanden til prosessen
. Gitt ulike matriser av vektfunksjoner
, er det mulig å sikre visse egenskaper ved den kontrollerte prosessen, spesielt egenskapene til stabilitet eller asymptotisk stabilitet.

Vi krever for eksempel at den lokalt optimale kontrollen tilfredsstiller betingelsen

. (4.31)

Deretter, ved å erstatte (4.30) med (4.29), fra (4.31) finner vi

(4.32)

Det følger av betingelse (4.32) at det vil være tilfredsstilt dersom matrisen
vil bli bestemt ut fra tilstanden

La oss nå vurdere kontrollert bevegelse på segmentet
, Hvor - et fast tidspunkt. Det krever vi også i øyeblikket matrisefunksjon
oppfylte den endelige betingelsen

(4.34)

Så fra en sammenligning av formler (4.24), (4.26), (4.22) og (4.30), (4.33), (4.34) følger det at lokalt optimal kontroll (4.30) i henhold til kriterium (4.27) med matrisen
, bestemt fra ligning (4.33) med betingelse (4.34) faller sammen med kontroll (4.24), optimal i henhold til kvadratisk kriteriet (4.19) på intervallet
.

5. Optimal kontroll av stokastiske systemer under forhold med usikkerhet.

5.1. Kjennetegn på tilfeldige signaler

Manualen bruker stokastiske (tilfeldige) prosesser og sekvenser som matematiske modeller for forstyrrelser og målefeil.

Tilfeldig prosess
er en funksjon hvis verdi på et fast tidspunkt Det er tilfeldig verdi, dvs. en tilfeldig prosess kan betraktes som en tilfeldig variabel avhengig av parameteren . I tilfelle når parameteren endres diskret, den tilfeldige prosessen kalles en tilfeldig sekvens.

Gjennom
vi vil betegne realiseringen av den tilfeldige prosessen
.

Det skal bemerkes at mange statistiske kjennetegn ved tilfeldige prosesser og sekvenser sammenfaller.

Som kjent er den mest komplette egenskapen til en tilfeldig prosess - dimensjonsfordelingslov

eller -dimensjonal distribusjonstetthet

Her er symbolet angir sannsynligheten for hendelsen i parentes. Betydning kan være alt fra jeg til
. For en vilkårlig tilfeldig prosess er det umulig å ha slik informasjon. Imidlertid er det en klasse av tilfeldige prosesser (sekvenser), kalt Markov-prosesser, for hvilke de statistiske egenskapene er fullstendig bestemt av en todimensjonal distribusjonslov eller todimensjonal distribusjonstetthet.

Ofte, spesielt i anvendte problemer, brukes startverdier for å statistisk beskrive tilfeldige prosesser.
og sentralt
øyeblikk -te orden. Her er symbolet
driften av gjennomsnittsberegning (matematisk forventning) er indikert. Følgende punkter spiller den viktigste rollen:

Matematisk forventning (gjennomsnittsverdi)

; (5.3)

Varians av en tilfeldig prosess

Andre første øyeblikk

Hvor
- sentrert tilfeldig prosess med null matematisk forventning;

Standardavvik

. (5.6)

Fra definisjonen
,
,
Og
det følger at disse mengdene karakteriserer en tilfeldig prosess kun i en fast del . For å karakterisere sammenhengen mellom to ulike deler av en tilfeldig prosess, brukes en korrelasjonsfunksjon;

. (5.7)

Hvis den matematiske forventningen
tilfeldig prosess er ikke avhengig av tid, og korrelasjonsfunksjonen er en funksjon av ett argument
, da kalles en slik prosess stasjonær i vid forstand.

Hvis distribusjonstettheten har en Gaussisk karakter, kalles en slik prosess Gaussisk

Den Gaussiske prosessen er fullstendig bestemt ved å spesifisere den matematiske forventningen
og korrelasjonsfunksjon
.

Et viktig kjennetegn ved en stasjonær tilfeldig prosess i vid forstand er den spektrale tettheten
- tetthet av spredning (energi) fordeling over frekvenser.

Spektral tetthet
og korrelasjonsfunksjon
forbundet med direkte og invers Fourier-transformasjon:

; (5.8)

. (5.9)

En ren tilfeldig prosess (sekvens) er en prosess der de tilfeldige variablene
er gjensidig uavhengige for eventuelle verdier av argumentene. En slik prosess er fullstendig preget av en endimensjonal fordelingsfunksjon. En rent tilfeldig stasjonær prosess kalles hvit støy hvis korrelasjonsfunksjonen har formen - funksjoner. Spektraltettheten til en slik prosess er konstant ved alle frekvenser. Fordi
, da er det lett å se at variansen hvit støy er uendelig stor. Slike prosesser eksisterer egentlig ikke i naturen. Imidlertid kan ekte støy erstattes av hvit støy i sin effekt på systemet. I tillegg kan en ekte tilfeldig prosess representeres som utgangssignalet til et system (formingsfilter), hvis inngang er hvit støy. Derfor kan problemet med statistisk analyse eller syntese av systemer med reelle egenskaper av tilfeldige påvirkninger reduseres til problemet med statistisk analyse eller syntese når inngangssignalet er hvit støy. Denne opplæringen vil vanligvis bruke hvit støy og rene tilfeldige sekvensmodeller.

Sammen med skalære tilfeldige prosesser, kan vektortilfeldige prosesser også vurderes:

hvor hver komponent
er en tilfeldig prosess. For å karakterisere en tilfeldig vektorprosess, introduseres følgende vektorer og matriser:

Forventet verdi :

; (5.11)

Dispersjonsmatrise
:

(5.12)

med elementer

; (5.13)

Kovariansmatrise
:

(5.14)

med elementer

; (5.15)

Matrise

med elementer

. (5.17)

Her
betyr transponering.

Direkte fra matrisedefinisjonen
det kan sees at variansene til komponentene i den tilfeldige prosessen er plassert på diagonalen.

Matriser
,
Og
har følgende egenskaper:

; (5.18)

for alle Og (5.I9)

For en stasjonær vektor tilfeldig prosess
matrisen av spektrale tettheter introduseres som Fourier-transformasjonen av kovariansmatrisen
, dvs.

. (5.21)

Matrise
har følgende egenskap:

(5.22)

5.2. Matematisk beskrivelse av lineære systemer under tilfeldige forstyrrelser.

Generelt kan ligningen til et kontrollert dynamisk system skrives som:

Hvor - operatør (eller i et spesielt tilfelle funksjon) av systemet, dvs. et sett med regler som starttilstanden transformeres etter
, kontrollhandlinger
, forstyrrende påvirkninger
til systemutgangen
i øyeblikket .

Hvis parameteren endres kontinuerlig, da vil vi kalle et slikt system for kontinuerlig; Hvis endres diskret, da kalles systemet diskret.

Hvis operatøren er ikke avhengig av parametere Og , da kalles et slikt system stasjonært. Operatør kan være lineære eller ikke-lineære, homogene eller inhomogene og kan spesifiseres i ulike former, for eksempel i form av differensial- og integrodifferensialligninger, ved bruk av overføringsfunksjoner og differanseligninger.

I dette lærebok Kun lineære systemer vil bli vurdert.

La oss vurdere systemer beskrevet av differensialligninger.

La oss betegne med

-dimensjonal vektor av systemtilstanden; gjennom
- -dimensjonal vektor av kontrollhandlinger; gjennom
- -dimensjonal vektor av forstyrrelser. Deretter kan bevegelsesligningen til et lineært kontinuerlig dynamisk system skrives i følgende differensialform:

Her
,
,
- henholdsvis dimensjonale matriser. Elementene i disse matrisene er kontinuerlige funksjoner. Hvis matriser
Og er konstante, så kalles det kontrollerte systemet stasjonært. Ligninger (5.24) kalles vanligvis tilstandsligninger, siden de beskriver endringen i tilstandsvariablene til systemet over tid.

For administrasjonsformål er det nødvendig å vite statusen til systemet til enhver tid. Ved hjelp av målere er det imidlertid mulig å få informasjon, som regel, bare om enkelte komponentprosesser eller deres kombinasjoner. I tillegg kan observerte (output) variabler inneholde målefeil. I det følgende vil vi anta at måleligningene har formen:

Hvor
-
-dimensjonalt observert signal;
- dimensjonsmatrise
, som karakteriserer målemetoden;
- målefeil. Hvis
(- identitetsmatrise) og
, så sier de at målingen er fullstendig og nøyaktig.

I noen tilfeller er det praktisk å representere løsningen av systemet (5.24) i integrert form gjennom den grunnleggende matrisen av løsninger
, som tilfredsstiller følgende matriseligning:

(5.26)

I integrert form kan løsningen av systemet (5.24), i samsvar med Cauchy-formelen, representeres i følgende form:

(5.27)

I uttrykk (5.27) tar den første komponenten hensyn til den frie bevegelsen forårsaket av starttilstanden , tar den andre komponenten hensyn til den tvungne bevegelsen forårsaket av kontrollhandlinger over tidsintervallet
, karakteriserer den tredje komponenten den tvungne bevegelsen forårsaket av forstyrrelser
på intervallet
.

Når det gjelder system (5.24), (5.25), gjør vi følgende forutsetninger:

(5.28)

Fra relasjoner (5.28) er det klart at tilfeldige prosesser
Og
er prosesser av typen hvit støy. Matriser
og vektor regnes som kjent. Antas å være kjent i hvert øyeblikk og kontrollpåvirkninger.

En av typene dynamiske systemer er diskrete systemer som kan deles inn i to typer:

a) faktisk diskrete systemer, som digitale datamaskiner, automatiske maskiner forskjellige typer etc.;

b) diskrete systemer som oppnås som et resultat av bruk av kontinuerlige systemer på diskrete tidspunkter, spesielt når de brukes i kontrollsløyfen til datamaskiner. Oppførselen til diskrete systemer beskrives vanligvis av differanseligninger, som er en analog av differensialligninger for kontinuerlige systemer.

R La oss vurdere oppførselen til et kontinuerlig system med diskret kontroll, som kan representeres i form av en stykkevis konstant vektorfunksjon (fig. 15), dvs. kontrollhandlinger kan skrives i følgende form:

for (5,29)

Hvor - en sekvens av øyeblikk i tid, ikke nødvendigvis like avstand fra hverandre.

Hvis vi er interessert i tilstanden til systemet bare på diskrete tidspunkter , så kan det kontinuerlige systemet (5.24) i disse øyeblikkene, ved å bruke relasjon (5.27), skrives i følgende form:

(5.30)

Med hensyn til (5.29), omskriver vi relasjonen (5.30) som:

(5.31)

Det tredje leddet i relasjon (5.3I) kan betraktes som en tilfeldig rekkefølge. I tilfellet der den tilfeldige prosessen er av typen hvit støy, er følgende relasjon gyldig:

Hvor
- rent tilfeldig rekkefølge.

Introduserer betegnelser

(5.32)

vi skriver ligningssystemet (5.31) på formen:

Matrisene kalles henholdsvis tilstands-, kontroll- og forstyrrelsesovergangsmatriser;
- diskret tid.

Måleligningen kan følgelig skrives som:

Noen ganger er system (5.33) - (5.34) skrevet i følgende form:

Når det gjelder systemer (5.33), (5.34), vil vi anta at:

(5.37)

Eksempel. La oss vurdere rotasjonsbevegelsen til et legeme rundt en av aksene under påvirkning av et forstyrrende øyeblikk
. Bevegelsesligningene er:

, (5.38)

Hvor - kroppens treghetsmoment; - rotasjonsvinkel av kroppen i et eller annet treghetskoordinatsystem. Introduserer nye variabler

(5.39)

vi får bevegelseslikningene til objektet i normal form:

(5.40)

For dette ligningssystemet den grunnleggende matrisen
består av to kolonnevektorløsninger til følgende ligningssystem

med startbetingelser

Det følger at matrisen
har formen:

(5.41)

Det samme resultatet oppnås hvis vi ser etter matrisen
i form av en serie:

La oss vurdere oppførselen til systemet (5.40) med jevne tidsintervaller i øyeblikk , dvs.
.

Basert på relasjoner (5.3I) - (5.33), forutsatt at
konstant på det diskrete trinnet, får vi følgende ekvivalente diskrete system:

(5.43)

(5.44)

I fremtiden må du få en avhengighet
ikke bare fra Og
, men fra og alle tidligere
. Ved å bruke relasjoner (5.33), for div kan skrives:

Ved å fortsette de tilsvarende beregningene kan vi få relasjonen

, (5.45)

hvor er matrisen
er definert som følger:

og
på
.

De resulterende relasjonene (5.45), (5.46) vil bli brukt i statistisk analyse av diskrete systemer.

5.3. Momentligninger for lineære systemer

La oss først vurdere kontinuerlige systemer. La bevegelseslikningene ha formen;

. (5.47)

Angående forstyrrende påvirkninger
og starttilstand vi vil anta at de tilfredsstiller vilkår (5.28).

Når man oppnår relasjoner for den matematiske forventningen til systemets tilstand
La oss gjennomsnittlig ligning (5,47):

Med hensyn til (5.28), får vi:

. (5.48)

Basert på (5.47), (5.48), ligningen for den sentrerte komponenten
har formen:

. (5.49)

La oss nå finne ligningen for dispersjonsmatrisen. Å skille ved matrise
og gitt at matrisene
Og
ikke tilfeldig, vi får:

(5.50)

For å beregne den matematiske forventningen
vi bruker Cauchy-formelen (5.27):

. (5.51)

Multiplisere uttrykk (5.51) til høyre med
, gjennomsnittlig tatt i betraktning (5.28), får vi:

(5.52)

Vurderer

, (5.53)

ligning (5.50) vil ha formen;

med starttilstand
.

La nå oppførselen til systemet beskrives ved den diskrete ligningen

Vi vil anta at den opprinnelige tilstanden og forstyrrende påvirkninger
tilfredsstille relasjoner (5.37). La oss finne ligningene for den matematiske forventningen og spredningsmatrisen.

Gjennomsnittlig (5,55) og tar i betraktning (5,37), får vi:

Ligning for den sentrerte komponenten
har formen:

Ved å bruke (5.57) og (5.37) finner vi ligningen for dispersjonsmatrisen
:

(5.58)

La oss definere den matematiske forventningen
, ved å bruke relasjon (5.45) og egenskaper (5.37):

(5.59)

like måte

Dermed er ligningen for å bestemme matrisen
har formen:

5.4. Det optimale filtreringsproblemet og dets løsning ved Kalman-metoden

Som vist tidligere, for optimal tilbakemeldingskontroll er det nødvendig å ha full informasjon om tilstanden til systemet. Imidlertid kan bare noen tilstandsfunksjoner eller kombinasjoner av dem måles. I tillegg inneholder det observerte signalet målefeil. I en slik situasjon er den viktige oppgaven å skaffe beste estimat tilstanden til systemet basert på måleresultater – problemet med optimal filtrering.

La oss anta at den dynamiske prosessen er beskrevet av et sett med differensialligninger

Hvor
--dimensjonal tilstandsvektor,
--dimensjonal vektor av forstyrrende påvirkninger,
Og
matriser med tilsvarende dimensjoner.

La det være målbart
-dimensjonal vektor av noen kombinasjoner av tilstandsfunksjoner (5.25)

Hvor
- målefeil.

Angående egenskapene til tilfeldige prosesser
og starttilstand
vil anta at de tilfredsstiller vilkår (5.28), dvs. vil anta at dette er tilfeldige prosesser som hvit støy, ukorrelert med hverandre og den initiale tilstanden til systemet.

Matematisk er problemet med optimal filtrering stilt som problemet med å finne et estimat
systemtilstand (5.61)
basert på tilgjengelig informasjon
.

Kalman foreslo å se etter filterligningen i form av et lineært system til inngangen som det observerte signalet tilføres
. Deretter kan bevegelseslikningene til et slikt system beskrives med et sett med ligninger

(5.63)

hvor er matrisene
Og
underlagt fastsettelse, dvs. filterstrukturen er spesifisert, og strukturparametrene og starttilstanden bestemmes ut fra tilleggsbetingelser.

Fordi
, så vil det alltid være en estimeringsfeil

Deretter for å bestemme de nødvendige matrisene
Og
du kan bruke betingelsen om objektiv estimering

(5.64)

og betingelsen for dens optimalitet

Hvor
er en symmetrisk positiv bestemt matrise.

For å bruke betingelsene (5.64) og (5.65), finner vi en ligning for estimeringsfeilen. Ved å trekke fra (5.63) fra (5.61) tar vi hensyn til (5.62), får vi

Hvis vi nå sier det

da er ligningen for estimeringsfeilen
vil ta formen:

med starttilstand

. (5.68)

Fra (5.67), (5.68) følger det at betingelsen for det objektive estimatet (5.64) vil være oppfylt hvis vi setter

. (5.69)

For å bekrefte dette er det nok å ta den matematiske forventningen fra uttrykk (5.67), (5.68)

de. ble homogen lineær ligning med null startbetingelser, som det umiddelbart følger av
for alle .

Det gjenstår å definere matrisen
fra betingelsen om minimumskriteriet (5,65). La oss for enkelhets skyld anta at
er en konstant identitetsmatrise, altså

Her
- korrelasjonsmatrise for estimeringsfeilen (matrise av de andre sentrale øyeblikkene av estimeringsfeil for komponentene i systemtilstandsvektoren). La oss betegne det med
, da er optimalitetskriteriet summen av de diagonale elementene i denne matrisen. I samsvar med den lokale optimalitetstilstanden vil vi se etter den optimale verdien av matrisen
fra betingelsen om minimumsderivat Til tidskriterier:

. (5.71)

Det er lett å vise at å minimere den deriverte av kriteriet gir et minimum for selve kriteriet

La oss skrive ned uttrykket
, utelate tid for enkelhet :

. (5.72)

Bytter inn i (5.72) uttrykket for fra (5.67) og det tilsvarende uttrykket for , vi får:

(5.73)

Vi finner
, som vi skriver Cauchy-ligningen for (5.67):

Hvor
- vektmatrisefunksjon. Deretter

Vi bruker egenskapen til deltafunksjonen:

Hvis har et gap på punktet
.

Fordi det

. (5.74)

På samme måte kan du finne
:

. (5.75)

Erstatter de resulterende uttrykkene for
og tilsvarende transponerte uttrykk for
i (5.73) får vi:

Følgende identitet kan enkelt verifiseres ved å åpne brakettene på høyre side og bruke symmetrien til matrisen
:

Med hensyn til identiteten reduserer vi ligningen (5.76) til formen:

På høyre side (5,78) av koeffisienten
Bare siste ledd vil avhenge, og det er en positiv bestemt matrise. Åpenbart, for å minimere kriteriet (5.71) må man velge
i følgende form:

I dette tilfellet blir siste ledd i ligning (5.78) null og ligningen har formen

med startverdi
.

Så vi kan skrive filterligningen

Ligninger (5,79), (5,80), (5,81) er Kalman-Bucy filterligningene.

Evalueringssystemet (filteret) er skjematisk presentert i fig. 16.

Det skal bemerkes at filterligningen og dens parametere ikke avhenger av matrisen
, men sistnevnte må være positivt bestemt.

For et stasjonært system med en stasjonær forstyrrelse og stasjonær målerstøy, etter slutten av transiente prosesser, blir matriseforsterkningen i Kalman-filteret konstant
, og Riccati-ligningen (5.80) degenererer til en algebraisk. I dette tilfellet er prosessen
og med Derfor prosessen
er stasjonære, så
.

La oss skrive ligningene til det stasjonære Kalman-filteret i følgende form:

; (5.83)

En av de ofte brukte metodene for å løse ligning (5.84) (vanligvis ved hjelp av en digital datamaskin) er å løse den ikke-stasjonære ligningen (5.80) med de tilsvarende konstante verdiene av koeffisientene som matrisene A, C, Q, R er sammensatt, og en vilkårlig ikke-negativ bestemt matrise av startbetingelser for i gjeldende tid til den resulterende løsningen når en konstant steady-state verdi. Denne endelige verdien tas som ønsket løsning på ligning (5.84). Denne løsningsmetoden er praktisk fordi algoritmer for å løse differensialligninger som regel er mer effektive enn algoritmer for å løse ikke-lineære algebraiske ligninger.

Merknad 1.

En viktig egenskap ved den resulterende feilen er at den er ukorrelert med estimeringsfeilen, dvs.

Notat 2.

La nå måleligningen ha formen (5.62), og det er ingen målefeil. I dette tilfellet, for å få et estimat
du må bruke den deriverte
observert signal

som kan representeres som (5.62)

Merknad 3.

For kontrollerbare systemer beskrevet av et sett med ligninger

Filterligningen kan utledes på samme måte. I dette tilfellet vil filterligningen ha formen

hvor er matrisen
, og korrelasjonsmatrisen
, som før, er funnet fra matriseligningen

med starttilstand
.

MED Evalueringssystemet (filteret) er skjematisk presentert i fig. 17.

5.5. Syntese av lokalt optimal kontroll av lineære stokastiske systemer med fullstendig og nøyaktig informasjon.

La kontrollert bevegelse under forstyrrelsesforhold beskrives ved hjelp av et ligningssystem

Tilfeldig prosess
og starttilstand vi vil anta at de er uavhengige og har egenskaper (5.28). Det forutsettes at tilstanden
når som helst kjent. La oss se etter kontroll
som noen lineær funksjon nåværende situasjon

. (5.88)

Da er problemet med å bestemme lokalt optimal kontroll redusert til å finne
-matriser
. Optimal matrise
Vi vil søke blant matriser hvis elementer er kontinuerlige funksjoner med verdier fra det åpne domenet.

Som en funksjonell karakteriserende kontrollert bevegelse tar vi den matematiske forventningen til den lokale funksjonelle
(4.27)

La oss introdusere matrisen av korrelasjonsmomenter

. (5.89)

Ved å bruke (5.88), (5.89) funksjonelle kan vi
konvertere til visning

(5.90)

Dermed blir verdien av kvalitetskriteriet på det aktuelle tidspunktet bestemt av matrisen av korrelasjonsmomenter.

La oss finne en ligning for å bestemme den. Ligningen for den kontrollerte prosessen (5.87) som tar hensyn til (5.88) kan representeres i skjemaet

hvor er matrisen

I samsvar med (5.54), ligningen for matrisen
vil se ut

eller, tatt i betraktning (5.91),

(5.92)

Starttilstanden er åpenbart

Fra (5.92), (5.93) tar hensyn til antakelsen om at matrisene er symmetriske ,
Det følger umiddelbart at matrisen
er symmetrisk, dvs.
.

Dermed har problemet med å bestemme optimal kontroll blitt redusert til problemet med å bestemme matrisen
fra minimumsbetingelsen
(5,90). For å finne den bruker vi betingelse (4.28). Å differensiere (5,90) og ta (5,92) i betraktning, får vi

La oss skrive ut komponentene
, avhengig av
:

La oss betegne med
den ønskede lokalt optimale matrisen. La oss introdusere en familie av matrisesammenligningsfunksjoner

Hvor
- vilkårlig liten variasjon av matrisefunksjonen
fra den aktuelle klassen.

Øke
, forårsaket av matrisevariasjon
, vil se ut

Så fra (5.94) følger det at

På grunn av vilkårlighet
og forutsatt at matrisen
ikke spesielt, på grunn av forhold
får vi en ligning for å bestemme den optimale matrisen

Fant verdi
leverer virkelig minimum
, siden den andre varianten

på grunn av matrisens visse positivitet
. Her.

Sammenligner (5,88), (5,95) med (4,30), ser vi at den funnet lokalt optimale kontrollen er fullstendig sammenfallende med den lokalt optimale kontrollen for det deterministiske tilfellet.

Dermed viser den syntetiserte lokalt optimale kontrollen for et deterministisk system med fullstendig og nøyaktig informasjon om dets tilstand å være lokalt optimal for et stokastisk system eksitert av en tilfeldig forstyrrelse som hvit støy

Et lignende resultat oppstår med det kvadratiske kvalitetskriteriet (4.19).

Dette forklares med at når
oppførselen til et stokastisk system avhenger av forstyrrelsen
, hvis verdi ikke er mulig å forutsi, og derfor er det tilrådelig å la kontrollen være den samme som i det deterministiske tilfellet i fravær av disse forstyrrelsene.

5.6. Syntese av lokalt optimal kontroll av lineære stokastiske systemer (separasjonsteorem).

La den kontrollerte bevegelsen beskrives ved ligning (5.87), og måleligningen – (5.62).

La oss vurdere synteseproblemet som er optimalt i henhold til kriteriet

I dette tilfellet vil vi se etter en kontroll hvis verdi på tidspunktet bestemt av verdiene til vektorfunksjonen
på segmentet
.

La oss betegne med
optimal vurdering av tilstanden til det kontrollerte systemet, gjennom
- estimeringsfeil.

Sammen med system (5.87) vurderer vi det tilsvarende ukontrollerbare systemet

med måleligning

For hjelpesystemet er filtreringsproblemet løst og estimatet
tilfredsstiller ligningen

(5.98)

med starttilstand

hvor er matrisen
bestemt fra ligninger (5,79), (5,80).

Fra ligningene (5.87) og (5.97) følger det at

, (5.99)

Hvor
- grunnleggende matrise av løsninger av systemer (5.87).

Vi ser etter kontroll som er bestemt i tidens øyeblikk verdier av vektorfunksjonen
på segmentet
. Deretter for hver implementering
prosess
kontroll
får en bestemt betydning, dvs. kontroll er en deterministisk operator på en vektor av observasjoner. Derfor

(5.100)

Fra (5.99) og (5.100) følger det at

La oss nå finne ligningen for å bestemme
. For å gjøre dette, differensiering (5.100), får vi

Tar vi (5,98) i betraktning, finner vi

(5.101)

Da vil filterligningen til slutt bli skrevet på formen (5.85)

med starttilstand

, (5.103)

de. et filter for å bestemme en vurdering av kontrolltilstanden til et system er en dynamisk kobling, hvis inngang mottar det målte signalet og kontroll
.

Separasjonsteorem. Lokalt optimal kontroll av systemet (5.87) i henhold til kriteriet (5.96) har formen:

Her
er de gitte matrisene til den lokale funksjonelle, og
- løsning av vektorligningen (5.102) med startbetingelsen (5.103).

Bevis. La oss vurdere det funksjonelle (5.96). Tatt i betraktning at estimatene
og estimeringsfeil
ikke korrelert for alle , funksjonell (5.96) kan representeres som

Siden
påvirker heller ikke
, ingen
, så reduseres problemet til å minimere under forhold (5.102), (5.103). I dette tilfellet er vurderingen fullstendig observerbar.

Tenk på uttrykket

Gitt det er det ikke vanskelig å vise det

Således, i ligning (5.102), uttrykket
kan betraktes som ekvivalent "hvit støy" med en korrelasjonsmatrise
.

Som et resultat kom vi til problemet med å syntetisere en lokalt optimal ligning i systemet (5.102), (5.103), forstyrret av "hvit støy" med en fullstendig og nøyaktig måling av tilstanden, hvis løsning ble gitt i forrige avsnitt. Teoremet er bevist. Det kan vises at separasjonsteoremet også er gyldig når man syntetiserer optimal kontroll ved bruk av en kvadratisk løsning.

4 millioner rubler ble bevilget til utvikling av tre handelsbedrifter. Effektiviteten av kapitalinvesteringer i hvert foretak spesifisert av verdien er kjent ikke-lineær funksjon? k(xk). Nødvendig for å komponere optimal plan fordeling av kapitalinvesteringer mellom foretak. Det forutsettes at fordelingen Penger utført i heltall x k, x k = 0, 1, 2, 3, 4.

Innledende data.

Ved hjelp av den dynamiske programmeringsmetoden løser vi problemet ved hjelp av kontantdistribusjonstjenesten.

Trinn I. Betinget optimalisering.

1. trinn. k = 3.

2. trinn. k = 2.

3. trinn. k = 1.

La oss forklare konstruksjonen av tabellene og rekkefølgen av beregninger.

Kolonne 1, 2 og 3 er de samme for alle tre bordene, så de kan deles. Kolonne 4 er fylt ut basert på de første dataene om inntektsfunksjonene, verdiene i kolonne 5 er hentet fra kolonne 7 i forrige tabell, kolonne 6 er fylt ut med summen av verdiene i kolonne 4 og 5 (kolonne 5 og 6 mangler i tabellen for 3. trinn).

Kolonne 7 poster maksimal verdi forrige kolonne for en fast starttilstand, og i kolonne 8 registreres kontrollen fra kolonne 2, hvorved maksimalt 7 oppnås.

Trinn II. Ubetinget optimalisering.

Fra tabellen for 3. trinn har vi F* 3 (e 0 = 4) = 7,6. Det er maksimal inntekt av hele systemet med mengden midler e 0 = 4 er lik 7,6 millioner rubler.

Fra samme tabell finner vi at det første handelsforetaket skal tildeles u* 1 (e 0 = 4) = 1

Fra tabellen for 2. trinn har vi F* 2 (e 1 = 3) = 4,5. Det vil si at den maksimale inntekten til hele systemet med mengden midler e 1 = 3 er lik 4,5 millioner rubler.

Fra samme tabell finner vi at det andre handelsforetaket skal tildeles u* 2 (e 1 = 3) = 2

De resterende midlene vil være:

Den siste handelsbedriften får 1 million rubler.

Dermed, ved å bruke den dynamiske programmeringsmetoden, fant vi at kapitalinvesteringer i mengden 4 millioner rubler. skal fordeles som følger:

tildele 1 til det første handelsforetaket;

tildele 2 til det andre handelsforetaket;

tildele 1 til det tredje handelsforetaket;

Som vil gi maksimal inntekt lik 7,6 millioner rubler.