Najjednostavniji tokovi su Markovljevi procesi i lanci rješenja. Elementi teorije čekanja. Modeliranje ovog procesa
Federalna agencija o obrazovanju u Ruskoj Federaciji
FGOU SPO "Perevozski građevinski koledž"
po disciplini" Matematičke metode»
na temu „SMO sa ograničenim vremenom čekanja. Zatvoren QS"
Uvod................................................................ ........................................................ ........................ 2
1. Osnove teorije čekanja .............................................. ................ ...... 3
1.1 Koncept slučajnog procesa ........................................ ........................ 3
1.2 Markovljev slučajni proces.................................................. ...... ................ 4
1.3 Tokovi događaja.................................................. ................................................................... ............. 6
1.4 Kolmogorovljeve jednačine za vjerovatnoće stanja. Verovatnoće konačnog stanja ................................................. ................................................................ ........................ 9
1.5 Problemi teorije čekanja.................................................. ..... .. 13
1.6 Klasifikacija sistema čekanja.................................................. ..... 15
2. Sistemi čekanja sa čekanjem.................................................. ........ 16
2.1 Jednokanalni QS sa čekanjem ........................................ ........................ 16
2.2 Višekanalni QS sa čekanjem........................................ ........................ 25
3. Zatvoreni QS.................................................. ........................................................ ... 37
Rješenje problema ................................................................. .................................................... 45
Zaključak................................................................ ................................................................ ...... 50
Bibliografija ................................................. .................................... 51
U ovom kursu ćemo pogledati različite sisteme čekanja (QS) i mreže čekanja (Queuing).
Sistem čekanja (QS) se shvata kao dinamički sistem dizajniran da efikasno servisira tok zahteva (zahteva za uslugu) pod ograničenjima sistemskih resursa.
QS modeli su pogodni za opisivanje pojedinačnih podsistema savremenih računarskih sistema, kao što je procesorski podsistem - glavna memorija, ulazno-izlazni kanal, itd. Računski sistem kao celina je skup međusobno povezanih podsistema čija je interakcija verovatnoća. Aplikacija za rešavanje određenog problema ulaskom u računarski sistem prolazi kroz niz faza brojanja, pristupa eksternim uređajima za skladištenje i ulazno-izlaznim uređajima. Nakon završetka određenog niza takvih faza, čiji broj i trajanje zavisi od složenosti programa, zahtjev se smatra servisiranim i napušta računarski sistem. Dakle, računarski sistem kao celina može biti predstavljen skupom QS-a, od kojih svaki odražava proces funkcionisanja pojedinačnog uređaja ili grupe sličnih uređaja koji su deo sistema.
Skup međusobno povezanih QS-ova naziva se mreža čekanja (stohastička mreža).
Za početak ćemo se osvrnuti na osnove teorije QS-a, a zatim ćemo preći na detaljnije upoznavanje sa QS-om sa očekivanjem i zatvorenim QS-om. Kurs uključuje i praktični dio, u kojem ćemo detaljno naučiti kako primijeniti teoriju u praksi.
Teorija čekanja je jedna od grana teorije vjerovatnoće. Ova teorija razmatra vjerovatnoća problemi i matematički modeli (prije toga smo razmatrali determinističke matematičke modele). Podsjetimo da:
Deterministički matematički model odražava ponašanje objekta (sistema, procesa) iz perspektive puna sigurnost u sadašnjosti i budućnosti.
Vjerovatni matematički model uzima u obzir uticaj slučajnih faktora na ponašanje objekta (sistema, procesa) i stoga procenjuje budućnost sa stanovišta verovatnoće određenih događaja.
One. ovdje se, na primjer, razmatraju problemi u teoriji igara u uslovima neizvjesnost .
Hajde da prvo razmotrimo neke koncepte koji karakterišu „stohastičku neizvesnost“, kada su neizvesni faktori uključeni u problem slučajne varijable (ili slučajne funkcije), čije su vjerovatnoće karakteristike poznate ili se mogu dobiti iz iskustva. Takva nesigurnost se naziva i „povoljna“, „benigna“.
Strogo govoreći, slučajni poremećaji su svojstveni svakom procesu. Lakše je navesti primjere slučajnog procesa nego „neslučajnog“ procesa. Čak je, na primjer, proces pokretanja sata (čini se da je to strogo kalibriran rad - "radi kao sat") podložan je nasumičnim promjenama (pomicanje naprijed, zaostajanje, zaustavljanje). Ali sve dok su ovi poremećaji beznačajni i imaju mali uticaj na parametre koji nas zanimaju, možemo ih zanemariti i proces smatrati determinističkim, neslučajnim.
Neka postoji neki sistem S (tehnički uređaj, grupa takvih uređaja, tehnološki sistem - mašina, gradilište, radionica, preduzeće, industrija itd.). U sistemu S curenja slučajni proces, ako mijenja svoje stanje tokom vremena (prelazi iz jednog stanja u drugo), osim toga, na prethodno nepoznat nasumičan način.
primjeri:
1. Sistem S– tehnološki sistem (mašinski dio). Mašine se s vremena na vrijeme pokvare i popravljaju. Proces koji se odvija u ovom sistemu je nasumičan.
2. Sistem S- vazduhoplov koji leti na određenoj visini duž određene rute. Uznemirujući faktori - vremenski uslovi, greške posade itd., posljedice - neravnina, kršenje reda letenja itd.
Nasumični proces koji se odvija u sistemu se zove Markovsky, ako za bilo koji trenutak t 0 probabilističke karakteristike procesa u budućnosti zavise samo od njegovog trenutnog stanja t 0 i ne zavise od toga kada i kako je sistem dostigao ovo stanje.
Neka je sistem u određenom stanju u trenutku t 0 S 0 . Znamo karakteristike stanja sistema u sadašnjosti i sve ono što se dešavalo tokom t <t 0 (istorija procesa). Možemo li predvidjeti (predvidjeti) budućnost, tj. šta će se desiti kada t >t 0 ? Ne baš, ali neke probabilističke karakteristike procesa mogu se naći u budućnosti. Na primjer, vjerovatnoća da nakon nekog vremena sistem Sće biti u mogućnosti da S 1 ili će ostati u stanju S 0 itd.
Primjer. Sistem S- grupa aviona koja učestvuje u vazdušna borba. Neka x– broj „crvenih“ aviona, y– broj „plavih“ aviona. Do vremena t 0 broj preživjelih (nije oborenih) aviona, odnosno – x 0 , y 0 . Zanima nas vjerovatnoća da će u jednom trenutku brojčana nadmoć biti na strani “crvenih”. Ova vjerovatnoća zavisi od toga u kakvom je stanju sistem bio u to vrijeme t 0, a ne o tome kada i kojim slijedom su ubijeni poginuli do trenutka t 0 aviona.
Na praksi Markovljevi procesi obično se ne nalaze u svom čistom obliku. Ali postoje procesi kod kojih se uticaj “praistorije” može zanemariti. A kada se proučavaju takvi procesi, mogu se koristiti Markovljevi modeli (teorija čekanja ne razmatra Markovljeve sisteme čekanja, ali je matematički aparat koji ih opisuje mnogo složeniji).
U istraživanju operacija veliki značaj imaju Markovljeve slučajne procese sa diskretnim stanjima i kontinuiranim vremenom.
Proces se zove proces diskretnog stanja, ako su njegova moguća stanja S 1 , S 2, ... može se odrediti unaprijed, a prijelaz sistema iz stanja u stanje se odvija „skokom“, gotovo trenutno.
Proces se zove kontinuirani vremenski proces, ako momenti mogućih prijelaza iz stanja u stanje nisu unaprijed fiksirani, već su neizvjesni, nasumični i mogu se dogoditi u svakom trenutku.
Primjer. Tehnološki sistem (sekcija) S sastoji se od dvije mašine od kojih svaka može otkazati (otkazati) u nasumičnom trenutku, nakon čega odmah počinje popravka jedinice koja se također nastavlja nepoznato, nasumično vrijeme. Moguća su sljedeća stanja sistema:
S 0 - obe mašine rade;
S 1 - prva mašina se popravlja, druga radi;
S 2 - druga mašina se popravlja, prva radi;
S 3 - obje mašine su u remontu.
Sistemske tranzicije S iz stanja u stanje se dešavaju gotovo trenutno, u nasumičnim trenucima kada određena mašina pokvari ili je popravka završena.
Kada analizirate slučajne procese sa diskretnim stanjima, zgodno je koristiti geometrijsku šemu - graf stanja. Vrhovi grafa su stanja sistema. Lukovi grafa su mogući prijelazi iz stanja u stanje. Za naš primjer, graf stanja je prikazan na Sl. 1.
Rice. 1. Grafikon stanja sistema
Bilješka. Prelazak iz države S 0 in S 3 nije naznačeno na slici, jer pretpostavlja se da mašine otkazuju nezavisno jedna od druge. Zanemarujemo mogućnost istovremenog kvara obje mašine.
Prijenos događaja– niz homogenih događaja koji slijede jedan za drugim u nekim nasumičnim trenucima vremena.
U prethodnom primjeru, ovo je tok kvarova i tok restauracija. Drugi primjeri: tok poziva na telefonskoj centrali, tok kupaca u prodavnici, itd.
Tok događaja se može vizuelno predstaviti nizom tačaka na vremenskoj osi O t- pirinač. 2.
Rice. 2. Slika toka događaja na vremenskoj osi
Položaj svake tačke je nasumičan, a ovdje je prikazana samo jedna implementacija toka.
Intenzitet toka događaja ( ) je prosječan broj događaja u jedinici vremena.
Pogledajmo neka svojstva (tipove) tokova događaja.
Tok događaja se zove stacionarno, ako njegove vjerovatnoće ne zavise od vremena.
Konkretno, intenzitet stacionarnog strujanja je konstantan. Tok događaja neminovno ima kondenzacije ili razrjeđivanja, ali oni nisu pravilne prirode, a prosječan broj događaja u jedinici vremena je konstantan i ne ovisi o vremenu.
Tok događaja se zove teče bez posledica, ako za bilo koja dva odsječka vremena koja se ne preklapaju i (vidi sliku 2) broj događaja koji pada na jedan od njih ne ovisi o tome koliko događaja pada na drugi. Drugim riječima, to znači da se događaji koji formiraju tok pojavljuju u određenim trenucima vremena nezavisno jedno od drugog i svaki je uzrokovan svojim uzrocima.
Tok događaja se zove običan, ako se događaji pojavljuju u njemu jedan po jedan, a ne u grupama od nekoliko odjednom.
Tok događaja se zove najjednostavniji (ili stacionarni Poisson), ako ima tri svojstva odjednom:
1) stacionarni;
2) običan;
3) nema posledica.
Najjednostavniji tok ima najjednostavniji matematički opis. On igra istu posebnu ulogu među tokovima kao i pravo. normalna distribucija između ostalih zakona distribucije. Naime, kada se nanese dovoljno je veliki broj nezavisni, stacionarni i obični tokovi (uporedivi jedno s drugim po intenzitetu) rezultiraju strujanjem bliskim najjednostavnijem.
Za najjednostavniji protok sa intervalom intenziteta T između susjednih događaja ima tzv eksponencijalna distribucija sa gustinom:
gdje je parametar eksponencijalnog zakona.
Za slučajna varijabla T, koji ima eksponencijalnu distribuciju, očekivanu vrijednost je recipročna vrijednost parametra, a standardna devijacija jednaka je matematičkom očekivanju:
Uzimajući u obzir Markovljeve procese sa diskretnim stanjima i kontinuiranim vremenom, pretpostavlja se da su svi prelazi sistema S iz stanja u stanje nastaju pod uticajem jednostavnih tokova događaja (tokovi poziva, tokovi kvarova, tokovi oporavka, itd.). Ako svi tokovi događaja prenose sistem S od stanja do stanja najjednostavnijeg, tada će proces koji se odvija u sistemu biti markovski.
Dakle, na sistem u stanju utiče jednostavan tok događaja. Čim se pojavi prvi događaj ovog toka, sistem „skače“ iz stanja u stanje (na grafu stanja duž strelice).
Radi jasnoće, na grafikonu stanja sistema, za svaki luk je naznačen intenzitet toka događaja koji pomiče sistem duž ovog luka (strelica). - intenzitet toka događaja koji sistem prenosi iz stanja u . Takav graf se zove označeno. Za naš primjer, označeni graf je prikazan na Sl. 3.
Rice. 3. Označeni grafikon stanja sistema
Na ovoj slici - intenzitet toka kvara; - intenzitet toka oporavka.
Pretpostavljamo da prosečno vreme za popravku mašine ne zavisi od toga da li se popravlja jedna mašina ili obe odjednom. One. Svaku mašinu popravlja poseban stručnjak.
Neka sistem bude u stanju S 0 . U stanju S 1 preveden je protokom kvarova prve mašine. Njegov intenzitet je jednak:
gdje je prosječno vrijeme rada prve mašine bez otkaza.
Od države S 1 in S 0 sistem se prenosi tokom "završetaka popravke" prve mašine. Njegov intenzitet je jednak:
gdje je prosječno vrijeme popravke za prvu mašinu.
Na sličan način se izračunavaju intenziteti tokova događaja koji prenose sistem duž svih lukova grafa. Imajući na raspolaganju označeni graf stanja sistema, konstruišemo matematički model ovog procesa.
Neka sistem koji se razmatra S ima moguća stanja. Vjerovatnoća th stanja je vjerovatnoća da će u tom trenutku sistem biti u tom stanju. Očigledno je da je u svakom trenutku zbir svih vjerovatnoća stanja jednak jedan:
Da biste pronašli sve vjerovatnoće stanja kao funkcije vremena, sastavite i riješite Kolmogorovljeve jednadžbe – poseban tip jednadžbe u kojima su nepoznate funkcije vjerovatnoće stanja. Pravilo za sastavljanje ovih jednačina je ovdje dato bez dokaza. Ali prije nego što ga uvedemo, objasnimo koncept konačna vjerovatnoća stanja .
Šta će se dogoditi sa vjerovatnoćama stanja u ? Hoće li težiti bilo kakvim granicama? Ako ova ograničenja postoje i ne ovise o početnom stanju sistema, onda se nazivaju vjerovatnoće konačnog stanja .
gdje je konačan broj stanja sistema.
Vjerovatnoće konačnog stanja– to više nisu promjenljive veličine (funkcije vremena), već konstantni brojevi. Očigledno je da:
Vjerovatnoća konačnog stanja je u suštini prosječno relativno vrijeme u kojem sistem ostaje u ovom stanju.
Na primjer, sistem S ima tri države S 1 , S 2 i S 3. Njihove konačne vjerovatnoće su 0,2; 0,3 i 0,5. To znači da sistem u graničnom stacionarnom stanju provodi u prosjeku 2/10 svog vremena u tom stanju S 1, 3/10 – sposoban S 2 i 5/10 – u stanju S 3 .
Pravilo za sastavljanje Kolmogorovljevog sistema jednačina: u svakoj jednadžbi sistema na lijevoj strani je konačna vjerovatnoća datog stanja, pomnožena ukupnim intenzitetom svih tokova, vodi iz ove države, A u njegovoj desnoj strani dijelovi– zbir proizvoda intenziteta svih strujanja, uključeno u -th state, na vjerovatnoćama stanja iz kojih ti tokovi dolaze.
Koristeći ovo pravilo, pišemo sistem jednačina za naš primjer :
.
Ovaj sistem od četiri jednačine sa četiri nepoznanice, čini se, može se u potpunosti riješiti. Ali ove jednadžbe su homogene (nemaju slobodan član) i stoga određuju nepoznanice samo do proizvoljnog faktora. Međutim, možete koristiti uvjet normalizacije: 
i koristiti ga za rješavanje sistema. U ovom slučaju, jedna (bilo koja) jednačina se može odbaciti (slijedi kao posljedica ostalih).
Nastavak primjera. Neka su intenziteti strujanja jednaki: .
Odbacujemo četvrtu jednačinu i umjesto nje dodajemo uvjet normalizacije:
.
One. u ograničavajućem, stacionarnom režimu rada sistema S u prosjeku će 40% vremena biti provedeno u stanju S 0 (obe mašine su u funkciji), 20% - u dobrom stanju S 1 (prva mašina je u remontu, druga radi), 27% - u stanju S 2 (druga mašina je u remontu, prva radi), 13% - u stanju S 3 (obje mašine su u remontu). Poznavanje ovih konačnih vjerovatnoća može pomoći u procjeni prosječne efikasnosti sistema i opterećenja organa za popravku.
Pustite sistem S u stanju S 0 (potpuno operativan) donosi prihod od 8 konvencionalnih jedinica po jedinici vremena, u mogućnosti S 1 – prihod 3 konvencionalne jedinice, sposob S 2 – prihod 5 konvencionalnih jedinica, sposob S 3 – ne ostvaruje prihod. Tada će, u ograničavajućem, stacionarnom načinu rada, prosječni prihod po jedinici vremena biti jednak: konvencionalnim jedinicama.
Mašina 1 se popravlja u djeliću vremena jednakom: . Mašina 2 se popravlja u djeliću vremena jednakom: . Ustaje problem optimizacije. Iako možemo smanjiti prosječno vrijeme popravke prve ili druge mašine (ili oboje), to će nas koštati određeni iznos. Pitanje je da li će povećani prihodi povezani sa bržim popravkama platiti povećane troškove popravke? Moraćete da rešite sistem od četiri jednačine sa četiri nepoznate.
Primjeri sistema za usluge čekanja (QS): telefonske centrale, radionice za popravke, blagajne, informacioni pultovi, alatne mašine i drugi tehnološki sistemi, fleksibilni kontrolni sistemi proizvodni sistemi itd.
Svaki QS se sastoji od određenog broja servisnih jedinica, koje se nazivaju servisni kanali(to su mašine, transportna kolica, roboti, komunikacione linije, blagajnici, prodavci itd.). Svaki QS je dizajniran da služi nekoj vrsti tok aplikacija(zahtjevi) koji dolaze u nekim slučajnim trenucima u vremenu.
Servisiranje zahtjeva se nastavlja neko, općenito govoreći, nasumično vrijeme, nakon čega se kanal oslobađa i spreman je za prijem sljedećeg zahtjeva. Nasumična priroda toka aplikacija i servisnog vremena dovodi do činjenice da se u nekim vremenskim periodima na ulazu QS-a akumulira prekomjerno veliki broj aplikacija (one ili čekaju u redu ili ostavljaju QS neuslužen). U drugim periodima, sistem će raditi sa podopterećenjem ili će biti potpuno neaktivan.
Proces rada QS je slučajan proces sa diskretnim stanjima i kontinuiranim vremenom. Stanje QS-a se naglo menja kada dođe do određenih događaja (dolazak nove aplikacije, kraj servisa, trenutak kada aplikacija koja je umorna od čekanja napusti red čekanja).
Predmet teorije čekanja– izgradnja matematički modeli, povezujući date uslove rada QS-a (broj kanala, njihova produktivnost, pravila rada, priroda toka zahteva) sa karakteristikama koje nas zanimaju – indikatorima efektivnosti QS-a. Ovi pokazatelji opisuju sposobnost CMO-a da se nosi sa tokom aplikacija. Oni mogu biti: prosječan broj aplikacija koje QS opslužuje po jedinici vremena; prosječan broj zauzetih kanala; prosječan broj aplikacija u redu čekanja; prosječno vrijeme čekanja na uslugu itd.
Matematička analiza Rad QS-a je znatno olakšan ako je proces ovog rada markovski, tj. tokovi događaja koji prenose sistem iz stanja u stanje su najjednostavniji. Inače, matematički opis procesa postaje vrlo komplikovan i rijetko ga je moguće dovesti do specifičnih analitičkih ovisnosti. U praksi se ne-Markovljevi procesi svode na Markovljeve procese sa aproksimacijom. Sljedeći matematički aparat opisuje Markovljeve procese.
Prva podjela (na osnovu prisutnosti redova):
1. QS sa kvarovima;
2. Red s redom.
U QS sa kvarovima aplikacija primljena u trenutku kada su svi kanali zauzeti se odbija, napušta QS i ne servisira se u budućnosti.
U SMO sa redom aplikacija koja stigne u vrijeme kada su svi kanali zauzeti ne napušta, već staje u red i čeka priliku da bude uslužena.
QS sa redovima su podijeljeni on različite vrste zavisno od toga kako je red organizovan - ograničeno ili neograničeno. Ograničenja se mogu odnositi i na dužinu reda i na vrijeme čekanja, „disciplina usluga“.
Tako se, na primjer, razmatraju sljedeći QS-ovi:
· CMO sa nestrpljivim zahtjevima (dužina reda i vrijeme usluge su ograničeni);
· QS sa prioritetnom uslugom, tj. neke aplikacije se obrađuju van reda itd.
Pored toga, QS-ovi se dijele na otvorene QS-ove i zatvorene QS-ove.
U otvorenom QS-u karakteristike toka aplikacija ne zavise od stanja samog QS-a (koliko kanala je zauzeto). U zatvorenom QS– zavisi. Na primjer, ako jedan radnik servisira grupu mašina koje s vremena na vrijeme zahtijevaju prilagođavanje, onda intenzitet toka „zahtjeva“ od mašina ovisi o tome koliko ih je već u funkciji i čeka na prilagođavanje.
Klasifikacija SMO daleko od toga da je ograničena na gore navedene sorte, ali ovo je dovoljno.
Hajde da razmotrimo najjednostavniji QS sa čekanjem - jednokanalni sistem (n - 1), koji prima tok zahteva sa intenzitetom; intenzitet usluge (tj., u prosjeku, kanal koji je kontinuirano zauzet će izdavati servisirane zahtjeve po jedinici (vremena). Zahtjev primljen u vrijeme kada je kanal zauzet je u redu čekanja i čeka uslugu.
Sistem sa ograničenom dužinom čekanja. Pretpostavimo prvo da je broj mjesta u redu ograničen brojem m, tj. ako aplikacija stigne u vrijeme kada već ima m-aplikacija u redu čekanja, ona ostavlja sistem neuslužen. U budućnosti, usmjeravanjem m ka beskonačnosti, dobićemo karakteristike jednokanalnog QS-a bez ograničenja na dužinu reda.
Stanja QS-a ćemo numerisati prema broju aplikacija u sistemu (i na servisu i na servisu):
Kanal je besplatan;
Kanal je zauzet, nema reda;
Kanal je zauzet, jedna aplikacija je u redu;
Kanal je zauzet, k-1 aplikacije su u redu;
Kanal je zauzet, aplikacije su u redu.
GSP je prikazan na sl. 4. Svi intenziteti tokova događaja koji se kreću u sistem duž strelica s lijeva na desno jednaki su , a s desna na lijevo - . Zaista, tok zahtjeva pomiče sistem duž strelica s lijeva na desno (čim zahtjev stigne, sistem prelazi u sljedeće stanje), s desna na lijevo - tok „otpuštanja“ zauzetog kanala, koji ima intenzitet (čim se sljedeći zahtjev servisira, kanal će ili postati slobodan ili će smanjiti broj aplikacija u redu čekanja).
Rice. 4. Jednokanalni QS sa čekanjem
Prikazano na sl. 4 dijagram je dijagram reprodukcije i smrti. Napišimo izraze za granične vjerovatnoće stanja:
(5)
ili koristeći: :
(6)
Posljednji red u (6) sadrži geometrijsku progresiju s prvim članom 1 i nazivnikom p, iz čega dobijamo:
(7)
u vezi s tim granične vjerovatnoće poprimaju oblik:
(8).
Izraz (7) vrijedi samo za< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Odredimo karakteristike QS-a: vjerovatnoću kvara, relativnu propusnost q, apsolutnu propusnost A, prosječnu dužinu reda čekanja, prosječan broj aplikacija povezanih sa sistemom, prosječno vrijeme čekanja u redu, prosječno vrijeme koje je aplikacija provela u QS-u .
Vjerovatnoća neuspjeha. Očigledno, aplikacija se odbacuje samo ako je kanal zauzet i sva t-mjesta u redu su također zauzeta:
(9).
Relativna širina pojasa:
(10).
Prosječna dužina čekanja. Nađimo prosječan broj aplikacija u redu kao matematičko očekivanje diskretne slučajne varijable R-broj aplikacija u redu:
Sa vjerovatnoćom postoji jedna aplikacija u redu, sa vjerovatnoćom postoje dvije aplikacije, općenito s vjerovatnoćom ima k-1 aplikacija u redu, itd., od kojih:
(11).
Budući da se zbir u (11) može tumačiti kao derivacija zbira geometrijske progresije:
Zamena ovaj izraz u (11) i koristeći iz (8), konačno dobijamo:
(12).
Prosječan broj aplikacija u sistemu. Zatim dobijamo formulu za prosječan broj -zahtjeva povezanih sa sistemom (koji stoje u redu i koji se servisiraju). Budući da je , gdje je prosječan broj aplikacija u usluzi, a k je poznato, ostaje da se odredi . Budući da postoji samo jedan kanal, broj servisiranih zahtjeva može biti 0 (sa vjerovatnoćom ) ili 1 (sa vjerovatnoćom 1 - ), od čega:
.
a prosječan broj aplikacija povezanih sa QS-om je:
(13).
Prosječno vrijeme čekanja za aplikaciju u redu čekanja. Označimo ga; ako zahtjev dođe u sistem u nekom trenutku, tada sa vjerovatnoćom servisni kanal neće biti zauzet i neće morati čekati u redu (vrijeme čekanja je nula). Najvjerovatnije će ući u sistem dok se neki zahtjev uručuje, ali ispred nje neće biti reda i zahtjev će čekati na početak svog servisiranja određeno vrijeme (prosječno vrijeme servisiranja jednog zahtjev). Postoji vjerovatnoća da će u redu čekanja biti još jedna aplikacija prije razmatranja aplikacije, a prosječno vrijeme čekanja će biti jednako , itd.
Ako je k=m+1, tj. kada novopristigli zahtjev utvrdi da je servisni kanal zauzet i m-zahtjeva je u redu (vjerovatnoća za to), onda u ovom slučaju zahtjev ne stoji u redu (i nije uslužen), tako da je vrijeme čekanja nula. Prosječno vrijeme čekanja će biti:
ako ovdje zamijenimo izraze za vjerovatnoće (8), dobićemo:
(14).
Ovdje koristimo relacije (11), (12) (derivacija geometrijske progresije), kao i iz (8). Upoređujući ovaj izraz sa (12), primjećujemo da je, drugim riječima, prosječno vrijeme čekanja jednako prosječnom broju aplikacija u redu podijeljenom sa intenzitetom toka aplikacije.
(15).
Prosječno vrijeme boravka aplikacije u sistemu. Označimo matematičko očekivanje slučajne varijable kao vrijeme zadržavanja zahtjeva u QS-u, što je zbir prosječnog vremena čekanja u redu i prosječnog vremena usluge. Ako je opterećenje sistema 100%, očigledno, u suprotnom:
.
Primer 1. Benzinska stanica (benzinska stanica) je servisna stanica sa jednim servisnim kanalom (jedna pumpa).
Područje na stanici dozvoljava da ne više od tri automobila istovremeno budu u redu za punjenje goriva (m = 3). Ako su već tri vagona u redu, sljedeći automobil koji stiže na stanicu ne ulazi u red. Protok automobila koji dolaze na punjenje goriva ima intenzitet = 1 (automobil u minuti). Proces dopunjavanja goriva u prosjeku traje 1,25 minuta.
Definiraj:
vjerovatnoća neuspjeha;
relativni i apsolutni kapacitet benzinskih stanica;
prosječan broj automobila koji čekaju da dopune gorivo;
prosječan broj automobila na benzinskoj pumpi (uključujući i one koji se servisiraju);
prosječno vrijeme čekanja na automobil u redu;
prosječno vrijeme koje automobil provede na benzinskoj pumpi (uključujući servis).
Drugim riječima, prosječno vrijeme čekanja je jednako prosječnom broju aplikacija u redu podijeljenom sa intenzitetom toka aplikacije.
Prvo nalazimo smanjeni intenzitet toka aplikacija: =1/1,25=0,8; =1/0,8=1,25.
Prema formulama (8):
Verovatnoća kvara je 0,297.
Relativni kapacitet QS-a: q=1-=0,703.
Apsolutni protok QS-a: A==0,703 automobila u minuti.
Prosječan broj automobila u redu pronalazimo pomoću formule (12):
one. Prosječan broj automobila koji čekaju u redu za punjenje benzinske pumpe je 1,56.
Dodajući ovoj vrijednosti prosječan broj vozila u servisu:
dobijamo prosečan broj automobila povezanih sa benzinskom pumpom.
Prosječno vrijeme čekanja za automobil u redu prema formuli (15):
Dodajući ovoj vrijednosti, dobijamo prosječno vrijeme koje automobil provede na benzinskoj pumpi:
Sistemi sa neograničenim čekanjem. U takvim sistemima vrijednost m nije ograničena i stoga se glavne karakteristike mogu dobiti prelaskom do granice u prethodno dobijenim izrazima (5), (6) itd.
Imajte na umu da je imenilac u posljednjoj formuli (6) zbir beskonačnog broja članova geometrijske progresije. Ovaj zbir konvergira kada je progresija beskonačno opadajuća, tj. at<1.
To se može dokazati<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
Ako, onda relacije (8) imaju oblik:
(16).
Ako nema ograničenja na dužinu reda, svaka aplikacija koja dođe u sistem će biti servisirana, dakle q=1, 
.
Dobijamo prosječan broj aplikacija u redu iz (12) na:
Prosječan broj aplikacija u sistemu prema formuli (13) na:
.
Prosječno vrijeme čekanja se dobija iz formule (14) sa:
.
Konačno, prosječno vrijeme koje aplikacija ostaje u QS-u je:
Sistem sa ograničenom dužinom čekanja. Razmotrimo kanal QS sa čekanjem, koji prima tok zahtjeva sa intenzitetom; intenzitet usluge (za jedan kanal); broj mjesta u redu.
Stanja sistema su numerisana prema broju zahteva povezanih sa sistemom:
bez reda:
Svi kanali su besplatni;
Jedan kanal je zauzet, ostali su slobodni;
-kanali su zauzeti, ostali nisu;
Svi kanali su zauzeti, nema slobodnih kanala;
postoji red:
Svi n-kanali su zauzeti; jedna aplikacija je u redu;
Svi n-kanali, r-zahtjevi u redu su zauzeti;
Svi n-kanali, r-zahtjevi u redu su zauzeti.
GSP je prikazan na sl. 17. Svaka strelica je označena odgovarajućim intenzitetima tokova događaja. Duž strelica slijeva na desno, sistem se uvijek prenosi istim tokom zahtjeva intenziteta od
Rice. 17. Višekanalni QS sa čekanjem
Grafikon je tipičan za procese reprodukcije i smrti, za koje je prethodno dobiveno rješenje. Napišimo izraze za granične vjerovatnoće stanja koristeći oznaku: (ovdje koristimo izraz za zbir geometrijske progresije sa nazivnikom).
Tako su pronađene sve vjerovatnoće stanja.
Hajde da odredimo karakteristike performansi sistema.
Vjerovatnoća neuspjeha. Dolazni zahtjev se odbija ako su svi n-kanali i sva m-mjesta u redu zauzeti:
(18)
Relativna propusnost dopunjuje vjerovatnoću kvara na jednu:
Apsolutna propusnost QS-a:
(19)
Prosječan broj zauzetih kanala. Za QS sa odbijanjima, to se poklopilo sa prosječnim brojem aplikacija u sistemu. Za QS sa redom, prosječan broj zauzetih kanala ne poklapa se sa prosječnim brojem aplikacija u sistemu: potonja vrijednost se razlikuje od prve po prosječnom broju aplikacija u redu.
Označimo prosječan broj zauzetih kanala sa . Svaki zauzeti kanal služi u prosjeku A-zahtjeva u jedinici vremena, a QS u cjelini služi u prosjeku A-zahtjeva u jedinici vremena. Dijelimo jedno na drugo, dobijamo:
Prosječan broj zahtjeva u redu može se izračunati direktno kao matematičko očekivanje diskretne slučajne varijable:
(20)
Ovdje se opet (izraz u zagradama) javlja derivacija zbira geometrijske progresije (vidi gore (11), (12) - (14)), koristeći relaciju za to, dobijamo:
Prosječan broj aplikacija u sistemu:
Prosječno vrijeme čekanja za aplikaciju u redu čekanja. Razmotrimo niz situacija koje se razlikuju po stanju u kojem će novopristigli zahtjev naći sistem i koliko dugo će morati da čeka na servis.
Ako zahtjev ne otkrije da su svi kanali zauzeti, on uopće neće morati čekati (odgovarajući termini u matematičkom očekivanju jednaki su nuli). Ako zahtjev stigne u vrijeme kada su svi n-kanali zauzeti i nema reda, morat će čekati u prosjeku vrijeme koje je jednako (jer "tok oslobađanja" -kanala ima intenzitet ). Ako zahtjev utvrdi da su svi kanali zauzeti i da je jedan zahtjev ispred njega u redu čekanja, morat će čekati u prosjeku određeno vrijeme (za svaki zahtjev ispred) itd. Ako se zahtjev nađe u redu od - zahtjeva, morat će u prosjeku čekati vrijeme Ako novopristigli zahtjev pronađe m-zahtjeve koji su već u redu čekanja, onda uopće neće čekati (ali neće biti uslužen). Pronalazimo prosječno vrijeme čekanja množenjem svake od ovih vrijednosti sa odgovarajućim vjerovatnoćama:
(21)
Kao iu slučaju jednokanalnog QS-a sa čekanjem, napominjemo da se ovaj izraz od izraza za prosječnu dužinu reda (20) razlikuje samo po faktoru , tj.
.
Prosječno vrijeme boravka zahtjeva u sistemu, kao i za jednokanalni QS, razlikuje se od prosječnog vremena čekanja za prosječno vrijeme usluge pomnoženo sa relativnom propusnošću:
.
Sistemi sa neograničenom dužinom čekanja. Razmatrali smo kanal QS sa čekanjem, kada u redu istovremeno ne može biti više od m-zahtjeva.
Kao i do sada, pri analizi sistema bez ograničenja potrebno je uzeti u obzir dobijene relacije za .
Dobijamo vjerovatnoće stanja iz formula prelaskom na granicu (na ). Imajte na umu da se zbir odgovarajuće geometrijske progresije konvergira na i divergira na >1. Pod pretpostavkom da<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Vjerovatnoća kvara, relativna i apsolutna propusnost. Budući da će svaki zahtjev prije ili kasnije biti servisiran, karakteristike QS propusnosti će biti:
Prosječan broj aplikacija u redu se dobija iz (20):
,
a prosječno vrijeme čekanja je od (21):
.
Prosječan broj zauzetih kanala, kao i ranije, određuje se kroz apsolutnu propusnost:
.
Prosječan broj aplikacija povezanih s QS-om definiran je kao prosječan broj aplikacija u redu plus prosječan broj aplikacija u usluzi (prosječan broj zauzetih kanala):
Primjer 2. Benzinska stanica sa dvije pumpe (n = 2) opslužuje protok automobila intenziteta =0,8 (automobila u minuti). Prosečno servisno vreme po mašini:
U okolini nema druge benzinske pumpe, tako da red automobila ispred pumpe može rasti gotovo neograničeno. Pronađite karakteristike QS-a.
Zbog<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
itd.
Prosječan broj zauzetih kanala ćemo pronaći tako što ćemo apsolutni kapacitet QS A = = 0,8 podijeliti sa intenzitetom usluge = 0,5:
Verovatnoća da nema čekanja u redu na benzinskoj pumpi će biti:
Prosječan broj automobila u redu:
Prosječan broj automobila na benzinskim pumpama:
Prosječno vrijeme čekanja u redu:
Prosječno vrijeme koje automobil provede na benzinskoj pumpi:
QS sa ograničenim vremenom čekanja. Ranije smo razmatrali sisteme sa čekanjem ograničenim samo dužinom reda (broj m-zahtjeva istovremeno u redu). U takvom QS-u, aplikacija koja je narasla u redu čekanja ne napušta je dok ne čeka na servis. U praksi postoje i drugi tipovi QS-a u kojima aplikacija nakon nekog vremena može napustiti red čekanja (tzv. „nestrpljive“ aplikacije).
Razmotrimo QS ovog tipa, pod pretpostavkom da je ograničenje vremena čekanja slučajna varijabla.
Pretpostavimo da postoji n-kanalni QS sa čekanjem, u kojem je broj mjesta u redu neograničen, ali je vrijeme zadržavanja zahtjeva u redu neka slučajna varijabla srednje vrijednosti, tako da svaki zahtjev u redu čekanja red je podložan svojevrsnom Poissonovom "toku brige" sa intenzitetom:
Ako je ovaj tok Poisson, tada će proces koji se odvija u QS-u biti markovski. Nađimo vjerovatnoće stanja za to. Numeracija stanja sistema povezana je sa brojem aplikacija u sistemu - i koje se poslužuju i stoje u redu:
bez reda:
Svi kanali su besplatni;
Jedan kanal je zauzet;
Dva kanala su zauzeta;
Svi n-kanali su zauzeti;
postoji red:
Svi n-kanali su zauzeti, jedan zahtjev je u redu;
Svi n-kanali su zauzeti, r-zahtjevi su u redu itd.
Grafikon stanja i prelaza sistema prikazan je na Sl. 23.
Rice. 23. QS sa ograničenim vremenom čekanja
Označimo ovaj graf kao prije; sve strelice koje vode s lijeva na desno pokazat će intenzitet toka aplikacija. Za stanja bez reda, strelice koje vode od njih s desna na lijevo će, kao i do sada, označavati ukupan intenzitet toka koji opslužuje sve zauzete kanale. Što se tiče stanja sa redom, strelice koje vode od njih s desna na lijevo imat će ukupan intenzitet toka usluge svih n-kanala plus odgovarajući intenzitet toka odlazaka iz reda. Ako u redu ima r aplikacija, tada će ukupan intenzitet toka odlazaka biti jednak .
Kao što se može vidjeti iz grafikona, postoji obrazac reprodukcije i smrti; koristeći opšte izraze za granične vjerovatnoće stanja u ovoj shemi (koristeći skraćene oznake, pišemo:
(24)
Napomenimo neke karakteristike QS-a sa ograničenim čekanjem u poređenju sa prethodno razmatranim QS-om sa zahtjevima „pacijenata“.
Ako dužina reda nije ograničena i zahtjevi su "strpljivi" (ne napuštaju red), tada stacionarni granični režim postoji samo u slučaju (na , odgovarajuća beskonačna geometrijska progresija divergira, što fizički odgovara neograničenom rastu reda u ).
Naprotiv, u QS-u sa “nestrpljivim” zahtjevima koji prije ili kasnije napuštaju red, uvijek se postiže uspostavljeni servisni režim na, bez obzira na smanjeni intenzitet toka zahtjeva. Ovo slijedi iz činjenice da red za u nazivniku formule (24) konvergira za bilo koje pozitivne vrijednosti i .
Za QS sa “nestrpljivim” zahtjevima, koncept “vjerovatnosti neuspjeha” nema smisla - svaki zahtjev dolazi u red, ali možda neće čekati uslugu, već odlazi prije vremena.
Relativna propusnost, prosječan broj zahtjeva u redu čekanja. Relativni kapacitet q takvog QS-a može se izračunati na sljedeći način. Očigledno je da će sve aplikacije biti servisirane, osim onih koje napuste red prije roka. Izračunajmo prosječan broj aplikacija koje rano napuštaju red čekanja. Da bismo to učinili, izračunavamo prosječan broj aplikacija u redu čekanja:
Svaka od ovih aplikacija podliježe „toku odlazaka“ s intenzitetom od . To znači da će od prosječnog broja -prijava u redu čekanja, u prosjeku, -prijave otići bez čekanja na servis, -prijave po jedinici vremena i ukupno po jedinici vremena, u prosjeku -prijave će biti uslužene. Relativni kapacitet QS-a će biti:
Još uvijek dobijamo prosječan broj zauzetih kanala dijeljenjem apsolutne propusnosti A sa:
(26)
Prosječan broj aplikacija u redu čekanja. Relacija (26) vam omogućava da izračunate prosječan broj aplikacija u redu bez zbrajanja beskonačne serije (25). Iz (26) dobijamo:
a prosječan broj zauzetih kanala uključenih u ovu formulu može se naći kao matematičko očekivanje slučajne varijable Z, uzimajući vrijednosti 0, 1, 2,..., n sa vjerovatnoćama ,:
U zaključku, napominjemo da ako u formulama (24) idemo do granice na (ili, što je isto, na ), tada će se dobiti formule (22), tj. „nestrpljive“ aplikacije će postati „strpljive“.
Do sada smo razmatrali sisteme u kojima dolazni tok nije ni na koji način povezan sa odlaznim tokom. Takvi sistemi se nazivaju otvorenim krugom. U nekim slučajevima, servisirani zahtjevi se ponovo primaju na ulaz nakon kašnjenja. Takvi QS se nazivaju zatvorenim. Klinika koja opslužuje određeno područje, tim radnika dodijeljen grupi mašina, primjeri su zatvorenih sistema.
U zatvorenom QS-u kruži isti konačan broj potencijalnih zahtjeva. Dok se potencijalni zahtjev ne realizuje kao zahtjev za uslugu, smatra se da je u bloku odgode. U trenutku implementacije ulazi u sam sistem. Na primjer, radnici održavaju grupu mašina. Svaka mašina je potencijalni zahtjev, koji se u trenutku kvara pretvara u stvarnu. Dok mašina radi, nalazi se u bloku kašnjenja, a od trenutka kvara do završetka popravke nalazi se u samom sistemu. Svaki radnik je servisni kanal.
Neka n- broj servisnih kanala, s- broj potencijalnih aplikacija, n <s , - intenzitet toka aplikacija za svaki potencijalni zahtjev, μ - intenzitet usluge:
Vjerovatnoća zastoja sistema određena je formulom
R
0
= 
.
Konačne vjerovatnoće stanja sistema:
P k= at k
Prosječan broj zauzetih kanala izražava se kroz ove vjerovatnoće
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) ili
=P 1 + 2P 2 +…+(n- 1)Pn- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Koristeći ovo nalazimo apsolutnu propusnost sistema:
kao i prosječan broj aplikacija u sistemu
M=s- =s- .
Primjer 1. Ulaz trokanalnog QS-a sa kvarovima prima tok zahtjeva sa intenzitetom =4 zahtjeva u minuti, vrijeme za servisiranje zahtjeva po jednom kanalu t obs =1/μ =0,5 min. Sa stanovišta kapaciteta QS-a, da li je isplativo natjerati sva tri kanala na servisiranje zahtjeva odjednom, a da se prosječno vrijeme usluge smanji za tri puta? Kako će to uticati na prosječno vrijeme koje aplikacija provede u CMO-u?
Rješenje. Pronalazimo vjerovatnoću zastoja trokanalnog QS-a koristeći formulu
ρ = /μ =4/2=2, n=3,
P 0 = = = 0,158.
Vjerovatnoća kvara određena je formulom:
P otvoren = P n ==
P otvoren = 0,21.
Relativna propusnost sistema:
R obsl = 1-R otvoren 1-0,21=0,79.
Apsolutna propusnost sistema:
A= P opsl 3,16.
Prosječan broj zauzetih kanala određen je formulom:
1,58, udio kanala zauzetih servisiranjem,
q = 0,53.
Prosječno vrijeme zadržavanja aplikacije u QS-u nalazi se kao vjerovatnoća da je aplikacija prihvaćena za servis, pomnožena s prosječnim vremenom usluge: t SMO 0.395 min.
Kombinujući sva tri kanala u jedan, dobijamo jednokanalni sistem sa parametrima μ= 6, ρ= 2/3. Za jednokanalni sistem, vjerovatnoća zastoja je:
R 0 = = =0,6,
vjerovatnoća neuspjeha:
P otvoren =ρ P 0 = = 0,4,
relativna propusnost:
R obsl = 1-R otvoren =0,6,
apsolutna propusnost:
A=P obs =2.4.
t SMO =P obsl= =0,1 min.
Kao rezultat kombinovanja kanala u jedan, propusnost sistema se smanjila kako se povećavala verovatnoća kvara. Prosječno vrijeme koje aplikacija provede u sistemu se smanjilo.
Primjer 2. Ulaz trokanalnog QS-a sa neograničenim redom čekanja prima tok zahtjeva s intenzitetom =4 aplikacije na sat, prosječno vrijeme servisiranja jedne aplikacije t=1/μ=0,5 h Pronađite indikatore performansi sistema.
Za sistem koji se razmatra n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
Pronalazimo prosječan broj aplikacija u redu pomoću formule:
L
=
.
L = = .
Prosječno vrijeme čekanja za aplikaciju u redu čekanja izračunavamo pomoću formule:
t= = 0,22 sata.
Prosječno vrijeme boravka aplikacije u sistemu:
T=t+ 0,22+0,5=0,72.
Primjer 3. U frizerskom salonu rade 3 frizera, au čekaonici su 3 stolice. Protok klijenata ima intenzitet =12 klijenata na sat. Prosječno vrijeme servisiranja t obsl =20 min. Odredite relativnu i apsolutnu propusnost sistema, prosječan broj zauzetih stolica, prosječnu dužinu reda, prosječno vrijeme koje klijent provodi u frizeru.
Za ovaj zadatak n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. Vjerovatnoća zastoja je određena formulom:
R
0
=
.
P
0
= 
0,012.
Vjerovatnoća uskraćivanja usluge određena je formulom
P otvoren =P n+m = .
P otvoren =P n + m 0,307.
Relativni kapacitet sistema, tj. vjerovatnoća usluge:
P obsl =1-P otvoren 1-0,307=0,693.
Apsolutna propusnost:
A= P opsl 12 .
Prosječan broj zauzetih kanala:
.
Prosječna dužina reda se određuje po formuli:
L
=
L= 
1,56.
Prosječno vrijeme čekanja na uslugu u redu čekanja:
t= h.
Prosječan broj prijava na CMO:
M=L + .
Prosječno vrijeme boravka aplikacije u CMO-u:
T=M/ 0,36 sati
Primjer 4. Radnik upravlja sa 4 mašine. Svaka mašina otkazuje sa intenzitetom =0,5 kvarova na sat, prosečno vreme popravke t rem=1/μ=0,8 h Odrediti propusnost sistema.
Ovaj problem smatra zatvoreni QS, μ =1,25, ρ=0,5/1,25=0,4. Vjerovatnoća zastoja radnika određena je formulom:
R
0
=
.
P
0
= 
.
Vjerovatnoća zaposlenja radnika R zan = 1-P 0 . A=( 1-P 0 )μ =0,85μ mašina na sat.
zadatak:
Dva radnika upravljaju grupom od četiri mašine. Do zaustavljanja radne mašine dolazi u prosjeku nakon 30 minuta. Prosečno vreme podešavanja je 15 minuta. Vrijeme rada i podešavanja su raspoređeni prema eksponencijalnom zakonu.
Pronađite prosječan udio slobodnog vremena za svakog radnika i prosječno vrijeme rada mašine.
Pronađite iste karakteristike za sistem u kojem:
a) svakom radniku su dodeljene dve mašine;
b) dva radnika uvijek servisiraju mašinu zajedno, i to dvostrukim intenzitetom;
c) jedinu neispravnu mašinu servisiraju oba radnika odjednom (dvostrukim intenzitetom), a kada se pojavi bar još jedna neispravna mašina, oni počinju da rade odvojeno, svaki opslužuje jednu mašinu (prvo opišite sistem u smislu procesa smrt i rođenje).
Rješenje:
Moguća su sljedeća stanja sistema S:
S 0 – sve mašine su u funkciji;
S 1 – 1 mašina je u remontu, ostale su u ispravnom stanju;
S 2 – 2 mašina je u remontu, ostali su ispravni;
S 3 – 3 mašina je u remontu, ostale su ispravne;
S 4 – 4 mašina je u remontu, ostali su u ispravnom stanju;
S 5 – (1, 2) mašine su u remontu, ostale su u ispravnom stanju;
S 6 – (1, 3) mašine su u remontu, ostale su ispravne;
S 7 – (1, 4) mašine su u remontu, ostale su ispravne;
S 8 – (2, 3) mašine su u remontu, ostale su u ispravnom stanju;
S 9 – (2, 4) mašine su u remontu, ostale su u ispravnom stanju;
S 10 – (3, 4) mašine su u remontu, ostale su u ispravnom stanju;
S 11 – (1, 2, 3) mašine su u remontu, 4 mašine su u funkciji;
S 12 – (1, 2, 4) mašine su u remontu, 3 mašine su u funkciji;
S 13 – (1, 3, 4) mašine su u remontu, mašina 2 je u funkciji;
S 14 – (2, 3, 4) mašine su u remontu, 1 mašina je u funkciji;
S 15 – sve mašine su popravljene.
Grafikon stanja sistema...
Ovaj sistem S je primjer zatvorenog sistema, jer je svaka mašina potencijalni zahtjev, koji se u trenutku kvara pretvara u stvarnu. Dok mašina radi, nalazi se u bloku kašnjenja, a od trenutka kvara do završetka popravke nalazi se u samom sistemu. Svaki radnik je servisni kanal.
Ako je radnik zauzet, postavlja μ-mašina po jedinici vremena, kapacitet sistema:
odgovor:
Prosječan udio slobodnog vremena za svakog radnika je ≈ 0,09.
Prosječno vrijeme rada mašine ≈ 3,64.
a) Svakom radniku su dodijeljene dvije mašine.
Vjerovatnoća zastoja radnika određena je formulom:
Vjerovatnoća zaposlenja radnika:
Ako je radnik zauzet, postavlja μ-mašina po jedinici vremena, kapacitet sistema:
odgovor:
Prosječan udio slobodnog vremena za svakog radnika je ≈ 0,62.
Prosječno vrijeme rada mašine ≈ 1,52.
b) Dva radnika uvijek zajedno servisiraju mašinu i to dvostrukim intenzitetom.
c) Jedinu neispravnu mašinu servisiraju oba radnika odjednom (dvostrukim intenzitetom), a kada se pojavi bar još jedna neispravna mašina, oni počinju da rade odvojeno, svaki opslužuje jednu mašinu (prvo opišite sistem u smislu procesa smrt i rođenje).
Poređenje 5 odgovora:
Najefikasniji način organiziranja radnika na mašinama bit će početna verzija zadatka.
Gore su razmotreni primjeri najjednostavnijih sistema čekanja (QS). Izraz "protozoa" ne znači "elementarni". Matematički modeli ovih sistema su primenljivi i uspešno se koriste u praktičnim proračunima.
Mogućnost primjene teorije odlučivanja u sistemima čekanja određuju sljedeći faktori:
1. Broj aplikacija u sistemu (koji se smatra QS) mora biti prilično velik (masovno).
2. Sve prijave primljene na ulaz QS-a moraju biti istog tipa.
3. Da biste izračunali pomoću formula, potrebno je poznavati zakone koji određuju prijem prijava i intenzitet njihove obrade. Štaviše, tokovi naloga moraju biti Poissonovi.
4. Struktura QS-a, tj. skup ulaznih zahtjeva i redoslijed obrade aplikacije moraju biti striktno fiksirani.
5. Potrebno je isključiti subjekte iz sistema ili ih opisati kao zahtjeve sa stalnim intenzitetom obrade.
Gore navedenim ograničenjima možemo dodati još jedno, koje ima snažan utjecaj na dimenziju i složenost matematičkog modela.
6. Broj korištenih prioriteta treba da bude minimalan. Prioriteti aplikacija moraju biti konstantni, tj. ne mogu se mijenjati tokom obrade unutar QS-a.
U toku rada ostvaren je glavni cilj - proučavan je osnovni materijal „QS sa ograničenim vremenom čekanja“ i „Zatvoreni QS“, koji je postavio nastavnik nastavne discipline. Upoznali smo se i sa primjenom stečenog znanja u praksi, tj. konsolidovao obrađeni materijal.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolution..
5) Fomin G.P. Matematičke metode i modeli u komercijalnim djelatnostima. M: Finansije i statistika, 2001.
6) Gmurman V.E. Teorija vjerojatnosti i matematička statistika. M: Viša škola, 2001.
7) Sovetov B.A., Yakovlev S.A. Modeliranje sistema. M: Viša škola, 1985.
8) Lifshits A.L. Statističko modeliranje QS. M., 1978.
9) Ventzel E.S. Istraživanja operacija. M: Nauka, 1980.
10) Ventzel E.S., Ovcharov L.A. Teorija vjerojatnosti i njene inženjerske primjene. M: Nauka, 1988.
QS proces je slučajan proces. Pod slučajnim (verovatnim ili stohastičkim) procesom se podrazumeva proces promene stanja sistema tokom vremena u skladu sa probabilističkim zakonima.
Proces se naziva procesom sa diskretnim stanjima ako se njegova moguća stanja S1, S2, S3... mogu unaprijed navesti, a prijelazi sistema iz stanja u stanje se dešavaju trenutno (skok). Proces se naziva procesom s kontinuiranim vremenom ako momenti mogućih prijelaza sistema iz stanja u stanje nisu unaprijed fiksirani, već su slučajni.
Proces rada QS je slučajan proces sa diskretnim stanjima i kontinuiranim vremenom.
Slučajni proces se naziva Markovljevim ili slučajnim procesom bez posljedica ako za bilo koji trenutak vremena t0 vjerojatnostne karakteristike procesa u budućnosti zavise samo od njegovog stanja u datom trenutku t0 i ne ovise o tome kada i kako sistem došao u ovo stanje.
Primjer Markovljevog procesa: sistem S je taksi mjerač. Stanje sistema u trenutku t karakteriše broj pređenih kilometara automobilom do ovog trenutka. Neka brojač pokaže S0 u trenutku t0. Verovatnoća da će u trenutku t>t0 brojač pokazati ovaj ili onaj broj kilometara (tačnije, odgovarajući broj rubalja) S1 zavisi od S0, ali ne zavisi od toga u kom trenutku su se očitanja brojača promenila pre trenutak t0.
U nekim slučajevima, pretpovijest procesa koji se razmatra može se jednostavno zanemariti i Markovljevi modeli se mogu koristiti za njihovo proučavanje.
Prilikom analize slučajnih procesa sa diskretnim stanjima, zgodno je koristiti geometrijsku shemu - takozvani graf stanja. Tipično, stanja sistema su prikazana pravougaonicima (krugovima), a mogući prelazi iz stanja u stanje su prikazani strelicama (orijentisanim lukovima) koje povezuju stanja (slika 1).
Slika 1 - Grafikon stanja
Za matematički opis Markovljevog slučajnog procesa sa diskretnim stanjima i kontinuiranim vremenom koje teče u QS, upoznaćemo se sa jednim od važnih koncepata teorije verovatnoće - konceptom toka događaja.
Tok događaja se razumije kao niz homogenih događaja koji slijede jedan za drugim u nekim slučajnim trenucima vremena
Primjeri mogu biti:
- - protok poziva na telefonskoj centrali;
- - tok uključivanja uređaja u kućnoj električnoj mreži;
- - protok teretnih vozova koji dolaze na železničku stanicu:
- - protok kompjuterskih kvarova (kvarova);
- - niz hitaca usmjerenih na metu.
Protok je karakteriziran intenzitetom n - učestalošću pojavljivanja događaja ili prosječnim brojem događaja koji ulaze u QS po jedinici vremena.
Tok događaja se naziva regularnim ako događaji slijede jedan za drugim u određenim intervalima. Takav tok je relativno rijedak u praksi, ali je od nekog interesa kao ekstremni slučaj.
Tok događaja se naziva stacionarnim ako njegove vjerovatnoće ne zavise od vremena. Konkretno, intenzitet stacionarnog strujanja je konstantna vrijednost: .
Tok događaja naziva se tok bez naknadnog efekta ako, za bilo koja dva ne-preklapajuća odsječka vremena i _, broj događaja koji pada na jedan od njih ne ovisi o broju događaja koji pada na druge. Na primjer, protok putnika koji ulaze u metro nema praktički nikakav uticaj. A, recimo, tok kupaca koji napuštaju šalter s kupovinom već ima posljedice (makar samo zato što vremenski interval između pojedinih kupaca ne može biti manji od minimalnog vremena servisa za svakog od njih).
Tok događaja se naziva običnim ako je vjerovatnoća da će se dva ili više događaja desiti u malom (elementarnom) vremenskom intervalu zanemarljiva u odnosu na vjerovatnoću da se dogodi jedan događaj. Drugim riječima, tok događaja je običan ako se događaji u njemu pojavljuju pojedinačno, a ne u grupama.
Za tok događaja se kaže da je najjednostavniji (ili stacionarni Poisson) ako je istovremeno stacionaran, običan i bez posljedica.
Najjednostavniji tok kao granica javlja se u teoriji slučajnih procesa jednako prirodno kao i u teoriji vjerovatnoće, normalna raspodjela se dobija superpozicijom (superpozicijom) dovoljno velikog broja n nezavisnih, stacionarnih i običnih tokova (uporedivih jedni s drugima u intenzitet), rezultat je tok blizu najjednostavnijeg intenziteta l, jednak zbiru intenziteta dolaznih strujanja:
Razmotrimo najjednostavniji tok događaja na vremenskoj osi kao neograničeni niz slučajnih tačaka. (sl. 2)
Slika 2 – Tok događaja
Može se pokazati da je za najjednostavniji tok broj m događaja (tačaka) koji padaju na proizvoljni vremenski segment φ distribuiran prema Poissonovom zakonu
za koje je matematičko očekivanje slučajne varijable jednako njenoj varijansi:
Konkretno, vjerovatnoća da se nijedan događaj neće dogoditi tokom vremena φ (m = 0) jednaka je
Nađimo distribuciju vremenskog intervala T između proizvoljna dva susjedna događaja najjednostavnijeg toka.
U skladu sa formulom, verovatnoća da se tokom vremenskog perioda dužine t neće desiti nijedan od narednih događaja jednaka je
i vjerovatnoća suprotnog događaja, tj. funkcija raspodjele slučajne varijable T, je
Gustoća vjerovatnoće slučajne varijable je derivacija njene funkcije distribucije:
Distribucija koju daje gustina vjerovatnoće ili funkcija raspodjele naziva se eksponencijalna (ili eksponencijalna). Dakle, vremenski interval između dva susjedna proizvoljna događaja ima eksponencijalnu distribuciju, za koju je matematičko očekivanje jednako standardnoj devijaciji slučajne varijable
i obrnuto prema intenzitetu toka l.
Najvažnije svojstvo eksponencijalne raspodjele (inherentno samo eksponencijalnoj raspodjeli) je sljedeće: ako je vremenski period raspoređen prema eksponencijalnom zakonu već trajao neko vrijeme φ, onda to ni na koji način ne utiče na zakon raspodjele preostalog dijela intervala (T-φ): bit će isti, kao i zakon raspodjele cijelog intervala T.
Drugim riječima, za vremenski interval T između dva uzastopna susjedna događaja protoka koji ima eksponencijalnu distribuciju, bilo koja informacija o tome koliko je taj interval trajao ne utiče na zakon raspodjele preostalog dijela.
Za najjednostavniji tok intenziteta l, vjerovatnoća da se barem jedan događaj protoka dogodi u elementarnom (malom) vremenskom intervalu?t jednaka je
Pitanja za učenje:
Osnovni koncepti Markovljevih procesa.
Tokovi događaja.
Poissonov tok.
Diskretni Markovi lanci.
Ergodični i upijajući lanci.
Neprekidni Markovi lanci.
Primjena Markovljevih procesa.
Teorija Markovljevih slučajnih procesa.
Teorija vjerovatnoće ima veoma zanimljivu istoriju. Korijeni nauke sežu stoljećima; u najstarijim državama - Kini, Indiji, Egiptu, Grčkoj, neki elementi teorije vjerovatnoće korišteni su za popise stanovništva, pa čak i za određivanje broja neprijateljskih trupa.
Osnivačom teorije smatra se matematičar, fizičar i filozof B. Pascal. Teoriju vjerovatnoće prvi je preuzeo pod utjecajem pitanja koja mu je postavljao jedan od dvorjana francuskog dvora - Chevalier de Mere, briljantni gospodin, filozof, likovni kritičar i kockar. Ali igra je bila i razlog za duboko razmišljanje. De Mere je B. Pascalu postavio dva poznata pitanja:
1. Koliko puta trebate baciti dvije kockice da bi broj puta kada dvije šestice odjednom ispale više od polovine ukupnog broja bacanja?
2. Kako pravedno podijeliti ulog na dva igrača ako su iz nekog razloga prerano prekinuli igru?
Ovi problemi su poslužili kao razlog za početno uvođenje koncepta „matematičkog očekivanja“ i formulisanje osnovnih teorema sabiranja i množenja verovatnoća. Ubrzo su identificirane praktične primjene: osiguranje, demografija itd.
Jacob Bernoulli je otkrio zakon velikih brojeva, koji je omogućio uspostavljanje veze između vjerovatnoće bilo kojeg slučajnog događaja i učestalosti njegovog pojavljivanja, posmatrano direktno iz iskustva.
Dalji napredak u razvoju teorije vjerovatnoće povezan je sa P. Laplaceom, C. Gaussom, S. Poissonom i drugima.
U Rusiji, matematičar V.Ya. Bunyakovsky početkom 19. vijeka. napisao je prvi udžbenik o teoriji vjerovatnoće i razvio njenu terminologiju u njenom modernom obliku. P.A. Čebišev, A.A. Markov i A.M. Ljapunov je uveo koncept "slučajne varijable", s kojim se počela razvijati nova grana teorije vjerojatnosti - teorija slučajnih procesa.
Osnovni koncepti Markovljevih procesa
Funkcionisanje različitih sistema je niz prijelaza iz jednog stanja u drugo. Ako se stanje sistema nasumično mijenja tokom vremena, tada se slijed stanja može smatrati slučajnim procesom.
Sistem se zove sistem diskretnog stanja, ako je skup njegovih stanja konačan, a prijelazi iz jednog stanja u drugo se vrše naglo.
Proces tranzicije se zove lanac.
Definicija Markovljevog lanca
Postoji neki fizički sistem koji ima konačan broj TO
sva moguća fazna stanja. Neka, u zavisnosti od intervencije slučaja, sistem korak po korak (u trenucima vremena t 0
gdje je jedan od mogućih prostora stanja.
Vjerovatnoća prijelaza na m-korak (uslovna vjerovatnoća):
Dakle, izračunati zajedničke vjerovatnoće R(Q 0 , ..,Q n) potrebno je postaviti početno stanje sistema i ukazati na fizički mehanizam za promjenu stanja, koji omogućava izračunavanje vjerovatnoće prijelaza.
1. Poseban (degenerirani) slučaj Markovljevog lanca. Promjena svih stanja se odvija nezavisno, odnosno vjerovatnoća bilo kojeg stanja u m-tom koraku ne zavisi od stanja u kojem je sistem bio u prethodnim vremenima.
– redoslijed nezavisnih testova.
2. Vjerovatnoća faznog stanja parametra Qn u određenom trenutku tn zavisi samo od stanja u kojem je sistem bio u prethodnom trenutku tn-1, i ne zavisi od stanja u kojem je sistem bio u ranijim vremenima t 0 ,…,t n-2.
3. Markovljev lanac reda, ako vjerovatnoća novog stanja zavisi samo od m stanja sistema koja mu neposredno prethode:
Vrijeme koje sistem ostaje u određenom stanju može biti diskretno ili kontinuirano. U zavisnosti od toga, razlikuju se sistemi sa diskretnim ili kontinuiranim vremenom.
Najjednostavnija probabilistička karakteristika slučajnog procesa je skup vjerovatnoća stanja P 1 (t), P 2 (t), ... P n (t), Gdje P i (t)– vjerovatnoća prelaska sistema u stanje S i u određenom trenutku t. Stanje normalizacije P 1 +P 2 +...+P n =1.
Ako je tokom rada sistem u stanju S i, zatim vjerovatnoća njegovog prijelaza u stanje S j generalno ne zavisi samo od države S i, ali i iz prethodnog stanja.
Nasumični proces koji se odvija u sistemu se zove Markovsky(proces bez naknadnih efekata), ako u bilo kom trenutku t 0 vjerovatnoća stanja sistema u budućnosti (sa t>t 0) zavisi samo od stanja u sadašnjosti (sa t=t 0) i ne zavisi od toga kako je i na koji način sistem došao u ovo stanje (tj. ne zavisi od prethodne istorije).
Tokovi događaja
Prelazak sistema u određeno stanje je događaj.
Redoslijed prijelaza sistema u stanje S i predstavlja tok događaja.
Tok događaja se zove običan, ako se događaj u njemu javlja jedan po jedan.
Vremenski intervali t 1, t 2, ... t n obični tok može biti isti ili različit, diskretan ili kontinuiran, nasumičan ili neslučajan.
Ako vremenski intervali t 1, t 2, ... t n su neslučajne vrijednosti, tada se tok naziva regularnim ili determinističkim, a ovaj tok se opisuje specificiranjem vrijednosti T 1 ,T 2 , ... T n.
Ako T 1 ,T 2 , ... T n su nasumični, onda se tok zove nasumično a karakteriše ga zakon raspodele veličina T 1 ,T 2 ,... T n.
U praksi često postoje sistemi u kojima T i– kontinuirana slučajna varijabla. U ovim slučajevima, sistem se može opisati gustinom vjerovatnoće f(t 1 , t 2 , ... t n), Gdje t i– specifična vrijednost slučajne varijable T i.
Potok se zove stacionarno, ako se njegove vjerovatnoće karakteristike ne mijenjaju tokom vremena, tj. vjerovatnoća pojave određenog broja događaja m na dio vremenske ose t¢+t zavisi samo od dužine segmenta t i ne zavisi od toga gde je na vremenskoj osi odabran segment.
Intenzitet (gustina) toka događaja (prosečan broj događaja u jedinici vremena) je konstantan.
Ako vremenski interval t i je uniformna slučajna varijabla, onda takav tok nazvan tok posle efekta a njegovo stanje je u verovatnoj zavisnosti od prethodnog stanja.
Ako su slučajne varijable t i nezavisno, onda se takav tok naziva protok sa ograničenim naknadnim efektom a gustina vjerovatnoće ovog toka jednaka je proizvodu gustoće vjerovatnoće:
f(t 1 ,t 2 , ...t n) = f 1 (t 1) f 2 (t 2) ... f n (t n)(6.5)
Protok sa ograničenim naknadnim efektom može biti stacionaran i ujednačen u vremenu. U ovom slučaju, svi intervali između susjednih događaja imaju isti zakon raspodjele:
f i (t i) = f (t i)(6.6)
Zove se tok bez naknadnog dejstva slučajni tok ako, za bilo koji vremenski segment koji se ne preklapa, broj događaja koji pada na jedan od njih ne zavisi od toga koliko događaja pada na druge segmente.
Poissonov tok
Tokovi nasumičnih događaja nazivaju se Poisson, ako je broj događaja niti m, pada na bilo koje područje t, distribuiran prema Poissonovom zakonu
P m = e - a , (6.7)
Gdje A– prosječan broj događaja koji se nalaze na tom području t.
Poissonov tok je stacionaran ako je gustina događaja l je konstantan, onda je prosječan broj događaja lt, inače će protok biti nestabilan.
Nasumični tok događaja, koji ima svojstvo stacionarnosti, običnosti i nema naknadnog efekta, naziva se najjednostavnijim i stacionarni Poissonov tok.
Prosijani potoci
Proces tranzicija sistema sa diskretnim vremenom rada može se posmatrati kao uticaj diskretnog toka događaja, koji se odlikuje činjenicom da se u vremenima t 1, t 2, ..., t n događaji događaju sa verovatnoćom P i. Funkcija distribucije takvog toka je:
Probiranje kroz tok događaja S 1, S 2, ... S n, koje se dešavaju u određenim vremenima sa verovatnoćom p 1 , p 2 , ... p n, znači transformaciju ovih vjerovatnoća u , , ..., . Ako je tok stacionaran, onda su ove vjerovatnoće jednake: = =...=1-p.
U ovom slučaju, p je konstanta prosijavanja, koja je određena ili utjecajem nekog destabilizirajućeg faktora, ili je određena isključenjem bilo kojeg događaja iz skupa stanja sistema.
Primjeri tokova sa ograničenim naknadnim efektom su Erlang tokovi. Nastaju redovnim prosejavanjem najjednostavnijeg toka, dok se pod redovnim prosejavanjem podrazumeva postupak koji rezultira isključenjem nekoliko naknadnih događaja u izvornom toku. Ako se svaki neparni događaj eliminira u najjednostavnijem toku, onda preostali događaji formiraju Erlangov tok drugog reda. Vremenski interval između susjednih događaja u takvom toku je zbir nezavisnih slučajnih varijabli i , raspoređenih prema eksponencijalnom zakonu ( = + ).
Ako je u najjednostavnijem toku pohranjen samo svaki treći događaj, onda dobijamo Erlangov tok trećeg reda, itd. Uglavnom, Erlang stream k- o poziva se najjednostavniji tok koji proizvede izuzetak (k- 1) događaja i štednje k-th event.
Diskretni Markovi lanci
Markovljev slučajni proces sa diskretnim stanjima i diskretnim radnim vremenom opisuje sistem S sa konačnim brojem stanja. U ovom slučaju, prijelazi su mogući u određeno vrijeme t 1 , t 2 , ..., t k. Proces koji se odvija u ovom sistemu može se predstaviti kao lanac slučajnih događaja
S 1 (0) ® S 2 (1) ® ... ® S i (n) ® ... ® S n (k).
Ovaj niz se zove diskretni Markovljev lanac ako za svaki korak n=1,2, ... k vjerovatnoća prijelaza iz bilo kojeg stanja (S i ®S j) ne zavisi od toga kako je sistem stigao u stanje S i. Svaki prelaz sistema odgovara uslovnoj verovatnoći
P. (6.9)
Za svaki broj koraka n mogući oblici prelaza kompletna grupa događaja.
homogena, ako vjerovatnoće prijelaza ne zavise od broja koraka. Potpuni opis takvog lanca može biti kvadratna matrica vjerovatnoća tranzicije
| P 11 | P 12 | ... | P 1n | |
| P ij = | P 21 | P 22 | ... | P2n |
| ... | ... | ... | ... | |
| Pn1 | Pn2 | ... | Pnn |
i vektor početne distribucije vjerovatnoće za sva stanja u trenutku t=0.
= . (6.10)
Vjerovatnoće prijelaza koje odgovaraju nemogućim prijelazima jednake su 0, a vjerovatnoće duž glavne dijagonale odgovaraju činjenici da sistem nije promijenio svoje stanje.
Diskretni Markovljev lanac se zove heterogena, ako se vjerovatnoće prijelaza mijenjaju s brojem koraka. Za opisivanje takvih kola potrebno je postaviti k matrice vjerovatnoće tranzicije P ij (k– broj razmatranih koraka). Glavni zadatak analize Markovljevih procesa je određivanje vjerovatnoće svih stanja sistema nakon bilo kojeg broja koraka. Štaviše, ako su poznati matrica vjerovatnoća tranzicije i vektor početne distribucije, tada su vjerovatnoće stanja sistema nakon svakog koraka određene formulom ukupne vjerovatnoće:
P(A) = P(B i)*P(A/B i)(6.11)
Nakon prvog koraka vjerovatnoća P i može se definirati na sljedeći način:
P i (1) = P j (0)P ji , (6.12)
Gdje Pj(0) – vektor početnih stanja,
P ji– red matrice uslovnih vjerovatnoća.
P i (2) = P j (1)P ji = P j (0)P ji (1)(6.13)
Poslije k koraci:
P i (k) = P j (k-1)P ji = P j (0)P ji (k),(6.14)
Gdje pji(k)– vjerovatnoće prijelaza sistema iz stanja S i V S j iza k stepenice.
Ako je prijelaz iz stanja moguć S i u državi S j iza k korake, zatim vrijednost P ji (k)>0. Ako je obrnuti prijelaz moguć u istom broju koraka, onda stanje S i pozvao povratno. Verovatnoća da će sistem izaći iz stanja S i i za k koraci će se vratiti na njega, jednako 1 za povratna stanja.
Država S i - neopoziv, ako je ova vjerovatnoća drugačija od 1.
države S i I S j su pozvani komuniciranje, ako je tranzicija moguća S i ®S j u konačnom broju koraka.
Na prethodnim predavanjima naučili smo kako simulirati pojavu slučajnih događaja. Odnosno, možemo igrati koji mogućih događaja će se dogoditi i u kojem količina. Da biste to odredili, morate znati statističke karakteristike nastanka događaja, na primjer, takva vrijednost može biti vjerovatnoća da se neki događaj dogodi ili distribucija vjerovatnoće različitih događaja, ako postoji beskonačno mnogo tipova ovih događaja.
Ali često je takođe važno znati Kada ovaj ili onaj događaj će se posebno dogoditi u vremenu.
Kada ima mnogo događaja i oni slijede jedan za drugim, formiraju se protok. Imajte na umu da događaji moraju biti homogeni, odnosno donekle slični jedni drugima. Na primjer, pojava vozača na benzinskim pumpama koji žele napuniti svoj automobil gorivom. To jest, homogeni događaji čine određeni niz. U ovom slučaju se pretpostavlja da je data statistička karakteristika ovog fenomena (intenzitet toka događaja). Intenzitet toka događaja pokazuje koliko prosjek takvi događaji se dešavaju u jedinici vremena. Ali tačno kada će se svaki određeni događaj dogoditi mora se odrediti pomoću metoda modeliranja. Važno je da kada generišemo, na primjer, 1000 događaja u 200 sati, njihov broj će biti približno jednak prosječnom intenzitetu pojave događaja 1000/200 = 5 događaja po satu, što je statistička vrijednost koja karakteriše ovaj tok kao cijeli.
Intenzitet protoka je u određenom smislu matematičko očekivanje broja događaja u jedinici vremena. Ali u stvarnosti se može ispostaviti da se 4 događaja pojavljuju u jednom satu, 6 u drugom, iako u prosjeku ima 5 događaja po satu, tako da jedna vrijednost nije dovoljna za karakterizaciju toka. Druga veličina koja karakteriše koliko je širenje događaja u odnosu na matematičko očekivanje je, kao i ranije, disperzija. Zapravo, ta vrijednost određuje slučajnost nastanka događaja, slabu predvidljivost trenutka njegovog nastanka. O ovoj vrijednosti ćemo govoriti u sljedećem predavanju.
Tok događaja je niz homogenih događaja koji se javljaju jedan za drugim u nasumičnim intervalima. Na vremenskoj osi ovi događaji izgledaju kao što je prikazano na sl. 28.1.
Primjer toka događaja je niz trenutaka kada avioni slijeću na pistu kada stignu na aerodrom.
Intenzitet protoka λ ovo je prosječan broj događaja u jedinici vremena. Intenzitet protoka može se eksperimentalno izračunati pomoću formule: λ = N/T n, Gdje N broj događaja koji su se desili tokom posmatranja T n.
Ako je interval između događaja τ j jednaka konstanti ili definirana nekom formulom u obliku: t j = f(t j 1), tada se zove tok deterministički. Inače se tok naziva slučajnim.
Postoje nasumični tokovi:
- običan: vjerovatnoća istovremene pojave dva ili više događaja je nula;
- stacionarni: učestalost pojavljivanja događaja λ (t) = const( t) ;
- bez naknadnog dejstva: vjerovatnoća nastanka slučajnog događaja ne zavisi od trenutka nastanka prethodnih događaja.
Poissonov tok
Uobičajeno je uzeti Poissonov tok kao standard protoka u modeliranju..
Poissonov tok ovo je običan tok bez naknadnih efekata.
Kao što je ranije navedeno, vjerovatnoća da će tokom vremenskog intervala (t 0 , t 0 + τ ) desiće se m događaji su određeni Poissonovim zakonom:
Gdje a Poissonov parametar.
Ako λ (t) = const( t) , to je stacionarni Poissonov tok(najjednostavniji). U ovom slučaju a = λ · t . Ako λ = var( t) , to je nestalni Poissonov tok.
Za najjednostavniji tok, vjerovatnoća pojave m događaji tokom τ je jednako:
Vjerovatnoća da se ne dogodi (odnosno da nema, m= 0 ) događaji tokom vremena τ je jednako:
Rice. 28.2 ilustruje zavisnost P 0 od vremena. Očigledno, što je duže vrijeme posmatranja, manja je vjerovatnoća da se događaj neće dogoditi. Štaviše, veća je vrijednost λ , što je graf strmiji, odnosno, brže opada vjerovatnoća. To odgovara činjenici da ako je intenzitet pojave događaja visok, onda vjerovatnoća da se događaj ne dogodi brzo opada s vremenom posmatranja.
Vjerovatnoća da se dogodi barem jedan događaj ( P HB1S) se izračunava na sljedeći način:
jer P HB1S + P 0 = 1 (ili će se pojaviti barem jedan događaj, ili se neće pojaviti nijedan, drugi nije dat).
Iz grafikona na sl. 28.3 jasno je da vjerovatnoća pojave barem jednog događaja teži jedinstvu tokom vremena, odnosno, uz odgovarajuće dugotrajno posmatranje događaja, to će se sigurno dogoditi prije ili kasnije. Što duže posmatramo događaj (to više t), veća je vjerovatnoća da će se događaj dogoditi; graf funkcije monotono raste.
Što je veći intenzitet pojave događaja (više λ ), što se ovaj događaj brže dešava, i brže funkcija teži ka jedinici. Parametar na grafikonu λ predstavljeno strminom linije (nagib tangente).
Ako povećate λ , zatim kada posmatrate događaj u isto vrijeme τ , povećava se vjerovatnoća da će se neki događaj dogoditi (vidi sliku 28.4). Očigledno, graf počinje od 0, jer ako je vrijeme posmatranja beskonačno malo, onda je vjerovatnoća da će se događaj desiti za to vrijeme zanemarljiva. I obrnuto, ako je vrijeme posmatranja beskonačno dugo, tada će se događaj definitivno dogoditi barem jednom, što znači da graf teži vrijednosti vjerovatnoće jednakoj 1.
Proučavanjem zakona možete utvrditi da: m x = 1/λ , σ = 1/λ , odnosno za najjednostavniji tok m x = σ . Jednakost matematičkog očekivanja sa standardnom devijacijom znači da je ovaj tok tok bez naknadnog efekta. Disperzija (tačnije, standardna devijacija) takvog protoka je velika. Fizički, to znači da je vrijeme nastanka događaja (razdaljina između događaja) loše predvidljivo, nasumično i da se nalazi u intervalu m x σ < τ j < m x + σ . Iako je jasno da je u prosjeku približno jednako: τ j = m x = T n/ N . Događaj se može dogoditi u bilo kojem trenutku, ali unutar raspona ovog trenutka τ j relativno m x do [ σ ; +σ ] (veličina naknadnog efekta). Na sl. Slika 28.5 prikazuje moguće pozicije događaja 2 u odnosu na vremensku osu za dati σ . U ovom slučaju kažu da prvi događaj ne utiče na drugi, drugi ne utiče na treći, i tako dalje, odnosno da nema naknadnog efekta.
U smislu P jednaki r(vidi predavanje 23. Modeliranje slučajnog događaja. Modeliranje kompletne grupe nekompatibilnih događaja), dakle, izražavanje τ iz formule (*) , konačno, da bismo odredili intervale između dva slučajna događaja imamo:
τ = 1/ λ Ln( r) ,
Gdje r slučajni broj ravnomjerno raspoređen od 0 do 1, koji je preuzet iz RNG-a, τ interval između slučajnih događaja (slučajna varijabla τ j ).
Primjer 1. Razmotrimo tok proizvoda koji stižu u tehnološku operaciju. Proizvodi dolaze nasumično u prosjeku osam komada dnevno (brzina protoka λ = 8/24 [jedinica/sat]). Potrebno je simulirati ovaj proces iznutra T n = 100 sati. m = 1/λ = 24/8 = 3 , odnosno u prosjeku jedan dio na tri sata. primeti, to σ = 3 . Na sl. Slika 28.6 predstavlja algoritam koji generiše tok slučajnih događaja.
Na sl. Slika 28.7 prikazuje rezultat algoritma: trenutke u vremenu kada su dijelovi stigli na operaciju. Kao što se može vidjeti, samo u tom periodu T n = 100 obrađenih proizvodnih jedinica N= 33 proizvoda. Ako ponovo pokrenemo algoritam, onda N može ispasti jednako, na primjer, 34, 35 ili 32. Ali u prosjeku, for K algoritam radi Nće biti jednako 33,33 Ako izračunate udaljenosti između događaja t With i i vremenske tačke definisane kao 3 i, tada će u prosjeku vrijednost biti jednaka σ = 3 .
Modeliranje izvanrednih tokova događaja
Ako se zna da tok nije običan, onda je potrebno modelirati, pored trenutka nastanka događaja, i broj događaja koji bi se mogli pojaviti u ovom trenutku. Na primjer, automobili stižu na željezničku stanicu kao dio voza u nasumično vrijeme (redovni tok voza). Ali u isto vrijeme, voz može imati različit (slučajni) broj automobila. U ovom slučaju, o toku vagona se govori kao o toku vanrednih događaja.
Pretpostavimo to M k = 10 , σ = 4 (to jest, u prosjeku u 68 slučajeva od 100 u vozu ima od 6 do 14 vagona) i njihov broj je raspoređen po normalnom zakonu. Na mjesto označeno (*) u prethodnom algoritmu (vidi sliku 28.6), potrebno je da umetnete fragment prikazan na sl. 28.8.
Primjer 2. Rješenje sljedećeg problema je vrlo korisno u proizvodnji. Koliko je prosječno dnevno vrijeme zastoja opreme tehnološkog čvora ako čvor obrađuje svaki proizvod nasumično vrijeme određeno intenzitetom toka slučajnih događaja λ 2? Istovremeno, eksperimentalno je utvrđeno da se proizvodi također dovode na obradu u nasumično vrijeme određeno protokom λ 1 u serijama od 8 komada, a veličina serije nasumično varira prema normalnom zakonu sa m = 8 , σ = 2 (vidi predavanje 25). Prije modeliranja T= 0 nema proizvoda na zalihama. Potrebno je simulirati ovaj proces iznutra T n = 100 sati.
Na sl. Slika 28.9 predstavlja algoritam koji nasumično generiše tok dolazaka serija proizvoda na obradu i tok slučajnih događaja izlaza serija proizvoda iz obrade.
Na sl. Slika 28.10 prikazuje rezultat algoritma: trenutke u vremenu kada su dijelovi stigli u operaciju i trenutke u vremenu kada su dijelovi napustili operaciju. Treći red pokazuje koliko je dijelova bilo u redu za obradu (koji su ležali u skladištu čvora) u različitim vremenskim trenucima.
Zabilježivši za čvor za obradu vremena kada je bio u stanju mirovanja čekajući sljedeći dio (pogledajte na slici 28.10 vremenske dijelove označene crvenom bojom), možemo izračunati ukupno vrijeme zastoja čvora za cijelo vrijeme posmatranja, a zatim izračunati prosječno vrijeme zastoja u toku dana. Za ovu implementaciju ovo vrijeme se računa na sljedeći način:
T itd. Wed. = 24 · ( t 1 ave + t 2 ave + t 3 ave + t 4 ave ++ t N itd.)/ T n.
Vježba 1. Promjena vrijednosti σ , instalirati ovisnost T itd. Wed. ( σ ) . Postavljanjem cene zastoja čvora na 100 evra/sat, odredite godišnje gubitke preduzeća od nepravilnosti u radu dobavljača. Predložite tekst klauzule ugovora preduzeća sa dobavljačima „Iznos kazne za kašnjenje u isporuci proizvoda“.
Zadatak 2. Promjenom iznosa početnog punjenja skladišta odrediti kako će se mijenjati godišnji gubici preduzeća od nepravilnosti u radu dobavljača, u zavisnosti od količine zaliha prihvaćenih u preduzeću.
Simulacija nestacionarnih tokova događaja
U nekim slučajevima, intenzitet protoka se može promijeniti tokom vremena λ (t) . Takav tok se naziva nestacionarnim. Na primjer, prosječan broj kola hitne pomoći po satu koja napuštaju stanicu kao odgovor na pozive stanovništva velikog grada može varirati tokom dana. Poznato je, na primjer, da najveći broj poziva pada na intervale od 23 do 01 ujutro i od 05 do 07 sati ujutro, dok je u ostalim satima upola manji (vidi sliku 28.11).
U ovom slučaju, distribucija λ (t) može se specificirati bilo grafom, formulom ili tablicom. I u algoritmu prikazanom na sl. 28.6, na mjesto označeno (**), morat ćete umetnuti fragment prikazan na sl. 28.12.
Transkript
1 AN Moiseev AA Nazarov Asimptotička analiza polu-Markovljevog toka visokog intenziteta 9 UDC 5987 AN Moiseev AA Nazarov Asimptotička analiza polu-Markovljevog toka događaja visokog intenziteta Studija polumarkovskog toka događaja visokog intenziteta je Pokazuje se da se za razmatrani tok raspodjela vjerovatnoće broja događaja koji se dešavaju u fiksnom vremenskom intervalu, podložna neograničenom povećanju intenziteta protoka, može aproksimirati normalnom distribucijom. Ova distribucija dobijena je u radu Ključne reči: tok događaja visokog intenziteta, polu-Markovljev tok, asimptotska analiza Jedan od osnovnih elemenata sistema i mreža čekanja je dolazni tok zahteva Savremene telekomunikacione mreže i distribuirana obrada informacija sistemi zahtevaju visoku propusnost kanala za prenos informacija.Tako je u ovim sistemima broj paketa podataka koji pristižu na obradu u jedinici vremena veoma visok.U teoriji čekanja, u takvim slučajevima govore o velikom intenzitetu dolaznog toka. Konkretno, u radu se koristi model toka visokog intenziteta za simulaciju toka dolaznih poruka višefaznog distribuiranog sistema za obradu podataka.U radovima su proučavana svojstva rekurentnih MMPP- i MAP-tokova visokog intenziteta Ovaj rad predstavlja analiza svojstava polumarkovskog (semimarkovskog ili SM-) toka visokog intenziteta kao najopštijeg modela tokova događaja Matematički model Razmotrimo polumarkovski tok homogenih događaja specificiranih na sljedeći način Neka (ξ n τ n ) stacionarni dvodimenzionalni Markovljev proces sa diskretnim vremenom. tzv. semi-Markovljeva matrica A (x) = ( Ak ν ) k ν= kako slijedi K: x Akν (x) = P ξ n+ =ν τ n+< ξ n = k N Здесь N некоторая большая величина которая введена искусственно чтобы явным образом подчеркнуть малость величин τ n В теоретических исследованиях будем полагать N и таким образом τ n На практике полученные результаты можно использовать для аппроксимации соответствующих величин при достаточно больших значениях N (в условии высокой интенсивности потока) Пусть в момент времени t = произошло изменение состояния процесса {ξ n τ n } Последовательность моментов времени t n определяемая рекуррентным выражением tn+ = tn+τ n+ для n = называется полумарковским потоком случайных событий определяемым полумарковской матрицей A(x) Процесс ξ n =ξ(t n) называют вложенной в полумарковский поток цепью Маркова Поскольку средняя длина интервалов τ n обратно пропорциональна N то при N интенсивность наступления событий в таком потоке будет неограниченно расти Такой поток событий будем называть высокоинтенсивным полумарковским или HISM-потоком (от High-Intensive Semi- Markovian) Ставится задача нахождения числа событий m(t) наступивших в этом потоке в течение интервала времени (t) Вывод уравнений Колмогорова Пусть z(t) длина интервала времени от момента t до момента наступления следующего события в потоке; k(t) случайный процесс значения которого на каждом из интервалов = () Отсюда получаем матричное дифференциальное уравнение относительно функции R(z): R (z) = R ()[ I A (z) ] (3) граничное условие для которого при z имеет вид R () = λr (4) где λ некоторый коэффициент вектор-строка r есть стационарное распределение состояний вложенной цепи Маркова Этот вектор является решением уравнения Колмогорова r= r P где P= lim A (z) есть стохастическая матрица определяющая вероятности переходов вложенной цепи z Маркова Таким образом решение уравнения (3) имеет вид z R() z = R ()[ I A () x ] dx (5) Пусть R= R () есть стационарное распределение значений полумарковского процесса k(t) тогда при z из (5) получаем R= R ()[ I A(x) ] dx=λ r[ I A(x) ] dx=λr [ P A(x) ] dx=λra (6) где A матрица с элементами Akν = [ Pkν Akν(x) ] dx Умножая левую и правую части равенства (6) на единичный вектор-столбец E получим RE = =λrae откуда находим значение коэффициента λ: λ= (7) rae Доклады ТУСУРа 3 (9) сентябрь 3
3 AN Moiseev AA Nazarov Asimptotička analiza polu-Markovljevog strujanja visokog intenziteta jum Uvedemo oznaku Hkuzt () = e Pkmzt () gdje je j = imaginarna jedinica i u neka varijabla Množenje () sa e jum i zbrajanje preko m od da dobijemo m = Hkuzt () Hkuzt ( ) Hku (t) K ju Hku (t) = + e Aν k (z) N ν= Uzimajući u obzir notaciju vektora reda H(u z t) = (H(u z t) H (K u z t)), ova jednadžba ima oblik H(uzt) H(uzt) H(u t) ju = + e A(z) I (8) N Diferencijalnu matričnu jednačinu (8) riješit ćemo asimptotički metodom pod uslovom neograničeno rastućeg intenziteta λn polu-Markovljevog toka koji se razmatra kao N asimptotika prvog reda. Uvedemo oznaku N =ε u= ε w H(uzt) = F (wzt ε) Iz (8) dobijamo F(wzt ε) F(wzt ε) F(w t ε) jwε ε = + e A(z) I ( 9) Teorema Asimptotičko rješenje F(wzt) = lim F (wzt ε) jednačine (9) ima oblik ε () () jw λ F wzt = R ze t () gdje je R(z) određen izrazom (5) Dokaz Uradimo to u (9) prelazeći na granicu ε dobijamo jednačinu F(wzt) F(w t) = + [ A(z) I ] koji ima oblik sličan () Stoga se funkcija F (w z t) može predstaviti kao F(wzt) = R (z) Φ(wt) () gdje je Φ (w t) je neka skalarna funkcija. Prijeđimo na granicu z u (9) i zbrojimo sve komponente ove jednadžbe (da bismo to učinili, pomnožimo obje strane na desnoj strani vektorom jediničnog stupca E) Dobijamo F (w t ε) F (w t ε) ε E= e P I E Zamijenite ovdje izraz () koristite proširenje e = + jε w+ O(ε) podijelite obje strane sa ε i prijeđite na granicu ε: Φ(wt) RE = jwr () PE Φ(wt) odakle, uzimajući u obzir (4), dobijamo diferencijalnu jednačinu za funkciju Φ (w t): Φ(wt) = jwλφ (wt) Rješavanje ove jednačine pod početnim uvjetom Φ (w ) = dobijamo rešenje jwλt Φ (wt) = e Zamenimo ovaj izraz u ( ) dobijamo () Teorema je dokazana ju Nt asimptotika drugog reda Napravimo zamenu H(uzt) = H (uzte) λ u ( 8): H(uzt) H(uzt) H(u t) ju + juλ H(u z t) = + e A(z) I () N Uvedemo oznaku N =ε u= ε w H(uzt) = F (wzt ε) (3) TUSUR Izvještaji 3 (9) 3. septembar
4 UPRAVLJANJE RAČUNARSKOM INŽENJERSTVOM I INFORMACIJSKIM NAUKA Tada će () biti prepisano kao F(wzt ε) F(wzt ε) F(w t ε) ε + λf (wzt ε) = + e A(z) I (4) Teorema Asimptotičko rješenje F( wzt) = lim F (wzt ε) jednadžba (4) ima oblik ε (jw) F (wzt) = R (z)exp (λ+κ) t (5) gdje je R(z) određen izraz (5) κ= fe (6) vektor reda f zadovoljava sistem linearnih algebarskih jednadžbi f I P =λ rp R λ a (7) f AE= a = rae A = x da (x) Dokaz Prijeđimo na granica ε u (4) dobijamo jednačinu F( wzt) F(w t) = + [ A(z) I ] koja ima oblik sličan () Stoga se funkcija F (w z t) može predstaviti kao F(wzt ) = R (z) Φ(wt) (8) gdje je Φ ( w t) neka skalarna funkcija Rješenje jednadžbe (4) tražit će se u obliku proširenja F(wzt ε) =Φ (wt) R(z) + jε wf (z) + O(ε) (9) gdje je f(z) neka vektorska funkcija (niz) Zamjena ovog izraza u (4) i primjena proširenja e = + jε w+ O(ε) nakon nekih transformacija dobijamo ( ) λφ (wt) R() z=φ (wt) R() z+ f () z+ R() A() z I + R() A() z+ f () A() z I+ A () z + O(ε) Uzimajući u obzir (3) (4) dijeljenjem obje strane sa jεw i poništavanjem Φ ( w t) dobijamo λ R(z) = f (z) + λ ra(z) + f () [ A(z) I ] + O(ε) Odavde, za ε, dobijamo diferencijalnu jednačinu za nepoznatu vektorsku funkciju f(z) f ( z) = f ()[ I A(z) ] λ[ ra( z) R (z) ] integrirajući koji pod početnim uvjetom f() = dobijamo izraz z f(z) = ( f ()[ I A(x) ] λ [ ra(x) R (x) ]) dx ( ) Tražićemo f(z) u klasi funkcija koje zadovoljavaju uslov lim ( f ()[ I A(x) ] λ[ ra(x) R (x) ]) = x Odavde dobijamo f ()[ I P] λ[ rp R ] = () Oduzimanjem lijeve strane ove jednakosti od integranda () uzimajući u obzir (6) dobijamo f() = f () A+λrA λ [ R R (x) ] dx () Može se pokazati da je [ R R (x) ] dx= λ ra gdje je A = x da (x) Uzimajući ovo u obzir, množenjem obje strane () s desne strane jediničnim vektorom E dobijamo TUSUR Reports 3 (9) septembar 3
5 AN Moiseev AA Nazarov Asimptotička analiza polu-Markovljevog toka visokog intenziteta 3 λ a [ f () A f()] E = (3) gdje je a = rae Uz pretpostavku da je f() E = i označavajući f = f () iz () i (3) dobijamo sistem jednadžbi (7) Prijeđimo na granicu z u (4) i pomnožimo obje strane jednačine sa E na desnoj strani, dobićemo F(w t ε) F(w t ε) jw (w t) jw jw (w t) ε ε e F ε ε E+ ε λf ε E= P I E= E (e) () 3 Zamijenite ovdje (9) i primijenite proširenje e = + jε w+ + O(ε ) dobijamo Φ(wt) (jεw) 3 ε RE+ λφ (wt) RE = Φ (wt)[ R () + f ()] E jw ε + + O(ε) Smanjenje sličnih redukcija za ε koristeći notaciju (6 ) i prelazeći na granicu na ε dobijamo sledeću diferencijalnu jednačinu za nepoznatu funkciju Φ (w t): Φ(wt) (jw) = Φ(wt) (λ+κ) (jw) rešavajući koju pod početnim uslovom Φ (w) = dobijamo Φ (wt) = exp (λ+κ) t Zamenom ovog izraza u (8) dobijamo (5) Teorema je dokazana Aproksimacija distribucije broja događaja koji se dešavaju u HISM toku Pravljenje promena u (5) obrnuto od (3) i vraćajući se na funkciju H(u z t) dobijamo (ju) H(u z t) R (z)exp juλ Nt + (λ+κ) Nt Dakle, karakteristična funkcija broja događaji koji se dešavaju u polumarkovskom strujanju visokog intenziteta tokom vremena t zadovoljava relaciju (ju) hut () = H(u t) E exp juλ Nt+ (λ+κ) Nt To jest, za dovoljno velike vrijednosti N raspodjela broja događaja koji se dešavaju u toku HISM tokom vremena t može se aproksimirati normalnom distribucijom sa matematičkim očekivanjem λnt i varijansom (λ + κ)nt pri čemu su λ i κ određeni izrazima (7) i (6) Numerički rezultati Kao primjer za numerički proračuni Razmotrimo problem modeliranja događaja u polu-Markovljevom toku visokog intenziteta određenom polu-Markovljevom matricom trećeg reda A(x) zapisanom u obliku A(x) = P * G(x) gdje je P stohastička matrica; G(x) je matrica sastavljena od nekih funkcija distribucije; operacija * Adamardov proizvod matrica Razmotrićemo primjer kada elementi matrice G(x) odgovaraju funkcijama gama raspodjele s parametrima oblika α kν i skale β kν k ν = 3, koje ćemo predstaviti u obliku matrica α i β Odabraćemo sledeće specifične vrednosti parametara: P = 3 5 α = 5 4 β = Kao rezultat proračuna, dobijene su sledeće vrednosti parametara: λ 99; κ 96 Za ovaj problem izvršena je simulacija protoka za vrijednosti N = 3 i konstruirane su empirijske distribucije broja događaja u intervalima dužine t =. Serije distribucija empirijskih podataka i odgovarajuće aproksimacije za N = i N = su grafički prikazano na slici (za ostale vrijednosti N, grafikoni se skoro poklapaju i ne mogu se razlikovati na slici) TUSUR izvještava 3 (9) 3. septembar
6 4 4 UPRAVLJANJE RAČUNARSKOM INŽENJERSTVOM I INFORMACIJOM 5 8 N = N = sl. Kolmogorovljeva udaljenost Dq = sup Fq(x) F(x) Ovdje F q (x) empirijska funkcija distribucije F(x) funkcija x distribucije normalne slučajne varijable sa karakteristikama pronađenim iznad Tabela prikazuje ovisnost kvaliteta aproksimacije na vrijednost N N δ relativne greške pri izračunavanju matematičkog a δ D D q 8% 6% 464 očekivanja δ a i varijanse δ D kao i Kolmogorovljeve udaljenosti D q za razmatrane slučajeve 9% 7% % 5% Slika prikazuje graf koji prikazuje % 4% 44 smanjenje Kolmogorovljeve udaljenosti između empirijske i 8% % analitičke (normalne) distribucije s povećanjem vrijednosti N D q Možete primijetiti da je već pri 5 N > 3, dovoljno visok kvalitet Gaussovog Postiže se aproksimacija broja događaja u razmatranom poluMarkovljevom toku visokog intenziteta (kolmogorovljeva udaljenost ne prelazi) 3 Slika Promjena Kolmogorovljeve udaljenosti D q u zavisnosti od intenziteta strujanja (logaritamska skala u N) N Zaključak rad predstavlja proučavanje polu-Markovljevog toka događaja visokog intenziteta. Pokazuje se da, pod uslovom neograničenog rasta njegovog intenziteta, distribucija broja događaja koji se dešavaju u datom toku tokom vremenskog intervala fiksne dužine može biti aproksimirani normalnom distribucijom.U radu su dobijeni parametri ove raspodjele.Razmatrani numerički primjeri demonstriraju primjenjivost dobijenih asimptotičkih rezultata za HISM-tokove događaja Slični rezultati su ranije dobijeni za druge tipove strujanja visokog intenziteta: periodični MMPP MAP TUSUR Izvještaji 3 (9) 3. septembar
7 AN Moiseev AA Nazarov Asimptotička analiza polu-Markovljevog toka visokog intenziteta 5 Literatura Gnedenko BV Uvod u teoriju čekanja / BV Gnedenko IN Kovalenko 4. izdanje revizija M: Izdavačka kuća LKI 7 4 s Gračev VV Multifazni model raspodjele sistem za obradu podataka / VV Grachev AN Moiseev AA Nazarov VZ Yampolsky // TUSUR izvještaji (6) h C Moiseev A Istraživanje visokog intenzivnog opšteg toka / A Moiseev A Nazarov // Proc of IV Međunarodna konferencija “Problemi kibernetike i informatike” ( PCI) Baku: IEEE P Moiseev Istraživanje visoko intenzivnog Markov-moduliranog Poissonovog procesa / A Moiseev A Nazarov // Proc of the International Conference on Application of Information and Communication Technology and Statistics in Economy and Education (ICAICTSEE-) Sofia: University Nacionalne i svjetske ekonomije P Moiseev AN Proučavanje MAP toka visokog intenziteta / AN Moiseev AA Nazarov // Izv. Tom Polytechnic University 3 T 3 S Korolyuk VS Stohastički modeli sistema Kijev: Nauk Dumka s 7 Nazarov AA Teorija vjerovatnoće i slučajnosti procesi: udžbenik / AA Nazarov AF Terpugov-e izd ispr Tomsk: Izdavačka kuća NTL 4 str 8 Nazarov AA Metoda asimptotske analize u teoriji čekanja / AA Nazarov SP Moiseeva Tomsk: Izdavačka kuća NTL 6 str 9 Korn G Priručnik iz matematike za naučnike i inženjeri / G Korn T Korn M: Nauka sa Rykovom VV Matematička statistika i eksperimentalno planiranje: udžbenik / VV Rykov VY Itkin M: MAKS Press 38 sa Moisejevim Aleksandrom Nikolajevičem Kandidat tehničkih nauka vanredni profesor, Odsjek za softversko inženjerstvo, Tomsk State University (TSU) ) Tel: 8 (38-) Email: Nazarov Anatolij Andrejevič Doktor tehničkih nauka Profesor Šef katedre za teoriju vjerovatnoće i matematičku statistiku TSU Tel: 8 (38-) Email: Moiseev AN Nazarov AA Asimptotička analiza visokointenzivne polu -Markovski proces pristizanja U radu je prikazano istraživanje visokointenzivnog polumarkovskog procesa dolaska. Pokazuje se da distribucija broja dolazaka u proces tokom nekog perioda pod asimptotičkim uslovom beskonačnog rasta brzine procesa može biti aproksimirano normalnom distribucijom Dobijene su i karakteristike aproksimacije. Rezultati analize su potkrijepljeni numeričkim primjerima Ključne riječi: visokointenzivan dolazni proces polumarkovski proces asimptotska analiza TUSUR Reports 3 (9) 3. septembar
BIBLIOGRAFIJA. Balasanyan S.Sh. Stratifikovani model za procenu i analizu efikasnosti funkcionisanja složenih tehnoloških sistema sa mnogim državama // Vesti Politehnike Tomsk
ASIMPTOTSKA ANALIZA OTVORENE PETLJE NEMARKOVSKIH PITANJA MREŽE HIMMPP (GI) K A. Nazarov, A. Moiseev Državni univerzitet Tomsk Tomsk, Rusija [email protected] Rad predstavlja
BILTEN DRŽAVNOG UNIVERZITETA TOMSK 2008 Katedra za računarstvo i informatiku 3(4) UDK 6239; 592 SV Lopukhova ISTRAŽIVANJE MMR PROTOKA ASIMPTOTSKOM METODOM TH RED U radu se razmatra
S.A. Matveev, A.N. Moiseev, A.A. Nazarov. Primjena metode početnih momenata 9 UDK 59.87 S.A. Matveev, A.N. Moiseev, A.A. Nazarov Primena metode početnih momenata za proučavanje višefaznog sistema
BILTEN DRŽAVNOG UNIVERZITETA TOMSK 7 Menadžment računarske tehnologije i informacionih nauka UDK 5987 TA Karlykhanova SIFT FLOW METODA ZA PROUČAVANJE GI/GI/ SISTEMA Za sistem čekanja
UDK 6.39.; 59. S.V. Lopukhova A.A. Nazarov PROUČAVANJE MAR-TOKA METODOM ASIMPTOTSKE ANALIZE N-TOG REDA Razmatra se MAR-tok. Ovaj tok je proučavan asimptotičkom metodom.
BILTEN DRŽAVNOG UNIVERZITETA TOMSK 8 Menadžment računarske tehnologije i informacionih nauka 4(5) MATEMATIČKO MODELIRANJE UDK 59.87 V.A. Vavilov A.A. Nazarov MATEMATIČKO MODELIRANJE NESTABILNOG
Ogranak Kemerovskog državnog univerziteta u Anžero-Sudžensku Nacionalni istraživački Tomski državni univerzitet Kemerovski državni univerzitet Institut za probleme menadžmenta
BILTEN DRŽAVNOG UNIVERZITETA TOMSK Menadžment računarske tehnologije i informacionih nauka 3() UDK 59.87 I.A. Ivanovskaya S.P. Moiseeva ISTRAŽIVANJE MODELA PARALELNE USLUGE VIŠE NARUDŽBINA
BILTEN DRŽAVNOG UNIVERZITETA TOMSK 2011 Menadžment, računarska tehnologija i informacione nauke 3(16) OBRADA INFORMACIJA UDK 519.872 I.L. Lapatin, A.A. Nazarov KARAKTERISTIKE MARKOV SISTEMA
AA. Nazarov I.A. Semenov. Poređenje asimptotičkih i predgraničnih karakteristika 187 UDK 4.94:519.872 A.A. Nazarov I.A. Semenova Poređenje asimptotičkih i predgraničnih karakteristika MAP/M/ sistema
Ogranak Kemerovskog državnog univerziteta u Anžero-Sudžensku Nacionalni istraživački Tomski državni univerzitet Kemerovski državni univerzitet Institut za probleme menadžmenta
Statistička radiofizika i teorija informacija Predavanje 7 8. Kontinuirani Markovi lanci Kontinuirani Markovi lanci su Markovljev slučajni proces X t, koji se sastoji od
BILTEN DRŽAVNOG UNIVERZITETA TOMSK 9 Menadžment računarske tehnologije i informacionih nauka (7) MATEMATIČKO MODELIRANJE UDK 5987 VA Vavilov MATEMATIČKO MODELIRANJE NESTABILNIH SLUČAJNIH MREŽA
POGLAVLJE 5. MARKOVSKI PROCESI SA KONTINUALNIM VREMENOM I DISKRETNIM SKUPOM STANJA Kao rezultat proučavanja ovog poglavlja, studenti treba da: poznaju definicije i svojstva Markovljevih procesa sa kontinuiranim
Kao rukopis Zadiranova Lyubov Aleksandrovna ISTRAŽIVANJE MATEMATIČKIH MODELA PROTOKA U BESKONAČNO LINEARNIM QS SA PONOVLJENIM ODRŽAVANJEM ZAHTEVA 05.13.18 Matematičko modeliranje, numeričko
BILTEN DRŽAVNOG UNIVERZITETA TOMSK 7 Menadžment računarske tehnologije i informacionih nauka UDK 59 NV Stepanova AF Terpugov UPRAVLJANJE CIJENAMA U PRODAJI KVARLJIVIH PROIZVODA Razmatra se upravljanje
BILTEN DRŽAVNOG UNIVERZITETA TOMSK Menadžment, računarska tehnologija i informacione nauke () UDK 59.865 K.I. Livšits, Ya.S. Bagel VEROVATNOST PROPADA OSIGURAVAJUĆE KOMPANIJE POD DUPLOM STOHASTIKOM
UDK 6-5 Spektralne karakteristike linearnih funkcionala i njihove primjene u analizi i sintezi stohastičkih upravljačkih sistema K.A. Rybakov Članak uvodi koncept spektralnih karakteristika linearnog
Kao rukopis Lapatin Ivan Leonidovič ISTRAŽIVANJE MATEMATIČKIH MODELA IZLAZNOG TOKA SISTEMA REDOVA SA NEOGRANIČENIM BROJOM UREĐAJA 13.05.18. Matematičko modeliranje, numeričko
Sadržaj Poglavlje Slučajni procesi Jednostavan homogeni Markovljev lanac Markovljeva jednadžba Jednostavan homogeni Markovljev lanac 4 Osobine prelazne matrice 5 Numerički eksperiment: stabilizacija distribucije vjerovatnoće
INSTITUT ZA RAČUNARSKU MATEMATIKU I MATEMATIČKU GEOFIZIKU SIBIRSKO ODRŽANJE RUSKE AKADEMIJE NAUKA MARČUKOV NAUČNA ČITANJA 017 5. jun 14. jula 017. Zbornik radova Uredništvo akademici
PROUČAVANJE RQ-SISTEMA M GI 1 METODOM ASIMPTOTSKE ANALIZE U USLOVIMA TEŠKOG OPTEREĆENJA E. Moiseeva, A. Nazarov Tomski državni univerzitet Tomsk, Rusija [email protected] Rad smatra
UDK 6-5:59 NS Demin SV Rozhkova OV Rozhkova FILTERIRANJE U DINAMSKIM SISTEMIMA KONTINUIJNO-DISKRETNIM POSMATRANJAMA SA PAMĆENJEM U PRISUSTVO ANOMALNE INTERFERENCIJE II KONTINUIRANO-DISKRETNO PROMATRANJE U ovom radu
Numeričke metode Tema 2 Interpolacija V I Velikodny 2011 2012 akademska godina 1 Koncept interpolacije Interpolacija je metoda približno ili tačnog pronalaženja bilo koje vrijednosti iz poznatih pojedinačnih vrijednosti
Ukrainian Mathematical Journal, svezak 5 (28), 3, 293 34 O graničnim problemima za obični diferencijalni operator s matričnim koeficijentima Anna V Agibalova (Predstavio M M Malamud) Sažetak
Predavanje 2. Statistika prvog tipa. Tačkaste procjene i njihova svojstva Bure V.M., Grauer L.V. ShAD Sankt Peterburg, 2013. Bure V.M., Grauer L.V. (SHAD) Predavanje 2. Statistika prvog tipa. Tačkasti Sankt Peterburg,
Menadžment računarske tehnologije i informacionih nauka UDK 6-5:59 ISTRAŽIVANJE EFIKASNOSTI DISKRETNOG KANALA ZA POSMATRAĆANJE SA PAMĆENJEM U PROBLEMU EKSTRAPOLACIJE NS Demin OV Rožkova* Tomski državni univerzitet
Statistička radiofizika i teorija informacija Predavanje 6 7. Markovljevi* slučajni procesi i Markovljevi lanci. *Markov Andrej Andrejevič (rođen 1890) ruski matematičar, akademik Markov slučajni proces
Sibirski matematički časopis jul avgust 2003. Svezak 44, 4 UDK 51921+5192195 O KOMPONENTIMA ZASTUPANJA FAKTORIZACIJE ZA VREME STANOVANJA POLU-KONtinuiranih nasumičnih šetnji u OPRU U S Lugavówu
Kao rukopis Gorbatenko Anna Evgenievna ISTRAŽIVANJE SISTEMA REDOVA SA KORELATIVNIM TOKOVIMA POD POSEBNIM GRANIČNIM USLOVIMA 13.05.18 Matematičko modeliranje, numeričke metode
Menadžment računarske tehnologije i informacionih nauka UDK 59. INFORMACIJSKI ASPEKT U ZAJEDNIČKOM PROBLEMU KONTINUIRANO-DISKRENOG FILTRIRANJA I INTERPOLACIJE. ANALIZA S.V. Rozhkova O.V. Rozhkova Tomsk Politehnika
Sibirski matematički časopis jul avgust 2005. Svezak 46, 4 UDK 519.21 O FAKTORIZACIJSKIM REPREZENTACIJAMA U GRANIČNIM PROBLEMIMA ZA NASLUČAJNE ŠETNJE ZADANE NA MARKOVOM LANCU V. I. Lotov, N. G. Orlova
Predavanje 3 Stabilnost ravnoteže i kretanja sistema Kada se razmatraju ustaljena kretanja, zapisujemo jednačine poremećenog kretanja u obliku d dt A Y gdje je vektor stupca kvadratna matrica konstantnih koeficijenata
Poglavlje 1 Diferencijalne jednačine 1.1 Koncept diferencijalne jednačine 1.1.1 Problemi koji vode do diferencijalnih jednačina. U klasičnoj fizici svaka fizička veličina je povezana sa
Predavanje KARAKTERISTIČKA FUNKCIJA SVRHA PREDAVANJA: konstruisati metodu za linearizaciju funkcija slučajnih varijabli; uvesti pojam kompleksne slučajne varijable i dobiti njene numeričke karakteristike; odrediti karakteristiku
Modeliranje sistema pomoću Markovljevih slučajnih procesa Osnovni koncepti Markovljevih procesa Funkcija X(t) se naziva slučajna ako je njena vrijednost za bilo koji argument t slučajna varijabla.
1. KONAČNI HOMOGENI MARKOVSKI LANCI Razmotrimo niz slučajnih varijabli ξ n, n 0, 1,..., od kojih je svaka diskretno raspoređena i uzima vrijednosti iz istog skupa (x 1,...,
Poglavlje 6 Osnove teorije stabilnosti Predavanje Izjava problema Osnovni koncepti Ranije je pokazano da rješenje Cauchyjevog problema za normalan sistem ODE = f, () kontinuirano zavisi od početnih uslova na
Sin cos R Z cos ImZ cos sin sin Ovako pronađena rješenja čine fundamentalni sistem rješenja i stoga opšte rješenje sistema ima oblik ili, detaljnije, sin cos cos sin cos cos cos sin sin
Pouzdanost konstrukcije. Teorija i praksa Kashtanov V.A. KONTROLA STRUKTURE U MODELIMA REDOVANJA I POUZDANOSTI Koristeći kontrolisane polu-Markovljeve procese, optimalna je
MATEMATIČKI MODEL DRUŠTVA ZA OSIGURANJE U FORMU SISTEMA USLUGE RED M M I. Sinyakova, S. Moiseeva Nacionalni istraživački Tomski državni univerzitet Tomsk, Rusija [email protected]
UDK 59. TEOREMA RAZDVAJANJA U SLUČAJU ZAPAŽANJA SA PAMĆENJEM N.S. Demin, S.V. Rožkova Tomski državni univerzitet Tomski politehnički univerzitet E-mail: [email protected] Dokaz je dat
Prema uslovima teoreme L B (m Tada, zbog linearnosti operatora L, imamo: m m m L L ] B [ Sistemi linearnih diferencijalnih jednadžbi sa konstantnim koeficijentima Svojstvene vrijednosti i svojstveni vektori
REFERENCE Kalashnikova TV Izvekov NU Integracija metode orijentacije na potražnju u cjenovni sistem maloprodajnog lanca // News of Tomsk Polytechnic University T 3 6 S 9 3 Fomin
INSTITUT ZA RAČUNARSKU MATEMATIKU I MATEMATIČKU GEOFIZIKU SIBIRSKO ODRŽANJE RUSKOG AKADEMIJE NAUKA MARČUKOV NAUČNA ČITANJA 217 25. jun 14. jula 217. Zbornik radova Uredništvo akadem.
TEMA 7. Slučajni procesi. Svrha sadržaja teme 7 je da da početne pojmove o slučajnim procesima i Markovljevim lancima posebno; ocrtati raspon ekonomskih problema koje modeli koriste u svom rješavanju,
Predavanje 4. Intervali povjerenja Bure V.M., Grauer L.V. ShAD Sankt Peterburg, 2013. Bure V.M., Grauer L.V. (SHAD) Predavanje 4. Intervali povjerenja Sankt Peterburg, 2013. 1 / 49 Sadržaj Sadržaj 1 Intervali povjerenja
Sibirski matematički časopis Januar Februar, 2. Svezak 41, 1 UDK 517.948 ASIMPTOTIKA RJEŠENJA SINGULARNO PERTURBOVANIH NELINEARNIH INTEGRODIFERENCIJALNIH JEDNAČINA M. K. Dauylbaev Apstrakt: Razmatrano singularno
Predavanje Modeliranje sistema pomoću Markovljevih slučajnih procesa Osnovni koncepti Markovljevih procesa Funkcija X(t) se naziva slučajna ako je njena vrijednost za bilo koji argument t slučajna
7 (), 9 G. V. Boykova o svijetu svijeta Sažetak: za diferencijalnu jednačinu drugog reda pronađeno je rješenje koje predstavlja
PRIRODNE I EKZACTNE NAUKE UDK 57977 O UPRAVLJANJU LINEARNIM SINGULARNO poremećenim SISTEMA SA MALIM KAŠNJENJEM Kandidat fizičko-matematičkih nauka vanredni profesor KOPEYKINA T B GUSEINOVA A S Beloruski nacionalni teh.
Računarsko modeliranje. SMO. Predavanje 2 1 Sadržaj Poglavlje 2. Reprezentacija QS-a Markovljevim slučajnim procesom... 1 I. Klasifikacija QS prema Kendall-u... 1 II. Markov slučajni proces... 2 III. Markovsky
48 Vestnik RAU Serija fizičke, matematičke i prirodne nauke, 1, 28, 48-59 UDK 68136 PROCJENA KARAKTERISTIKA POUZDANOSTI SISTEMA ZA UČENJE NA DALJINU 2. DIO HV Kerobyan, NN Khublaryan, AG Oganesyan
Osnovni koncepti teorije razlika šema. Primjeri konstruiranja dijagrama za početno-granične probleme. Veliki broj problema u fizici i tehnologiji dovodi do graničnih ili početnih graničnih problema za linearne
4 (0) 00 Bayesova analiza kada je procijenjeni parametar slučajni normalan proces Razmatra se problem Bayesove procjene niza nepoznatih prosječnih vrijednosti q q... q...
RUSKI TEHNOLOŠKI UNIVERZITET MIREA DODATNA GLAVA VISOKE MATEMATIKE POGLAVLJE 3. SISTEMI DIFERENCIJALNIH JEDNAČINA Rad je posvećen modeliranju dinamičkih sistema pomoću elemenata
SISTEMI LINEARNIH DIFERENCIJALNIH JEDNAČINA SA KONSTANTNIM KOEFICIJENTIMA Svođenje na jednu jednačinu th reda Sa praktične tačke gledišta, linearni sistemi sa konstantnim koeficijentima su veoma važni
1 Naslov dokumenta Ovsyannikov A.V. STATISTIČKE NEJEDNAKOSTI U SUPERPRAVILNIM STATISTIČKIM EKSPERIMENTIMA TEORIJE PROCJENE // West National Academy of Sciences Belarus, 009. Ser fz-mat. navuk. P.106-110
UDK 59 EV Novitskaya AF Terpugov ODREĐIVANJE OPTIMALNOG VOLUMINA MNOGE PROIZVODA I MALOPRODAJNE CIJENE PRODAJE KONTINUALNO KVARIVIH PROIZVODA Razmatra se problem određivanja optimalnog volumena serije robe.
Moskovski državni tehnički univerzitet po imenu NE Bauman Fakultet fundamentalnih nauka Katedra za matematičko modeliranje A. K. K. K., A. K. ZAMJENA
Math-Net.Ru Sveruski matematički portal A. A. Nazarov, T. V. Lyubina, Ne-Markovski dinamički RQ sistem sa dolaznim MMP protokom zahteva, Avtomat. i telemekh., 213, izdanje 7, 89 11 Upotreba
MINISTARSTVO PROSVETE RUSKE FEDERACIJE KRASNOJSKI DRŽAVNI UNIVERZITET UDC BBK Sastavio: N.A. Pinkina KATEDRA ZA VIŠU MATEMATIKU Linearna algebra. Rješavanje tipičnih primjera. Opcije testiranja
Predavanje 2 Rješavanje sistema linearnih jednačina. 1. Rješavanje sistema 3 linearne jednadžbe korištenjem Cramerove metode. Definicija. Sistem od 3 linearne jednačine je sistem oblika U ovom sistemu tražene veličine su
Učitavanje...