Mnoge operacije koje je potrebno analizirati pri izboru optimalnog rješenja razvijaju se kao slučajni procesi koji zavise od niza slučajnih faktora.

Za matematički opis mnogih operacija koje se razvijaju u obliku slučajnog procesa, mogu se uspješno primijeniti matematički aparat, razvijen u teoriji vjerovatnoće za takozvane Markovljeve slučajne procese.

Objasnimo koncept Markovljevog slučajnog procesa.

Neka postoji neki sistem S,čije se stanje mijenja tokom vremena (pod sistemom S sve se može razumjeti: industrijsko preduzeće, tehnički uređaj, radionica za popravke itd.). Ako stanje sistema S promjene u vremenu na nasumičan, nepredvidiv način, kažu to u sistemu S curenja slučajni proces.

Primjeri nasumičnih procesa:

fluktuacije cijena na berzi;

služba za korisnike u frizerskom salonu ili radionici za popravke;

ispunjenje plana snabdevanja grupe preduzeća itd.

Specifičan tok svakog od ovih procesa zavisi od niza slučajnih, nepredvidivih faktora, kao što su:

primanje na berzi nepredvidivih vijesti o političkim promjenama;

nasumična priroda toka aplikacija (zahtjeva) koje dolaze od kupaca;

povremeni prekidi u ispunjavanju plana snabdijevanja i sl.

DEFINICIJA. Nasumični proces u sistemu se zove Markovian(ili proces bez posledica) ako ima sljedeće svojstvo: za svaki trenutak vremena t 0 vjerovatnoća bilo kojeg stanja sistema u budućnosti (at t > t0) zavisi samo od njegovog stanja u sadašnjosti (s t = t0) i ne zavisi od toga kada i kako je sistem došao u ovo stanje (tj. kako se proces razvijao u prošlosti).

Drugim riječima, u Markovljevom slučajnom procesu, njegov budući razvoj zavisi samo od sadašnjeg stanja i ne zavisi od „predistorije“ procesa.

Razmotrimo primjer. Pustite sistem S predstavlja berzu koja postoji već neko vrijeme. Zanima nas kako će sistem funkcionirati u budućnosti. Jasno je, barem kao prva aproksimacija, da karakteristike budućih performansi (vjerovatnosti pada cijena pojedinih akcija u sedmici) zavise od trenutnog stanja sistema (najviše razni faktori kao što su vladine odluke ili izborni rezultati) i ne zavise od toga kada i kako je sistem dostigao svoje sadašnje stanje (ne zavise od prirode kretanja cena ovih akcija u prošlosti).

U praksi se često susreću slučajni procesi koji se, uz ovaj ili onaj stepen aproksimacije, mogu smatrati markovskim.

Teorija Markovljevih slučajnih procesa ima širok raspon različitih primjena. Uglavnom će nas zanimati primjena teorije Markovljevih slučajnih procesa na konstrukciju matematičkih modela operacija čiji tok i ishod suštinski zavise od slučajnih faktora.

Markovljevi slučajni procesi se dijele na casovi u zavisnosti od toga kako i u kojim trenucima vremena sistem S" može promijeniti svoja stanja.

DEFINICIJA. Nasumični proces se zove proces sa diskretnim stanjima, ako su moguća stanja sistema s x , s 2 , s v... mogu se popisivati ​​(numeriti) jedan za drugim, a sam proces se sastoji u tome da s vremena na vrijeme sistem S skače (trenutačno) iz jednog stanja u drugo.

Na primjer, razvoj projekta S provode zajedno dva odjela, od kojih svako može pogriješiti. Moguća su sljedeća stanja sistema:

5, - oba odjela rade normalno;

s 2 - prvi odjel je napravio grešku, drugi radi dobro;

s 3 - drugi odjel je napravio grešku, prvi radi dobro;

s 4 Oba odjela su pogriješila.

Proces koji se odvija u sistemu je da on nasumično u nekim vremenskim momentima prelazi („skače“) iz stanja u stanje. Sistem ima ukupno četiri moguća stanja. Pred nama je proces sa diskretnim stanjima.

Pored procesa sa diskretnim stanjima, postoje slučajni procesi sa kontinuiranim stanjima: ove procese karakterizira postepeni, glatki prijelaz iz stanja u stanje. Na primjer, proces promjene napona u rasvjetnoj mreži je slučajan proces sa kontinuiranim stanjima.

Razmotrićemo samo slučajne procese sa diskretnim stanjima.

Prilikom analize slučajnih procesa sa diskretnim stanjima, vrlo je zgodno koristiti geometrijsku shemu - tzv. graf stanja. State Graph geometrijski prikazuje moguća stanja sistema i njegove moguće prelaze iz stanja u stanje.

Neka postoji sistem S sa diskretnim stanjima:

Svako stanje će biti predstavljeno pravokutnikom, a mogući prijelazi (“skokovi”) iz stanja u stanje strelicama koje povezuju ove pravokutnike. Primjer grafa stanja prikazan je na sl. 4.1.

Imajte na umu da strelice označavaju samo direktne prelaze iz stanja u stanje; ako sistem može preći iz stanja s2 na 5 3 samo kroz s y tada strelice označavaju samo prelaze s2-> i l, 1 -> 5 3 ali ne s2 -» s y Pogledajmo nekoliko primjera:

1. Sistem S- firma koja može biti u jednom od pet mogućih stanja: s]- radi sa profitom;

s2- izgubio izglede za razvoj i prestao da ostvaruje profit;

5 3 - postao predmet potencijalnog preuzimanja;

s4- je pod eksternom kontrolom;

s5- imovina likvidiranog preduzeća se prodaje na aukciji.

