Markovin satunnaisten prosessien käsite. Jonoteorian elementtejä Stationaarinen Markov-prosessi

Tapahtukoon jossain järjestelmässä s.p. erillisten tilojen kanssa
ja diskreetti aika, ts. järjestelmän siirtyminen tilasta toiseen tapahtuu vain tiettyinä aikoina
. Näitä hetkiä kutsutaan askeleet prosessi (yleensä vierekkäisten havaintohetkien välinen ero
yhtä suuri kuin vakioluku - askelpituus otettuna aikayksikkönä);
prosessin alku.

Tämä s.p. voidaan pitää tapahtumien sarjana (ketjuna).
.

järjestelmän alkutila, ts. ennen ensimmäistä vaihetta;
järjestelmän tila ensimmäisen vaiheen jälkeen,
järjestelmän tila toisen vaiheen jälkeen jne.), ts. tapahtumia kuten
Missä.

Kutsutaan Markovin satunnaisprosessia, jossa on diskreetit tilat ja diskreetti aika Markovin ketju(Markov-ketju).

Ota huomioon, että Markovin ketju, jossa tilojen ehdolliset todennäköisyydet tulevaisuudessa riippuvat vain viimeisen vaiheen tilasta (eivät riipu edellisistä). yksinkertainen Markov-ketju. (A.A. Markov 1856-1922 - venäläinen matemaatikko).

Esimerkki tällaisesta järjestelmästä voi toimia teknisenä laitteena, jonka mahdolliset tilat ovat seuraavat:

hyvää työtä;

ennaltaehkäisevä tarkastus ja huolto;

kunnostustyöt;

poistot käyttökelvottomuudesta;

Työn tilakaavio näkyy kuvassa

Riisi. 1.11. (A.A. Belov jne.)

Graafin analyysistä käy selvästi ilmi, että kärjen normaalin toiminnan tilasta järjestelmä voi siirtyä ennaltaehkäisevän huollon tilaan ja palaa sitten kohtaan . Tai muuttaa pois korjauskunnossa , jonka jälkeen se joko palaa , tai siirry poistotilaan. Osavaltio on äärellinen, koska siirtyminen siitä on mahdotonta. Siirtyminen kohteesta takaisin tarkoittaa viivettä tässä tilassa.

Käytännössä kohtaamme usein järjestelmiä, joiden tilat muodostavat ketjun, jossa jokainen tila (paitsi äärimmäinen Ja ) on yhdistetty suorilla ja takaisinkytkentäyhteyksillä kahteen viereiseen,
ja ääritilat - yhden naapurin kanssa (katso kuva)

Kuva 1.12 (Belov...)

Esimerkki tällaisesta järjestelmästä on tekninen laite, joka koostuu samankaltaisista yksiköistä. Jokaiselle järjestelmätilalle on tunnusomaista viallisten määrä solmut varmennushetkellä.

Tutkimuksen päätavoitteena on löytää tilan todennäköisyydet millä tahansa
m askel. Laskemme diskreetin järjestelmän tilojen todennäköisyydet

Tässä tarkastellaan vain yksinkertaisia ​​Markov-ketjuja. Lisäksi tarkastellaan lyhyesti jatkuvien Markov-prosessien käsitteitä.

Kun järjestelmän tiloissa tapahtuu diskreettiaikaisia ​​muutoksia, kutsutaan jokaista siirtymää tilasta toiseen askel.

Markovin ketjun määritelmästä seuraa, että sille järjestelmäsiirtymän todennäköisyys tilassa
m askel riippuu vain tilasta järjestelmä oli edellisessä
askel.

Missä
ehdoton todennäköisyys
Ensimmäisessä vaiheessa järjestelmä on tilassa . Näiden todennäköisyyksien löytämiseksi on tiedettävä alkuperäinen todennäköisyysjakauma, ts. tilan todennäköisyydet
tiettynä ajankohtana
(prosessin alku) ja ns siirtymän todennäköisyyksiä
Markovin ketju päällä
m askel.

Siirtymän todennäköisyys
kutsutaan järjestelmän ehdollisen siirtymän todennäköisyydeksi päällä

m askel, tilassa
m askeleen hän pystyi , eli

(43),

jossa ensimmäinen indeksi osoittaa edellisen tilan numeron ja toinen indeksi osoittaa järjestelmän seuraavan tilan numeron.

Markovin ketjua kutsutaan homogeeninen, jos arvo
nuo. ehdolliset todennäköisyydet
eivät riipu testinumerosta, muuten sitä kutsutaan heterogeeniseksi.

Lisäksi tarkastellaan vain homogeenisia ketjuja, jotka voidaan määrittää vektorilla - tilojen todennäköisyys kerrallaan
ja matriisit ( kutsutaan siirtymämatriisiksi)

(44)
.

Matriisielementit
niillä on tavallisten neliömatriisien perusominaisuudet ja lisäksi seuraavat ominaisuudet:

A)
, b)
jokaiselle kiinteälle
, eli kunkin rivin elementtien summa siirtymämatriiseja yhtä suuri kuin yksi (siirtymätapahtumien todennäköisyys yhdestä tilasta mihin tahansa muuhun mahdolliseen tilaan - kokonaisen tapahtumaryhmän muodostaminen).

Järjestelmän tilan todennäköisyys seuraavassa vaiheessa määritetään toistuvalla kaavalla:

Tietyissä olosuhteissa (ergodisuus, homogeenisuus, syklien puuttuminen) Markov-ketju muodostuu paikallaan oleva tila, jossa järjestelmän tilojen todennäköisyydet eivät riipu askelnumerosta. Tällaisia ​​todennäköisyyksiä kutsutaan äärimmäinen(tai lopullinen) Markovin ketjun todennäköisyydet:

.

On olemassa väite.

Lause 17.1.varten matriiseja todennäköisyyksien siirtyminen pidemmälle askeleet
kaava on voimassa

(45)
,

Todiste. Kahden neliömatriisin kertolaskusäännön mukaan
meidän järjestyksessämme

Missä

Lisäksi siirtymämatriisin määritelmän perusteella tiedetään, että
milloin tahansa
.

Lasketaan yhteen tasa-arvon molemmat puolet
kaikissa
, ja korvaamalla summausjärjestyksen ominaisuuden a) soveltamisen jälkeen kahdesti, saamme sen
siirtymämatriisi kahdessa vaiheessa. Samoin johdonmukaisesti askel askeleelta päättelemällä saamme lausuntomme yleisessä tapauksessa.

Esimerkki 3. Siirtymämatriisi määritetty

.

Etsi siirtymän todennäköisyysmatriisit
.

Kahden matriisin kertomissäännön perusteella saamme

.

Harjoittele. Tarkista, että tasa-arvo on totta

On huomattava, että äärellinen diskreetti Markovin ketju edustaa Bernoullin kaavion lisäyleistystä, lisäksi riippuvien testien tapauksessa; riippumattomat testit ovat Markov-ketjun erikoistapaus. Täällä "tapahtuma" alla

tarkoittaa järjestelmän tilaa ja "testi" tarkoittaa muutosta järjestelmän tilassa.

jos " testit"(kokeet) ovat riippumattomia, silloin tietyn tapahtuman esiintyminen missään kokeessa ei riipu aiemmin suoritettujen testien tuloksista.

Tehtävät. a) Siirtymämatriisit on annettu

1.
;

2.
;

3.
.

Etsi matriisi kussakin tapauksessa
.

Vastaukset: a) 1.
;

2.
;

3.

c) Siirtymämatriisit on annettu

;
.

löytö
.

Vastaukset: c) 1.
;2.
;

3.
.

Kommentti. Yleensä diskreetti Markovin ketju
on Markovin satunnaisprosessi, jonka tilaavaruus on äärellinen tai laskettava, ja joukko indeksejä
- kaikkien ei-negatiivisten kokonaislukujen joukko tai jokin sen osajoukko (äärellinen tai laskettava). Voimme puhua entä lopputulos
th testit.

