Multe operațiuni care trebuie analizate la alegerea soluției optime se dezvoltă ca procese aleatorii care depind de o serie de factori aleatori.

Pentru descrierea matematică a multor operații care se desfășoară sub forma unui proces aleatoriu, pot fi aplicate cu succes aparate matematice, dezvoltat în teoria probabilității pentru așa-numitele procese aleatoare Markov.

Să explicăm conceptul de proces aleatoriu Markov.

Să existe un sistem S, a cărui stare se schimbă în timp (în cadrul sistemului S orice poate fi înțeles: o întreprindere industrială, un dispozitiv tehnic, un atelier de reparații etc.). Dacă starea sistemului S schimbări în timp într-un mod aleatoriu, imprevizibil, ei spun că în sistem S scurgeri proces aleatoriu.

Exemple de procese aleatorii:

fluctuațiile de preț pe bursă;

serviciu pentru clienți într-o coaforă sau atelier de reparații;

îndeplinirea planului de aprovizionare a grupului de întreprinderi etc.

Cursul specific al fiecăruia dintre aceste procese depinde de o serie de factori aleatori, imprevizibili, cum ar fi:

primirea pe bursa de stiri imprevizibile despre schimbarile politice;

natura aleatorie a fluxului de aplicații (cerințe) venite de la clienți;

întreruperi ocazionale în îndeplinirea planului de aprovizionare etc.

DEFINIȚIE. Procesul aleatoriu din sistem este numit Markovian(sau proces fără consecințe) dacă are următoarea proprietate: pentru fiecare moment de timp t 0 probabilitatea oricărei stări a sistemului în viitor (at t > t0) depinde doar de starea sa în prezent (cu t = t0)și nu depinde de când și cum a ajuns sistemul în această stare (adică, cum s-a dezvoltat procesul în trecut).

Cu alte cuvinte, într-un proces aleatoriu Markov, dezvoltarea sa viitoare depinde doar de starea prezentă și nu depinde de „preistoria” procesului.

Luați în considerare un exemplu. Lasă sistemul S reprezintă o bursă care există de ceva timp. Suntem interesați de modul în care sistemul va funcționa în viitor. Este clar, cel puțin ca primă aproximare, că caracteristicile performanței viitoare (probabilitățile de scădere a prețurilor anumitor acțiuni într-o săptămână) depind de starea sistemului în acest moment (cel mai diverși factori precum deciziile guvernamentale sau rezultatele alegerilor) și nu depind de când și cum a ajuns sistemul în starea actuală (nu depind de natura mișcării prețului acestor acțiuni în trecut).

În practică, se întâlnesc adesea procese aleatorii care, cu unul sau altul grad de aproximare, pot fi considerate markoviane.

Teoria proceselor aleatoare Markov are o gamă largă de aplicații diferite. Vom fi interesați în principal de aplicarea teoriei proceselor aleatorii Markov la construirea de modele matematice de operații, al căror curs și rezultat depind în mod esențial de factori aleatori.

Procesele aleatoare Markov sunt subdivizate în claseîn funcţie de cum şi în ce momente de timp sistemul S" îşi poate schimba stările.

DEFINIȚIE. Procesul aleatoriu este numit proces cu stări discrete, dacă stările posibile ale sistemului s x , s 2 , s v... pot fi enumerate (numerotate) una după alta, iar procesul în sine constă în faptul că din când în când sistemul S sare (instantaneu) de la o stare la alta.

De exemplu, dezvoltarea proiectelor S realizate în comun de două departamente, fiecare dintre ele putând greși. Sunt posibile următoarele stări ale sistemului:

5, - ambele compartimente functioneaza normal;

s 2 - primul departament a greșit, al doilea funcționează bine;

s 3 - al doilea departament a greșit, primul funcționează bine;

s 4 Ambele departamente au făcut o greșeală.

Procesul care are loc în sistem este că în anumite momente trece aleatoriu („sări”) de la o stare la alta. Sistemul are patru stări posibile în total. În fața noastră este un proces cu stări discrete.

Pe lângă procesele cu stări discrete, există procese aleatorii cu stări continue: aceste procese sunt caracterizate printr-o tranziție graduală, lină de la stare la stare. De exemplu, procesul de schimbare a tensiunii în rețeaua de iluminat este un proces aleatoriu cu stări continue.

Vom lua în considerare numai procesele aleatoare cu stări discrete.

Când se analizează procese aleatoare cu stări discrete, este foarte convenabil să se folosească o schemă geometrică - așa-numitul grafic de stare. Graficul de statînfățișează geometric stările posibile ale sistemului și posibilele sale tranziții de la stare la stare.

Să existe un sistem S cu stări discrete:

Fiecare stare va fi reprezentată printr-un dreptunghi, iar posibilele tranziții („sărituri”) de la o stare la alta prin săgeți care leagă aceste dreptunghiuri. Un exemplu de grafic de stare este prezentat în fig. 4.1.

Rețineți că săgețile marchează doar tranzițiile directe de la stat la stat; dacă sistemul poate trece de la stare s2 la 5 3 numai prin s y apoi săgețile marchează doar tranzițiile s2-> și l, 1 -> 5 3 dar nu s2 -» s y Să ne uităm la câteva exemple:

1. Sistem S- o firmă care se poate afla într-una din cele cinci stări posibile: s]- lucreaza cu profit;