Grafikon stanja firme prikazan je na Sl. 4.2.

Rice. 4.2

• 2. Sistem S- banka sa dvije filijale. Moguća su sljedeća stanja sistema:
• 5, - obje grane rade sa profitom;

s 2 - prvo odeljenje radi bez dobiti, drugo radi sa profitom;

5 3 - drugi odjel radi bez profita, prvi radi sa profitom;

s 4 - obje filijale posluju bez dobiti.

Pretpostavlja se da nema poboljšanja stanja.

Grafikon stanja je prikazan na sl. 4.3. Imajte na umu da grafikon ne prikazuje mogući prijelaz iz stanja s] direktno na s 4 ,što će se ostvariti ako banka odmah poslovaće sa gubitkom. Mogućnost ovakvog događaja se može zanemariti, što potvrđuje i praksa.

Rice. 4.3

3. Sistem S- investiciono društvo koje se sastoji od dva trgovca (odjeljenja): I i II; svaki od njih može u nekom trenutku početi raditi s gubitkom. Ako se to dogodi, rukovodstvo kompanije odmah poduzima mjere za vraćanje profitabilnog rada odjela.

Moguća stanja sistema: s- djelatnost oba odjela je isplativa; s2- prvi odjel je obnovljen, drugi radi s profitom;

s3- prvi odjel radi s profitom, drugi je obnovljen;

s4- oba odjela se obnavljaju.

Grafikon stanja sistema je prikazan na sl. 4.4.

4. U uslovima prethodnog primera, aktivnost svakog trgovca, pre nego što počne da obnavlja profitabilan rad odeljenja, ispituje menadžment kompanije kako bi preduzeo mere za njeno unapređenje.

Radi pogodnosti, numerisaćemo stanja sistema ne sa jednim, već sa dva indeksa; prvi će značiti stanje prvog trgovca (1 - radi sa profitom, 2 - njegovu aktivnost proučava menadžment, 3 - obnavlja profitabilnu aktivnost odjela); drugi - iste države za drugog trgovca. Na primjer, s 23 značiće: aktivnost prvog trgovca se proučava, drugog vraća profitabilan rad.

Moguća stanja sistema S:

s u- djelatnost oba trgovca donosi dobit;

s l2- prvi trgovac radi sa profitom, aktivnost drugog proučava menadžment kompanije;

5 13 - prvi trgovac radi sa profitom, drugi obnavlja profitabilnu aktivnost odjela;

s2l- aktivnost prvog trgovca proučava menadžment, drugog radi sa profitom;

s 22 - aktivnost oba trgovca proučava menadžment;

• 5 23 - rad prvog trgovca se proučava, drugi trgovac obnavlja profitabilnu aktivnost odjela;
• 5 31 - prvi trgovac obnavlja profitabilnu aktivnost odeljenja, drugi radi sa profitom;
• 5 32 - prvi trgovac obnavlja profitabilnu djelatnost odjela, proučava se rad drugog trgovca;
• 5 33 - oba trgovca obnavljaju profitabilan rad svog odjela.

Ukupno ima devet država. Grafikon stanja je prikazan na sl. 4.5.

U ovom dijelu koristimo metodu Markovljevih procesa za pronalaženje optimalnog demodulatora. Naše izlaganje je površno, pa bi se za detaljnije razmatranje, zainteresovani čitaoci trebali obratiti na dodatne izvore (posebno,). I ovaj put ćemo pretpostaviti da je poruka Gausov slučajni proces sa konačnim prikazom u varijablama stanja, tj.

gdje je bijeli Gaussov slučajni proces s kovarijansnom funkcijom

Iako ovu činjenicu ne koristimo u toku izlaganja, treba istaći da se postupak opisan u ovom dijelu može izvesti i kada su jednadžba stanja i jednačina opažanja nelinearne i imaju oblik

Imajte na umu da je pod nekim ograničenjima nametnutim vektorski Markovljev proces, koji nije nužno Gausov. Nijedna od prethodno razmatranih metoda ne dozvoljava rješavanje problema s porukama ove klase. Većina rezultata koji će se dobiti u ovom odeljku može se dobiti i za opštiji proces opisan jednačinama (78) i (79).

Vratimo se sada na model u obliku slučajnog procesa opisanog relacijama Radi jednostavnosti notacije, razmotrit ćemo poruku koja je skalarni Gaussov Markovljev proces i s kojom se prenesena oscilacija modulira nekom vrstom modulacije bez inercije. . Primljena oscilacija se zapisuje kao

Proces komunikacije zadovoljava diferencijalnu jednačinu prvog reda

Dakle, za bilo koju konačnu poruku je stacionaran proces i ima Butterworthov spektar prvog reda. Nadalje, zbog činjenice da je Markovljev proces prvog reda, njegova gustina vjerovatnoće u odsustvu ikakvih opservacija zadovoljava Fokker-Planckovu jednačinu [vidi. (3.79)]

Međutim, budući da je opažena tokom vremenskog intervala, gustina verovatnoće koja nas zanima nije bezuslovna gustina, već gustina usled uočene fluktuacije. Označimo ovu gustinu sa