Usein on kätevää tunnistaa prosessin tila-avaruus ei-negatiivisten kokonaislukujen joukosta
ja näissä tapauksissa he sanovat sen on tilassa , Jos
.

Satunnaismuuttujan osumisen todennäköisyys
tilassa (kutsutaan yksivaiheisen siirtymän todennäköisyydeksi), kuten edellä mainittiin, on merkitty
, eli

Tämä merkintä korostaa, että yleisessä tapauksessa siirtymän todennäköisyydet eivät riipu pelkästään alku- ja lopputilasta, vaan myös siirtymän hetkestä.

Tapauksissa, joissa yksivaiheisen siirtymän todennäköisyydet eivät riipu aikamuuttujasta (ts. arvosta , sitten he sanovat, että Markovin prosessi on kiinteät siirtymän todennäköisyydet. Joten lisätarkoituksia varten panemme merkille, että on olemassa tasa-arvo, joka ei riipu , Ja tarkoittaa siirtymisen todennäköisyyttä tilasta yhdessä kokeessa tilassa .

Yleensä todennäköisyyksiä yhdistetty neliömatriisiin (äärelliseen tai laskettavaan) tarkasteltavasta prosessista riippuen:

,

ja sitä kutsutaan Markov-matriisiksi tai siirtymän todennäköisyysmatriisi Markovin ketju.

Matriisissa
i-rivi edustaa r.v:n todennäköisyysjakaumaa.
edellyttäen että
. Jos tilojen määrä on äärellinen, niin - äärellinen neliömatriisi, jonka järjestys (rivien lukumäärä) on yhtä suuri kuin tilojen lukumäärä.

Luonnollisesti todennäköisyydet täyttää seuraavat kaksi ehtoa:

A)
,

b)
jokaiselle kiinteälle

Ehto b) kuvastaa sitä tosiasiaa, että jokainen koe aiheuttaa jonkin verran siirtymää tilasta toiseen. Mukavuuden vuoksi puhumme yleensä myös siirtyminen ja siinä tapauksessa, että tila pysyy muuttumattomana. On olemassa väite.

Lause 17.2.Prosessi on täysin määritelty, jos todennäköisyydet on annettu(46), eli

ja satunnaismuuttujan todennäköisyysjakauma .

Todiste. Osoittakaamme se mille tahansa äärelliselle miten todennäköisyydet lasketaan

koska kokonaistodennäköisyyskaavan mukaan kaikki muut satunnaismuuttujiin liittyvät todennäköisyydet voidaan saada summaamalla muodon (47) termejä (jäseniä).

Ehdollisen todennäköisyyden määritelmän mukaan meillä on

Mutta Markovin prosessin määritelmän saamme

Laittamalla tasa-arvon (49) arvoon (48) saadaan

Jatkamalla tätä prosessia peräkkäin, saamme:

Prosessi on täysin määritelty. Mitä piti todistaa.

Jonoteoria on yksi todennäköisyysteorian haaroista. Tämä teoria harkitsee todennäköisyys ongelmia ja matemaattisia malleja (ennen tätä tarkasteltiin deterministisiä matemaattisia malleja). Muistutetaan, että:

Deterministinen matemaattinen malli heijastaa objektin (järjestelmän, prosessin) käyttäytymistä perspektiivistä täyttä varmuutta nykyisyydessä ja tulevaisuudessa.

Todennäköisyyspohjainen matemaattinen malli ottaa huomioon satunnaisten tekijöiden vaikutuksen kohteen (järjestelmän, prosessin) käyttäytymiseen ja siksi arvioi tulevaisuutta tiettyjen tapahtumien todennäköisyyden näkökulmasta.

Nuo. täällä, kuten esimerkiksi peliteoriassa pohditaan ongelmia olosuhteissaepävarmuus.

Tarkastellaan ensin joitain käsitteitä, jotka luonnehtivat "stokastista epävarmuutta", kun ongelmaan sisältyvät epävarmat tekijät ovat satunnaismuuttujia (tai satunnaisfunktioita), joiden todennäköisyysominaisuudet ovat joko tiedossa tai kokemuksesta saatavia. Tällaista epävarmuutta kutsutaan myös "suotuisaksi", "suotuisaksi".

Satunnaisen prosessin käsite

Tarkkaan ottaen satunnaiset häiriöt ovat luontaisia ​​jokaiselle prosessille. On helpompi antaa esimerkkejä satunnaisesta prosessista kuin "ei-satunnaisesta" prosessista. Jopa esimerkiksi kellon käyttöprosessi (se näyttää olevan tiukasti kalibroitu työ - "toimii kuin kello") on alttiina satunnaisille muutoksille (liikkuminen eteenpäin, jäljessä, pysähtyminen). Mutta niin kauan kuin nämä häiriöt ovat merkityksettömiä ja niillä on vain vähän vaikutusta meitä kiinnostaviin parametreihin, voimme jättää ne huomiotta ja pitää prosessia deterministisenä, ei-satunnaisena.

Olkoon joku järjestelmä S(tekninen laite, tällaisten laitteiden ryhmä, tekninen järjestelmä - kone, työmaa, konepaja, yritys, teollisuus jne.). Järjestelmässä S vuotoja satunnainen prosessi, jos se muuttaa tilaansa ajan myötä (siirtyy tilasta toiseen), lisäksi aiemmin tuntemattomalla satunnaisella tavalla.

Esimerkkejä: 1. Järjestelmä S– tekninen järjestelmä (koneosa). Koneet hajoavat ajoittain ja niitä korjataan. Tässä järjestelmässä tapahtuva prosessi on satunnainen.

2. Järjestelmä S- ilma-alus, joka lentää tietyllä korkeudella tiettyä reittiä pitkin. Häiritsevät tekijät - sääolosuhteet, miehistön virheet jne., seuraukset - kuoppaisuus, lentoaikataulun rikkominen jne.

Markovin satunnainen prosessi

Järjestelmässä tapahtuvaa satunnaista prosessia kutsutaan Markovski, jos hetkeksikään t 0 prosessin todennäköisyysominaisuudet tulevaisuudessa riippuvat vain sen tilasta tällä hetkellä t 0 eivätkä riipu siitä, milloin ja miten järjestelmä saavutti tämän tilan.

Olkoon järjestelmä tietyssä tilassa hetkellä t 0 S 0 . Tiedämme järjestelmän nykytilan ominaisuudet, kaiken mitä tapahtui milloin t<t 0 (prosessihistoria). Voimmeko ennustaa (ennustaa) tulevaisuutta, ts. mitä tapahtuu milloin t>t 0 ? Ei aivan, mutta joitain prosessin todennäköisyysominaisuuksia voidaan löytää tulevaisuudessa. Esimerkiksi todennäköisyys, että jonkin ajan kuluttua järjestelmä S pystyvät S 1 tai jää tilaan S 0 jne.

Esimerkki. Järjestelmä S- ilmataisteluihin osallistuva ilma-alusten ryhmä. Antaa x- "punaisten" lentokoneiden lukumäärä, y– "sinisten" lentokoneiden lukumäärä. Siihen mennessä t 0 eloonjääneiden (ei alasammuttujen) lentokoneiden lukumäärä, vastaavasti – x 0 ,y 0 . Meitä kiinnostaa todennäköisyys, että tällä hetkellä numeerinen ylivoima on "punaisten" puolella. Tämä todennäköisyys riippuu siitä, missä tilassa järjestelmä oli sillä hetkellä t 0, eikä siihen, milloin ja missä järjestyksessä alas ammutut kuolivat tähän hetkeen asti t 0 lentokonetta.