s2- a pierdut perspectiva dezvoltării și a încetat să facă profit;

5 3 - a devenit obiect pentru o eventuală preluare;

s4- este sub control extern;

s5- proprietatea societatii lichidate se vinde la licitatie.

Graficul de stare a firmei este prezentat în Fig. 4.2.

Orez. 4.2

• 2. Sistem S- o bancă cu două sucursale. Sunt posibile următoarele stări ale sistemului:
• 5, - ambele sucursale lucreaza cu profit;

s 2 - primul departament lucreaza fara profit, al doilea lucreaza cu profit;

5 3 - al doilea departament lucrează fără profit, primul lucrează cu profit;

s 4 - ambele sucursale functioneaza fara profit.

Se presupune că nu există nicio îmbunătățire a stării.

Graficul de stare este prezentat în fig. 4.3. Rețineți că graficul nu arată o posibilă tranziție de la stare s] direct către s 4, ceea ce se va împlini dacă banca pe loc va funcționa în pierdere. Posibilitatea unui astfel de eveniment poate fi neglijată, ceea ce este confirmat de practică.

Orez. 4.3

3. Sistem S- o societate de investitii formata din doi comercianti (departamente): I si II; fiecare dintre ei poate la un moment dat să înceapă să funcționeze în pierdere. Dacă se întâmplă acest lucru, atunci conducerea companiei ia imediat măsuri pentru a restabili activitatea profitabilă a departamentului.

Stări posibile ale sistemului: s- activitatea ambelor departamente este profitabilă; s2- se reface primul departament, al doilea lucreaza cu profit;

s3- primul departament lucreaza cu profit, al doilea se reface;

s4- ambele departamente sunt în curs de restaurare.

Graficul stării sistemului este prezentat în fig. 4.4.

4. In conditiile exemplului anterior, activitatea fiecarui comerciant, inainte de a incepe refacerea muncii profitabile a departamentului, este examinata de conducerea societatii pentru a lua masuri de imbunatatire a acesteia.

Pentru comoditate, vom numerota stările sistemului nu cu unul, ci cu doi indici; primul va însemna starea primului comerciant (1 - lucrează cu profit, 2 - activitatea sa este studiată de conducere, 3 - restabilește activitatea profitabilă a departamentului); al doilea - aceleași stări pentru al doilea comerciant. De exemplu, s 23 va însemna: activitatea primului comerciant este în studiu, al doilea este refacerea muncii profitabile.

Stări posibile ale sistemului S:

s u- activitatea ambilor comercianti realizeaza profit;

s l2- primul comerciant lucreaza cu profit, activitatea celui de-al doilea este studiata de conducerea firmei;

5 13 - primul comerciant lucrează cu profit, al doilea restabilește activitatea profitabilă a departamentului;

s2l- activitatea primului comerciant este studiată de conducere, al doilea lucrează cu profit;

s 22 - activitatea ambilor comercianti este studiata de catre conducere;

• 5 23 - se studiază munca primului comerciant, al doilea comerciant reface activitatea profitabilă a departamentului;
• 5 31 - primul comerciant reface activitatea profitabilă a departamentului, al doilea lucrează cu profit;
• 5 32 - activitatea profitabilă a departamentului se reface de către primul comerciant, se studiază munca celui de-al doilea comerciant;
• 5 33 - ambii comercianți refac munca profitabilă a departamentului lor.

Sunt nouă state în total. Graficul de stare este prezentat în fig. 4.5.

În această secțiune, folosim metoda proceselor Markov pentru a găsi demodulatorul optim. Prezentarea noastră este superficială, prin urmare, pentru o analiză mai detaliată, cititorii interesați ar trebui să consulte surse suplimentare (în special,). Și de data aceasta vom presupune că mesajul este un proces aleator gaussian cu o reprezentare finită în variabile de stare, i.e.

unde este un proces aleator gaussian alb cu funcție de covarianță

Deși nu folosim acest fapt în cursul prezentării, trebuie subliniat că procedura descrisă în această secțiune poate fi efectuată și atunci când ecuația de stare și ecuația de observație sunt neliniare și au forma

Rețineți că sub unele restricții impuse este un proces Markov vectorial, care nu este neapărat un gaussian. Niciuna dintre metodele luate în considerare anterior nu permite rezolvarea problemelor cu mesaje din această clasă. Majoritatea rezultatelor care vor fi obținute în această secțiune pot fi obținute și pentru procesul mai general descris de ecuațiile (78) și (79).

Să revenim acum la model sub forma unui proces aleatoriu descris prin relații Pentru simplitatea notării, vom lua în considerare un mesaj care este un proces scalar Gaussian Markov și cu care oscilația transmisă este modulată de un tip de modulație inerțială. . Oscilația recepționată este scrisă ca

Procesul de comunicare satisface ecuația diferențială de ordinul întâi

Astfel, pentru orice mesaj finit este un proces staționar și are un spectru Butterworth de ordinul întâi. În plus, datorită faptului că procesul Markov este de ordinul întâi, densitatea sa de probabilitate în absența oricăror observații satisface ecuația Fokker-Planck [vezi. (3,79)]

Totuși, întrucât a fost observată în intervalul de timp, densitatea de probabilitate care ne interesează nu este o densitate necondiționată, ci o densitate datorată fluctuației observate.Notăm această densitate prin