Imajte na umu da je (86) gustina vjerovatnoće za jedan slučajna varijabla(veličina koja označava vrijednost a u vremenskoj tački zbog uočene fluktuacije, i dobro je definirana karakteristika. Može se pokazati da ova gustina vjerovatnoće zadovoljava jednačinu

pri čemu su matematička očekivanja uzeta iz gustine Ako formalno uvedemo izvod

tada se (87) može formalno zapisati kao diferencijalna jednačina

Odnos između posteriorne gustine i procjene minimalne standardne greške je dobro poznat. Procjena minimalne srednje kvadratne greške je uslovna srednja vrijednost posteriorne gustine (vidi str. 73 prvog toma), tj.

Množenjem oba dijela (89) sa A, integrirajući u odnosu na i uzimajući u obzir odgovarajuće uslove na krajevima intervala, dobijamo (vidi problem 7.2.2)

Imajte na umu da (91) još uvijek sadrži očekivana vrijednost by Kao što se očekivalo, ova jednačina nije riješena za opći slučaj modulacije. Kada linearne metode modulaciju je lako pokazati (na primjer, 18] ili problem 7.2.1) da se ona svodi na Za mnoge probleme nelinearne modulacije, uspjeh se može postići proširenjem na više različitih članova jednačine (91). Zatim, ako pretpostavimo da je greška procene mala i nametnemo neke uslove na momente viših redova, možemo zanemariti članove drugog i viših redova i dobiti sledeću približnu jednačinu (detaljan izvod je dat u poglavlju 4. knjiga):

gdje označava približnu procjenu minimalne srednje kvadratne greške. Funkcija je približni uslov [u srednjem kvadratu greške] koji zadovoljava diferencijalnu jednadžbu

sa graničnim uslovom