Käytännössä Markovin prosesseja puhtaassa muodossaan ei yleensä kohdata. Mutta on prosesseja, joissa "esihistorian" vaikutus voidaan jättää huomiotta. Ja tällaisia ​​prosesseja tutkittaessa voidaan käyttää Markovin malleja (jonoteoria ei ota huomioon Markovin jonojärjestelmiä, mutta niitä kuvaava matemaattinen laite on paljon monimutkaisempi).

Operaatiotutkimuksessa Markovin satunnaiset prosessit, joissa on diskreetit tilat ja jatkuva aika, ovat erittäin tärkeitä.

Prosessi on ns erillinen tilaprosessi, jos se on mahdollista S 1 ,S 2, ... voidaan määrittää etukäteen, ja järjestelmän siirtyminen tilasta tilaan tapahtuu "hyppynä", melkein välittömästi.

Prosessi on ns jatkuva aikaprosessi, jos mahdollisten tilasta tilaan siirtymien hetket eivät ole ennalta määrättyjä, vaan ovat epävarmoja, satunnaisia ​​ja voivat tapahtua milloin tahansa.

Esimerkki. Tekninen järjestelmä (osio) S koostuu kahdesta koneesta, joista kukin voi epäonnistua (vikaa) satunnaisella hetkellä, jonka jälkeen alkaa välittömästi yksikön korjaus, joka jatkuu myös tuntemattoman, satunnaisen ajan. Seuraavat järjestelmätilat ovat mahdollisia:

S 0 - molemmat koneet toimivat;

S 1 - ensimmäistä konetta korjataan, toinen toimii;

S 2 - toista konetta korjataan, ensimmäinen toimii;

S 3 - molempia koneita korjataan.

Järjestelmän siirtymät S tilasta toiseen tapahtuu lähes välittömästi, satunnaisina hetkinä, kun tietty kone vioittuu tai korjaus on valmis.

Analysoitaessa satunnaisia ​​prosesseja diskreeteillä tiloilla on kätevää käyttää geometrista kaaviota - tilakaavio. Graafin kärjet ovat järjestelmän tiloja. Kuvaajan kaaret – mahdolliset siirtymät tilasta toiseen

Kuva 1. Järjestelmän tilakaavio

osavaltio. Esimerkissämme tilakaavio on esitetty kuvassa 1.

Huomautus. Siirtyminen tilasta S 0 tuumaa S 3 ei ole esitetty kuvassa, koska oletetaan, että koneet epäonnistuvat toisistaan ​​riippumatta. Emme ota huomioon mahdollisuutta molempien koneiden samanaikaiseen vikaan.

Luento 9

Markovin prosesseja
Luento 9
Markovin prosesseja



1

Markovin prosesseja

Markovin prosesseja
Järjestelmässä tapahtuvaa satunnaista prosessia kutsutaan
Markovian, jos sillä ei ole seurauksia. Nuo.
jos otetaan huomioon prosessin nykyinen tila (t 0) - as
läsnä, joukko mahdollisia tiloja ( (s),s t) - as
menneisyys, joukko mahdollisia tiloja ( (u),u t) - as
tulevaisuudessa, sitten Markov-prosessia varten kiinteäksi
nykyisyys, tulevaisuus ei riipu menneestä, vaan on määrätty
vain nykyhetkessä, eikä se riipu siitä, milloin ja miten järjestelmä
tuli tähän tilaan.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
2

Markovin prosesseja

Markovin prosesseja
Markovin satunnaiset prosessit on nimetty erinomaisen venäläisen matemaatikon A.A. Markovin mukaan, joka aloitti ensimmäisenä satunnaismuuttujien todennäköisyysyhteyden tutkimisen
ja loi teorian, jota voidaan kutsua "dynamiikaksi".
todennäköisyydet." Myöhemmin tämän teorian perusteet olivat
Satunnaisprosessien yleisen teorian alkuperusta sekä sellaiset tärkeät soveltavat tieteet kuin diffuusioprosessien teoria, luotettavuusteoria, jonoteoria jne.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
3

Markov Andrey Andreevich Markov Andrey Andreevich Markov Andrey Andreevich

Markovin prosesseja
Markov Andrey Andreevich
1856-1922
venäläinen matemaatikko.
Kirjoitti noin 70 teosta
teorioita
numerot,
teorioita
funktion approksimaatiot, teoriat
todennäköisyydet. Laajensi huomattavasti lain soveltamisalaa
suuri määrä ja keskeinen
rajalause. On
satunnaisprosessien teorian perustaja.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
4

Markovin prosesseja

Markovin prosesseja
Käytännössä Markovin prosessit puhtaassa muodossaan ovat yleensä
älä tapaa. Mutta on prosesseja, joissa "esihistorian" vaikutus voidaan jättää huomiotta, ja opiskellessa
Tällaisia ​​prosesseja varten voidaan käyttää Markovin malleja. SISÄÄN
Tällä hetkellä Markovin prosessien teoriaa ja sen sovelluksia käytetään laajasti useilla aloilla.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
5

Markovin prosesseja

Markovin prosesseja
Biologia: syntymän ja kuoleman prosessit - populaatiot, mutaatiot,
epidemiat.
Fysiikka:
radioaktiivinen
rappeutuu,
teoria
laskurit
alkuainehiukkaset, diffuusioprosessit.
Kemia:
teoria
jälkiä
V
ydin
valokuvaemulsiot,
kemiallisen kinetiikan todennäköisyysmallit.
Kuvat.jpg
Tähtitiede: fluktuaatioteoria
Linnunradan kirkkautta.
Jonoteoria: puhelinkeskukset,
korjaamot, lipputoimistot, infopisteet,
kone- ja muut tekniset järjestelmät, ohjausjärjestelmät
joustavat tuotantojärjestelmät, tietojenkäsittely palvelimilla.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
6

Markovin prosesseja

Markovin prosesseja
Olkoon järjestelmä tällä hetkellä t0 sisällä
tietty tila S0. Tunnemme ominaisuudet
järjestelmän nykytila ​​ja kaikki mitä tapahtui t< t0
(prosessin tausta). Voimmeko ennustaa tulevaisuutta,
nuo. mitä tapahtuu t > t0?
Ei aivan, mutta joitain todennäköisyysominaisuuksia
prosessi löytyy tulevaisuudessa. Esimerkiksi todennäköisyys, että
että hetken kuluttua
järjestelmä S on tilassa
S1 tai pysyy tilassa S0 jne.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
7

Markovin prosesseja. Esimerkki.

Markovin prosesseja
Markovin prosesseja. Esimerkki.
System S on ryhmä ilmataisteluihin osallistuvia lentokoneita. Olkoon x määrä
"punaiset" tasot, y - "sinisten" tasojen lukumäärä. Ajanhetkellä t0 selviytyneiden (ei alasammuttujen) lentokoneiden lukumäärä
vastaavasti – x0, y0.
Meitä kiinnostaa todennäköisyys, että tällä hetkellä
t 0 numeerinen ylivoima on "punaisten" puolella. Tämä todennäköisyys riippuu tilasta, jossa järjestelmä oli
hetkellä t0, eikä sillä, milloin ja missä järjestyksessä koneet ammuttiin alas ennen hetkeä t0 kuoli.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
8

Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Markovin prosessi äärellisellä tai laskettavalla luvulla
ajan tiloja ja hetkiä kutsutaan diskreeteiksi
Markovin ketju. Siirtyminen tilasta tilaan on mahdollista vain kokonaislukuisina ajanhetkenä.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
9

10. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja

Olettaa
Mitä
puhetta
tulossa
O
peräkkäisiä kolikonheittoja
heittopeli; siihen heitetään kolikko
ehdolliset ajanhetket t =0, 1, ... ja at
jokainen askel pelaaja voi voittaa ±1 s
sama
todennäköisyys
1/2,
kuten tämä
Siten hetkellä t sen kokonaisvahvistus on satunnaismuuttuja ξ(t), jonka mahdolliset arvot ovat j = 0, ±1, ... .
Edellyttäen, että ξ(t) = k, seuraavassa vaiheessa voitto on
on jo yhtä suuri kuin ξ(t+1) = k ± 1, ottaen arvot j = k ± 1 samalla todennäköisyydellä 1/2. Voidaan sanoa, että tässä tapahtuu vastaavalla todennäköisyydellä siirtymä tilasta ξ(t) = k tilaan ξ(t+1) = k ± 1.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
10

11. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Yleistäen tämän esimerkin voimme kuvitella järjestelmän
laskettava määrä mahdollisia tiloja, jotka ajan myötä
diskreetti aika t = 0, 1, ... liikkuu satunnaisesti tilasta toiseen.
Olkoon ξ(t) sen sijainti hetkellä t satunnaisten siirtymien ketjun seurauksena
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
11

12. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Analysoitaessa satunnaisia ​​prosesseja diskreeteillä tiloilla on kätevää käyttää geometristä kaaviota - graafia
valtioita. Graafin kärjet ovat järjestelmän tiloja. Kaavion kaaret
– mahdolliset siirtymät tilasta tilaan.
Heittopeli.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
12

13. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Merkitään kaikki mahdolliset tilat kokonaisluvuilla i = 0, ±1, ...
Oletetaan, että tunnetulle tilalle ξ(t) =i järjestelmä menee seuraavassa vaiheessa ehdollisella todennäköisyydellä tilaan ξ(t+1) = j
P( (t 1) j (t) i)
riippumatta hänen käyttäytymisestään menneisyydessä tai pikemminkin riippumatta
siirtymäketjusta hetkeen t:
P( (t 1) j (t) i; (t 1) it 1;...; (0) i0 )
P( (t 1) j (t) i)
Tätä kiinteistöä kutsutaan nimellä Markovian.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
13

14. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Määrä
pij P( (t 1) j (t) i)
kutsutaan todennäköisyydeksi
järjestelmän siirtyminen tilasta i tilaan j yhdessä vaiheessa
aika t 1.
Jos siirtymän todennäköisyys ei riipu t:stä, niin piiri
Markovia kutsutaan homogeeniseksi.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
14

15. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Matriisi P, jonka alkiot ovat todennäköisyydet
siirtymäpij:tä kutsutaan siirtymämatriisiksi:
p11...p1n
P p 21 ... s 2n
s
n1...pnn
Se on stokastinen, ts.
pij 1;
i
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
p ij 0.
15

16. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja
Diskreetit Markovin ketjut. Esimerkki
Siirtymämatriisi heittopeliin
...
k 2
k 2
0
k 1
1/ 2
k
0
k 1
k
k 1
k 2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16

17. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja
Diskreetit Markovin ketjut. Esimerkki
Maaperän kemiallisen analyysin tuloksena puutarhuri arvioi
sen kunto on yksi kolmesta numerosta - hyvä (1), tyydyttävä (2) tai huono (3). Monien vuosien havaintojen seurauksena puutarhuri huomasi
että maaperän tuottavuus nykyisessä
vuosi riippuu vain sen tilasta
Edellinen vuosi. Siksi todennäköisyydet
maaperän siirtyminen yhdestä tilasta toiseen
toinen voidaan esittää seuraavasti
Markovin ketju matriisilla P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
17

18. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja
Diskreetit Markovin ketjut. Esimerkki
Puutarhuri voi kuitenkin maatalouskäytäntöjen seurauksena muuttaa siirtymän todennäköisyyksiä matriisissa P1.
Sitten matriisi P1 korvataan
matriisiin P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
18

19. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Tarkastellaan kuinka prosessin tilat muuttuvat ajan myötä. Tarkastellaan prosessia peräkkäisillä ajanhetkillä, alkaen hetkestä 0. Asetetaan alkuperäinen todennäköisyysjakauma p(0) ( p1 (0),..., pm (0)), missä m on tilojen lukumäärä prosessin pi (0) on löytämisen todennäköisyys
prosessi tilassa i alkuhetkellä. Todennäköisyyttä pi(n) kutsutaan tilan ehdottomaksi todennäköisyydeksi
minä hetkellä n 1.
Vektorin p (n) komponentit osoittavat, mitkä piirin mahdollisista tiloista hetkellä n ovat eniten
todennäköistä.
m
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
pk(n) 1
k 1
19

20. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Kun tiedät sekvenssin ( p (n)) arvolle n 1,... voit saada käsityksen järjestelmän käyttäytymisestä ajan kuluessa.
3-tilan järjestelmässä
p11 p12 p13
P p21
s
31
p22
p32
p23
p33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
Yleisesti:
p j (1) pk (0) pkj
p j (n 1) pk (n) pkj
k
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
k
p(n 1) p(n) P
20

21. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja
Diskreetit Markovin ketjut. Esimerkki
Matriisi
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Vaihe
(p(n))
n
0
1, 0, 0
n
1
0.2 , 0.5 , 0.3
n
2
0.04 , 0.35 , 0.61
n
3
0.008 , 0.195 , 0.797
n
4
0.0016 , 0.1015 , 0.8969
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
21

22. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
n
Siirtymämatriisi n vaiheelle P(n) P .
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
p(2) p(0) P
2
p(2)
P(2) P2
1, 0, 0
0.0016
0.
0.
0.0016
0.
0.
0.1015
0.0625
0.
0.1015
0.0625
0.
0.8969
0.9375
1.
0.8969
0.9375
1.
0.04 , 0.35 , 0.61
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
22

23. Diskreetit Markovin ketjut

Markovin prosesseja
Diskreetit Markovin ketjut
Miten Markovin ketjut käyttäytyvät n:n kohdalla?
Homogeeniselle Markov-ketjulle pätee tietyissä olosuhteissa seuraava ominaisuus: p (n) n:lle.
Todennäköisyydet 0 eivät riipu alkujakaumasta
p(0) , ja ne määritetään vain matriisin P avulla. Tässä tapauksessa sitä kutsutaan kiinteäksi jakaumaksi, ja itse ketjua kutsutaan ergodiseksi. Ergodisuusominaisuus tarkoittaa, että kun n kasvaa
tilojen todennäköisyys lakkaa käytännössä muuttumasta ja järjestelmä siirtyy vakaaseen toimintatilaan.
i
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
23

24. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja
Diskreetit Markovin ketjut. Esimerkki
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
0 0 1
P() 0 0 1
0 0 1
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
p()(0,0,1)
24

25. Diskreetit Markovin ketjut. Esimerkki

Markovin prosesseja
Diskreetit Markovin ketjut. Esimerkki
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
0.1017 0.5254 0.3729
P() 0,1017 0,5254 0,3729
0.1017 0.5254 0.3729
p() (0,1017,0,5254,0,3729)
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
25

26. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja

Prosessia kutsutaan jatkuvaaikaiseksi prosessiksi, jos
mahdollisten tilasta tilaan siirtymien hetket eivät ole ennalta määrättyjä, vaan ne ovat epävarmoja, satunnaisia ​​ja voivat tapahtua
milloin tahansa.
Esimerkki. Teknologinen järjestelmä S koostuu kahdesta laitteesta,
joista jokainen voi poistua satunnaisella hetkellä
rakennus, jonka jälkeen alkaa välittömästi yksikön korjaus, joka jatkuu myös tuntemattoman, satunnaisen ajan.
Seuraavat järjestelmätilat ovat mahdollisia:
S0 - molemmat laitteet toimivat;
S1 - ensimmäistä laitetta korjataan, toinen toimii kunnolla;
S2 - toista laitetta korjataan, ensimmäinen toimii kunnolla;
S3 - molempia laitteita korjataan.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
26

27. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja
Jatkuva-aikaiset Markov-prosessit
Järjestelmässä S tapahtuu siirtymiä tilasta tilaan
lähes välittömästi, satunnaisina epäonnistumisaikoina
yksi tai toinen laite tai
korjausten valmistuminen.
Samanaikaisuuden todennäköisyys
molempien laitteiden vika
voidaan jättää huomiotta.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
27