Rețineți că (86) este densitatea de probabilitate a unuia variabilă aleatorie(o mărime care denotă valoarea lui a în momentul de timp din cauza fluctuației observate și este o caracteristică bine definită. Se poate demonstra că această densitate de probabilitate satisface ecuația

unde asteptarile matematice sunt luate din densitate Daca introducem formal derivata

atunci (87) poate fi scris formal ca o ecuație diferențială

Relația dintre densitatea posterioară și estimarea erorii standard minime este bine cunoscută. Estimarea pentru eroarea pătratică medie minimă este media condiționată a densității posterioare (vezi p. 73 din primul volum), adică.

Înmulțind ambele părți ale lui (89) cu A, integrând în raport cu și ținând cont de condițiile corespunzătoare de la capetele intervalului, obținem (vezi problema 7.2.2)

Rețineți că (91) mai conține valorea estimata de După cum era de așteptat, această ecuație nu este rezolvată pentru cazul general al modulării. Când metode liniare modulare este ușor de arătat (de exemplu, 18] sau problema 7.2.1) că se reduce la. Pentru multe probleme de modulare neliniară, succesul poate fi obținut prin extinderea într-un număr de termeni diferiți ai ecuației (91). Atunci, dacă presupunem că eroarea de estimare este mică și impunem anumite condiții momentelor de ordin superior, putem neglija termenii de ordinul doi și de cel mai înalt și putem obține următoarea ecuație aproximativă (o derivare detaliată este dată în capitolul 4 din carte):

unde denotă o estimare aproximativă pentru eroarea pătratică medie minimă. Funcția este o condițională aproximativă [în pătrat mediu al erorii] care satisface ecuația diferențială

cu condiție de limită