Imajte na umu da su jednadžba procjene (92) i jednačina disperzije (93) povezane. Dalje imajte na umu da uslovna srednja kvadratna greška [tj. e. greška pod uslovom da su aproksimacije koje se moraju dozvoliti da budu važeće kada je greška mala.

Vidimo da se jednačina (92) može implementirati u obliku blok dijagrama prikazanog na Sl. 7.3. Ova implementacija je vrlo slična strukturi estimatora maksimalne posteriorne vjerovatnoće sintetizirane u Pogl. 2, s jedinom razlikom što je filter u petlji sada automatski implementiran. Nedostatak ove implementacije je prisutnost komunikacije između petlji.

U slučaju kutne modulacije, može se pokazati da se ova sprega obično može zanemariti. Na primjer, sa faznom modulacijom

Pretpostavlja se da je mnogo veća od najveće frekvencije u spektru poruke i da je sistem u statistički stacionarnom stanju. U ovom slučaju se pokazuje da

zadovoljava disperzijsku jednačinu prilikom zamjene

Za Markovljev proces prvog reda, ova jednačina ima oblik

Blok dijagram prijemnika prikazan je na sl. 7.4. Ova struktura se tačno poklapa sa realističnim delom aproksimativnog prijemnika u smislu maksimalne aposteriorne verovatnoće, koja je ranije sintetizovana (vidi problem u (68) sada se može tumačiti kao približna uslovna srednja kvadratna greška.

Rice. 7.4. Optimalni prijemnik: fazna modulacija, komunikacija spektra Butterworth prvog reda.

Budući da je većina detalja izlaza izostavljena, važno je napomenuti ograničenja rezultata. Diferencijalna jednadžba (91) koja određuje uslovni prosjek je tačna. Međutim, aproksimacije povezane sa dobijanjem (92)-(93) odgovaraju linearizujućoj pretpostavci. Stoga je naš rezultat približna procjena minimalnom srednje kvadratne greške koja odgovara prvom članu proširenja u niz tačne procjene. Da biste dobili bolju aproksimaciju, možete držati više uslovi proširenja (vidi, na primjer, ). Poteškoća s ovim postupkom je u tome što je dvočlana aproksimacija već toliko složena da vjerovatno nije od praktičnog interesa.

Ispod slučajni proces razumjeti promjenu vremena stanja nekog fizičkog sistema na do tada nepoznat slučajan način. Gde pod fizičkim sistemom mislimo bilo koji tehnički uređaj, grupa uređaja, preduzeće, industrija, biološki sistem itd.

slučajni proces teče u sistemu se zove Markovsky – ako za bilo koji trenutak vremena, vjerovatnoća karakteristike procesa u budućnosti (t > ) zavisi samo od njegovog stanja u datom trenutku ( prisutan ) i ne zavise od toga kada i kako je sistem došao u ovo stanje u prošlosti .(Na primjer, Geigerov brojač koji registruje broj kosmičkih čestica).

Markovljevi procesi se obično dijele u 3 tipa:

1. Markov lanac – proces čija su stanja diskretna (tj. mogu se prenumerisati), a diskretno je i vrijeme za koje se smatra (tj. proces može promijeniti svoja stanja samo u određenim vremenskim trenucima). Takav proces ide (mijenja se) u koracima (drugim riječima, u ciklusima).

2. Diskretni Markovljev proces - skup stanja je diskretan (može se nabrojati), a vrijeme je kontinuirano (prijelaz iz jednog stanja u drugo - u bilo kojem trenutku).

3. Kontinuirani Markov proces – skup stanja i vremena su kontinuirani.

U praksi se ne susreću često Markovljevi procesi u njihovom čistom obliku. Međutim, često se mora suočiti s procesima kod kojih se utjecaj praistorije može zanemariti. Osim toga, ako se svi parametri iz „prošlosti“ od kojih zavisi „budućnost“ uključe u stanje sistema u „sadašnjosti“, onda se on može smatrati i markovskim. Međutim, to često dovodi do značajnog povećanja broja varijabli koje se uzimaju u obzir i nemogućnosti dobivanja rješenja problema.

U Operativnom istraživanju veliki značaj zauzimaju tzv Markovljevi stohastički procesi sa diskretnim stanjima i kontinuiranim vremenom.

Proces se zove proces diskretnog stanja, ako se sva njegova moguća stanja , ,... mogu unaprijed nabrojati (prenumerirati). Prelazak sistema iz stanja u stanje prolazi gotovo trenutno - skok.

Proces se zove kontinuirani vremenski proces, ako trenuci prijelaza iz stanja u stanje mogu potrajati bilo koje slučajne vrijednosti na vremenskoj osi.

na primjer : Tehnički uređaj S se sastoji od dva čvora , od kojih svaki u nasumičnom trenutku može propasti ( odbiti). Nakon toga, popravak čvora počinje odmah ( oporavak) koji se nastavlja nasumično vrijeme.

Moguća su sljedeća stanja sistema:

Oba čvora su OK;

Prvi čvor se popravlja, drugi radi.

- drugi čvor se popravlja, prvi radi

Oba čvora se popravljaju.

Prelazak sistema iz stanja u stanje dešava se u nasumično vrijeme gotovo trenutno. Pogodno je prikazati stanja sistema i odnos između njih pomoću graf stanja .

države

Tranzicije

Prijelazi i izostaju jer kvarovi i oporavak elemenata se javljaju nezavisno i nasumično, a vjerovatnoća istovremenog kvara (oporavka) dva elementa je beskonačno mala i može se zanemariti.

Ako svi tokovi događaja prevode sistem S od drzave do drzave protozoa, onda proces, teče u takvom sistemu biće Markovski. To je zbog činjenice da najjednostavniji tok nema naknadno dejstvo, tj. u njemu "budućnost" ne zavisi od "prošlosti" i, osim toga, ima svojstvo običnosti - verovatnoća istovremene pojave dva ili više događaja je beskonačno mala, tj. nemoguće je preći iz stanja stanje bez prolaska nekoliko međustanja.

Radi jasnoće, na grafu stanja je zgodno zapisati intenzitet toka događaja koji prenosi sistem iz stanja u stanje duž date strelice na svakoj prelaznoj strelici ( - intenzitet toka događaja koji prenosi sistem od drzave in. Takav graf se zove markirano.

Koristeći označeni graf stanja sistema, može se konstruisati matematički model ovaj proces.

Razmotrite prelaze sistema iz nekog stanja u prethodno ili sledeće. Fragment grafa stanja u ovom slučaju će izgledati ovako:

Neka sistem u to vrijeme t je u stanju .

Označiti (t)- vjerovatnoća i-tog stanja sistema je vjerovatnoća da sistem u trenutku t je u stanju . Za bilo koji trenutak vremena t =1 je tačno.

Odredimo vjerovatnoću da u tom trenutku t+∆t sistem će biti u stanju. To može biti u sljedećim slučajevima:

1) i nije ga napustio za vrijeme ∆ t. To znači da za vrijeme ∆t nije nastao događaj koji dovodi sistem u stanje (tok sa intenzitetom) ili događaj koji ga dovodi u stanje (tok sa intenzitetom). Odredimo vjerovatnoću toga za mali ∆t.

Prema eksponencijalnom zakonu raspodjele vremena između dva susjedna zahtjeva, koji odgovaraju najjednostavnijem toku događaja, vjerovatnoća da se u vremenskom intervalu ∆t neće pojaviti zahtjevi u toku s intenzitetom λ1će biti jednako

Proširujući funkciju f(t) u Taylorov red (t>0) dobijamo (za t=∆t)

f(∆t)=f(0)+ (0)* ∆t + *∆ + *∆ +…=

= +(-l) *∆t+ (∆ + *(∆ +…” 1-l*∆t za ∆t®0

Slično, za tok intenziteta λ 2 dobijamo .

Vjerovatnoća da na vremenskom intervalu ∆t (za ∆t®0) nijedan zahtjev neće biti jednak

(∆t)/ = (∆t/ * (∆t/ = (1- *∆t)(1- *∆t) =

1 - - *∆t + 1 - ( + )*∆t + b.m.

Dakle, vjerovatnoća da sistem nije napustio stanje tokom vremena ∆t za mali ∆t će biti jednaka

P( / )=1 – ( + )* ∆t

2) Sistem je bio u stanju S i -1 i za vrijeme prešao u stanje S i . To jest, najmanje jedan događaj se dogodio u toku sa intenzitetom. Vjerovatnoća za to je jednaka najjednostavnijem toku s intenzitetom λ će

Za naš slučaj, vjerovatnoća takvog prijelaza bit će jednaka

3)Sistem je bio u stanju i tokom vremena ∆t prešao u stanje . Vjerovatnoća za to će biti

Tada je vjerovatnoća da će sistem u trenutku (t+∆t) biti u stanju S i jednaka

Oduzmite P i (t) od oba dijela, podijelite sa ∆t i, prelazeći do granice, sa ∆t→0, dobijamo

Zamjenom odgovarajućih vrijednosti intenziteta prijelaza iz stanja u stanja, dobijamo sistem diferencijalne jednadžbe opisujući promjenu vjerovatnoća stanja sistema kao funkcije vremena.

Ove jednačine se nazivaju jednadžbe Kolmogorov-Chapman za diskretni Markovljev proces.

upitavši početni uslovi(na primjer, P 0 (t=0)=1,P i (t=0)=0 i≠0) i njihovim rješavanjem dobijamo izraze za vjerovatnoće stanja sistema kao funkciju vremena. Analitička rješenja je prilično lako dobiti ako je broj jednačina ≤ 2.3. Ako ih ima više, tada se jednadžbe obično rješavaju numerički na kompjuteru (na primjer, Runge-Kutta metodom).

U teoriji slučajnih procesa dokazan , šta ako je broj n stanja sistema svakako i od svakog od njih moguće je (u konačnom broju koraka) ići na bilo koji drugi, onda postoji granica , kojem vjerovatnoće teže kada t→ . Takve vjerovatnoće se nazivaju konačne vjerovatnoće stanja, a stabilno stanje - stacionarni način rada funkcionisanje sistema.

Od u stacionarni način rada sve , dakle, sve =0. Izjednačavajući leve delove sistema jednačina sa 0 i dopunjujući ih jednačinom =1, dobijamo sistem linearnih algebarske jednačine, rješavajući koje nalazimo vrijednosti konačnih vjerovatnoća.

Primjer. Neka u našem sistemu stope kvarova i obnavljanja elemenata budu sljedeće

Neuspjesi 1el:

2el:

Repair 1el:

2el:

P 0 + P 1 + P 2 + P 3 \u003d 1

0=-(1+2)P 0 +2P 1 +3 P 2

0=-(2+2)P 1 +1P 0 +3P 3

0=-(1+3)P 2 +2P 0 +2P 3

0=-(2+3)P 3 +2P 1 +1P 2

Odlučivanje ovaj sistem, dobijamo

P 0 =6/15=0,4; P 1 =3/15=0,2; P2=4/15=0,27; P3=2/15≈0,13.

One. u stacionarnom stanju, sistem u prosjeku

40% je u stanju S 0 (oba čvora su zdrava),

20% - u stanju S 1 (1. element je u popravci, 2. je u dobrom stanju),

27% - u stanju S 2 (2. el. u remontu, 1 je u dobrom stanju),

13% - u stanju S 3 - oba elementa su u popravci.

Poznavanje konačnih vjerovatnoća dozvoljava Procijenite prosječne performanse sistema i opterećenje servisa popravke.

Neka sistem u stanju S 0 donosi prihod od 8 jedinica. po jedinici vremena; u državi S 1 - prihod 3 sr.u.; u državi S 2 - prihod 5; u državi S 3 - prihod \u003d 0

Cijena popraviti po jedinici vremena za el-ta 1- 1 (S 1, S 3) arb jedinica, el-ta 2- (S 2, S 3) 2 arb. Zatim u stacionarnom načinu rada:

Sistemski prihod po jedinici vremena će biti:

W max =8P 0 +3P 1 +5P 2 +0P 3 =8 0,4+3 0,2+5 0,27+0 0,13=5,15 c.u.

Trošak popravke u jedinicama vrijeme:

W rem =0P 0 +1P 1 +2P 2 +(1+2)P 3 =0 0,4+1 0,2+2 0,27+3 0,13=1,39 c.u.

Profit po jedinici vremena

W \u003d W doh -W rem \u003d 5,15-1,39 \u003d 3,76 jedinica

Potrošenim određenim troškovima moguće je promijeniti intenzitet λ i μ i, shodno tome, efikasnost sistema. Izvodljivost takvih troškova može se ocijeniti ponovnim izračunavanjem P i . i indikatore performansi sistema.

Neka se s.p. pojavi u nekom sistemu. sa diskretnim stanjima
i diskretno vrijeme, tj. prelazak sistema iz jednog stanja u drugo dešava se samo u određenim vremenskim trenucima
. Ovi trenuci se zovu stepenice proces (obično razlika između susjednih trenutaka promatranja
jednak konstantnom broju - dužina koraka, uzeta kao jedinica vremena);
početak procesa.

Ovaj s.p. može se posmatrati kao niz (lanac) događaja
.

početno stanje sistema, tj. prije 1. koraka;
stanje sistema nakon 1. koraka,
stanje sistema nakon 2. koraka itd.), tj. događaji forme
gdje.

Poziva se Markovljev slučajni proces sa diskretnim stanjima i diskretnim vremenom Markov lanac(Markovljev lanac).

Zapiši to Markov lanac, u kojem uslovne vjerovatnoće stanja u budućnosti zavise samo od stanja u posljednjoj fazi (i ne zavise od prethodnih), naziva se jednostavan Markov lanac. (A.A. Markov 1856-1922 - ruski matematičar).

Primjer takvog sistema može poslužiti kao tehnički uređaj čija su moguća stanja sljedeća:

dobar posao;

preventivni pregled i održavanje;

radovi na popravci;

otpis bezvrijednosti;

Grafikon stanja rada prikazan je na slici

Rice. 1.11 (A.A. Belov, et al.)

Iz analize grafa to se vidi iz stanja normalnog rada vrha sistem može preći u stanje preventivnog održavanja , a zatim se vratite na . Ili se preseliti iz u stanju popravke , nakon čega se ili vraća na , ili prijeći u stanje otpisa. Država je konačan, budući da je prijelaz iz njega nemoguć. Prijelaz iz ponovo unutra znači kašnjenje u ovom stanju.

U praksi često postoje sistemi čija stanja čine lanac u kojem svako stanje (osim ekstremnih i ) povezan je pravom linijom i povratne informacije sa dva susjedna
a ekstremna stanja - sa jednim susjednim (vidi Sl.)

Fig.1.12(Belov...)

Primjer takvog sistema je tehnički uređaj koji se sastoji od istog tipa čvorova. Svako stanje sistema karakteriše broj neispravnih čvorova u vrijeme verifikacije.

Glavni zadatak studije je pronaći vjerovatnoće stanja na bilo koji
m korak. Izračunaćemo verovatnoće stanja diskretnog sistema

Ovdje ćemo razmotriti samo jednostavne Markovljeve lance. Nadalje, također ćemo ukratko razmotriti koncepte kontinuiranih Markovljevih procesa.

Sa diskretnim vremenom promjene stanja sistema, svaki prijelaz iz jednog stanja u drugo se naziva korak.

Iz definicije Markovljevog lanca slijedi da je za njega vjerovatnoća tranzicije sistema u stanju
m korak zavisi samo od stanja u kojem sistem je bio na prethodnom
korak.

gdje
bezuslovna verovatnoća da
m koraku sistem će biti u stanju . Za pronalaženje ovih vjerovatnoća potrebno je poznavati početnu distribuciju vjerovatnoće, tj. vjerovatnoće stanja
u to vrijeme
(početak procesa) i tzv vjerovatnoće tranzicije
Markov lanac uključen
m korak.

vjerovatnoća tranzicije
naziva se uslovna vjerovatnoća prijelaza sistema na

m koraka, u stanju
m korak je mogla , tj.

(43),

gdje prvi indeks ukazuje na broj prethodnog stanja, a drugi indeks na broj sljedećeg stanja sistema.

Markov lanac se zove homogena, ako je vrijednost
one. uslovne vjerovatnoće
ne zavise od broja ispitivanja, inače se nazivaju heterogenim.

Nadalje, razmatrat ćemo samo homogene lance, koji se mogu specificirati pomoću vektora - vjerovatnoća stanja u trenutku
i matrice ( nazvana prelazna matrica)

(44)
.

Matrični elementi
imaju osnovna svojstva običnih kvadratnih matrica i dodatno sljedeća svojstva:

a)
, b)
za svaki fiksni
, tj. zbir elemenata svakog reda prelazne matrice je jednaka jedan (kao verovatnoća prelaznih događaja iz jednog stanja u bilo koje drugo moguće stanje - formiranje kompletne grupe događaja).

Vjerovatnoća stanja sistema u sljedećem koraku određena je rekurzivnom formulom:

Pod određenim uslovima (ergodičnost, homogenost, odsustvo ciklusa) u Markovom lancu, stacionarni način rada, u kojem vjerovatnoće stanja sistema ne zavise od broja koraka. Takve vjerovatnoće se nazivaju marginalni(ili konačne) vjerovatnoće Markovljevog lanca:

.

Postoji tvrdnja.

Teorema 17.1.Za matrice tranzicija vjerovatnoća stepenice
formula je važeća

(45)
,

Dokaz. Po pravilu množenja dvije kvadratne matrice
poredak imamo

gdje

istovremeno, po definiciji prelazne matrice, poznato je da
za bilo koji
.

Zbrojimo obje strane jednakosti
za sve
, i promjenom redoslijeda zbrajanja nakon primjene svojstva a) dvaput, dobijamo to
tranzicijska matrica u dva koraka. Slično, konzistentno razmišljajući korak po korak, dobijamo našu tvrdnju u opštem slučaju.