28. Tapahtumavirrat

Markovin prosesseja
Tapahtumastreamit
Tapahtumavirta on homogeenisten tapahtumien sarja, jotka seuraavat peräkkäin satunnaisina hetkinä.
on tapahtumien keskimääräinen määrä
Tapahtumavirran intensiteetti
aikayksikköä kohti.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
28

29. Tapahtumavirrat

Markovin prosesseja
Tapahtumastreamit
Tapahtumavirtaa kutsutaan paikallaan pysyväksi, jos sen todennäköisyysominaisuudet eivät riipu ajasta.
Erityisesti intensiteetti
tasainen virtaus on vakio. Tapahtumien virtauksessa on väistämättä tiivistymisiä tai harvinaisuuksia, mutta ne eivät ole säännöllisiä, ja tapahtumien keskimääräinen määrä aikayksikköä kohti on vakio eikä riipu ajasta.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
29

30. Tapahtumavirrat

Markovin prosesseja
Tapahtumastreamit
Tapahtumien virtaa kutsutaan virtaukseksi ilman seurauksia
mitkä tahansa kaksi ei-päällekkäistä ajanjaksoa ja jompaankumpaan osuvien tapahtumien määrä ei riipu siitä, kuinka monta tapahtumaa sattuu toiseen. Toisin sanoen tämä tarkoittaa, että tapahtumat, jotka muodostavat virtauksen, ilmestyvät tiettyinä hetkinä
aikaa toisistaan ​​riippumatta ja kukin omien syidensä aiheuttama.
Tapahtumien kulkua kutsutaan tavalliseksi, jos kahden tai useamman tapahtuman todennäköisyys alkeissegmentissä t on merkityksetön verrattuna yhden tapahtuman todennäköisyyteen.
tapahtumia, ts. tapahtumat näkyvät siinä yksitellen, eivät useiden ryhmissä kerralla
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
30

31. Tapahtumavirrat

Markovin prosesseja
Tapahtumastreamit
Tapahtumien kulkua kutsutaan yksinkertaisimmiksi (tai kiinteäksi Poissoniksi), jos sillä on kolme ominaisuutta kerralla: 1) stationäärinen, 2) tavallinen, 3) ei ole seurauksia.
Yksinkertaisimmalla virtauksella on yksinkertaisin matemaattinen kuvaus. Hän soittaa virtojen joukossa samaa erikoista
rooli, kuten normaalijakauman laki mm
jakautumisen lakeja. Nimittäin kun päällekkäin riittävän suuri määrä itsenäisiä, kiinteitä ja tavallisia
virtaukset (voimakkuudeltaan verrattavissa toisiinsa), tuloksena on virtaus, joka on lähellä yksinkertaisinta.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
31

32. Tapahtumavirrat

Markovin prosesseja
Tapahtumastreamit
Yksinkertaisimpaan virtaukseen intensiteetillä
intervalli
aika T viereisten tapahtumien välillä on eksponentiaalinen
jakautuminen tiheyden kanssa
p(x) ex, x0.
Satunnaismuuttujalle T, jolla on eksponentiaalinen jakauma, matemaattinen odotus on parametrin käänteisluku.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
32

33. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja
Jatkuva-aikaiset Markov-prosessit
Kun otetaan huomioon prosessit, joissa on diskreetit tilat ja jatkuva aika, voidaan olettaa, että kaikki järjestelmän S siirtymät tilasta tilaan tapahtuvat vaikutuksen alaisena.
yksinkertaiset tapahtumavirrat (puheluvirrat, vikavirrat, palautusvirrat jne.).
Jos kaikki tapahtumavirrat, jotka siirtävät järjestelmän S tilasta tilaan, ovat yksinkertaisimpia, prosessi, joka tapahtuu
järjestelmä on Markovian.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
33

34. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja
Jatkuva-aikaiset Markov-prosessit
Toimikoon tilassa oleva järjestelmä
yksinkertaisin tapahtumakulku. Heti kun tämän virtauksen ensimmäinen tapahtuma ilmestyy, järjestelmä "hyppää" tilasta
kuntoon.
- järjestelmän siirtävien tapahtumien intensiteetti
valtiolta
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
V
.
34

35. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja
Jatkuva-aikaiset Markov-prosessit
Olkoon tarkasteltavalla järjestelmällä S
mahdolliset tilat
. Todennäköisyys p ij (t) on tilasta i tilaan j siirtymisen todennäköisyys ajassa t.
i:nnen tilan todennäköisyys
on se todennäköisyys
että hetkellä t järjestelmä on tilassa
. Ilmeisesti milloin tahansa määrä
kaikista tilatodennäköisyyksistä on yhtä suuri kuin yksi:
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
35

36. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja
Jatkuva-aikaiset Markov-prosessit
Löytää kaikki tilatodennäköisyydet
Miten
Ajan funktiot, Kolmogorov-differentiaaliyhtälöt kootaan ja ratkaistaan ​​- erityinen yhtälön tyyppi, jossa tuntemattomat funktiot ovat tilojen todennäköisyyksiä.
Siirtymistodennäköisyydet:
p ij (t) p ik (t) kj
k
Ehdottomille todennäköisyyksille:
p j (t) p k (t) kj
k
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
36

37. Kolmogorov Andrei Nikolajevitš

Markovin prosesseja
Kolmogorov Andrei Nikolajevitš
1903-1987
Suuri venäläinen
matemaatikko.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
37

38. Markov-prosessit jatkuvalla ajalla

Markovin prosesseja
Jatkuva-aikaiset Markov-prosessit
- vikavirtauksen intensiteetti;
- palautumisvirran intensiteetti.
Anna järjestelmän olla tilassa
S0. Virta siirtää sen tilaan S1
ensimmäisen laitteen vikoja. Sen intensiteetti on
Missä
- laitteen keskimääräinen käyttöaika.
Järjestelmä siirtyy tilasta S1 tilaan S0 palautusten virtauksen avulla
ensimmäinen laite. Sen intensiteetti on
Missä
- Keskimääräinen aika ensimmäisen koneen korjaamiseen.
Tapahtumavirtojen intensiteetit, jotka siirtävät järjestelmän graafin kaikkia kaaria pitkin, lasketaan samalla tavalla.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
38

39. Jonotusjärjestelmät

Markovin prosesseja

Esimerkkejä jonopalvelujärjestelmistä (QS): puhelinkeskukset, korjaamot,
lippu
kassakoneet,
viite
virasto,
työstökoneet ja muut teknologiset järjestelmät,
järjestelmät
hallinta
joustava
tuotantojärjestelmät,
tietojenkäsittely palvelimilla jne.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
39

40. Jonojärjestelmät

Markovin prosesseja
Jonotusjärjestelmät
QS koostuu tietystä määrästä annoksia
yksiköt, joita kutsutaan palvelukanaviksi (nämä ovat
koneet, robotit, viestintälinjat, kassat jne.). Mikä tahansa SMO
on suunniteltu palvelemaan satunnaisesti saapuvien sovellusten (vaatimusten) virtaa.
Pyynnön palvelu jatkuu satunnaisen ajan, jonka jälkeen kanava vapautuu ja on valmis vastaanottamaan seuraavan
sovellukset.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
40

41. Jonojärjestelmät

Markovin prosesseja
Jonotusjärjestelmät
QS-toimintaprosessi on satunnainen prosessi, jossa on diskreetti
tilat ja jatkuva aika. QS:n tila muuttuu äkillisesti joidenkin tapahtumien esiintymishetkellä
(uuden pyynnön saapuminen, palvelun päättyminen, hetki,
kun odottamiseen kyllästynyt sovellus poistuu jonosta).
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
41

42. Jonojärjestelmät