Rețineți că ecuația de estimare (92) și ecuația de dispersie (93) sunt cuplate. Mai rețineți că eroarea pătratică medie condiționată [i.e. e. eroare cu condiţia ca aproximările care trebuie permise să fie făcute să fie valabile atunci când eroarea este mică.

Vedem că ecuația (92) poate fi implementată sub forma unei diagrame bloc prezentată în Fig. 7.3. Această implementare este foarte asemănătoare cu structura estimatorului de probabilitate maximă posterior sintetizat în Cap. 2, singura diferență fiind că filtrul din buclă este acum implementat automat. Dezavantajul acestei implementări este prezența comunicării între bucle.

În cazul modulației unghiulare, se poate demonstra că această cuplare poate fi de obicei neglijată. De exemplu, cu modularea de fază

Se presupune că este mult mai mare decât frecvența cea mai înaltă din spectrul de mesaje și că sistemul este într-o stare staționară statistic. În acest caz, se arată că

satisface ecuația de dispersie la înlocuire

Pentru un proces Markov de ordinul întâi, această ecuație are forma

Schema bloc a receptorului este prezentată în fig. 7.4. Această structură coincide exact cu partea realizabilă a receptorului aproximativ în termeni de probabilitate maximă a posteriori, care a fost sintetizată mai devreme (vezi problema din (68) poate fi acum interpretată ca o eroare pătratică medie condițională aproximativă.

Orez. 7.4. Receptor optim: modulație de fază, comunicare cu spectru Butterworth de ordinul întâi.

Deoarece majoritatea detaliilor rezultatelor au fost omise, este important să rețineți limitările rezultatului. Ecuația diferențială (91), care determină media condiționată, este exactă. Cu toate acestea, aproximațiile asociate cu obținerea (92)-(93) corespund ipotezei de liniarizare. Prin urmare, rezultatul nostru este o estimare aproximativă cu minimul erorii pătratice medii corespunzătoare primului termen al expansiunii într-o serie a estimării exacte. Pentru a obține o aproximare mai bună, puteți ține Mai mult termeni de extindere (vezi, de exemplu, ). Dificultatea cu această procedură este că aproximarea în doi termeni este deja atât de complicată încât probabil că nu are niciun interes practic.

Sub proces aleatoriu să înțeleagă schimbarea în timp a stărilor unui sistem fizic într-un mod aleatoriu necunoscut anterior. în care prin sistem fizic ne referim orice dispozitiv tehnic, grup de dispozitive, întreprindere, industrie, sistem biologic etc.

proces aleatoriu care curge în sistem se numește Markovsky – dacă pentru orice moment de timp, caracteristicile probabilistice ale procesului in viitor (t > ) depinde numai de starea sa la un moment dat ( prezent ) și nu depind de când și cum a ajuns sistemul în această stare în trecut .(De exemplu, un contor Geiger care înregistrează numărul de particule cosmice).

Procesele Markov sunt de obicei împărțite în 3 tipuri:

1. lanțul Markov – un proces ale cărui stări sunt discrete (adică pot fi renumerotate), iar timpul în care este considerat este, de asemenea, discret (adică procesul își poate schimba stările numai în anumite momente de timp). Un astfel de proces merge (se schimbă) în pași (cu alte cuvinte, în cicluri).

2. Proces discret Markov - setul de stări este discret (poate fi enumerat), iar timpul este continuu (trecerea de la o stare la alta - în orice moment).

3. Procesul Markov continuu – setul de stări și timpul sunt continui.

În practică, procesele Markov în forma lor pură nu sunt adesea întâlnite. Cu toate acestea, de multe ori trebuie să se ocupe de procese pentru care influența preistoriei poate fi neglijată. În plus, dacă toți parametrii din „trecut”, de care depinde „viitorul”, sunt incluși în starea sistemului în „prezent”, atunci poate fi considerat și Markovian. Totuși, aceasta duce adesea la o creștere semnificativă a numărului de variabile luate în considerare și la imposibilitatea de a obține o soluție a problemei.

În Cercetare Operațională mare importanță ocupa asa-numita Procese stocastice Markov cu stări discrete și timp continuu.

Procesul este numit proces de stare discretă, dacă toate stările sale posibile , ,... pot fi enumerate (renumerotate) în prealabil. Trecerea sistemului de la stat la stat trece aproape instantaneu - sari.

Procesul este numit proces în timp continuu, dacă momentele de trecere de la stat la stat pot lua oricare valori aleatorii pe axa timpului.

De exemplu : Dispozitiv tehnic S este format din două noduri , dintre care fiecare la un moment aleator de timp poate eșua ( refuza). După aceea, reparația nodului începe imediat ( recuperare) care continuă pentru un timp aleatoriu.

Sunt posibile următoarele stări ale sistemului:

Ambele noduri sunt OK;

Primul nod este reparat, al doilea funcționează.

- al doilea nod este in reparatie, primul functioneaza

Ambele noduri sunt în curs de reparare.

Trecerea sistemului de la o stare la alta are loc aproape instantaneu în momente aleatorii. Este convenabil să afișați stările sistemului și relația dintre ele folosind grafic de stare .

state

Tranziții

Tranziţiile şi sunt absente pentru că defecțiunile și recuperarea elementelor apar independent și aleatoriu, iar probabilitatea defecțiunii (recuperării) simultane a două elemente este infinitezimală și poate fi neglijată.

Dacă toate fluxurile de evenimente traduc sistemul S de la stat la stat protozoare, apoi proces, curgând într-un astfel de sistem va fi Markovsky. Acest lucru se datorează faptului că cel mai simplu flux nu are un efect secundar, adică. în ea, „viitorul” nu depinde de „trecut” și, în plus, are proprietatea obișnuinței - probabilitatea apariției simultane a două sau mai multe evenimente este infinit mică, adică este imposibil să treci din stare. a afirma fără a trece mai multe stări intermediare.

Pentru claritate, pe graficul de stare, este convenabil să se menționeze intensitatea fluxului de evenimente care transferă sistemul de la o stare la alta de-a lungul săgeții date la fiecare săgeată de tranziție ( - intensitatea fluxului de evenimente care transferă sistemul de la stat în. Un astfel de grafic se numește marcat.

Folosind un grafic de stare a sistemului etichetat, se poate construi model matematic acest proces.

Luați în considerare tranzițiile sistemului de la o anumită stare la cea anterioară sau următoare. Un fragment din graficul de stare în acest caz va arăta astfel:

Lasă sistemul la momentul respectiv t este într-o stare de .

Notați (t)- probabilitatea stării i a sistemului este probabilitatea ca sistemul la timp t este într-o stare de . Pentru orice moment de timp t =1 este adevărat.

Să determinăm probabilitatea ca la momentul respectiv t+∆t sistemul va fi în stat. Acest lucru poate fi în următoarele cazuri:

1) și nu l-a părăsit în timpul ∆ t. Aceasta înseamnă că în timpul ∆t nu a apărut un eveniment care aduce sistemul într-o stare (curgere cu intensitate) sau un eveniment care îl pune într-o stare (curgere cu intensitate). Să determinăm probabilitatea acestui lucru pentru ∆t mic.

Conform legii exponențiale a distribuției timpului între două cerințe învecinate, corespunzătoare celui mai simplu flux de evenimente, probabilitatea ca, în intervalul de timp ∆t, să nu apară cerințe în fluxul cu intensitate. λ1 va fi egal cu

Extinderea funcției f(t) într-o serie Taylor (t>0) obținem (pentru t=∆t)

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

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

În mod similar, pentru un flux cu intensitatea λ 2 obținem .

Probabilitatea ca pe intervalul de timp ∆t (pentru ∆t®0) nicio cerință nu va fi egală cu

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

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

Astfel, probabilitatea ca sistemul să nu fi părăsit starea în timpul ∆t pentru ∆t mic va fi egală cu

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

2) Sistemul era într-o stare S i -1 şi pentru timp a trecut în starea S i . Adică cel puțin un eveniment a avut loc în fluxul cu intensitate. Probabilitatea acestui lucru este egală cu cel mai simplu flux cu intensitate λ va fi

Pentru cazul nostru, probabilitatea unei astfel de tranziții va fi egală cu

3)Sistemul era într-o stare iar în timpul ∆t a trecut în stat . Probabilitatea acestui lucru va fi

Atunci probabilitatea ca sistemul la momentul (t+∆t) să fie în starea S i este egală cu

Scădem P i (t) din ambele părți, împărțim la ∆t și, trecând la limită, cu ∆t→0, obținem

Înlocuind valorile corespunzătoare ale intensităților tranzițiilor de la stări la stări, obținem sistemul ecuatii diferentiale descriind modificarea probabilităților stărilor sistemului în funcție de timp.

Aceste ecuații se numesc ecuații Kolmogorov-Chapman pentru un proces Markov discret.