Primjer 3 Data je prijelazna matrica

.

Pronađite matrice vjerojatnosti prijelaza
.

Na osnovu pravila množenja dvije matrice dobijamo

.

Vježba. Provjerite da li je jednakost tačna

Treba napomenuti da je konačni diskretni Markovljev lanac daljnja generalizacija Bernoullijeve sheme, štoviše, na slučaj zavisnih ispitivanja; nezavisna ispitivanja su poseban slučaj Markovljevog lanca. Ovdje pod "događaj"

odnosi se na stanje sistema, a "test" se odnosi na promjenu stanja sistema.

ako " testovi” (eksperimenti) su nezavisni, onda pojava određenog događaja u bilo kojem eksperimentu ne ovisi o rezultatima prethodno obavljenih testova.

Zadaci. a) Date su prijelazne matrice

1.
;

2.
;

3.
.

Pronađite u svakom slučaju matricu
.

Odgovori: a) 1.
;

2.
;

3.

c) Date su prijelazne matrice

;
.

Naći
.

Odgovori: c) 1.
;2.
;

3.
.

Komentar. Općenito, diskretno Markov lanac
je Markovljev slučajni proces čiji je prostor stanja konačan ili prebrojiv, i skup indeksa
- skup svih nenegativnih cijelih brojeva ili neki njegov podskup (konačan ili prebrojiv). Možemo razgovarati o tome šta je sa ishodom
th test.