Markovin prosesseja
Jonotusjärjestelmät
Jonojärjestelmien luokittelu
1. QS epäonnistumisineen;
2. Jono jonon kanssa.
QS:ssä, jossa on hylkäys, hakemus, joka vastaanotetaan ajankohtana, jolloin kaikki kanavat ovat varattu, saa kieltäytymisen, poistuu QS:stä eikä ole enää
tarjoillaan.
Jonollisessa QS:ssä pyyntö, joka saapuu ajankohtana, jolloin kaikki kanavat ovat varattu, ei lähde, vaan menee jonoon ja odottaa mahdollisuutta palvella.
QS jonoilla on jaettu eri tyyppeihin riippuen
riippuu siitä, miten jono on järjestetty - rajoitettu vai rajoittamaton. Rajoitukset voivat koskea sekä jonon pituutta että aikaa
odotukset, "palvelukuri".
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
42

43. Jonotusjärjestelmät

Markovin prosesseja
Jonotusjärjestelmät
Jonoteorian aiheena on rakentaminen
matemaattiset mallit, jotka yhdistävät tietyt ehdot
QS:n toiminta (kanavien määrä, niiden suorituskyky, säännöt
työ, sovellusvirran luonne) meitä kiinnostavilla ominaisuuksilla - QS:n tehokkuuden indikaattoreita. Nämä indikaattorit kuvaavat QS:n kykyä selviytyä virtauksesta
sovellukset. Ne voivat olla: QS:n palvelemien sovellusten keskimääräinen määrä aikayksikköä kohti; varattujen kanavien keskimääräinen määrä; jonossa olevien hakemusten keskimääräinen määrä; keskimääräinen odotusaika palveluun jne.
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit"
43

44.

KIITOS
HUOMIOON!!!
44

45. Muodosta siirtymägraafi

Markovin prosesseja
Rakenna siirtymäkaavio
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
KHNURE, osasto PM, luennoitsija Kirichenko L.O.
"Todennäköisyysteoria, matemaattinen
tilastot ja satunnaiset prosessit" Operaatioita tutkiessa törmää usein uudelleenkäytettäviin järjestelmiin vastaavien ongelmien ratkaisussa. Tässä tapauksessa syntyviä prosesseja kutsutaan palveluprosessit, ja järjestelmät - jonotusjärjestelmät (QS). Esimerkkejä tällaisista järjestelmistä ovat puhelinjärjestelmät, korjaamot, tietokonekompleksit, lipputoimistot, kaupat, kampaajat jne.
Jokainen QS koostuu tietystä määrästä palveluyksiköitä (instrumentit, laitteet, pisteet, asemat), joita kutsumme kanavia palvelua. Kanavat voivat olla viestintälinjoja, työpisteitä, tietokoneita, myyjiä jne. Kanavien lukumäärän perusteella QS jaetaan yksikanavainen Ja monikanavainen.
Hakemuksia ei yleensä vastaanoteta CMO:lle säännöllisesti, vaan satunnaisesti, jolloin muodostuu ns satunnainen sovellusvirta (vaatimukset). Pyyntöjen palvelu jatkuu yleisesti ottaen myös jonkin aikaa satunnaisesti. Sovellusvirran ja palveluajan satunnaisuus johtaa siihen, että QS kuormittuu epätasaisesti: joinakin ajanjaksoina sovelluksia kertyy hyvin suuri määrä (ne joko joutuvat jonoon tai jättävät QS:n käyttämättä), toisinaan QS toimii alikuormituksella tai tyhjäkäynnillä.
Aiheena jonoteoria on matemaattisten mallien rakentaminen, jotka yhdistävät QS:n määritellyt toimintaolosuhteet (kanavien lukumäärä, niiden tuottavuus, pyyntövirran luonne jne.) QS:n suorituskykyindikaattoreihin, jotka kuvaavat sen kykyä selviytyä virtauksesta pyynnöistä.

Kuten tulosindikaattori QS:tä käytetään: keskimääräinen (jäljempänä keskiarvot ymmärretään vastaavien satunnaismuuttujien matemaattisiksi odotuksiksi) palveltujen pyyntöjen määrä aikayksikköä kohti; jonossa olevien hakemusten keskimääräinen määrä; keskimääräinen odotusaika palveluun; mahdollisuus palvelun epäämiseen odottamatta; todennäköisyys, että jonossa olevien sovellusten määrä ylittää tietyn arvon jne.

QS on jaettu kahteen päätyyppiin (luokkaan): CMO, jossa on epäonnistumisia ja href="cmo_length.php">CMO ja odottaa (jono). QS:ssä, jossa on kieltäytyminen, hakemus, joka on vastaanotettu ajankohtana, jolloin kaikki kanavat ovat varattu, saa kieltäytymisen, poistuu QS:stä eikä osallistu jatkopalveluprosessiin (esim. puhelinkeskustelupyyntö aikana, jolloin kaikki kanavat ovat varattu, saa kieltäytymisen ja jättää QS:n toimittamatta). Odottavassa QS:ssä pyyntö, joka saapuu aikana, jolloin kaikki kanavat ovat varattu, ei lähde, vaan joutuu palvelujonoon.
Jonot, joissa on odotus, jaetaan eri tyyppeihin riippuen siitä, miten jono on järjestetty: rajoitettu tai rajoittamaton jonon pituus, rajoitettu odotusaika jne.
QS:n työprosessi on satunnainen prosessi.
Alla satunnainen (todennäköisyys tai stokastinen) prosessi viittaa prosessiin, jossa järjestelmän tila muuttuu ajan myötä todennäköisyyslakien mukaisesti.
Prosessi on ns prosessi, jossa on erilliset tilat, jos sen mahdolliset tilat S 1, S 2, S 3 ... voidaan listata etukäteen ja järjestelmän siirtyminen tilasta tilaan tapahtuu välittömästi (hyppynä). Prosessi on ns jatkuva aikaprosessi jos järjestelmän mahdollisten tilasta tilaan siirtymien hetket eivät ole ennalta määrättyjä, vaan ovat satunnaisia.
QS-toimintaprosessi on satunnainen prosessi, jossa on diskreetit tilat ja jatkuva aika. Tämä tarkoittaa, että QS:n tila muuttuu äkillisesti satunnaisina hetkinä joidenkin tapahtumien sattuessa (esimerkiksi uuden pyynnön saapuminen, palvelun päättyminen jne.).
QS:n operaation matemaattinen analyysi yksinkertaistuu merkittävästi, jos tämän operaation prosessi on Markovin. Satunnaisprosessia kutsutaan Markovian tai satunnainen prosessi ilman seurauksia, jos millä tahansa ajanhetkellä t 0 prosessin todennäköisyysominaisuudet tulevaisuudessa riippuvat vain sen tilasta tietyllä hetkellä t 0 eivätkä riipu siitä, milloin ja miten järjestelmä on joutunut tähän tilaan.