după ce a întrebat condiții inițiale(de exemplu, P 0 (t=0)=1,P i (t=0)=0 i≠0) și rezolvându-le, obținem expresii pentru probabilitățile stării sistemului în funcție de timp. Soluțiile analitice sunt destul de ușor de obținut dacă numărul de ecuații ≤ 2,3. Dacă sunt mai multe, atunci ecuațiile sunt de obicei rezolvate numeric pe un computer (de exemplu, prin metoda Runge-Kutta).

În teoria proceselor aleatorii dovedit , ce dacă numărul n stările sistemului cu siguranță și din fiecare dintre ele este posibil (într-un număr finit de pași) să treci la oricare altul, atunci există o limită , spre care tind probabilitatile cand t→ . Astfel de probabilități sunt numite probabilități finale stări și starea de echilibru - modul staționar functionarea sistemului.

Din moment ce în modul staționar toate , prin urmare, toate =0. Echivalând părțile din stânga ale sistemului de ecuații cu 0 și completându-le cu ecuația =1, obținem un sistem liniar. ecuații algebrice, rezolvând care găsim valorile probabilităților finale.

Exemplu. Lăsați în sistemul nostru ratele de eșec și restaurare ale elementelor sunt următoarele

Eșecuri 1el:

2el:

Reparație 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

Hotărând acest sistem, primim

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

Acestea. în stare staționară, sistemul în medie

40% este în stare S 0 (ambele noduri sunt sănătoase),

20% - în stare S 1 (primul element este în curs de reparare, al 2-lea este în stare bună),

27% - în stare S 2 (al doilea electric este în curs de reparare, 1 este în stare bună),

13% - în stare S 3 - ambele elemente sunt în reparație.

Cunoașterea probabilităților finale permite Evaluați performanța medie a sistemului și sarcina serviciului de reparații.

Fie ca sistemul din starea S 0 să aducă un venit de 8 unități. pe unitatea de timp; în statul S 1 - venit 3 sr.u.; în statul S 2 - venit 5; în statul S 3 - venit \u003d 0

Preț reparație pe unitatea de timp pentru el-ta 1- 1 (S 1, S 3) unități arb., el-ta 2- (S 2, S 3) 2 arb. Apoi, în modul staționar:

Venituri de sistem pe unitate de timp va fi:

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.

Costul reparațiilor in unitati timp:

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 pe unitatea de timp

W \u003d W doh -W rem \u003d 5,15-1,39 \u003d 3,76 unități

După ce au cheltuit anumite cheltuieli, este posibil să se modifice intensitatea λ și μ și, în consecință, eficiența sistemului. Fezabilitatea unor astfel de cheltuieli poate fi evaluată prin recalcularea P i . și indicatorii de performanță ai sistemului.

Să apară s.p. într-un anumit sistem. cu stări discrete
și timp discret, adică trecerea sistemului de la o stare la alta are loc numai în anumite momente în timp
. Aceste momente se numesc trepte proces (de obicei, diferența dintre momentele adiacente de observație
egal cu un număr constant - lungimea pasului, luată ca unitate de timp);
începutul procesului.

Acest s.p. poate fi privit ca o succesiune (lanț) de evenimente
.

starea inițială a sistemului, adică înainte de pasul 1;
starea sistemului după primul pas,
starea sistemului după pasul 2 etc.), adică evenimentele formei
Unde.

Se numește un proces aleator Markov cu stări discrete și timp discret lanțul Markov(lanțul Markov).

Rețineți că lanțul Markov, în care probabilitățile condiționate ale stărilor în viitor depind doar de starea din ultima etapă (și nu depind de cele anterioare), se numește lanț Markov simplu. (A.A. Markov 1856-1922 - matematician rus).

Un exemplu de astfel de sistem poate servi ca dispozitiv tehnic, ale cărui posibile stări sunt următoarele:

buna treaba;

inspecție și întreținere preventivă;

lucrări de reparații;

anulare pentru inutilitate;

Graficul stării de lucru este prezentat în figură

Orez. 1.11 (A.A. Belov și colab.)

Din analiza graficului se poate observa că din starea de funcționare normală a vârfului sistemul poate intra într-o stare de întreținere preventivă , apoi reveniți la . Sau muta din in stare de reparatie , după care fie revine la , sau intră în starea de anulare. Stat este finită, deoarece trecerea de la ea este imposibilă. Tranziție de la din nou in înseamnă o întârziere în această stare.

În practică, există adesea sisteme ale căror stări formează un lanț în care fiecare stare (cu excepția extremelor și ) este legat printr-o linie dreaptă și părere cu doi vecini
iar stările extreme - cu una vecină (vezi Fig.)

Fig.1.12(Belov...)

Un exemplu de astfel de sistem este un dispozitiv tehnic format din același tip de noduri. Fiecare stare a sistemului este caracterizată de numărul de defecte noduri la momentul verificării.

Sarcina principală a studiului este de a găsi probabilitățile statului pe oricare
m pas. Vom calcula probabilitățile stărilor sistemului discret

Aici vom lua în considerare doar lanțuri Markov simple. Mai mult, vom lua în considerare pe scurt conceptele de procese Markov continue.

Cu un timp discret de schimbare a stărilor sistemului, fiecare tranziție de la o stare la alta este numită Etapa.

Din definiția unui lanț Markov rezultă că pentru acesta probabilitatea tranziției sistemului în stare de
m pas depinde numai de starea în care sistemul era pe precedentul
Etapa.