Često je zgodno identificirati prostor stanja procesa skupom nenegativnih cijelih brojeva
a u ovim slučajevima se kaže da je u stanju , ako
.

Vjerovatnoća pogađanja slučajne varijable
u stanje (naziva se vjerovatnoća prijelaza u jednom koraku), kao što je gore spomenuto, označava se
, tj.

Ova notacija naglašava da, u opštem slučaju, verovatnoće tranzicije ne zavise samo od početnog i krajnjeg stanja, već i od trenutka tranzicije.

U slučajevima kada vjerovatnoće prijelaza u jednom koraku ne zavise od vremenske varijable (tj. od vrijednosti , tada se kaže da ima Markovljev proces vjerovatnoće stacionarne tranzicije. Dakle, za ono što slijedi napominjemo da postoji jednakost od koje ne zavisi , i označava vjerovatnoću prijelaza u jednom ispitivanju iz stanja u stanje .

Obično vjerovatnoće kombinovano u kvadratnu matricu (konačnu ili prebrojivu) u zavisnosti od procesa koji se razmatra:

,

i naziva se Markovljeva matrica, ili matrica vjerovatnoće tranzicije Markov lanac.

U matrici
i red predstavlja distribuciju vjerovatnoće r.v.
pod uslovom da
. Ako je broj stanja konačan, onda - konačno kvadratna matrica, čiji je redosled (broj redova) jednak broju stanja.

Naravno, vjerovatnoće zadovoljiti sledeća dva uslova:

a)
,

b)
za svaki fiksni

Uslov b) odražava činjenicu da svako ispitivanje uzrokuje neki prijelaz iz jednog stanja u drugo stanje. Radi praktičnosti, takođe se govori o tranzicija iu slučaju kada stanje ostaje nepromijenjeno. Postoji tvrdnja.