Esimerkki Markovin prosessista: järjestelmä S on taksimittari. Järjestelmän tilaa hetkellä t kuvaa autolla tähän hetkeen mennessä kulkemien kilometrien määrä (kilometrien kymmenesosia). Olkoon laskuri S 0 hetkellä t 0 . Todennäköisyys, että tällä hetkellä t > t 0 laskuri näyttää tämän tai sen kilometrimäärän (tarkemmin sanoen vastaavan ruplamäärän) S 1 riippuu S 0 :sta, mutta ei riipu siitä, millä hetkellä laskurin lukemat muuttunut ennen hetkeä t 0 .
Monia prosesseja voidaan pitää suunnilleen Markovina. Esimerkiksi shakin pelaamisen prosessi; S järjestelmä - shakkinappuloiden ryhmä. Järjestelmän tilaa kuvaa pelilaudalla jäljellä olevien vihollisen nappuloiden määrä hetkellä t 0 . Todennäköisyys, että tällä hetkellä t > t 0 aineellinen etu on jonkun vastustajan puolella, riippuu ensisijaisesti järjestelmän tilasta hetkellä t 0, eikä siitä, milloin ja missä järjestyksessä nappulat katosivat lauta t 0 asti .
Joissakin tapauksissa tarkasteltavien prosessien esihistoria voidaan yksinkertaisesti jättää huomiotta ja niitä voidaan tutkia Markovin mallien avulla.
Diskreetin tilan satunnaisprosesseja analysoitaessa on kätevää käyttää geometristä kaaviota - ns. tilakaavio. Tyypillisesti järjestelmän tilat on kuvattu suorakulmioilla (ympyröillä), ja mahdolliset siirtymät tilasta tilaan esitetään tilat yhdistävillä nuolilla (suuntautuneilla kaarilla).
Tehtävä 1. Muodosta tilakaavio seuraavasta satunnaisprosessista: laite S koostuu kahdesta solmusta, joista kukin voi epäonnistua satunnaisella ajanhetkellä, jonka jälkeen solmun korjaus alkaa välittömästi ja jatkuu aiemmin tuntemattoman satunnaisen ajan.

Ratkaisu. Mahdolliset järjestelmän tilat: S 0 - molemmat solmut toimivat; S 1 - ensimmäistä yksikköä korjataan, toinen on toiminnassa; S 2 - toista yksikköä korjataan, ensimmäinen toimii; S 3 - molempia yksiköitä korjataan. Järjestelmäkaavio on esitetty kuvassa 1.
Riisi. 1
Esimerkiksi S 0:sta S1:een suunnattu nuoli tarkoittaa järjestelmän siirtymää ensimmäisen solmun vian hetkellä, S1:stä S 0:aan - siirtymää tämän solmun korjauksen valmistuttua.
Kaaviossa ei ole nuolia S 0:sta S 3:een ja S 1:stä S 2:een. Tämä selittyy sillä, että solmujen vikojen oletetaan olevan toisistaan ​​riippumattomia ja esimerkiksi kahden solmun samanaikaisen vian todennäköisyydellä (siirtymä S 0:sta S 3:een) tai kahden solmun korjausten samanaikaisella valmistumiselle (siirtymä). S 3 - S 0) voidaan jättää huomiotta.

Tapahtumavirta

Markovin satunnaisprosessin matemaattista kuvausta varten, jossa on diskreetit tilat ja jatkuva aika, joka virtaa QS:ssä, tutustumme yhteen todennäköisyysteorian tärkeistä käsitteistä - tapahtumavirran käsitteeseen.
Alla tapahtumien virta tarkoitetaan homogeenisten tapahtumien sarjaa, jotka seuraavat peräkkäin satunnaisina hetkinä (esimerkiksi puhelujen virta puhelinkeskuksessa, tietokonevikojen virta, asiakasvirta jne.).
Virtaus on karakterisoitu intensiteettil- tapahtumien esiintymistiheys tai QS:ään saapuvien tapahtumien keskimääräinen määrä aikayksikköä kohti.
Tapahtumavirtaa kutsutaan säännöllinen, jos tapahtumat seuraavat toisiaan tietyin tasaisin aikavälein. Esimerkiksi tuotteiden virtaus kokoonpanopajan kokoonpanolinjalla (vakionopeudella) on säännöllistä.
Tapahtumavirtaa kutsutaan paikallaan, jos sen todennäköisyysominaisuudet eivät riipu ajasta. Erityisesti paikallaan olevan virtauksen intensiteetti on vakioarvo: l(t)=l. Esimerkiksi autojen virtaus kaupunkikadulla ei ole paikallaan päivällä, mutta tätä virtausta voidaan pitää paikallaan päivällä, esimerkiksi ruuhka-aikoina. Huomaa, että jälkimmäisessä tapauksessa aikayksikköä kohti (esimerkiksi joka minuutti) kulkevien autojen todellinen määrä voi poiketa toisistaan ​​huomattavasti, mutta niiden keskimääräinen lukumäärä on vakio eikä riipu ajasta.
Tapahtumavirtaa kutsutaan virtaus ilman jälkivaikutuksia, jos kahdella ei-päällekkäisellä ajanjaksolla t 1 ja t 2 - yhdelle niistä osuvien tapahtumien lukumäärä ei riipu muiden tapahtumien lukumäärästä. Esimerkiksi metroon tulevalla matkustajavirralla ei ole käytännössä mitään jälkivaikutusta. Ja vaikkapa tiskiltä ostoksineen poistuvien asiakkaiden virralla on jo jälkivaikutus (jos vain siksi, että yksittäisten asiakkaiden välinen aika ei voi olla pienempi kuin kunkin asiakkaan vähimmäispalveluaika).
Tapahtumavirtaa kutsutaan tavallinen, jos kahden tai useamman tapahtuman todennäköisyys pienellä (alkeis) aikavälillä Dt on mitätön verrattuna yhden tapahtuman todennäköisyyteen. Toisin sanoen tapahtumavirta on tavallinen, jos tapahtumat esiintyvät siinä yksittäin, eivät ryhmissä. Esimerkiksi asemaa lähestyvien junien virtaus on tavallista, mutta autojen virtaus ei ole tavallista.
Tapahtumavirta on ns yksinkertaisin ( tai paikallaan oleva Poisson), jos se on samanaikaisesti paikallaan, tavallinen eikä sillä ole jälkivaikutusta. Nimi "yksinkertaisin" selittyy sillä, että yksinkertaisimmilla virroilla QS:llä on yksinkertaisin matemaattinen kuvaus. Huomaa, että säännöllinen virtaus ei ole "yksinkertaisin", koska sillä on jälkivaikutus: tapahtumien esiintymishetket sellaisessa virrassa ovat tiukasti kiinni.
Yksinkertaisin virtaus rajana syntyy satunnaisprosessien teoriassa yhtä luonnollisesti kuin todennäköisyysteoriassa normaalijakauma esiintyy rajana satunnaismuuttujien summalle: asettamalla (superpositio) riittävän suuri määrä n itsenäistä, paikallaan olevaa ja tavallista virtausta (voimakkuudeltaan toisiinsa verrattavissa) l 1 (i=1,2, ..., n) tuloksena on virtaus, joka on lähellä yksinkertaisinta intensiteetillä l, yhtä suuri kuin saapuvien virtojen intensiteettien summa, nuo.
Tarkastellaan aika-akselilla Ot (Kuva 2) yksinkertaisin tapahtumien kulku rajoittamattomana satunnaisten pisteiden sarjana.
Riisi. 2
Voidaan osoittaa, että yksinkertaisimmalla virtauksella numero T mielivaltaiselle ajanjaksolle t osuvat tapahtumat (pisteet) jaetaan Poissonin laki , (1)
jolle satunnaismuuttujan matemaattinen odotus on yhtä suuri kuin sen varianssi: a=s 2 =lt.
Erityisesti todennäköisyys, että mitään tapahtumaa ei tapahdu ajan t aikana (m = 0), on yhtä suuri kuin (2)
Etsitään aikavälin jakauma T yksinkertaisimman virtauksen mielivaltaisen kahden vierekkäisen tapahtuman välillä.
Kohdan (15.2) mukaisesti todennäköisyys, että ajanjaksolla, jonka pituus on t, ei esiinny mitään myöhemmistä tapahtumista, on yhtä suuri kuin (3).
ja päinvastaisen tapahtuman todennäköisyys, ts. satunnaismuuttujan jakaumafunktio T, kyllä ​​(4)
Satunnaismuuttujan todennäköisyystiheys on sen jakaumafunktion derivaatta (kuva 3), ts. (5)
Riisi. 3
Kutsutaan todennäköisyystiheyden (5) tai jakaumafunktion (4) määrittämää jakaumaa suuntaa antava(tai eksponentiaalinen). Siten kahden vierekkäisen mielivaltaisen tapahtuman välisellä aikavälillä on eksponentiaalinen jakauma, jonka matemaattinen odotus on yhtä suuri kuin satunnaismuuttujan (6) keskihajonta.
ja päinvastoin virtausvoimakkuuden l mukaan.
Eksponenttijakauman tärkein ominaisuus (vain eksponentiaalijakaumaan sisältyvä) on seuraava: jos eksponentiaalisen lain mukaan jakautunut aikajakso on kestänyt jo jonkin aikaa t, niin tämä ei vaikuta jakautumislakiin millään tavalla. välin (T-t) jäljellä olevasta osasta: se on sama kuin ja koko intervallin T jakautumislaki.
Toisin sanoen aikavälille T kahden peräkkäisen naapuritapahtuman välillä eksponentiaalisesti jakautuneen vuon välillä, mikään tieto siitä, kuinka kauan tämä aikaväli kesti, ei vaikuta jäljellä olevan osan jakautumislakiin. Tämä eksponentiaalisen lain ominaisuus on pohjimmiltaan toinen muotoilu "jälkivaikutuksen puuttumiselle" - yksinkertaisimman virtauksen pääominaisuus.
Yksinkertaisimmalla virtauksella, jonka intensiteetti on l, osumisen todennäköisyys alkeis (pieni) vähintään yhden virtaustapahtuman aikaväli Dt on yhtä suuri kuin (4)
(7)
(Huomaa, että tämä likimääräinen kaava, joka saadaan korvaamalla funktio e-lDt vain kaksi ensimmäistä termiä sen laajenemisesta Dt:n tehoissa, mitä tarkempi on pienempi Dt).