Unde
probabilitate necondiţionată ca
m pas sistemul va fi în stare . Pentru a găsi aceste probabilități, este necesar să se cunoască distribuția inițială a probabilității, i.e. probabilități de stare
atunci
(începutul procesului) și așa-numitul probabilități de tranziție
Lanțul Markov pe
m pas.

probabilitatea de tranziție
se numește probabilitatea de tranziție condiționată a sistemului pe

m pas, în stat
m pas ea a putut , adică

(43),

unde primul indice indică numărul precedentului, iar al doilea indice către numărul stării următoare a sistemului.

Lanțul Markov se numește omogen, dacă valoarea
acestea. probabilități condiționate
nu depind de numărul de încercări, altfel numite eterogene.

În plus, vom lua în considerare numai lanțuri omogene, care pot fi specificate folosind vectorul - probabilitatea stărilor la momentul de timp
și matrice ( numită matrice de tranziție)

(44)
.

Elemente de matrice
au proprietățile de bază ale matricelor pătrate obișnuite și, în plus, următoarele proprietăți:

A)
, b)
pentru fiecare fix
, adică suma elementelor fiecărui rând matrice de tranziție este egal cu unu (ca probabilitatea de evenimente de tranziție dintr-o stare la orice altă stare posibilă - formarea unui grup complet de evenimente).

Probabilitatea stării sistemului la pasul următor este determinată de formula recursivă:

În anumite condiții (ergodicitate, omogenitate, absență a ciclurilor) în lanțul Markov, modul staționar, în care probabilitățile stărilor sistemului nu depind de numărul pasului. Astfel de probabilități sunt numite marginal(sau finale) probabilități ale lanțului Markov:

.

Există o afirmație.

Teorema 17.1.Pentru matrici tranziția probabilităților trepte
formula este valabila

(45)
,

Dovada. După regula înmulțirii a două matrici pătrate
comanda pe care o avem

Unde

totodată, prin definiţia matricei de tranziţie se ştie că
pentru orice
.

Să însumăm ambele părți ale egalității
pentru toți
, și schimbând ordinea însumării după aplicarea proprietății a) de două ori, obținem asta
matricea de tranziție în două etape. În mod similar, raționând consecvent pas cu pas, obținem afirmația noastră în cazul general.

Exemplul 3 Este dată matricea de tranziție

.

Găsiți matrice de probabilitate de tranziție
.

Pe baza regulii înmulțirii a două matrici, obținem

.

Exercițiu. Verificați dacă egalitatea este adevărată

Trebuie remarcat că un lanț Markov finit discret este o generalizare suplimentară a schemei Bernoulli, în plus, în cazul încercărilor dependente; încercările independente sunt un caz special al unui lanț Markov. Aici sub „eveniment”

se referă la starea sistemului, iar „test” se referă la schimbarea stării sistemului.

În cazul în care un " teste” (experimentele) sunt independente, atunci apariția unui anumit eveniment în orice experiment nu depinde de rezultatele testelor efectuate anterior.

Sarcini. a) Sunt date matrice de tranziție

1.
;

2.
;

3.
.

Găsiți în fiecare caz matricea
.

Raspunsuri: a) 1.
;

2.
;

3.

c) Sunt date matrice de tranziție

;
.

Găsi
.

Raspunsuri: c) 1.
;2.
;

3.
.

Cometariu.În general, discret lanțul Markov
este un proces aleator Markov al cărui spațiu de stări este finit sau numărabil și setul de indici
- mulțimea tuturor numerelor întregi nenegative sau a unui subset al acestuia (finit sau numărabil). Putem vorbi despre ce zici de rezultat
al-lea test.

Este adesea convenabil să se identifice spațiul de stare a procesului cu mulțimea de numere întregi nenegative
iar în aceste cazuri se spune că este într-o stare , dacă
.

Probabilitatea de a atinge o variabilă aleatoare
intr-o stare (numită probabilitate de tranziție într-un singur pas), după cum sa menționat mai sus, este notat
, adică

Această notație subliniază că, în cazul general, probabilitățile de tranziție depind nu numai de stările inițiale și finale, ci și de momentul tranziției.

În cazurile în care probabilitățile de tranziție într-un singur pas nu depind de variabila de timp (adică, de valoare , atunci se spune că un proces Markov are probabilități de tranziție staționară. Deci, pentru cele ce urmează, observăm că există o egalitate de care nu depinde , și denotă probabilitatea tranziției într-un singur proces de la stat intr-o stare .

De obicei, probabilitățile combinate într-o matrice pătrată (finită sau numărabilă) în funcție de procesul luat în considerare:

,

și se numește o matrice Markov, sau matricea probabilității de tranziție lanțul Markov.

În matrice
rândul i reprezintă distribuția de probabilitate a r.v.
cu conditia ca
. Dacă numărul de stări este finit, atunci - finală matrice pătrată, a cărui ordine (număr de rânduri) este egală cu numărul de stări.

Desigur, probabilitățile satisface următoarele două condiții:

A)
,

b)
pentru fiecare fix

Condiția b) reflectă faptul că fiecare încercare determină o anumită tranziție de la o stare la alta. Pentru comoditate, se vorbește și despre tranziție iar în cazul în care starea rămâne neschimbată. Există o afirmație.