Teorema 17.2.Proces je potpuno definisan ako su date vjerovatnoće(46), tj.

i distribuciju vjerovatnoće slučajne varijable .

Dokaz. Pokažimo to za bilo koje konačno kako se izračunavaju vjerovatnoće

budući da se prema formuli ukupne vjerovatnoće sve druge vjerovatnoće vezane za slučajne varijable mogu dobiti sabiranjem pojmova (termina) oblika (47).

Po definiciji uslovne vjerovatnoće, imamo

Ali po definiciji Markovljevog procesa, dobijamo

Stavljajući jednakost (49) u (48) dobijamo

Nastavljajući ovaj proces uzastopno, dobijamo:

Proces je u potpunosti definisan. Šta je trebalo dokazati.

Markovljevi slučajni procesi.

Pretpostavimo da treba da proučavamo neki "fizički sistem" S(čiji proces funkcionisanja se može eksplicitno opisati), koji može da menja svoje stanje tokom vremena (prelasci iz jednog stanja u drugo) na prethodno nepoznat, nasumičan način. Sve se može shvatiti kao „fizički sistem“: tehnički uređaj, grupa takvih uređaja, preduzeće, industrija, živi organizam, populacija itd.

Pretpostavljamo da je sistem koji se proučava S može se opisati nekim skupom mogućih, prethodno poznatih stanja sistema Si, koji se može odrediti na osnovu "fizičke prirode" procesa funkcionisanja sistema koji se proučava, tj. .

- i Stanje sistema zavisi od k parametri.

U stvarnoj situaciji, stanje sistema može zavisiti od uzročno-posledičnih veza između stanja i procesa koji se dešavaju u sistemu. Odnosno, priroda ponašanja sistema je utisnuta „predistorijom“ prirode ponašanja sistema i skupom nekih slučajnih faktora (spoljašnji ili unutrašnji perturbacioni procesi). Suočeni smo sa mnogim „predloženim scenarijima“ procesa funkcionisanja sistema. I sam „izbor“ dominantnog „scenarijuma ponašanja“ (kako će se ponašati sistem koji se proučava) je slučajan.

Treba napomenuti da je tranzicija iz dr S ja da navedem S j je stohastički. Funkcionisanje sistema počinjemo razmatrati od početnog stanja S 0, što odgovara vremenu t 0 . Odnosno, ono što se dogodilo sistemu prije vremena t 0 odnosi se na "njegovu prošlost", na njegovu praistoriju.

definicija: Slučajni proces u sistemu naziva se Markovljev proces ako za bilo koji trenutak vremena t 0 vjerovatnoća karakteristike procesa u budućnosti zavise samo od njegovog trenutnog stanja t 0 i ne zavise od toga kada i kako je sistem došao u ovo stanje.

Pretpostavljamo da je stanje sistema opisano funkcijom S(t), argument ove funkcije je vrijeme t kontinuirano su poznate vremenske tačke prelaska sistema iz jednog stanja u drugo t: t 1 <t 2 < … <t n. Štaviše, prijelaz iz jednog stanja u drugo događa se "skokom", gotovo trenutno.

Došli smo do zaključka da je proces funkcionisanja sistema povezan sa lancem diskretnih stanja: S 1® S 2 ® … ® S n-1® S n (uzastopni prijelaz iz jednog stanja u drugo, bez "skakanja" kroz bilo koje stanje). Odnosno, sistem koji se razmatra je opisan Markovljevim slučajnim procesom sa diskretnim stanjima i kontinuiranim vremenom.

Iz teorije vjerovatnoće znamo da je funkcija gustoće vjerovatnoće za n-to stanje se traži kao zajednička funkcija gustine za čitavu "predistoriju" procesa dolaska sistema u ovo stanje: .

U praksi se Markovljevi procesi ne javljaju u svom čistom obliku, ali se često mora suočiti s procesima kod kojih se utjecaj praistorije može zanemariti. Prilikom proučavanja takvih procesa mogu se koristiti Markovljevi modeli.

Kada se proces posmatra kao markovski, analitički opis modela je pojednostavljen, jer pretpostavljamo da stanje sistema zavisi samo od jednog prethodnog stanja: .

Markovljevi lanci su definirani skupom dobro definiranih stanja: . Prema tome kada i kako nastaju "tranzicije", Markovi lanci se dijele na diskretne, za koje je vrijeme prijelaza iz jednog stanja u drugo fiksno, a određeno je vjerovatnoćom ovog prijelaza, i kontinuirane, za koje su stanja diskretna, vrijeme je kontinuirano i prijelazi iz jednog stanja u drugo se dešavaju nasumično, unaprijed nepoznati, trenutci vremena.

Prilikom analize slučajnih procesa sa diskretnim stanjima, zgodno je koristiti geometrijsku shemu - takozvani graf stanja.

Definicija. Graf je skup mnogih vrhova V i skup uređenih parova vrhova A={(a 1 a i)( a 2 a j) … ), čiji se elementi nazivaju ivicama G(V,A).

Stanja sistema su povezana sa vrhovima grafa, a prelazi iz jednog stanja u drugo povezani su sa užadima koji ukazuju na „smer toka“ procesa.

U sljedećem primjeru ćemo razmotriti tehniku ​​proučavanja Markovljevih lanaca koristeći označeni graf stanja.

Primjer #1. TEA tehnički rad automobila.

Pojednostavljeni TEA model podrazumijeva prisustvo najmanje četiri od sljedećih stanja: S 1 - dijagnostika stanja automobila, S 2 - rad na liniji (auto je u dobrom stanju), S 3 - održavanje, S 4 - otklanjanje kvarova (popravka).