Jonojärjestelmälle on ominaista satunnainen prosessi. Järjestelmässä tapahtuvan satunnaisen prosessin ja sen matemaattisen ilmaisun tutkiminen on jonoteorian aihe.

Jonojärjestelmän toiminnan matemaattinen analyysi helpottuu suuresti, jos tämän toiminnon satunnainen prosessi on Markovski. Järjestelmässä tapahtuvaa prosessia kutsutaan Markoviksi, jos järjestelmän minkä tahansa tilan todennäköisyys tulevaisuudessa riippuu vain järjestelmän tilasta tällä hetkellä, eikä se riipu siitä, kuinka järjestelmä on joutunut tähän tilaan. . Talousjärjestelmien tutkimuksessa käytetään laajimmin Markovin satunnaisprosesseja, joissa on diskreetit ja jatkuvat tilat.

Satunnaisprosessia kutsutaan prosessi, jossa on erilliset tilat, jos kaikki sen mahdolliset tilat voidaan listata etukäteen, ja itse prosessi koostuu siitä, että järjestelmä hyppää aika ajoin tilasta toiseen.

Satunnaisprosessia kutsutaan prosessi jatkuvassa tilassa, jos sille on ominaista tasainen, asteittainen siirtyminen tilasta tilaan.

Voimme myös erottaa Markovin prosessit diskreetti Ja jatkuva aika. Ensimmäisessä tapauksessa järjestelmän siirtymät tilasta toiseen ovat mahdollisia vain tiukasti määritellyillä, ennalta määrätyillä ajanhetkillä. Toisessa tapauksessa järjestelmän siirtyminen tilasta tilaan on mahdollista millä tahansa aiemmin tuntemattomalla, satunnaisella hetkellä. Jos siirtymän todennäköisyys ei riipu ajasta, kutsutaan Markovin prosessia homogeeninen.

Jonojärjestelmien tutkimuksessa satunnaiset Markov-prosessit, joissa on diskreetit tilat ja jatkuva aika, ovat erittäin tärkeitä.

Markovin prosessien tutkiminen rajoittuu siirtymän todennäköisyysmatriisien () tutkimukseen. Jokainen tällaisen matriisin elementti (tapahtumavirta) edustaa todennäköisyyttä siirtyä tietystä tilasta (vastaa riviä) seuraavaan tilaan (vastaa saraketta). Tämä matriisi tarjoaa kaikki mahdolliset tietyn tilajoukon siirtymät. Näin ollen prosesseilla, joita voidaan kuvata ja mallintaa käyttämällä siirtymän todennäköisyysmatriiseja, on oltava riippuvuus tietyn tilan todennäköisyydestä välittömästi edeltävästä tilasta. Näin se rivittyy Markovin ketju. Tässä tapauksessa ensimmäisen asteen Markov-ketju on prosessi, jossa kukin tietty tila riippuu vain edellisestä tilastaan. Toisen ja korkeamman asteen Markovin ketju on prosessi, jossa nykyinen tila riippuu kahdesta tai useammasta edellisestä.

Alla on kaksi esimerkkiä siirtymän todennäköisyysmatriiseista.

Siirtymätodennäköisyysmatriisit voidaan esittää siirtymätilakaavioilla, kuten kuvassa näkyy.

Esimerkki

Yritys valmistaa tuotetta, joka on kyllästänyt markkinat. Jos yritys saa voittoa (P) tuotteen myynnistä kuluvan kuukauden aikana, niin se saa seuraavan kuukauden todennäköisyydellä 0,7 voittoa ja 0,3 todennäköisyydellä tappiota. Jos yritys saa kuluvana kuukautena tappiota (L), niin se saa seuraavan kuukauden todennäköisyydellä 0,4 voittoa ja 0,6 todennäköisyydellä tappiota (todennäköisyysarviot saatiin kyselyn tuloksena asiantuntijoista). Laske todennäköisyysarvio voiton saamisesta tavaroiden myynnistä yrityksen kahden kuukauden toiminnan jälkeen.

Matriisimuodossa tämä tieto ilmaistaan ​​seuraavasti (vastaa matriisiesimerkkiä 1):

Ensimmäinen iteraatio – kaksivaiheisten siirtymien matriisin rakentaminen.

Jos yritys tekee voittoa kuluvan kuukauden aikana, niin todennäköisyys, että se tuottaa voittoa jälleen ensi kuussa on yhtä suuri kuin

Jos yritys tekee voittoa kuluvan kuukauden aikana, sen todennäköisyys, että se tuottaa tappiota seuraavan kuukauden aikana, on

Jos yritys tekee tappiota kuluvan kuukauden aikana, niin todennäköisyys, että se tuottaa voittoa ensi kuussa, on yhtä suuri

Jos yritys tekee tappiota kuluvan kuukauden aikana, niin todennäköisyys, että se tekee tappiota jälleen ensi kuussa, on

Laskelmien tuloksena saamme kaksivaiheisen siirtymän matriisin:

Tulos saadaan kertomalla matriisi m matriisilla, jolla on samat todennäköisyysarvot:

Suorittaaksesi nämä toimenpiteet Excelissä, sinun on suoritettava seuraavat vaiheet:

• 1) muodostaa matriisin;
• 2) kutsua MULTIPLE-funktiota;
• 3) osoittavat ensimmäisen matriisin - matriisin;
• 4) osoittaa toinen matriisi (sama matriisi tai muu);
• 5) OK;
• 6) valitse uuden matriisin vyöhyke;
• 7) F2;
• 8) Ctrl+Shift+Enter;
• 9) hanki uusi matriisi.

Toinen iteraatio – kolmivaiheisten siirtymien matriisin rakentaminen. Voiton tai tappion saamisen todennäköisyydet seuraavassa vaiheessa lasketaan samalla tavalla ja lasketaan kolmivaiheisten siirtymien matriisi, jolla on seuraava muoto:

Yrityksen seuraavien kahden toimintakuukauden aikana todennäköisyys saada voittoa tuotteen julkaisusta on siis suurempi kuin todennäköisyys saada tappiota. On kuitenkin huomioitava, että voiton todennäköisyys pienenee, joten yrityksen on kehitettävä uusi tuote valmistettavan tuotteen tilalle.