Teorema 17.2.Procesul este complet definit dacă sunt date probabilitățile(46), adică

și distribuția de probabilitate a variabilei aleatoare .

Dovada. Să arătăm asta pentru orice finit cum se calculează probabilitățile

întrucât conform formulei probabilității totale, orice alte probabilități legate de variabile aleatoare pot fi obținute prin însumarea termenilor (termenilor) din forma (47).

Prin definiția probabilității condiționate, avem

Dar prin definiția unui proces Markov, obținem

Punând egalitatea (49) în (48) obținem

Continuând acest proces secvențial, obținem:

Procesul este complet definit. Ceea ce trebuia dovedit.

procese aleatorii Markov.

Să presupunem că trebuie să studiem un „sistem fizic” S(al cărui proces de funcționare poate fi descris în mod explicit), care își poate schimba starea în timp (tranziții de la o stare la alta) într-un mod necunoscut anterior, aleatoriu. Orice poate fi înțeles ca un „sistem fizic”: un dispozitiv tehnic, un grup de astfel de dispozitive, o întreprindere, o industrie, un organism viu, o populație și așa mai departe.

Presupunem că sistemul studiat S poate fi descris de un set de stări posibile, cunoscute anterior ale sistemului Si, care poate fi determinată pe baza „naturei fizice” a procesului de funcționare a sistemului studiat, adică. .

- i Starea sistemului depinde de k parametrii.

Într-o situație reală, starea sistemului poate depinde de relațiile cauză-efect dintre stările și procesele care apar în sistem. Adică natura comportamentului sistemului este imprimată de „preistoria” naturii comportamentului sistemului și de un ansamblu de factori aleatori (procese de perturbare externe sau interne). Ne confruntăm cu multe „scenarii sugerate” ale procesului de funcționare a sistemului. Și însăși „alegerea” „scenariului de comportament” dominant (cum se va comporta sistemul studiat) este aleatorie.

De remarcat faptul că trecerea de la stat S eu să afirm S j este stocastică. Începem să luăm în considerare funcționarea sistemului din starea inițială S 0 , care corespunde timpului t 0 . Adică ceea ce s-a întâmplat cu sistemul înainte de momentul t 0 se referă la „trecutul său”, la preistoria lui.

Definiție: Un proces aleatoriu dintr-un sistem se numește proces Markov dacă pentru orice moment de timp t 0 caracteristicile probabilistice ale procesului în viitor depind numai de starea acestuia în momentul de față t 0 și nu depind de când și cum a ajuns sistemul în această stare.

Presupunem că starea sistemului este descrisă de funcție S(t), argumentul acestei funcții este timpul t continuu se cunosc momentele de timp ale trecerii sistemului de la o stare la alta t: t 1 <t 2 < … <t n. Mai mult, trecerea de la o stare la alta are loc „salt”, aproape instantaneu.

Am ajuns la concluzia că procesul de funcționare a sistemului este asociat cu un lanț de stări discrete: S 1® S 2 ® … ® S n-1® S n (trecerea succesivă de la o stare la alta, fără a „sări” prin vreo stare). Adică, sistemul luat în considerare este descris printr-un proces aleator Markov cu stări discrete și timp continuu.

Știm din teoria probabilității că funcția densității probabilității pentru n-a stare se caută ca funcţie de densitate comună pentru întreaga „preistorie” a procesului de venire a sistemului în această stare: .

În practică, procesele Markov nu au loc în forma lor pură, dar de multe ori trebuie să se ocupe de procese pentru care influența preistoriei poate fi neglijată. Când se studiază astfel de procese, pot fi utilizate modele Markov.

Când se consideră procesul ca unul Markov, descrierea analitică a modelului este simplificată, deoarece presupunem că starea sistemului depinde doar de o stare anterioară: .

Lanțurile Markov sunt definite de un set de stări bine definite: . În funcție de când și cum au loc „tranzițiile”, lanțurile Markov sunt împărțite în discrete, pentru care timpul de tranziție de la o stare la alta este fix și este determinat de probabilitatea acestei tranziții, și continue, pentru care stările sunt discrete, timp. este continuă și tranzițiile de la o stare în alta au loc la întâmplare, necunoscute dinainte, momente de timp.

Când se analizează procese aleatoare cu stări discrete, este convenabil să se folosească o schemă geometrică - așa-numitul grafic de stare.

Definiție. Un grafic este o colecție de mai multe vârfuri Vși mulțimea de perechi ordonate de vârfuri A={(A 1 A i)( A 2 A j) … ), ale căror elemente se numesc muchii G(V,A).

Stările sistemului sunt asociate cu vârfurile graficului, iar tranzițiile de la o stare la alta sunt asociate cu frânghiile care indică „direcția fluxului” a procesului.

În exemplul următor, vom lua în considerare o tehnică pentru studierea lanțurilor Markov folosind un grafic de stare etichetat.

Exemplul #1. TEA funcționarea tehnică a mașinii.

Un model TEA simplificat implică prezența a cel puțin patru dintre următoarele stări: S 1 - diagnosticarea stării mașinii, S 2 - lucru pe linie (mașina este în stare bună), S 3 - întreținere, S 4 - depanare (reparare).

Graficul etichetat corespunzător sistemului dat

m ij este densitatea probabilității de tranziție din starea S i a afirma S j (Si® Sj), Unde P ij(D t) este probabilitatea ca această tranziție să se producă în intervalul de timp Dt.