Označeni graf koji odgovara datom sistemu

m ij je gustina vjerovatnoće prijelaza iz stanja S i izjaviti S j (Si® Sj), gdje P ij(D t) je vjerovatnoća da će se ovaj prijelaz dogoditi tokom vremenskog intervala Dt.

Za male vrijednosti Dt vrijedi sljedeća približna jednakost.

Vjerovatnoće prijelaza se određuju iz sistema diferencijalnih jednačina (Kolmogorov) prema sljedećim pravilima:

1) svakom vrhu je dodeljeno odgovarajuće stanje, opisano verovatnoćom da se sistem nalazi u njemu, pa broj stanja određuje broj jednačina u sistemu;

2) na levoj strani jednačine - izvod verovatnoće odgovarajućeg stanja;

3) na desnoj strani ima onoliko pojmova koliko ima prelaza (grana) u označenom grafu koji je povezan sa datim stanjem;

4) svaki element desne strane jednak je proizvodu gustine verovatnoće prelaza i gustine verovatnoće stanja iz kojeg je prelaz izvršen;

5) sa desne strane sa znakom “+” nalaze se (zbrajani) elementi koji opisuju ulazak sistema u ovo stanje, a sa znakom “-” (oduzeti) elementi koji opisuju “izlazak” sistema iz ovog država;

6) da bi se pojednostavila „rešivost“, u sistem se uvodi normalizujuća jednačina koja opisuje kompletnu grupu događaja: , gde je N broj vrhova u označenom grafu stanja.

Za razmatrani graf stanja dobijamo sledeći sistem jednačina:

Ovaj sistem jednačina će biti lakše rešiti u slučaju kada opisuje stacionarni proces rada tehničkog sistema koji se proučava (obično ulazak sistema u stacionarni režim rada traje od 2 do 4 ciklusa).

U praksi smatramo da je pretpostavka o stacionarnosti funkcionisanja sistema opravdana ako je vreme funkcionisanja sistema kao celine za red veličine veće od (20¸40) × ciklusa rada sistema („uzastopni” pojedinačni prolaz kroz grane grafa).

Stacionarnost režima rada podrazumeva jednakost sa nulom vremenskih izvoda verovatnoća stanja, tj. .

Sistem jednačina se svodi na sljedeći oblik:

i njegovo rješenje više nije teško.

Sistem jednačina po Kolmogorovu omogućava rešavanje problema nalaženja verovatnoća za stacionarni režim (konačnih verovatnoća) iz poznatih gustina verovatnoće prelaza duž grana grafa, kao i inverznog problema, tj. pronalaženje gustoće vjerovatnoće za date konačne vjerovatnoće.

Primjer #2.

Razmotrite tehnički sistem S, koji se sastoji od dva paralelna čvora (dva mesta na benzinskim stanicama, dve mašine za punjenje na benzinskim pumpama). Pretpostavićemo da se tranzicije sistema iz jednog stanja u drugo dešavaju trenutno, u nasumičnom vremenu. Čim čvor pokvari, "trenutno" ide na popravku i nakon dovođenja u radno stanje, također "trenutno" počinje da se koristi.

Vjerujemo da ovaj sistem u potpunosti opisuju samo četiri stanja: S 0 - oba čvora su operativna; S 1 - prvi čvor se popravlja, drugi je servisiran; S 2 - drugi čvor se popravlja, prvi je servisiran; S 3 - oba čvora se popravljaju.

l 1 , l 2 je gustina vjerovatnoće kvara prvog i drugog stupa, m 1 , m 2 – gustina vjerovatnoće obnavljanja prvog i drugog čvora, respektivno.

Sastavimo sistem diferencijalnih jednačina po Kolmogorovu za vjerovatnoće stanja ovog sistema.

Za rješavanje Kolmogorovljevih jednadžbi i pronalaženje numeričkih vrijednosti za vjerovatnoće odgovarajućih stanja, potrebno je postaviti početne uslove.

Pretpostavićemo da su u početnom trenutku oba čvora sistema koji se proučavaju operativna, sistem je u stanju S 0 , tj. P 0 (t=0)=1, a sve ostale početne vjerovatnoće jednake su nuli: P 1 (0)=P 2 (0)=P 3 (0)=0.

Ovaj sistem jednačina se lako rješava ako sistem radi u ustaljenom stanju i svi procesi koji se u njemu odvijaju su stacionarni.

Stacionarnost režima rada podrazumeva jednakost sa nulom vremenskih izvoda verovatnoća stanja, tj. i=1, 2, … , n, , gdje n je broj mogućih stanja. A uzimajući u obzir punu grupu događaja, jednačina se dodaje

Poslednji, takozvani uslov normalizacije, omogućava da se jedna od jednačina isključi iz sistema...

Rešimo ovaj sistem sa sledećim podacima: l 1 =1, l 2 =2, m 1 =2, m 2=3. Zapišimo sistem bez četvrte jednačine.

Rešavajući ih dobijamo: P 0 =0,4; P 1 =0,2; P 2 @0,27; P 3 @0,13.

One. u stacionarnom režimu rada, naš sistem će biti u stanju S 0 - oba čvora su zdrava, itd.

Vrijednosti ovih konačnih vjerovatnoća mogu pomoći u procjeni prosječne efikasnosti sistema i opterećenja organa za popravku. Pretpostavimo da je sistem S u stanju S 0 generiše prihod od 8 konvencionalnih jedinica (c.u.) po jedinici vremena, u državi S 1 3c.u., in S 2 5c.u., ali sposoban S 3 ne stvara prihod.