Pentru valori mici ale lui Dt, următoarea egalitate aproximativă este adevărată.

Probabilitățile de tranziție sunt determinate din sistemul de ecuații diferențiale (Kolmogorov) conform următoarelor reguli:

1) fiecărui vârf i se atribuie o stare corespunzătoare, descrisă de probabilitatea ca sistemul să se afle în el, deci numărul de stări determină numărul de ecuații din sistem;

2) în partea stângă a ecuației - derivata probabilității stării corespunzătoare;

3) există tot atâtea termeni în partea dreaptă câte tranziții (ramuri) există în graficul etichetat asociat cu starea dată;

4) fiecare element din partea dreaptă este egal cu produsul dintre densitatea de probabilitate a tranziției și densitatea de probabilitate a stării din care a fost făcută tranziția;

5) în partea dreaptă cu semnul „+” există elemente (adunate) care descriu intrarea sistemului în această stare, iar cu semnul „-” (scăzut) elemente care descriu „ieșirea” sistemului din aceasta. stat;

6) pentru a simplifica „solubilitatea”, în sistem este introdusă o ecuație de normalizare care descrie grupul complet de evenimente: , unde N este numărul de vârfuri din graficul de stare etichetat.

Pentru graficul de stare luat în considerare, obținem următorul sistem de ecuații:

Acest sistem de ecuații va fi mai ușor de rezolvat în cazul în care descrie procesul staționar de funcționare a sistemului tehnic studiat (de obicei, intrarea sistemului în modul staționar de funcționare durează de la 2 la 4 cicluri).

În practică, considerăm că ipoteza staționarității funcționării sistemului este justificată dacă timpul de funcționare a sistemului în ansamblu este cu un ordin de mărime mai mare decât (20¸40) × cicluri de funcționare a sistemului („succesive” singure). trecerea prin ramurile graficului).

Staționaritatea modului de funcționare implică egalitatea la zero a derivatelor temporale ale probabilităților de stare, i.e. .

Sistemul de ecuații se reduce la următoarea formă:

iar rezolvarea lui nu mai este dificilă.

Sistemul de ecuații conform lui Kolmogorov permite rezolvarea problemei găsirii probabilităților pentru modul staționar (probabilități finale) din densitățile de probabilitate cunoscute ale tranzițiilor de-a lungul ramurilor graficului, precum și a problemei inverse, i.e. găsirea densităților de probabilitate pentru probabilități finale date.

Exemplul #2.

Luați în considerare un sistem tehnic S, format din două noduri paralele (două posturi la benzinării, două mașini de umplere la benzinării). Vom presupune că tranzițiile sistemului de la o stare la alta au loc instantaneu, la momente aleatorii. De îndată ce nodul se defectează, acesta vine „instantaneu” pentru reparație și, după ce-l aduce în stare de funcționare, începe și „instantaneu” să fie folosit.

Credem că acest sistem este complet descris de doar patru stări: S 0 - ambele noduri sunt operaționale; S 1 - primul nod este reparat, al doilea este reparabil; S 2 - al doilea nod este în curs de reparare, primul este reparabil; S 3 - ambele noduri sunt în curs de reparare.

l 1 , l 2 este densitatea probabilității de defecțiune a primului și celui de-al doilea post, m 1 , m 2 – densitatea de probabilitate de restaurare a primului și respectiv al doilea nod.

Să compunem un sistem de ecuații diferențiale după Kolmogorov pentru probabilitățile stărilor acestui sistem.

Pentru a rezolva ecuațiile Kolmogorov și pentru a găsi valori numerice pentru probabilitățile stărilor corespunzătoare, este necesar să se stabilească condițiile inițiale.

Vom presupune că la momentul inițial de timp ambele noduri ale sistemului studiat sunt operaționale, sistemul este în starea S 0 , adică. P 0 (t=0)=1, iar toate celelalte probabilități inițiale sunt egale cu zero: P 1 (0)=P 2 (0)=P 3 (0)=0.

Acest sistem de ecuații este ușor de rezolvat dacă sistemul funcționează într-o stare staționară și toate procesele care au loc în el sunt staționare.

Staționaritatea modului de funcționare implică egalitatea la zero a derivatelor temporale ale probabilităților de stare, adică, i=1, 2, … , n, , Unde n este numărul de stări posibile. Și ținând cont de întregul grup de evenimente, se adaugă ecuația

Ultima, așa-numita condiție de normalizare, permite excluderea uneia dintre ecuații din sistem...

Să rezolvăm acest sistem cu următoarele date: l 1 =1, l 2 =2, m 1 =2, m 2=3. Să scriem sistemul fără a patra ecuație.

Rezolvându-le, obținem: P 0 =0,4; P 1 =0,2; P 2 @0,27; P 3 @0,13.

Acestea. într-un mod de funcționare staționar, sistemul nostru va fi într-o stare de S 0 - ambele noduri sunt sănătoase etc.

Valorile acestor probabilități finale pot ajuta la estimarea eficienței medii a sistemului și a sarcinii organelor de reparare. Să presupunem că sistemul S in stare S 0 generează un venit de 8 unități convenționale (uc) pe unitatea de timp, în stat S 1 3c.u., în S 2 5c.u., dar capabil S 3 nu generează venituri.