Järjekorra teooria. Praktilises tunnis vaatleme seda teed ja võrdleme simulatsiooni tulemusi teoreetilise lahendusega

Näited süsteemiprobleemide lahendamisest järjekorras seismine

See on vajalik ülesannete 1–3 lahendamiseks. Algandmed on toodud tabelis. 2–4.

Mõned järjekorrateoorias valemite jaoks kasutatud tähistused:

n on QS kanalite arv;

λ on sissetuleva rakenduste voo intensiivsus P in;

v on rakenduste väljuva voo intensiivsus P out;

μ on teenuse P voo intensiivsus;

ρ on süsteemi koormuse indikaator (liiklus);

m on maksimaalne kohtade arv järjekorras, mis piirab taotluste järjekorra pikkust;

i on päringu allikate arv;

p k on süsteemi k-nda oleku tõenäosus;

p o - kogu süsteemi jõudeoleku tõenäosus, st tõenäosus, et kõik kanalid on vabad;

p syst on rakenduse süsteemi vastuvõtmise tõenäosus;

p ref - taotluse tagasilükkamise tõenäosus selle süsteemi vastuvõtmisel;

р umbes - tõenäosus, et rakendust teenindatakse;

A on süsteemi absoluutne läbilaskevõime;

Q on süsteemi suhteline läbilaskevõime;

och - keskmine taotluste arv järjekorras;

r on teenindatavate rakenduste keskmine arv;

syst on keskmine rakenduste arv süsteemis;

pt on keskmine taotluse ooteaeg järjekorras;

r on päringu keskmine kättetoimetamise aeg, mis on seotud ainult teenindatud päringutega;

sys on rakenduse keskmine viibimisaeg süsteemis;

oj on keskmine aeg, mis piirab taotluse ooteaega järjekorras;

on hõivatud kanalite keskmine arv.

QS A absoluutne läbilaskevõime on rakenduste keskmine arv, ĸᴏᴛᴏᴩᴏᴇ saab süsteem teenindada ajaühikus.

Suhteline QS-i läbilaskevõime Q on süsteemi poolt ajaühikus teenindatavate päringute keskmise arvu ja selle aja jooksul saadud päringute keskmise arvu suhe.

Järjekorraprobleemide lahendamisel on äärmiselt oluline järgida järgmist järjestust:

1) QS tüübi määramine vastavalt tabelile. 4,1;

2) valemite valik vastavalt QS tüübile;

3) probleemide lahendamine;

4) probleemi kohta järelduste sõnastamine.

1. Surma ja paljunemise skeem. Teame, et kui meie käsutuses on märgistatud olekugraafik, saame hõlpsasti kirjutada Kolmogorovi võrrandeid olekutõenäosuste jaoks, samuti kirjutada ja lahendada algebralised võrrandid lõplike tõenäosuste jaoks. Tasub öelda, et mõnel juhul on viimased võrrandid

otsustage sõna otseses mõttes ette. Eelkõige saab seda teha siis, kui süsteemi olekugraafik on niinimetatud ʼʼsurma ja taastootmise skeemʼʼ.

Surma ja paljunemise skeemi olekugraafik on joonisel fig. 19.1. Selle graafiku eripära on see, et süsteemi kõiki olekuid saab laiendada üheks ahelaks, milles iga keskmine olek ( S 1 , S 2 ,…,S n-1) on ühendatud edasi- ja tagurpidi noolega iga naaberolekuga - parem ja vasak ning äärmuslikud olekud (S 0 , S n) - ainult ühe naaberriigiga. Mõiste ʼʼsurma ja paljunemise skeemʼʼ pärineb bioloogilistest probleemidest, kus selline skeem kirjeldab populatsiooni suuruse muutumist.

Surma ja paljunemise skeemi kohtab väga sageli erinevates praktikaprobleemides, eriti - järjekorra teoorias on sellega seoses kasulik üks kord ja igaveseks leida selle jaoks olekute lõplikud tõenäosused.

Oletame, et kõik sündmuste vood, mis edastavad süsteemi piki graafiku nooli, on kõige lihtsamad (lühiduse huvides nimetame süsteemiks ka S ja selles toimuv protsess – kõige lihtsam).

Kasutades joonisel fig. 19.1, koostame ja lahendame oleku lõpptõenäosuste algebralised võrrandid), olemasolu tuleneb sellest, et igast olekust saab minna igasse teise, olekute arv on lõplik). Esimese osariigi jaoks S 0 meil on:

(19.1)

Teise oleku jaoks S1:

(19.1) tõttu taandatakse viimane võrdsus vormile

kus k võtab kõik väärtused 0 kuni P. Nii et lõplikud tõenäosused p0, p1,..., p n rahuldavad võrrandid

(19.2)

lisaks peame arvestama normaliseerimise tingimusega

lk 0 + lk 1 + lk 2 +…+ lk n = 1. (19.3)

Lahendame selle võrrandisüsteemi. Esimesest võrrandist (19.2) väljendame lk 1 läbi R 0 :

lk 1 = lk 0. (19.4)

Teisest, võttes arvesse (19.4), saame:

(19.5)

‣‣‣ alates kolmandast, võttes arvesse (19.5),

(19.6)

ja üldiselt mis tahes k(alates 1 kuni n):

(19.7)

Pöörame tähelepanu valemile (19.7). Lugeja on kõigi vasakult paremale suunduvate noolte intensiivsuste korrutis (algusest kuni antud olek S k) ja nimetajas - kõigi paremalt vasakule suunduvate noolte intensiivsuste korrutis (algusest kuni Sk).

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, kõik olekutõenäosused R 0 , lk 1 , ..., р n väljendatud ühe neist ( R 0). Asendame need avaldised normaliseerimistingimusega (19.3). Saame sulgudes R 0:

siit saame väljendi jaoks R 0 :

(tõstsime sulgu astmeni -1, et mitte kirjutada kahekorruselisi murde). Kõik muud tõenäosused on väljendatud R 0 (vt valemeid (19.4) - (19.7)). Pange tähele, et koefitsiendid R 0 neist ei ole midagi muud kui järjestikused liikmed pärast ühikut valemis (19.8). Niisiis, arvutades R 0 , oleme kõik need koefitsiendid juba leidnud.

Saadud valemid on väga kasulikud järjekorrateooria lihtsamate ülesannete lahendamisel.

^ 2. Väike valem. Nüüd tuletame ühe olulise valemi, mis on seotud (piirava, statsionaarse režiimi jaoks) rakenduste keskmise arvuga L syst, mis asub järjekorrasüsteemis (st teenindatakse või seisab järjekorras) ja rakenduse keskmine viibimisaeg süsteemis W süsteem

Vaatleme mis tahes QS-i (ühe kanaliga, mitme kanaliga, markovi, mitte-Markovi, piiramatu või piiratud järjekorraga) ja kahte sellega seotud sündmuste voogu: QS-i saabuvate klientide voogu ja teenusest lahkuvate klientide voogu. QS. Kui süsteemis on kehtestatud piirav, statsionaarne režiim, siis QS-i saabuvate rakenduste keskmine arv ajaühikus võrdub sealt väljuvate rakenduste keskmise arvuga: mõlema voo intensiivsus λ on sama.

Tähistage: X(t) – taotluste arv, mis saabusid ühisele turukorraldusele enne hetke t. Y(t) - ühisturust lahkunud taotluste arv

hetkeni t. Mõlemad funktsioonid on juhuslikud ja muutuvad järsult (suurenevad ühe võrra) päringu saabumise hetkel (X(t)) ja taotluste lahkumised (Y(t)). Funktsioonide tüüp X(t) ja Y(t) näidatud joonisel fig. 19,2; mõlemad read on astmelised, ülemine on X(t), madalam- Y(t). Ilmselgelt igaks hetkeks t nende erinevus Z(t)= X(t) - Y(t) pole midagi muud kui rakenduste arv QS-is. Kui read X(t) ja Y(t) liita, süsteemis pole päringuid.

Mõelge väga pikale ajavahemikule T(mõtteliselt jätkates graafikut palju kaugemale joonisest) ja arvutage selle jaoks välja keskmine rakenduste arv QS-is. See on võrdne funktsiooni integraaliga Z(t) sellel intervallil jagatud intervalli pikkusega T:

L süsteem = . (19.9) o

Kuid see integraal pole midagi muud kui joonisel fig. 19.2. Vaatame seda pilti hästi. Joonis koosneb ristkülikutest, millest igaühe kõrgus on võrdne ühega ja alus on võrdne viibimisajaga vastava järjekorra süsteemis (esimene, teine ​​jne). Märgime need ajad ära t1, t2,... Tõsi, intervalli lõpus T mõned ristkülikud sisenevad varjutatud joonisele mitte täielikult, vaid osaliselt, kuid piisavalt suurena T need pisiasjad ei loe. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, võime eeldada, et

(19.10)

kus summa kehtib kõikide ajal saadud tellimuste kohta T.

Eraldame parem- ja vasak pool(.19.10) intervalli pikkuse järgi T. Saame, võttes arvesse (19.9),

L süsteem = . (19.11)

Jaga ja korruta parem pool(19.11) intensiivsusele X:

L süsteem = .

Aga suurusjärk Tλ ei ole midagi muud kui selle aja jooksul laekunud taotluste keskmine arv ^ T. Juhul, kui jagame kõigi aegade summa t i keskmise taotluste arvu kohta, siis saame rakenduse keskmise süsteemis viibimise aja W süsteem Niisiis,

L süsteem = λ W süsteem ,

W süsteem = . (19.12)

See on Little'i imeline valem: mis tahes QS-i jaoks, mis tahes rakenduste voo olemuse jaoks, mis tahes teenindusaja jaotuse jaoks, mis tahes teenindusdistsipliini jaoks kliendi keskmine viibimisaeg süsteemis võrdub keskmise klientide arvuga süsteemis jagatud kliendivoo intensiivsusega.

Täpselt samamoodi tuletatakse Little'i teine ​​valem, mis seostab rakenduse keskmist järjekorras veedetud aega ^ Oeh ja keskmine taotluste arv järjekorras L oh:

W oh = . (19.13)

Väljundi jaoks piisab joonise fig. alumise rea asemel. 19.2 võta funktsioon U(t)- hetkeni jäänud taotluste arv t mitte süsteemist, vaid järjekorrast (kui süsteemi sisenenud rakendus ei lähe järjekorda, vaid läheb kohe teenindusse, siis võib ikkagi eeldada, et ta satub järjekorda, kuid jääb sinna nulli).

Little'i valemid (19.12) ja (19.13) mängivad järjekorrateoorias olulist rolli. Kahjuks on enamikus olemasolevates juhendites need valemid (tõestatud üldine vaade suhteliselt hiljuti) ei anta 1).

§ 20. Lihtsamad järjekorrasüsteemid ja nende omadused

Selles jaotises käsitleme mõningaid lihtsamaid QS-e ja tuletame nende omaduste (jõudlusnäitajate) avaldisi. Samal ajal demonstreerime põhilisi metodoloogilisi võtteid, mis on iseloomulikud elementaarsele, ʼʼʼʼʼʼ järjekorrateooriale. Me ei uuri QS-proovide arvu, mille jaoks karakteristikute lõplikud avaldised tuletatakse; see raamat ei ole järjekorra teooria juhend (sellist rolli täidavad palju paremini spetsiaalsed käsiraamatud). Meie eesmärk on tutvustada lugejale mõningaid nüansse, et hõlbustada järjekorra teooria läbimist, mis paljudes saadaolevates (isegi populaarseks pidavates) raamatutes võib tunduda räpase näitekoguna.

Kõiki sündmuste vooge, mis edastavad QS-i olekust olekusse, käsitleme selles jaotises kõige lihtsamat (ilma seda iga kord konkreetselt täpsustamata). Nende hulgas on nn teenuse voog. See tähendab päringute voogu, mida teenindab üks pidevalt hõivatud kanal. Selles voos on sündmuste vaheline intervall, nagu ikka kõige lihtsama voo puhul, eksponentsiaalse jaotusega (paljudes käsiraamatutes hoopis: ʼʼteenindusaeg on eksponentsiaalneʼʼ, me ise kasutame seda terminit edaspidi).

1) Populaarses raamatus on toodud Little'i valemi teistsugune, võrreldes ülaltooduga, tuletis. Üldiselt on selle raamatuga tutvumine (ʼʼKeskne vestlusʼʼ) kasulik esmaseks tutvumiseks järjekorra teooriaga.

Selles jaotises peetakse eksponentsiaalset teenindusaja jaotust iseenesestmõistetavaks, nagu alati "lihtsaima" süsteemi puhul.

Vaadeldava QS-i efektiivsuskarakteristikuid tutvustame ettekande käigus.

^ 1. P-kanali QS tõrgetega(Erlangi probleem). Siin käsitleme üht esimest ajaliselt ʼʼklassikalistʼʼ järjekorrateooria probleemi;

see probleem tekkis telefoniside praktilistest vajadustest ja selle lahendas meie sajandi alguses Taani matemaatik Erlant. Ülesanne on püstitatud järgmiselt: on P kanalid (sideliinid), mis võtavad vastu rakenduste voogu intensiivsusega λ. Teenindusvoo intensiivsus on μ (keskmise teenindusaja pöördväärtus t umbes). Leidke QS-i olekute lõplikud tõenäosused ja selle efektiivsuse omadused:

^A- absoluutne läbilaskevõime, st ajaühikus teenindatud rakenduste keskmine arv;

K- suhteline läbilaskevõime, st süsteemi poolt teenindatavate sissetulevate päringute keskmine osakaal;

^ R otk- ebaõnnestumise tõenäosus, st asjaolu, et rakendus jätab QS-i teenindamata;

k- keskmine hõivatud kanalite arv.

Lahendus. Süsteemi olekud ^S(QS) nummerdatakse vastavalt taotluste arvule süsteemis (antud juhul langeb see kokku hõivatud kanalite arvuga):

S 0 -ühises turukorralduses ei ole taotlusi,

S 1 - QS-is on üks päring (üks kanal on hõivatud, ülejäänud on vabad),

Sk- SMO-s on k rakendused ( k kanalid on hõivatud, ülejäänud on tasuta),

S n - SMO-s on P rakendused (kõik n kanalid on hõivatud).

QS oleku graafik vastab sigimisel suremise skeemile (joonis 20.1). Märgistame selle graafiku – märkige sündmuste voogude intensiivsus noolte lähedale. Alates S 0 tolli S1 süsteemi edastab päringute voog intensiivsusega λ (niipea kui päring saabub, hüppab süsteem S0 sisse S1). Sama rakenduste voog tõlgib

süsteemi mis tahes vasakpoolsest olekust külgnevasse parempoolsesse olekusse (vt ülemisi nooli joonisel 20.1).

Paneme alumiste noolte intensiivsuse alla. Süsteem olgu seisukorras ^S 1 (üks kanal töötab). See toodab μ teenust ajaühiku kohta. Panime noole alla S 1 →S 0 intensiivsus μ. Kujutage nüüd ette, et süsteem on olekus S2(töötavad kaks kanalit). Et ta läheks S 1, on vajalik, et kas esimene või teine ​​kanal lõpetaks hoolduse; nende teenusevoogude koguintensiivsus on 2μ; pane see vastava noole juurde. Kolme kanali kogu teenusevoo intensiivsus on 3 μ, k kanalid - km. Panime need intensiivsused alla joonisel fig. 20.1.

Ja nüüd, teades kõiki intensiivsusi, kasutame surma ja paljunemise skeemis lõplike tõenäosuste jaoks valmis valemeid (19.7), (19.8). Valemi (19.8) järgi saame:

Lagunemise terminid on koefitsiendid p 0 väljendites jaoks p1

Pange tähele, et valemid (20.1), (20.2) ei sisalda intensiivsusi λ ja μ eraldi, vaid ainult suhtena λ/μ. Tähistage

λ/μ = ρ (20,3)

ja me nimetame р väärtust ʼʼpäringute voo vähendatud intensiivsuseksʼʼ. Selle tähendus on ühe päringu keskmise teenindusaja jooksul saabunud päringute keskmine arv. Seda tähistust kasutades kirjutame valemid (20.1), (20.2) ümber järgmisel kujul:

Lõpliku oleku tõenäosuste valemeid (20.4), (20.5) nimetatakse Erlangi valemiteks – järjekorrateooria rajaja auks. Enamik teisi selle teooria valemeid (tänapäeval on neid rohkem kui seeni metsas) ei kanna erilisi nimetusi.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, leitakse lõplikud tõenäosused. Nende põhjal arvutame välja QS efektiivsuskarakteristikud. Kõigepealt leiame ^ R otk. - tõenäosus, et sissetulevast päringust keeldutakse (ei toimetata kätte). Selleks on vaja, et kõik P kanalid olid hõivatud, nii et

R otk = R n = . (20.6)

Siit leiame suhtelise läbilaskevõime – rakenduse kättetoimetamise tõenäosuse:

Q = 1 - P avatud = 1 - (20,7)

Saame absoluutse läbilaskevõime, korrutades päringuvoo intensiivsuse λ-ga K:

A = λQ = λ. (20.8)

Jääb vaid leida hõivatud kanalite keskmine arv k. Selle väärtuse võib leida ʼʼotseʼʼ, as oodatud väärtus diskreetne juhuslik suurus võimalike väärtustega 0, 1, ..., P ja nende väärtuste tõenäosused p 0 p 1, ..., p n:

k = 0 · p 0 +üks · p 1 + 2 · p 2 + ... + n · p n .

Asendades siin avaldised (20.5) jaoks R k , (k = 0, 1, ..., P) ja sooritades vastavad teisendused, saaksime lõpuks õige valemi k. Kuid me printime seda palju lihtsamalt (siin see on, üks "väikesi nippe"!) Tõepoolest, me teame absoluutset ribalaiust AGA. See pole midagi muud kui süsteemi teenindatavate rakenduste voo intensiivsus. Iga hõivatud i .shal ajaühiku kohta teenindab keskmiselt |l päringut. Seega keskmine hõivatud kanalite arv on

k = A/μ, (20.9)

või antud (20.8),

k = (20.10)

Soovitame lugejal näidet ise välja töötada.
Majutatud aadressil ref.rf
Seal on kolme kanaliga sidejaam ( n= 3), rakenduste voo intensiivsus λ = 1,5 (rakendusi minutis); keskmine teenindusaeg taotluse kohta t vol = 2 (min), on kõik sündmuste vood (nagu kogu selles lõigus) kõige lihtsamad. Leidke QS-i lõppoleku tõenäosused ja jõudlusnäitajad: A, Q, P otk, k. Igaks juhuks vastused siin: lk 0 = 1/13, lk 1 = 3/13, lk 2 = 9/26, lk 3 = 9/26 ≈ 0,346,

AGA≈ 0,981, K ≈ 0,654, P avatud ≈ 0,346, k ≈ 1,96.

Vastustest on muide näha, et meie QS on suures osas ülekoormatud: kolmest kanalist on keskmiselt hõivatud umbes kaks ja umbes 35% sissetulevatest rakendustest jääb teenindamata. Kutsume lugejat, kui ta on uudishimulik ja mitte laisk, välja selgitama: mitu kanalit on vaja, et rahuldada vähemalt 80% sissetulevatest taotlustest? Ja kui suur osa kanalitest jääb samal ajal jõude?

Mingi vihje on juba olemas optimeerimine. Tegelikult maksab iga kanali sisu ajaühiku kohta teatud summa. Samas toob iga hooldatud rakendus omajagu tulu. Korrutades selle tulu keskmise taotluste arvuga AGA, teenindatakse ajaühiku kohta, saame ühise turukorralduse keskmise tulu ajaühiku kohta. Kanalite arvu kasvuga see tulu loomulikult kasvab, kuid kasvavad ka kanalite ülalpidamisega seotud kulud. Mis kaalub üles – tulude või kulude kasv? See sõltub töötingimustest, ʼʼrakenduse teenustasustʼʼ ja kanali ülalpidamiskuludest. Neid väärtusi teades saate leida optimaalse kanalite arvu, mis on kõige kuluefektiivsem. Sellist probleemi me ei lahenda, jättes kõik selle sama "mittelaisa ja uudishimuliku lugeja" hooleks, et tuua välja näide ja see lahendada. Üldiselt arendab probleemide väljamõtlemine rohkem kui kellegi poolt juba püstitatud probleemide lahendamine.

^ 2. Ühe kanaliga QS piiramatu järjekorraga. Praktikas on üsna levinud ühekanaliline järjekorraga QS (patsiente teenindav arst; ühe kabiiniga taksotelefon; kasutaja tellimusi täitev arvuti). Järjekorrateoorias on erilisel kohal ka ühe kanaliga QS koos järjekorraga (selliste QS-i alla kuulub enamik seni mitte-Markovi süsteemide kohta saadud analüütilisi valemeid). Sel põhjusel pöörame erilist tähelepanu ühe kanaliga järjekorraga QS-idele.

Olgu siis ühe kanaliga QS järjekorraga, millele piiranguid ei sea (ei järjekorra pikkusele ega ooteajale). See QS võtab vastu päringute voo intensiivsusega λ ; teenusevoo intensiivsus μ on päringu keskmise teenindusaja pöördvõrdeline t umbes. On vaja leida QS-i olekute lõplikud tõenäosused ja selle efektiivsuse omadused:

L süsteem - keskmine rakenduste arv süsteemis,

W süsteem - rakenduse keskmine süsteemis viibimise aeg,

^L jah- järjekorras olevate taotluste keskmine arv,

W och - keskmine aeg, mille rakendus järjekorras veedab,

P zan - tõenäosus, et kanal on hõivatud (kanali koormuse aste).

Mis puutub absoluutsesse ribalaius AGA ja suhteline K, siis pole vaja neid arvutada:

kuna järjekord on piiramatu, siis iga taotlus toimetatakse varem või hiljem seoses sellega A \u003d λ, samal põhjusel Q= 1.

Lahendus. Süsteemi olekud, nagu varemgi, nummerdatakse vastavalt QS-is olevate rakenduste arvule:

S 0 - kanal on tasuta

S 1 - kanal on hõivatud (teenidab päringut), järjekorda pole,

S 2 - kanal on hõivatud, üks päring on järjekorras,

S k - kanal on hõivatud, k- 1 taotlust on järjekorras,

Teoreetiliselt ei piira olekute arvu miski (lõpmatult). Olekugraafikul on joonisel fig. 20.2. See on surma ja paljunemise skeem, kuid lõpmatu arvu olekutega. Kõigil nooltel edastab päringute voog intensiivsusega λ süsteemi vasakult paremale ja paremalt vasakule - teenuse voo intensiivsusega μ.

Kõigepealt küsigem endalt, kas sel juhul on lõplikud tõenäosused? Lõppude lõpuks on süsteemi olekute arv lõpmatu ja põhimõtteliselt at t → ∞ järjekord võib kasvada lõputult! Jah, see on tõsi: sellise QS-i lõplikud tõenäosused ei eksisteeri alati, vaid ainult siis, kui süsteem pole ülekoormatud. Võib tõestada, et kui ρ on rangelt väiksem kui üks (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ kasvab lõputult. See asjaolu tundub eriti "arusaamatu" ρ = 1 juures. Tundub, et süsteemile pole võimatuid nõudeid: ühe päringu teenindamise ajal saabub keskmiselt üks päring ja kõik peaks olema korras, kuid tegelikult on ei ole. Kui ρ = ​​1, saab QS päringute vooga hakkama ainult siis, kui antud voog on regulaarne ja teenindusaeg ei ole samuti juhuslik, võrdne päringute vahelise intervalliga. Sel ʼʼʼʼʼ juhul ei teki QS-is üldse järjekorda, kanal on pidevalt hõivatud ja väljastab regulaarselt teenindatud päringuid. Kuid niipea, kui päringute voog või teenusevoog muutub vähemalt veidi juhuslikuks, kasvab järjekord juba määramatult. Praktikas ei juhtu see ainult seetõttu, et ʼʼlõpmatu arv rakendusi järjekorrasʼʼ on abstraktsioon. Siin on mõned vead, mis võivad viia asendamiseni juhuslikud muutujad nende matemaatilised ootused!

Kuid pöördume tagasi meie piiramatu järjekorraga ühe kanaliga QS-i juurde. Rangelt võttes tuletasime surma ja taastootmise skeemi lõpptõenäosuste valemid ainult lõpliku arvu olekute korral, kuid võtame vabadused - me kasutame neid lõpmatu arvu olekute jaoks. Arvutame olekute lõpptõenäosused valemite (19.8), (19.7) järgi. Meie puhul on valemis (19.8) olevate liikmete arv lõpmatu. Saame väljendi jaoks p 0:

lk 0 = -1 =

\u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

Seeria valemis (20.11) on geomeetriline progressioon. Me teame seda ρ puhul< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателœем р.
Majutatud aadressil ref.rf
Kui p ≥ 1, seeria lahkneb (mis on kaudne, kuigi mitte range tõend selle kohta, et lõppoleku tõenäosused p 0 , p 1 , ..., p k , ... eksisteerivad ainult r jaoks<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

lk 0 = 1 - lk. (20.12)

Tõenäosused p 1 , p 2 , ..., p k ,... leiad valemitega:

p1 = ρ p 0, lk 2= ρ2 p 0,…,p k = ρ p0, ...,

kust (20.12) arvesse võttes leiame lõpuks:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ k(1 - p), . . .(20.13)

Nagu näete, tõenäosus p0, p1, ..., p k , ... moodustavad geomeetrilise progressiooni nimetajaga p.
Majutatud aadressil ref.rf
Kummalisel kombel suurim neist p 0 - tõenäosus, et kanal üldse tasuta saab. Olenemata sellest, kui koormatud süsteem järjekorraga on, kui see ainult rakenduste vooga üldse hakkama saab (ρ<1), самое вероятное число заявок в системе будет 0.

Leidke QS-is rakenduste keskmine arv ^L süsteem. . Siin tuleb natuke nokitseda. Juhuslik väärtus Z- taotluste arv süsteemis - on võimalikud väärtused 0, 1, 2, .... k,... tõenäosustega p0, p 1 , p 2 , ..., p k , ... Selle matemaatiline ootus on

L süsteem = 0 p 0 +üks · lk 1 + 2 lk 2 +…+k · lk k +…= (20.14)

(summat ei võeta 0-st ∞-ni, vaid 1-st ∞-ni, kuna nullliige on võrdne nulliga).

Asendame valemisse (20.14) avaldise p k (20.13):

L süsteem =

Nüüd võtame välja summa ρ (1-ρ) märgi:

L süsteem = ρ(1-ρ)

Siin rakendame jälle ʼʼtrikkiʼʼ: kρ k-1 pole midagi muud kui avaldise ρ tuletis ρ suhtes k; tähendab,

L süsteem = ρ(1-ρ)

Diferentseerimise ja liitmise tehteid vahetades saame:

L süsteem = ρ (1-ρ) (20,15)

Kuid summa valemis (20.15) pole midagi muud kui lõpmatult kahaneva geomeetrilise progressiooni summa esimese liikmega ρ ja nimetajaga ρ; see summa

võrdne , ja selle tuletis . Asendades selle avaldise väärtusega (20.15), saame:

L syst = . (20.16)

Noh, nüüd rakendame Little'i valemit (19.12) ja leiame rakenduse keskmise viibimisaja süsteemis:

W syst = (20.17)

Leidke järjekorras olevate rakenduste keskmine arv L och. Me vaidleme järgmiselt: järjekorras olevate rakenduste arv võrdub süsteemis olevate rakenduste arvuga, millest on lahutatud teenuses olevate rakenduste arv. Seega (vastavalt matemaatiliste ootuste liitmise reeglile) keskmine taotluste arv järjekorras L pt võrdub süsteemis olevate rakenduste keskmise arvuga L syst miinus teenindatavate päringute keskmine arv. Teenuse all olevate päringute arv peab olema kas null (kui kanal on vaba) või üks (kui see on kinni). Sellise juhusliku muutuja matemaatiline ootus on võrdne tõenäosusega, et kanal on hõivatud (me tähistasime seda R zan). Ilmselgelt R zan on võrdne ühega miinus tõenäosus p 0 et kanal on vaba: L ext ja selle ootamise keskmine aeg W väline (kaks viimast suurust on seotud Little'i valemiga). Lõpuks leidke päevane kogutrahv W, mille jaam peab tasuma rongide seisaku eest välistel rööbasteedel, kui jaam maksab trahvi a (rubla) ühe rongi ühetunnise seisaku eest. Igaks juhuks vastused siin: L süsteem = 2 (koostis), W süsteem = 1 (tund), L punktid = 4/3 (koosseis), W pt = 2/3 (tunnid), L väline = 16/27 (koostis), W väline = 8/27 ≈ 0,297 (tunnid). Keskmine päevatrahv W rongide välistel rööbasteedel ootamise eest saadakse, kui korrutatakse ööpäevas jaama saabuvate rongide keskmine arv, keskmine välisteedel rongide ooteaeg ja tunnitasu. a: W ≈ 14,2 a.

^ 3. Kanalage QS uuesti piiramatu järjekorraga. Täiesti sarnane probleemiga 2, kuid veidi keerulisem, probleem n-channel QS piiramatu järjekorraga. Olekute nummerdamine toimub jällegi vastavalt rakenduste arvule süsteemis:

N<1. В случае если ρ/n≥ 1, järjekord kasvab lõpmatuseni.

Oletame, et tingimus ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя всœе те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 seal on rida termineid, mis sisaldavad faktoriaale, millele lisandub lõpmatult kahaneva geomeetrilise progressiooni summa nimetajaga ρ/ n. Kokkuvõtteks leiame

(20.22)

Nüüd leiame QS-i efektiivsuse omadused. Nendest on kõige lihtsam leida keskmise hõivatud kanalite arv k== λ/μ, = ρ (see kehtib üldiselt iga piiramatu järjekorraga QS-i kohta). Leidke keskmine rakenduste arv süsteemis L süsteem ja keskmine rakenduste arv järjekorras L och. Neist teist on valemi järgi lihtsam arvutada

L oh =

vastavate teisenduste sooritamine vastavalt ülesande 2 näidisele

(koos seeriate eristamisega) saame:

L oh = (20.23)

Lisades sellele keskmine teenuses olevate rakenduste arv (see on ka keskmine hõivatud kanalite arv) k =ρ, saame:

L syst = L och + ρ. (20.24)

Avaldiste jagamine L och ja L syst on λ , Little'i valemit kasutades saame rakenduse keskmise viibimisaja järjekorras ja süsteemis:

(20.25)

Nüüd lahendame huvitava näite.
Majutatud aadressil ref.rf
Kahe aknaga raudteepiletikassa on kahe kanaliga piiramatu järjekorraga QS, mis moodustatakse kohe kahele aknale (kui üks aken on vaba, võtab selle järjekorras järgmine reisija). Kassa müüb pileteid kahes punktis: A ja AT. Taotluste voo intensiivsus (reisijad, kes soovivad piletit osta) mõlema punkti kohta A ja B on sama: λ A = λ B = 0,45 (reisija minutis) ja kokku moodustavad nad üldise rakenduste voo intensiivsusega λ A + λB = 0,9. Kassapidaja kulutab reisija teenindamiseks keskmiselt kaks minutit. Kogemus näitab, et piletikassas kogunevad järjekorrad, reisijad kurdavad teeninduse aegluse üle. AGA ja sisse AT, luua kaks spetsialiseeritud piletikassat (üks aken mõlemas), müües pileteid üks - ainult punktini AGA, teine ​​- ainult punktini AT. Selle ettepaneku põhjendatus on vastuoluline – mõned väidavad, et järjekorrad jäävad samaks. Ettepaneku kasulikkust tuleb kontrollida arvutuste teel. Kuna karakteristikuid saame arvutada ainult kõige lihtsama QS jaoks, siis oletame, et kõik sündmuste vood on kõige lihtsamad (see ei mõjuta järelduste kvalitatiivset poolt).

Noh, asume siis asja kallale. Vaatleme kahte võimalust piletimüügi korraldamiseks – olemasolevat ja pakutavat.

Variant I (olemasolev). Kahe kanaliga QS võtab vastu rakenduste voo, mille intensiivsus on λ = 0,9; hooldusvoolu intensiivsus μ = 1/2 = 0,5; ρ = λ/μ = l.8. Kuna ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. Keskmine, järjekorras olevate taotluste arv leitakse valemiga (20,23): L och ≈ 7,68; kliendi keskmine järjekorras viibitud aeg (vastavalt esimesele valemitest (20.25)) on võrdne W pts ≈ 8,54 (min).

II variant (pakutud). On vaja arvestada kahe ühe kanaliga QS-iga (kaks spetsiaalset akent); igaüks saab päringute voo intensiivsusega λ = 0,45; μ . ikka võrdne 0,5-ga; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8,1.

Siin on üks teile! Selgub, et järjekorra pikkus mitte ainult ei vähenenud, vaid suurenes! Ehk on keskmine ooteaeg järjekorras vähenenud? Vaatame. Delya L punktid λ = 0,45, saame W pts ≈ 18 (minutit).

See on ratsionaliseerimine! Vähenemise asemel kasvas nii keskmine järjekorra pikkus kui ka keskmine ooteaeg selles!

Proovime arvata, miks see juhtus? Olles oma aju üle mõelnud, jõuame järeldusele: see juhtus seetõttu, et esimeses variandis (kahe kanaliga QS) on tühikäigu keskmine osa väiksem.

Näiteid järjekorrasüsteemide probleemide lahendamisest - mõiste ja tüübid. Kategooria "Järjekorrasüsteemide probleemide lahendamise näited" klassifikatsioon ja tunnused 2017, 2018.

Üsna sageli tuleb majandussüsteeme analüüsides lahendada nn järjekorraprobleemid, mis tekivad järgmises olukorras. Lase analüüsida teatud arvust erineva võimsusega jaamadest koosnevat autohooldussüsteemi. Igas jaamas (süsteemielemendis) võib esineda vähemalt kaks tüüpilist olukorda:

1. taotluste arv on selle jaama jaoks liiga suur, järjekorrad ja teenuse hilinemise eest tuleb maksta;
2. jaam laekub liiga vähe päringuid ja nüüd on juba vaja arvestada jaama seisakutest põhjustatud kahjudega.

Selge on see, et süsteemianalüüsi eesmärk on sel juhul kindlaks teha mingi seos tulude kaotuse vahel järjekorrad ja sellest tingitud kahjud ainult mina jaamad.

Järjekorra teooria– süsteemiteooria spetsiaalne sektsioon on tõenäosusteooria osa, milles järjekorrasüsteeme uuritakse matemaatiliste mudelite abil.

Järjekorrasüsteem (QS)- see on mudel, mis sisaldab: 1) nõuete, kõnede või teenindust vajavate klientide juhuslikku voogu; 2) selle teenuse rakendamise algoritm; 3) kanalid (seadmed) hoolduseks.

Ühised turukorraldused on näiteks kassad, bensiinijaamad, lennujaamad, müüjad, juuksurid, arstid, telefonijaamad ja muud teatud rakendusi teenindavad rajatised.

Järjekorra teooria probleem seisneb soovituste väljatöötamises QS-i ratsionaalseks ehitamiseks ja nende töö ratsionaalseks korraldamiseks, et tagada kõrge teenindusefektiivsus optimaalsete kuludega.

Selle klassi probleemide peamiseks tunnuseks on analüüsi tulemuste ja saadud soovituste selge sõltuvus kahest välistegurist: tellimuste laekumise sagedus ja keerukus (ja seega ka nende täitmise aeg).

Järjekorra teooria teemaks on seose loomine rakenduste voo olemuse, eraldi teeninduskanali toimivuse, kanalite arvu ja teenuse efektiivsuse vahel.

Nagu QS omadused kaalus:

• nende taotluste keskmine protsent, mis lükatakse tagasi ja jätavad süsteemi teenindamata;
• üksikute kanalite ja süsteemi kui terviku keskmine seisakuaeg;
• keskmine ooteaeg järjekorras;
• tõenäosus, et saabunud taotlust koheselt teenindatakse;
• järjekorra pikkuse jaotuse seadus ja teised.

Lisame, et päringud (nõuded) sisestatakse QS-i juhuslikult (juhuslikul ajal), koos kondenseerumis- ja hõrenemispunktidega. Iga nõude teenindusaeg on samuti juhuslik, mille järel teeninduskanal vabaneb ja on valmis täitma järgmist nõuet. Igal QS-il, olenevalt kanalite arvust ja nende jõudlusest, on teatud võimsus. SMO läbilaskevõime võib olla absoluutne(keskmine kättetoimetatud taotluste arv ajaühikus) ja sugulane(esitatud taotluste arvu keskmine suhe esitatud taotluste arvusse).

3.1 Järjekorrasüsteemide mudelid.

Iga QS-i saab iseloomustada avaldisega: (a / b / c) : (d / e / f) , kus

a - rakenduste sisendvoo jaotus;

b - rakenduste väljundvoo jaotus;

c – teenindusmehhanismi konfiguratsioon;

d – järjekorra distsipliin;

e – ooteplokk;

f on allika võimsus.

Nüüd vaatame iga funktsiooni lähemalt.

Rakenduste sisendvoog- süsteemi saabunud taotluste arv. Iseloomustab sisendvoolu intensiivsus l.

Rakenduste väljundvoog– süsteemi poolt teenindatavate rakenduste arv. Iseloomustab väljundvoolu intensiivsus m.

süsteemi konfiguratsioon tähendab kanalite ja teenindussõlmede koguarvu. SMO võib sisaldada:

1. üks kanal teenused (üks rada, üks müüja);
2. üks teenusekanal, sealhulgas mitu jadasõlme(söökla, kliinik, konveier);
3. mitu sarnast kanalit paralleelselt ühendatud teenused (tanklad, infolaud, raudteejaam).

Seega saab eristada ühe- ja mitme kanaliga QS-i.

Teisest küljest, kui kõik QS-i teeninduskanalid on hõivatud, võib pöördutud rakendus jääda järjekorda või süsteemist lahkuda (näiteks hoiukassa ja telefonikeskjaam). Sel juhul räägime süsteemidest, millel on järjekord (ootel) ja süsteemid, millel on tõrkeid.

Pöörake on rakenduste komplekt, mis on süsteemi teeninduseks sisenenud ja ootavad teenindust. Järjekorda iseloomustab järjekorra pikkus ja distsipliin.

Järjekorra distsipliin on järjekorrast päringute teenindamise reegel. Peamised järjekordade tüübid on järgmised:

1. PERPPO (kes ees, see mees) on kõige levinum tüüp;
2. POSPPO (viimane tuli - see esimene);
3. SOP (rakenduste juhuslik valik) - andmepangast.
4. PR - prioriteetne teenus.

Järjekorra pikkus võib olla

• piiramatu – siis räägitakse puhta ootusega süsteemist;
• võrdne nulliga - siis räägitakse riketega süsteemist;
• piiratud pikkusega (segatüüpi süsteem).

ooteplokk– süsteemi "võimsus" – süsteemis olevate rakenduste koguarv (järjekorras ja teenuses). Sellel viisil, e=c+d.

Allika võimsus mis loob teenusepäringuid, on maksimaalne taotluste arv, mis saab QS-i sisestada. Näiteks lennujaamas on lähtevõimsus piiratud kõigi olemasolevate lennukite arvuga ja telefonikeskjaama allikavõimsus võrdub Maa elanike arvuga, s.t. seda võib pidada piiramatuks.

QS mudelite arv vastab nende komponentide võimalike kombinatsioonide arvule.

3.2 Nõuete sisendvoog.

Iga aja jooksul a, a+ T ], seostame juhusliku muutuja X, mis võrdub süsteemi poolt aja jooksul saadud päringute arvuga T.

Taotluste voogu nimetatakse paigal, kui jaotusseadus ei sõltu intervalli algpunktist a, kuid sõltub ainult antud intervalli pikkusest T. Näiteks rakenduste voog telefonikeskjaama päevasel ajal ( T\u003d 24 tundi) ei saa pidada seisvaks, kuid 13 kuni 14 tundi ( T\u003d 60 minutit) - saate.

Voolu nimetatakse ei mingit järelmõju, kui voo ajalugu ei mõjuta nõuete laekumist tulevikus, s.t. nõuded on üksteisest sõltumatud.

Voolu nimetatakse tavaline, kui süsteemi ei saa väga lühikese aja jooksul sisestada rohkem kui üks päring. Näiteks juuksurisse vool on tavaline, aga mitte perekonnaseisuametisse. Kui aga juhusliku muutujana X arvestage registriametisse sisenevate taotluste paaridega, siis on selline voog tavaline (st mõnikord saab erakorralise voo taandada tavaliseks).

Voolu nimetatakse kõige lihtsam, kui see on paigal, ilma järelmõjuta ja tavaline.

Peamine teoreem. Kui vool on kõige lihtsam, siis r.v. X [ a . + T] levitatakse Poissoni seaduse järgi, s.o. .

Järeldus 1. Lihtsaimat voolu nimetatakse ka Poissoni vooluks.

Tagajärg 2. M(X)= M(X [ a , a + T ] )= lT, st. ajal T lT rakendusi. Seetõttu võtab süsteem ühe ajaühiku kohta keskmiselt vastu l rakendusi. Seda väärtust nimetatakse intensiivsusega sisendvoog.

Kaaluge NÄIDE .

Stuudio saab keskmiselt 3 avaldust päevas. Eeldades, et voog on kõige lihtsam, leidke tõenäosus, et järgmise kahe päeva jooksul on päringute arv vähemalt 5.

Lahendus.

Vastavalt ülesandele, l=3, T=2 päeva, Poissoni sisendvoog, n ³5. lahendamisel on mugav sisse tuua vastupidine sündmus, mis seisneb selles, et aja jooksul T laekub alla 5 avalduse. Seetõttu saame Poissoni valemi järgi

^

3.3 Süsteemi olek. Üleminekute maatriks ja graafik.

Suvalisel ajahetkel läheb QS ühest olekust teise: muutub hõivatud kanalite arv, päringute ja järjekordade arv jne. Seega QS koos n kanaleid ja järjekorra pikkus on võrdne m, võib olla ühes järgmistest olekutest:

E 0 – kõik kanalid on tasuta;

E 1 – üks kanal on hõivatud;

E n– kõik kanalid on hõivatud;

E n +1 – kõik kanalid on hõivatud ja üks päring on järjekorras;

E n + m– kõik kanalid ja kõik kohad järjekorras on hõivatud.

Sarnane riketega süsteem võib olla olekutes E 0 – E n .

Puhta ootusega QS-i jaoks on lõpmatu hulk olekuid. Sellel viisil, tingimus E n QS ajal t on kogus n rakendused (nõuded), mis on antud ajahetkel süsteemis, s.o. n= n(t) - juhuslik väärtus, E n (t) on selle juhusliku suuruse tulemused ja P n (t) on tõenäosus, et süsteem on olekus E n .

Oleme süsteemi olukorraga juba tuttavad. Pange tähele, et süsteemi kõik olekud ei ole samaväärsed. Süsteemi olekut nimetatakse allikas kui süsteem saab sellest olekust lahkuda, kuid ei saa sellesse naasta. Süsteemi olekut nimetatakse isoleeritud, kui süsteem ei saa sellest olekust väljuda ega siseneda.

Süsteemi olekute piltide visualiseerimiseks kasutatakse diagramme (nn üleminekugraafikuid), kus nooled näitavad süsteemi võimalikke üleminekuid ühest olekust teise, aga ka selliste üleminekute tõenäosusi.

Joonis 3.1 - üleminekugraafik

Comp.	E 0	E 1	E 2
E 0	P 0,0	P 0,1	P 0,2
E 1	P 1.0	R 1.1	R 1.2
E 2	R 2,0	R 2.2	R 2.2

Vahel on mugav kasutada ka üleminekumaatriksit. Sel juhul tähendab esimene veerg süsteemi algseisundeid (voolu) ja seejärel antakse nendest olekutest teistesse ülemineku tõenäosused.

Kuna süsteem läheb tingimata ühest üle

olek teisele, siis on iga rea ​​tõenäosuste summa alati võrdne ühega.

3.4 Ühe kanaliga QS.

3.4.1 Ühe kanaliga QS tõrgetega.

Vaatleme süsteeme, mis vastavad nõuetele:

(P/E/1):(–/1/¥) . Oletame ka, et kliendi teenindusaeg ei sõltu süsteemi sisenevate klientide arvust. Siin ja allpool tähendab "P" seda, et sisendvoog on jaotatud vastavalt Poissoni seadusele, st. kõige lihtsam, "E" tähendab, et väljundvoog jaotub eksponentsiaalselt. Ka siin ja allpool on põhivalemid toodud ilma tõestuseta.

Sellise süsteemi jaoks on võimalik kaks olekut: E 0 - süsteem on tasuta ja E 1 – süsteem on hõivatud. Loome üleminekumaatriksi. Võtame Dt on lõpmatult vähe aega. Olgu sündmus A seisneb selles, et süsteemis aja jooksul Dt saanud ühe palve. Sündmus B seisneb selles, et aja jooksul Dtüks taotlus on kätte toimetatud. Sündmus AGA i , k- ajal Dt süsteem läheb osariigist välja E i olekusse E k. Sest l on sisendvoolu intensiivsus, siis aja jooksul Dt siseneb süsteemi keskmiselt l*Dt nõuded. See tähendab ühe nõude saamise tõenäosust P(A)=l* Dt, ja vastupidise sündmuse tõenäosus Р(А)=1-l*Dt.P(B)=F(Dt)= P(b< D t)=1- e - m D t = m Dt- taotluse õigeaegse teenindamise tõenäosus Dt. Siis A 00 - avaldust ei laeku või võetakse kätte, aga toimetatakse kätte. A 00 \u003d Ā + A * V. R 00 \u003d 1 - l*Dt. (arvestasime sellega (Dt) 2 on lõpmata väike väärtus)

A 01 – avaldus võetakse vastu, kuid kätte ei anta. A 01 = A * . R 01 = l*Dt.

Ja 10 - avaldus toimetatakse kätte ja uut ei tule. A 10 \u003d B * a. R 10 = m*Dt.

Ja 11 - avaldust ei edastata või tuleb uus, mida pole veel kätte antud. A 11 = +V * A. R 01 = 1- m*Dt.

Seega saame üleminekumaatriksi:

Comp.	E 0	E 1
E 0	1-l * Dt	l * Dt
E 1	m * Dt	1-m * Dt

Süsteemi seisaku ja rikke tõenäosus.

Leiame nüüd tõenäosuse, et süsteem on olekus E 0 igal ajahetkel t(need. R 0 ( t) ). Funktsioonigraafik
näidatud joonisel 3.2.

Graafi asümptoodiks on sirgjoon
.

Ilmselgelt mingist hetkest t,

1

Joonis 3.2

Lõpuks saame selle kätte
ja
, kus R 1 (t) on tõenäosus, et hetkel t süsteem on hõivatud (st on olekus E 1 ).

On ilmne, et QS-i töö alguses ei ole käimasolev protsess paigal: see on "üleminek", mittestatsionaarne režiim. Mõne aja pärast (mis oleneb sisend- ja väljundvoogude intensiivsusest) see protsess kustub ja süsteem lülitub paigalseisvale, stabiilsele tööolekule ning tõenäosuslikud karakteristikud ei sõltu enam ajast.

Statsionaarne töörežiim ja süsteemi koormustegur.

Kui tõenäosus, et süsteem on seisundis E k, st. R k (t), ei sõltu ajast t, siis nad ütlevad, et QS on loodud statsionaarne režiim tööd. Samal ajal väärtus
helistas süsteemi koormustegur(või rakenduste voo vähenenud tihedus). Siis tõenäosuste kohta R 0 (t) ja R 1 (t) saame järgmised valemid:
,
. Samuti võite järeldada: mida suurem on süsteemi koormustegur, seda tõenäolisem on süsteemi tõrge (st tõenäosus, et süsteem on hõivatud).

Autopesulas on üks üksus hoolduseks. Autod saabuvad Poissoni jaotusse kiirusega 5 autot tunnis. Ühe auto keskmine hooldusaeg on 10 minutit. Leidke tõenäosus, et lähenev auto leiab, et süsteem on hõivatud, kui QS on paigal.

Lahendus. Vastavalt ülesandele, l=5, m y =5/6. Peame leidma tõenäosuse R 1 on süsteemi rikke tõenäosus.
.

3.4.2 Ühe kanaliga QS piiramatu järjekorra pikkusega.

Vaatleme süsteeme, mis vastavad nõuetele: (Р/Е/1):(d/¥/¥). Süsteem võib olla ühes olekus E 0 , …, E k, … Analüüs näitab, et mõne aja pärast hakkab selline süsteem töötama statsionaarses režiimis, kui väljundvoolu intensiivsus ületab sisendvoolu intensiivsust (st süsteemi koormustegur on alla ühe). Seda tingimust arvesse võttes saame võrrandisüsteemi

mille lahendamisel leiame, et . Seega eeldusel, et y<1, получим
Lõpuks
ja
on tõenäosus, et QS on olekus E k juhuslikul ajahetkel.

Süsteemi keskmised omadused.

Nõuete ebaühtlase laekumise tõttu süsteemis ja teenindusaja kõikumiste tõttu tekib süsteemis järjekord. Sellise süsteemi jaoks saate uurida:

• n – nõuete arv QS-is (järjekorras ja teeninduses);
• v – järjekorra pikkus;
• w – teenuse alguse ooteaeg;
• w 0 on kogu süsteemis veedetud aeg.

Tunneme huvi keskmised omadused(st võtame vaadeldavate juhuslike muutujate matemaatilise ootuse ja pidage seda meeles y<1).

on keskmine rakenduste arv süsteemis.

on järjekorra keskmine pikkus.

on teenuse alguse keskmine ooteaeg, s.o. ooteaeg järjekorras.

- keskmine aeg, mille rakendus veedab süsteemis - järjekorras ja teeninduses.

Autopesulas on üks blokk hoolduseks ja koht järjekorra jaoks. Autod saabuvad Poissoni jaotusse kiirusega 5 autot tunnis. Ühe auto keskmine hooldusaeg on 10 minutit. Leidke kõik keskmised QS-i omadused.

Lahendus. l=5, m=60min/10min = 6. Koormustegur y =5/6. Siis keskmine autode arv süsteemis
, järjekorra keskmine pikkus
, keskmine ooteaeg teenuse käivitamisel
tundi = 50 minutit ja lõpuks keskmine süsteemis veedetud aeg
tund.

3.4.3 Segatüüpi ühe kanaliga QS.

Oletame, et järjekorra pikkus on m nõuded. Siis mis tahes s£ m, QS leidmise tõenäosus olekus E 1+ s, arvutatakse valemiga
, st. üks taotlus esitatakse ja teine s taotlused on järjekorras.

Süsteemi seisaku tõenäosus on
,

ja süsteemi rikke tõenäosus on
.

Igaühe jaoks on antud kolm ühe kanaliga süsteemi l=5, m =6. Kuid esimene süsteem on tõrgetega, teine ​​on puhta ootamisega ja kolmas on piiratud järjekorra pikkusega, m=2. Leidke ja võrrelge nende kolme süsteemi seisakuid.

Lahendus. Kõigi süsteemide koormustegur y=5/6. Rikkega süsteemi jaoks
. Puhta ootusega süsteemi jaoks
. Piiratud järjekorra pikkusega süsteemi jaoks
. Järeldus on ilmne: mida rohkem rakendusi on järjekorras, seda väiksem on süsteemi seisaku tõenäosus.

3.5 Mitmekanaliline QS.

3.5.1 Mitmekanaliline QS tõrgetega.

Vaatleme süsteeme (Р/Е/s):(-/s/¥) eeldusel, et teenindusaeg ei sõltu sisendvoost ja kõik liinid töötavad iseseisvalt. Mitmekanalilisi süsteeme saab lisaks koormustegurile iseloomustada ka koefitsiendiga
, kus s– teeninduskanalite arv. Uurides mitmekanalilist QS-i, saame järgmised valemid (Erlangi valemid) süsteemi olekus olemise tõenäosuse kohta E k juhuslikul ajal:

, k=0, 1, …

kulufunktsioon.

Nagu ka ühe kanaliga süsteemide puhul, suurendab koormusteguri suurenemine süsteemi rikke tõenäosust. Teisest küljest toob teenindusliinide arvu suurenemine kaasa süsteemi või üksikute kanalite seisakute tõenäosuse suurenemise. Seega on vaja selle QS jaoks leida optimaalne teeninduskanalite arv. Tasuta teenindusliinide keskmise arvu leiate valemiga
. Tutvustame C( s) – kulufunktsioon QS olenevalt Koos 1 – ühe keeldumise maksumus (trahv täitmata avalduse eest) ja alates Koos 2 - ühe liini seisaku kulu ajaühiku kohta.

Optimaalse variandi leidmiseks peate leidma (ja seda saab teha) kulufunktsiooni minimaalse väärtuse: FROM(s) = koos 1* l * lk s +c 2*, mille graafik on näidatud joonisel 3.3:

Joonis 3.3

Kulufunktsiooni minimaalse väärtuse otsimine seisneb selles, et leiame kõigepealt selle väärtused s =1, siis jaoks s =2, siis jaoks s =3 jne. kuni mingil sammul saavutatakse funktsiooni С( s) ei ole eelmisest suurem. See tähendab, et funktsioon on saavutanud miinimumi ja hakanud kasvama. Vastus on teeninduskanalite arv (väärtus s), mille kulufunktsioon on minimaalne.

NÄIDE .

Mitu teenindusrida peaks sisaldama riketega QS-i, kui l\u003d 2 reb / ​​tund, m\u003d 1 reb / ​​tund, trahv iga rikke eest on 7 tuhat rubla, ühe liini seisaku maksumus on 2 tuhat rubla. tunnis?

Lahendus. y = 2/1=2. Koos 1 =7, Koos 2 =2.

Oletame, et QS-il on kaks teeninduskanalit, st. s =2. Siis
. Järelikult C(2) = c 1 *l*lk 2 +c 2 *(2- y*(1-r 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Teeskleme seda s =3. Siis
, C(3) = c 1 *l*lk 3 +c 2 *
=5.79.

Oletame, et kanaleid on neli, st. s =4. Siis
,
, C(4) = c 1 *l*lk 4 +c 2 *
=5.71.

Oletame, et QS-il on viis teeninduskanalit, st. s =5. Siis
, C(5) = 6,7 - rohkem kui eelmine väärtus. Seetõttu on optimaalne teeninduskanalite arv neli.

3.5.2 Mitme kanaliga QS koos järjekorraga.

Vaatleme süsteeme (Р/Е/s):(d/d+s/¥) eeldusel, et teenindusaeg ei sõltu sisendvoost ja kõik liinid töötavad iseseisvalt. Ütleme, et süsteem on installitud statsionaarne töö, kui sissetulevate kahjunõuete keskmine arv on väiksem kui süsteemi kõikidel ridadel teenindatud nõuete keskmine arv, s.o. l

P(w>0) on tõenäosus oodata teenuse käivitamist,
.

Viimane tunnus võimaldab lahendada optimaalse teeninduskanalite arvu määramise probleemi selliselt, et teenuse alguse ootamise tõenäosus on etteantud arvust väiksem. Selleks piisab, kui arvutada järjestikku ootuse tõenäosus s =1, s =2, s=3 jne.

NÄIDE .

SMO - väikese mikrorajooni kiirabijaam. l=3 kõnet tunnis ja m= 4 kõnet tunnis ühe meeskonna kohta. Mitu meeskonda peab jaamas olema, et väljapääsu ootamise tõenäosus oleks väiksem kui 0,01?

Lahendus. Süsteemi koormustegur y =0,75. Oletame, et saadaval on kaks meeskonda. Leiame tõenäosuse, et ootame teenuse algust kell s =2.
,
.

Oletame, et on kolm brigaadi, st. s=3. Valemite järgi saame selle R 0 =8/17, P(w>0)=0.04>0.01 .

Oletame, et jaamas on neli ekipaaži, s.o. s=4. Siis me saame selle R 0 =416/881, P(w>0)=0.0077<0.01 . Seetõttu peaks jaamas olema neli brigaadi.

3.6 Küsimused enesekontrolliks

1. Järjekorra teooria aine ja ülesanded.
2. QS, nende mudelid ja tähistused.
3. Nõuded sisendvoog. Sisendvoo intensiivsus.
4. Süsteemi olek. Üleminekute maatriks ja graafik.
5. Ühe kanaliga QS tõrgetega.
6. Ühe kanaliga QS järjekorraga. Omadused.
7. Statsionaarne töörežiim. Süsteemi koormustegur.
8. Mitmekanaliline QS tõrgetega.
9. Kulufunktsiooni optimeerimine.
10. Mitme kanaliga QS koos järjekorraga. Omadused.

3.7 Iseseisva töö harjutused

1. Tankla suupistelaual on üks lett. Autod saabuvad Poissoni jaotuse järgi, keskmiselt 2 autot 5 minuti kohta. Keskmiselt piisab tellimuse täitmiseks 1,5 minutist, kuigi teenuse kestus on jaotatud eksponentsiaalse seaduse järgi. Leidke: a) seisaku jõudeoleku tõenäosus; b) keskmine jõudlus; c) tõenäosus, et saabuvate autode arv on vähemalt 10.
2. Röntgeniaparaat võimaldab uurida keskmiselt 7 inimest tunnis. Külastajate intensiivsus on 5 inimest tunnis. Eeldades paigal töötamist, määrake keskmised omadused.
3. QS-i teenindusaeg järgib eksponentsiaalset seadust,
   m = 7 nõuet tunnis. Leidke tõenäosus, et a) teenindusaeg on vahemikus 3 kuni 30 minutit; b) nõue toimetatakse kätte ühe tunni jooksul. Kasutage funktsiooni väärtuste tabelit e X .
4. Jõesadamas on üks kai, sisendvoolu intensiivsus on 5 alust ööpäevas. Laadimis- ja lossimisoperatsioonide intensiivsus on 6 laeva päevas. Pidades silmas statsionaarset töörežiimi, määrake kindlaks kõik süsteemi keskmised omadused.
5. l=3, m=2, trahv iga rikke eest on 5 ja seisakukulu liini kohta on 2?
6. Kui suur on optimaalne teeninduskanalite arv, mis QS-il peaks olema l=3, m =1, trahv iga rikke eest on 7 ja seisakukulu liini kohta on 3?
7. Kui suur on optimaalne teeninduskanalite arv, mis QS-il peaks olema l=4, m=2, trahv iga rikke eest on 5 ja seisaku kulu liini kohta on 1?
8. Määrake õhusõidukite lennuradade arv tingimusel, et ootamise tõenäosus peab olema väiksem kui 0,05. Samal ajal on sisendvoo intensiivsus 27 lennukit päevas ja nende teenindamise intensiivsus 30 lennukit päevas.
9. Mitu samaväärset iseseisvat konveieriliini peaks töökojas olema, et tagada töörütm, mille juures toodete töötlemise ootamise tõenäosus peab olema väiksem kui 0,03 (iga toodet toodab üks liin). Teadaolevalt on tellimuste vastuvõtmise intensiivsus 30 toodet tunnis ja toote töötlemise intensiivsus ühel real on 36 toodet tunnis.
10. Pidev juhuslik suurus X jaotatakse vastavalt eksponentsiaalseadusele parameetriga l=5. Leidke jaotusfunktsioon, omadused ja r.v tabamise tõenäosus. X vahemikus 0,17 kuni 0,28.
11. Keskmine telefonikeskjaama saabuvate kõnede arv minutis on 3. Eeldusel, et voog on Poisson, leidke tõenäosus, et 2 minuti pärast tuleb: a) kaks kõnet; b) vähem kui kaks kõnet; c) vähemalt kaks kõnet.
12. Karbis on 17 osa, millest 4 defektsed. Kokkupanija loosib juhuslikult 5 tükki. Leidke tõenäosus, et a) kõik ekstraheeritud osad on kvaliteetsed; b) väljatõmmatud osade hulgast 3 defektset.
13. Mitu kanalit peaks riketega QS-il olema, kui l\u003d 2 reb / ​​tund, m\u003d 1 reb / ​​tund, trahv iga rikke eest on 8 tuhat rubla, ühe liini seisaku maksumus on 2 tuhat rubla. tunnis?

Ülesanne 1. Saatekonsool võtab vastu päringute voo, mis on teist järku Erlangi voog. Rakenduste voo intensiivsus on 6 rakendust tunnis. Kui dispetšer lahkub konsoolist suvalisel hetkel, siis esimesel järgmisel nõudmisel peab ta konsooli tagasi pöörduma. Leidke järgmise päringu ooteaja jaotustihedus ja koostage selle graafik. Arvutage tõenäosus, et dispetšer võib puududa 10 kuni 20 minutit. Lahendus. Kuna teist järku Erlangi voog on piiratud järelmõjuga statsionaarne voog, siis selle jaoks kehtib Palmi valem

kus f1(θ)- tõenäosusjaotuse tihedus esimese lähima sündmuse ooteaja kohta;
λ - voolu intensiivsus;
- voolu järjekord;
(θ) on tõenäosusjaotuse funktsioon Erlangi järjestuse voo (E) kahe kõrvuti asetseva sündmuse vahelise aja kohta.
On teada, et voolu E jaotusfunktsioonil on vorm

. (2)

Vastavalt ülesande tingimustele on rakenduste voog erlang järjestusega =2. Siis (1) ja (2) saame
.
Viimasest seosest λ=6 saame

f1(θ)=3e-6θ(1+6θ), θ≥0. (3)

Joonistame funktsiooni f1(θ) . Kell θ <0 meil on f1(θ) =0 . Kell θ =0 , f1(0)=3. Kaaluge piiri

Tüübi ebaselguse avalikustamise limiidi arvutamisel kasutati L'Hopitali reeglit. Uurimistöö tulemuste põhjal koostame funktsiooni graafiku f1(θ) (joonis 1).

Pöörame tähelepanu aja mõõtmetele ülesande tekstis: intensiivsuse jaoks on need rakendused tunnis, ajale, minutis. Liigume edasi ühe ajaühiku juurde: 10 minutit = 1/6 tundi, 20 minutit = 1/3 tundi. Nende väärtuste puhul saab arvutada f1(θ) ja täpsustada kõvera olemust

Need ordinaadid on näidatud vastavate kõvera punktide kohal oleval graafikul.
Tõenäosusteooria käigust on teada, et juhusliku suuruse tabamise tõenäosus X segmenti [α, β] on arvuliselt võrdne tõenäosustiheduse kõvera aluse pindalaga f(x). Seda ala väljendab kindel integraal

Seetõttu on soovitud tõenäosus võrdne

Seda integraali saab hõlpsasti osade kaupa arvutada, kui paneme
U=1+6θ ja dV = e-6θdθ. Siis dU=6dθ ja V= .
Kasutades valemit saame

Vastus: tõenäosus, et dispetšer võib puududa 10-20 minutit, on 0,28.

2. ülesanne. Väljapanekuruumis on 5 väljapanekut. Kasutajate voog on kõige lihtsam. Keskmine eksponeerimisruumi külastab ööpäevas 140 kasutajat. Ühe kasutaja info töötlemise aeg ühel kuvaril jaotub eksponentsiaalseaduse järgi ja on keskmiselt 40 minutit. Tehke kindlaks, kas saalil on statsionaarne töörežiim; tõenäosus, et kasutaja leiab, et kõik kuvad on hõivatud; keskmine kasutajate arv väljapanekuruumis; keskmine kasutajate arv järjekorras; keskmine tühikäigu kuvamisaeg; kasutaja kuvaruumis veedetud keskmine aeg. Lahendus. Probleemis käsitletav QS kuulub piiramatu järjekorraga mitmekanaliliste süsteemide klassi. Kanalite arv =5. Leiame rakenduste voo λ-intensiivsuse: kus (tunnid) - keskmine aeg sissetuleva kasutajavoo kahe järjestikuse rakenduse vahel. Siis kasutaja/tund

Leiame - teenuse voo intensiivsus: , kus M[T teenus]=40 min=0,67 tundi – keskmine teenindusaeg ühe kasutaja kohta ühe ekraaniga,

siis kasutaja/tund

Seega on selle süsteemi klassifikaatoril vorm CMO (5, ∞; 5,85; 1,49).
Arvutage QS-i koormustegur . On teada, et selle klassi QS-i puhul eksisteerib statsionaarne režiim, kui süsteemi koormusteguri ja kanalite arvu suhe on väiksem kui üks. Selle suhte leidmine
.
Seetõttu on statsionaarne režiim olemas. Valemite abil arvutatakse piirseisundi tõenäosusjaotus

Kuna =5, oleme

Arvutame P* – tõenäosus, et kasutaja leiab, et kõik kuvad on hõivatud. Ilmselgelt võrdub see selliste sündmuste tõenäosuste summaga: kõik kuvad on hõivatud, järjekorda pole (p5); kõik kuvad on hõivatud, üks kasutaja järjekorras (p6); kõik kuvarid on hõivatud, kaks kasutajat on järjekorras (p7) ja nii edasi. Kuna terve sündmuste rühma korral on nende sündmuste tõenäosuste summa võrdne ühega, siis võrdsus

P * \u003d p5 + p6 + p7 + ... \u003d 1 - ro - p1 - p2 - p3 - p4.

Leiame need tõenäosused: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Võttes ühisteguri sulgudest välja, saame
P*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Kas kasutada tulemusnäitajate arvutamiseks valemeid? leia:

• 1. keskmine kasutajate arv järjekorras

2. keskmine kasutajate arv väljapanekuruumis

3. Keskmine tasuta ekraani ooteaeg

4. kasutaja keskmine väljapanekuruumis veedetud aeg

Vastus: väljapanekuruumi statsionaarne töörežiim on olemas ja seda iseloomustavad järgmised näitajad R*=0,54; kasutaja; kasutaja; ; .

3. ülesanne. Statsionaarne Poissoni päringute voog siseneb tõrgetega kahekanalilisse järjekorrasüsteemi (QS). Kahe järjestikuse päringu saabumise vaheline aeg jaotatakse vastavalt eksponentsiaalseadusele parameetriga λ=5 päringut minutis. Iga päringu teenindamise kestus on 0,5 min. Monte Carlo meetodi abil leidke keskmine teenindatud päringute arv 4 minuti jooksul. Vihje: tehke kolm testi. Lahendus. Kujutagem etteantud QS töö statistilist modelleerimist ajadiagrammide abil. Tutvustame ajatelgede jaoks järgmist tähistust:
Vx- sissetulev rakenduste voog siin ti- avalduste laekumise hetk; Ti- ajavahemikud kahe järjestikuse rakenduse vahel. See on ilmne ti=ti-1 +Ti.
K1 - esimene teeninduskanal;
K2-teine ​​teeninduskanal; siin tähistavad paksud jooned ajateljel kanali hõivatud intervalle. Kui mõlemad kanalid on vabad, teenindatakse päringut kanalis K1, kui see on hõivatud, teenindab päringut kanal K2.
Kui mõlemad kanalid on hõivatud, jätab taotlus QS-i esitamata.
Out OB – teenindatud päringute väljuv voog.
Out PT on QS-i tõrgete tõttu kadunud päringute väljaminev voog (mõlemad kanalid on hõivatud).
Statistiline testimine jätkub teatud aja jooksul. Ilmselgelt iga ületunnitöö tmax tähendab päringu kukutamist väljuvasse voogu Out PT. Nii et joonisel fig. 3 avaldus nr 10, mis omal ajal süsteemi sisenes t10, ei jõua hetkeni kätte saada tmax, sest t10+Tmont.>tmax. Seetõttu ei aktsepteeri tasuta kanal K1 seda teeninduseks ja lähtestatakse väljund-PT-le, saades keeldumise.

Riis. 3

Ajastusskeemidelt on näha, et intervallide modelleerimist on vaja õppida Ti. Kasutame pöördfunktsioonide meetodit. Kuna juhuslik muutuja Ti jaotatud vastavalt eksponentsiaalseadusele parameetriga λ =5, siis on jaotustihedusel kuju f(τ)=5е-5τ. Siis väärtus F(Ti) tõenäosusjaotuse funktsiooni määrab integraal

.

On teada, et jaotusfunktsiooni vahemik F(T) seal on lõige. Valime juhuslike arvude tabelist arvu ja määrame Ti võrdsusest , kust . Kui aga . Seetõttu saate juhuslike arvude tabelist kohe rakendusi. Järelikult
e-5Ti= ri, või -5Ti= lnri, kus. Arvutuste tulemused on mugav sisestada tabelisse.
Testi nr 1 jaoks võeti juhuslikud arvud lisast 2, alustades esimese rea esimesest numbrist. Edasine proovide võtmine viidi läbi ridade kaupa. Teeme veel kaks testi.
Pöörake tähelepanu juhuslike arvude valikule lisa 2 tabelist, kui testis nr 1 oli taotluse nr 16 viimane juhuslik arv 0,37 (esimene juhuslik arv teisel real), siis test nr 2 algab sellega, et järgmine juhuslik arv 0,54 . Katse nr 2 sisaldab viimast juhuslikku numbrit 0,53 (viies number kolmandas reas). Seetõttu algab kolmas test numbriga 0,19. Üldjuhul valitakse sama testide seeria raames tabelist juhuslikud arvud ilma lünkadeta ja sisestamisteta kindlas järjekorras, näiteks ridadena.

Tabel 1. TEST nr 1

Taotlus nr. i	Sl. number ri		-Ln ri Ti	Avalduse kättesaamise hetk ti=ti-1+Ti	Teenindusaja lõpp. ti+0,50		Rakenduste loendur
					K1

Tabel 2 TEST nr 2

Taotlus nr. i	Sl. number ri		-Ln ri Ti	Avalduse kättesaamise hetk ti=ti-1+Ti	Teenindusaja lõpp. ti+0,50		Rakenduste loendur

Tabel #3 TEST #3

Taotlus nr. i		Sl. number ri		-Ln ri Ti	Avalduse kättesaamise hetk ti=ti-1+Ti	Teenindusaja lõpp. ti+0,50		Rakenduste loendur
						K1

Seega oli kolme testi tulemuste kohaselt teenindatud rakenduste arv vastavalt: x1=9, x2=9, x3=8. Leidke teenindatud taotluste keskmine arv:

Vastus: QS-i keskmine taotluste arv 4 minuti jooksul on 8,6(6).

Lihtsaim voog ja praktiliste ülesannete rakendamine.

Mittestatsionaarsed Poissoni voolud.

Piiratud tagajärgedega vood (Palma voolab).

Taastamisvood.

1. Sissejuhatus.

1.1. Ajaloo viide.

Enamik süsteeme, millega inimene tegeleb, on stohhastilised. Katse neid deterministlike mudelite abil matemaatiliselt kirjeldada viib asjade tegeliku olukorra jämestamiseni. Selliste süsteemide analüüsi ja projekteerimise probleemide lahendamisel tuleb arvestada asjade seisu, millal juhuslikkus on määrav süsteemides toimuvate protsesside jaoks. Samas toob juhuslikkuse eiramine, katse loetletud probleemide lahendamist deterministlikku raamistikku "pigistada" moonutusi, järeldusi ja praktilisi soovitusi.

Järjekorrasüsteemide teooria (TSMO) esimesi probleeme käsitles Kopenhaageni telefonifirma töötaja, Taani teadlane A.K. Erlang (1878-1929) aastatel 1908-1922. Need ülesanded tõi ellu soov telefonivõrgu tööd sujuvamaks muuta ja eelnevalt välja töötada meetodid klienditeeninduse kvaliteedi parandamiseks, olenevalt kasutatavate seadmete arvust. Selgus, et telefonikeskjaamades tekkivad olukorrad pole tüüpilised ainult telefonisuhtlusele. Lennuväljade, mere- ja jõesadamate, kaupluste, terminaliklasside, elektrooniliste arvutussüsteemide, radarijaamade jne töö. saab kirjeldada TSMO-ga.

1.2. Järjekorrasüsteemide näited. TSMO ülesannete analüüs.

Näide 1 Erlangi telefonisuhtlus oli telefonikeskjaam, mis oli ühendatud suure hulga abonentidega. Jaama telefonioperaatorid ühendasid kõnede vastuvõtmisel telefoninumbrid omavahel.

Ülesanne: Mitu telefonioperaatorit (eeldusel, et nad on täistööga) peaks jaamas töötama, et kahjud oleksid minimaalsed.

Näide 2 Teatud linnapiirkonna kiirabisüsteem koosneb punktist (mis võtab vastu rakendustaotlusi), mitmest kiirabiautost ja mitmest meditsiinimeeskonnast.

Ülesanne: Määrata kindlaks arstide, abipersonali, sõidukite arv, et kõne ooteaeg oleks patsientidele optimaalne, minimeerides samas süsteemi käitamise kulusid ja maksimeerides teenuse kvaliteeti.

Näide 3 Oluliseks ülesandeks on kaupade mere- ja jõetranspordi korraldamine. Sellega seoses on eriti oluline laevade ja sadamarajatiste optimaalne kasutamine.

Eesmärk: tagada teatud hulk liiklust minimaalsete kuludega. Samal ajal, et vähendada laevade seisakuid laadimis- ja lossimisoperatsioonide ajal.

Näide 4 Infotöötlussüsteem sisaldab multiplekskanalit ja mitut arvutit. Andurite signaalid suunatakse multiplekskanalisse, kus need puhverdatakse ja eeltöödeldakse. Seejärel sisenevad nad arvutisse, kus järjekord on minimaalne.

Ülesanne: Tagada signaali töötlemise kiirendus etteantud järjekorra kogupikkusel.

Näide 5. Joonisel 1.1. kuvatakse tüüpilise järjekorrasüsteemi plokkskeem - remondifirma (näiteks arvuti parandamiseks). Selle töö järjekord on diagrammil selge ega vaja täpsustamist.

joonis 1.1.

Ei ole raske tuua palju muid näiteid erinevatest tegevusvaldkondadest.

Selliste ülesannete puhul on tüüpiline:

1. "topelt" juhuslikkuse tingimused -

• teenindustellimuse kättesaamise hetk on juhuslik (telefonikeskjaamas, kiirabijaamas, protsessori sisendis on laeva laadimisele saabumise hetk jne juhuslik);
• teenistusaja pikkus on juhuslik.

2) meie aja nuhtluse probleem - järjekorrad: laevad lüüside ees, autod lettide ees, ülesanded arvutikompleksi protsessorite sisendis jne.

A.K. Erlang juhtis tähelepanu asjaolule, et QS-i saab jagada kahte tüüpi, nimelt: ootusega süsteemid ja kadudega süsteemid. Esimesel juhul "ootab" süsteemi sisendis saadud päring täitmisjärjekorda, teisel juhul lükatakse see tagasi, kuna teeninduskanal on hõivatud ja QS-i jaoks kadunud.

Tulevikus näeme, et klassikalistele Erlangi probleemidele lisanduvad uued probleemid:

Reaalsed süsteemid, millega tuleb praktikas tegeleda, on reeglina väga keerulised ja sisaldavad mitmeid hooldusetappe (etappe) (joonis 1.1.). Lisaks võib igas etapis esineda tõrgete täitmine või muude nõuetega võrreldes prioriteetse teenuse olukord. Sel juhul võivad üksikud teeninduslingid oma töö peatada (remondiks, reguleerimiseks jne) või võidakse ühendada lisavahendeid. Võib esineda olukordi, kus tagasilükatud päringud sisestatakse uuesti süsteemi (infosüsteemides võib see juhtuda).

1.3. Mõisted, definitsioonid, terminoloogia.

Kõigil QS-idel on täpselt määratletud struktuur, mis on näidatud joonisel 1.2

joonis 1.2

Definitsioonid, terminid

• Voog on sündmuste jada. Teenusepäringute voogu nimetatakse nõudluse vooks.
• Teenindussüsteemi sisenevate päringute voogu nimetatakse sissetulevaks vooks.
• Teenindatavate päringute voogu nimetatakse väljaminevaks vooks.
• Järjekordade ja teenindusseadmete (kanalite) kogumit nimetatakse teenindussüsteemiks.
• Iga päring saabub oma kanalile, kus see läbib teenindustoimingu.
• Igal ühisel turukorraldusel on teatud reeglid järjekorra ja reeglite või teenusedistsipliini kohta.

1.4. Ühise turukorralduse klassifikatsioon.

1.4.1. Nõuete allika olemuse järgi eristatakse QS-id, mille sisendis on lõplik ja lõpmatu arv nõudeid.

Esimesel juhul ringleb süsteemis piiratud, tavaliselt konstantne arv nõudeid, mis pärast teenuse lõppu naasevad lähtekohta.

Teisel juhul genereerib allikas lõpmatu arvu taotlusi.

Näide 1 Töökoda, kus on pidev arv masinaid või teatud arv terminaliklassi kuuluvaid personaalarvuteid, mis nõuavad pidevat ennetavat kontrolli ja remonti.

Näide 2. Interneti-võrk lõputu nõudlusega sissepääsu juures, igas kaupluses, juuksuris jne.

Esimest tüüpi QS-i nimetatakse suletud, teist - avatud.

SMO eristamine:

1.4.2. Teenindusdistsipliin:

1. teenindamine järjekorra alusel;
2. teenus juhuslikus järjekorras (vastavalt etteantud jaotusseadusele);
3. prioriteetne teenus.

1.4.3. organisatsiooni olemuse järgi:

1. ebaõnnestumistega;
2. ootustega;
3. piiratud ootamisega.

Esimesel juhul lükatakse taotlus tagasi, kui kanal on hõivatud. Teisel juhul pannakse see järjekorda ja ootab kanali vabastamist. Kolmandal juhul kehtestatakse ooteaja piirangud.

1.4.4. Teenindusüksuste arvu järgi:

1. ühe kanaliga;
2. kahe kanaliga;
3. mitme kanaliga.

1.4.5. Teenuse etappide (faaside) arvu järgi - ühefaasilise ja mitmefaasilise jaoks. (Mis tahes tootmisliin võib olla mitmefaasilise QS-i näide).

1.4.6. Kanali omadused: homogeenseks, kui kanalitel on samad omadused, ja heterogeenseks muidu.

See on vajalik ülesannete 1-3 lahendamiseks. Algandmed on toodud tabelis. 2-4.

Mõned järjekorrateoorias valemite jaoks kasutatud tähistused:

n on QS kanalite arv;

λ - sissetuleva rakenduste voo intensiivsus P in;

v - väljamineva rakenduste voo intensiivsus P out;

μ - teenuse voo intensiivsus P umbes;

ρ - süsteemi koormuse indikaator (liiklus);

m - maksimaalne kohtade arv järjekorras, piirates taotluste järjekorra pikkust;

i - rakendusallikate arv;

p kuni - süsteemi k-nda oleku tõenäosus;

p umbes - kogu süsteemi jõudeaja tõenäosus, st tõenäosus, et kõik kanalid on vabad;

p syst - rakenduse aktsepteerimise tõenäosus süsteemis;

p otk - taotluse tagasilükkamise tõenäosus selle süsteemi vastuvõtmisel;

p about – tõenäosus, et taotlus kätte toimetatakse;

A on süsteemi absoluutne läbilaskevõime;

Q on süsteemi suhteline läbilaskevõime;

och - keskmine taotluste arv järjekorras;

o - teenindatavate taotluste keskmine arv;

syst - keskmine rakenduste arv süsteemis;

pt - keskmine taotluse ooteaeg järjekorras;

o - taotluse keskmine kättetoimetamise aeg, mis puudutab ainult teenindatud päringuid;

sys - rakenduse keskmine süsteemis viibimise aeg;

exp - keskmine aeg, mis piirab taotluse ootamist järjekorras;

Keskmine hõivatud kanalite arv.

QS A absoluutne läbilaskevõime on keskmine rakenduste arv, mida süsteem saab ajaühikus teenindada.

QS suhteline läbilaskevõime Q on süsteemi poolt ajaühikus teenindatavate rakenduste keskmise arvu ja selle aja jooksul vastuvõetud rakenduste keskmise arvu suhe.

Järjekorraprobleemide lahendamisel tuleb järgida järgmist järjestust:

1) QS tüübi määramine vastavalt tabelile. 4,1;

2) valemite valik vastavalt QS tüübile;

3) probleemide lahendamine;

4) probleemi kohta järelduste sõnastamine.

1. Surma ja paljunemise skeem.

Teame, et märgistatud olekugraafiku abil saame hõlpsasti kirjutada Kolmogorovi võrrandid olekutõenäosuste jaoks ning samuti kirjutada ja lahendada lõplike tõenäosuste algebralisi võrrandeid. Mõnel juhul on võimalik lahendada viimased võrrandid ette, sõnasõnalises vormis. Eelkõige saab seda teha siis, kui süsteemi olekugraafik on nn "surma ja taastootmise skeem".

Surma ja paljunemise skeemi olekugraafik on joonisel fig. 19.1. Selle graafiku eripära on see, et süsteemi kõik olekud saab tõmmata ühte ahelasse, milles iga keskmine olek ( S 1 , S 2 , …, S n-1) on ühendatud edasi- ja tagasinoolega iga naaberolekuga - parem ja vasak ning äärmuslikud olekud (S 0 , S n) — ainult ühe naaberriigiga. Mõiste "surma ja paljunemise skeem" pärineb bioloogilistest probleemidest, kus populatsiooni suuruse muutust kirjeldatakse sellise skeemiga.

Surma ja paljunemise skeemi kohtab väga sageli erinevates praktikaprobleemides, eriti järjekorra teoorias, seetõttu on kasulik üks kord ja igaveseks leida selle jaoks olekute lõplikud tõenäosused.

Oletame, et kõik sündmuste vood, mis edastavad süsteemi piki graafiku nooli, on kõige lihtsamad (lühiduse huvides nimetame süsteemiks ka S ja selles toimuv protsess on kõige lihtsamad).

Kasutades joonisel fig. 19.1, koostame ja lahendame oleku lõpptõenäosuste algebralised võrrandid), olemasolu tuleneb sellest, et igast olekust saab minna igasse teise, olekute arv on lõplik).

Esimese osariigi jaoks S 0 meil on:

(19.1)

Teise oleku jaoks S1:

(19.1) tõttu taandatakse viimane võrdsus vormile

kus k võtab kõik väärtused 0 kuni P. Nii et lõplikud tõenäosused p0, p1,..., p n rahuldavad võrrandid

(19.2)

lisaks peame arvestama normaliseerimise tingimusega

lk 0 + lk 1 + lk 2 +…+ lk n = 1. (19.3)

Lahendame selle võrrandisüsteemi. Esimesest võrrandist (19.2) väljendame lk 1 läbi R 0 :

lk 1 = lk 0. (19.4)

Teisest, võttes arvesse (19.4), saame:

(19.5)

alates kolmandast, võttes arvesse (19,5),

(19.6)

ja üldiselt mis tahes k(alates 1 kuni n):

(19.7)

Pöörame tähelepanu valemile (19.7). Lugeja on kõigi vasakult paremale suunduvate noolte intensiivsuste korrutis (algusest antud olekusse S k) ja nimetaja on kõigi paremalt vasakule suunduvate noolte intensiivsuste korrutis (algusest kuni Sk).

Seega kõik olekutõenäosused R 0 , lk 1 , ..., р n väljendatud ühe neist ( R 0). Asendame need avaldised normaliseerimistingimusega (19.3). Saame sulgudes R 0:

siit saame väljendi jaoks R 0 :

(tõstsime sulgu astmeni -1, et mitte kirjutada kahekorruselisi murde). Kõik muud tõenäosused on väljendatud R 0 (vt valemeid (19.4)-(19.7)). Pange tähele, et koefitsiendid R 0 on igaühes neist midagi muud kui järjestikused liikmed valemis (19.8) ühiku järel. Niisiis, arvutades R 0 , oleme kõik need koefitsiendid juba leidnud.

Saadud valemid on väga kasulikud järjekorrateooria lihtsamate ülesannete lahendamisel.

2. Väike valem.

Nüüd tuletame ühe olulise valemi, mis on seotud (piirava, statsionaarse režiimi jaoks) rakenduste keskmise arvuga L syst, mis asub järjekorrasüsteemis (st teenindatakse või seisab järjekorras) ja rakenduse keskmine viibimisaeg süsteemis W süsteem

Vaatleme mis tahes QS-i (ühe kanaliga, mitme kanaliga, markovi, mitte-Markovi, piiramatu või piiratud järjekorraga) ja kahte sellega seotud sündmuste voogu: QS-i saabuvate klientide voogu ja teenusest lahkuvate klientide voogu. QS. Kui süsteemis on kehtestatud piirav statsionaarne režiim, siis QS-i saabuvate rakenduste keskmine arv ajaühikus võrdub sealt väljuvate rakenduste keskmise arvuga: mõlema voo intensiivsus λ on sama.

Tähistage: X(t) — taotluste arv, mis saabusid ühisele turukorraldusele enne hetke t. Y(t) — ühisturust lahkunud taotluste arv

hetkeni t. Mõlemad funktsioonid on juhuslikud ja muutuvad järsult (suurenevad ühe võrra) päringu saabumise hetkel (X(t)) ja taotluste lahkumised (Y(t)). Funktsioonide tüüp X(t) ja Y(t) näidatud joonisel fig. 19,2; mõlemad read on astmelised, ülemine on X(t), madalam - Y(t). Ilmselgelt igaks hetkeks t nende erinevus Z(t)= X(t) - Y(t) pole midagi muud kui rakenduste arv QS-is. Kui read X(t) ja Y(t) liita, süsteemis pole päringuid.

Mõelge väga pikale ajavahemikule T(mõtteliselt jätkates graafikut palju kaugemale joonisest) ja arvutage selle jaoks välja keskmine rakenduste arv QS-is. See on võrdne funktsiooni integraaliga Z(t) sellel intervallil jagatud intervalli pikkusega T:

L süsteem = . (19.9) o

Kuid see integraal pole midagi muud kui joonisel fig. 19.2. Vaatame seda joonist hästi. Joonis koosneb ristkülikutest, millest igaühe kõrgus on võrdne ühega ja alus on võrdne viibimisajaga vastava järjekorra süsteemis (esimene, teine ​​jne). Märgime need ajad ära t1, t2,... Tõsi, intervalli lõpus T mõned ristkülikud sisenevad varjutatud joonisele mitte täielikult, vaid osaliselt, kuid piisavalt suurena T need pisiasjad ei loe.

(19.10)

kus summa kehtib kõigi selle aja jooksul laekunud taotluste kohta T.

Jaga parem ja vasak pool (.19.10) intervalli pikkusega T. Saame, võttes arvesse (19.9),

L süsteem = . (19.11)

Jagame ja korrutame (19.11) parema poole intensiivsusega X:

L süsteem = .

Aga suurusjärk Tλ ei ole midagi muud kui selle aja jooksul laekunud taotluste keskmine arv ^ T. Kui jagame kõigi aegade summa t i keskmise taotluste arvu kohta, siis saame rakenduse keskmise süsteemis viibimise aja W süsteem Niisiis,

L süsteem = λ W süsteem ,

W süsteem = . (19.12)

See on Little'i imeline valem: mis tahes QS-i jaoks, mis tahes rakenduste voo olemuse jaoks, mis tahes teenindusaja jaotuse jaoks, mis tahes teenindusdistsipliini jaoks päringu keskmine viibimisaeg süsteemis võrdub keskmise päringute arvuga süsteemis, mis on jagatud päringu voo intensiivsusega.

Täpselt samamoodi tuletatakse Little'i teine ​​valem, mis seostab rakenduse keskmist järjekorras veedetud aega ^ Oeh ja keskmine taotluste arv järjekorras L oh:

W oh = . (19.13)

Väljundi jaoks piisab joonise fig. alumise rea asemel. 19.2 võta funktsioon U(t)- hetkeni jäänud taotluste arv t mitte süsteemist, vaid järjekorrast (kui süsteemi sisenenud rakendus ei satu järjekorda, vaid läheb kohe teenindusse, saame siiski arvestada, et ta satub järjekorda, kuid jääb sinna nulli) .

Little'i valemid (19.12) ja (19.13) mängivad järjekorrateoorias olulist rolli. Kahjuks ei ole enamikus olemasolevates juhendites neid valemeid (mis on suhteliselt hiljuti tõestatud üldisel kujul) 1).

Lihtsamad järjekorrasüsteemid ja nende omadused

Selles jaotises käsitleme mõningaid lihtsamaid QS-e ja tuletame nende omaduste (jõudlusnäitajate) avaldisi. Samas demonstreerime elementaarsele, “markovilikule” järjekorrateooriale iseloomulikke põhilisi metodoloogilisi võtteid.

Me ei uuri QS-proovide arvu, mille jaoks karakteristikute lõplikud avaldised tuletatakse; see raamat ei ole järjekorrateooria juhend (spetsiaalsed juhendid täidavad seda rolli palju paremini). Meie eesmärk on tutvustada lugejale mõningaid "nippe", et hõlbustada järjekorrateooria läbimist, mis paljudes saadaolevates (isegi populaarseks pidavates) raamatutes võib tunduda ulmelise näitekoguna.

Kõiki sündmuste vooge, mis edastavad QS-i olekust olekusse, käsitleme selles jaotises kõige lihtsamat (ilma seda iga kord konkreetselt täpsustamata). Nende hulgas on nn teenusevoog. See tähendab päringute voogu, mida teenindab üks pidevalt hõivatud kanal. Selles voos on sündmuste vaheline intervall, nagu ikka kõige lihtsamas voos, eksponentsiaalse jaotusega (paljudes juhendites on hoopis kirjas: "teenindusaeg on eksponentsiaalne", me ise kasutame seda terminit edaspidi).

Populaarses raamatus on toodud Little'i valemi tuletis ülaltooduga võrreldes mõnevõrra erinevalt. Üldiselt on selle raamatuga tutvumine (“Teine vestlus”) kasulik esmaseks tutvumiseks järjekorra teooriaga.

Selles jaotises peetakse teenindusaja eksponentsiaalset jaotust iseenesestmõistetavaks, nagu alati "lihtsaima" süsteemi puhul.

Vaadeldava QS-i efektiivsuskarakteristikuid tutvustame ettekande käigus.

1. P- kanal QS tõrgetega(Erlangi probleem). Siin käsitleme järjekorra teooria üht ajaliselt esimesi "klassikalisi" probleeme; see probleem tekkis telefoniside praktilistest vajadustest ja selle lahendas meie sajandi alguses Taani matemaatik Erlant. Ülesanne on püstitatud järgmiselt: on P kanalid (sideliinid), mis võtavad vastu rakenduste voogu intensiivsusega λ. Teenindusvoo intensiivsus on μ (keskmise teenindusaja pöördväärtus t umbes).

Leidke QS-i olekute lõplikud tõenäosused ja selle efektiivsuse omadused:

^ A - absoluutne läbilaskevõime, st ajaühikus teenindatud rakenduste keskmine arv;

K- suhteline läbilaskevõime, st süsteemi poolt teenindatavate sissetulevate päringute keskmine osakaal;

^ R otk- ebaõnnestumise tõenäosus, st asjaolu, et rakendus jätab QS-i teenindamata;

k - keskmine hõivatud kanalite arv.

Lahendus. Süsteemi olekud ^S(QS) nummerdatakse vastavalt taotluste arvule süsteemis (antud juhul langeb see kokku hõivatud kanalite arvuga):

S 0 —ühises turukorralduses ei ole taotlusi,

S 1 — QS-is on üks päring (üks kanal on hõivatud, ülejäänud on vabad),

Sk — SMO-s on k rakendused ( k kanalid on hõivatud, ülejäänud on tasuta),

S n — SMO-s on P rakendused (kõik n kanalid on hõivatud).

QS oleku graafik vastab sigimisel suremise skeemile (joonis 20.1). Märgistame selle graafiku – märkige sündmuste voogude intensiivsus noolte lähedale. Alates S 0 tolli S1 süsteemi edastab päringute voog intensiivsusega λ (niipea kui päring saabub, hüppab süsteem S0 sisse S1). Sama päringute voog kannab süsteemi mis tahes vasakpoolsest olekust üle parempoolsesse naaberolekusse (vt ülemisi nooli joonisel 20.1).

Paneme alumiste noolte intensiivsuse alla. Süsteem olgu seisukorras ^S 1 (üks kanal töötab). See toodab μ teenust ajaühiku kohta. Panime noole alla S 1 →S 0 intensiivsus μ. Kujutage nüüd ette, et süsteem on olekus S2(töötavad kaks kanalit). Et ta läheks S 1, on vajalik, et kas esimene või teine ​​kanal lõpetaks hoolduse; nende teenusevoogude koguintensiivsus on 2μ; pane see vastava noole juurde. Kolme kanali kogu teenusevoo intensiivsus on 3 μ, k kanalid - km. Panime need intensiivsused alla joonisel fig. 20.1.

Ja nüüd, teades kõiki intensiivsusi, kasutame surma ja paljunemise skeemis lõplike tõenäosuste jaoks valmis valemeid (19.7), (19.8).

Valemi (19.8) järgi saame:

Lagunemise terminid on koefitsiendid p 0 väljendites jaoks p1

Pange tähele, et valemid (20.1), (20.2) ei sisalda intensiivsusi λ ja μ eraldi, vaid ainult suhtena λ/μ. Tähistage

λ/μ = ρ (20,3)

Ja me nimetame p väärtust "rakenduste voo vähenenud intensiivsuseks". Selle tähendus on ühe päringu keskmise teenindusaja jooksul saabunud päringute keskmine arv. Seda tähistust kasutades kirjutame valemid (20.1), (20.2) ümber järgmisel kujul:

Lõpliku oleku tõenäosuste valemeid (20.4), (20.5) nimetatakse järjekorrateooria rajaja auks Erlangi valemiteks. Enamik teisi selle teooria valemeid (tänapäeval on neid rohkem kui seeni metsas) ei kanna erilisi nimetusi.

Seega leitakse lõplikud tõenäosused. Nende põhjal arvutame välja QS efektiivsuskarakteristikud. Kõigepealt leiame ^ R otk. - tõenäosus, et sissetulevast päringust keeldutakse (ei toimetata kätte). Selleks on vaja, et kõik P kanalid olid hõivatud, nii et

R otk = R n = . (20.6)

Siit leiame suhtelise läbilaskevõime – rakenduse kättetoimetamise tõenäosuse:

Q = 1 - P avatud = 1 - (20,7)

Saame absoluutse läbilaskevõime, korrutades päringuvoo intensiivsuse λ-ga K:

A = λQ = λ. (20.8)

Jääb vaid leida hõivatud kanalite keskmine arv k. Selle väärtuse võib leida "otse" kui diskreetse juhusliku suuruse matemaatilise ootuse võimalike väärtustega 0, 1, ..., P ja nende väärtuste tõenäosused p 0 p 1, ..., p n:

k = 0 · p 0 +üks · p 1 + 2 · p 2 + ... + n · p n .

Asendades siin avaldised (20.5) jaoks R k , (k = 0, 1, ..., P) ja sooritades vastavad teisendused, saaksime lõpuks õige valemi k. Kuid me tuletame selle palju lihtsamalt (siin see on üks "väikestest nippidest"!) Tõepoolest, me teame absoluutset läbilaskevõimet AGA. See pole midagi muud kui süsteemi teenindatavate rakenduste voo intensiivsus. Iga hõivatud i .shal ajaühiku kohta teenindab keskmiselt |l päringut. Seega keskmine hõivatud kanalite arv on

k = A/μ, (20.9)

või antud (20.8),

k = (20.10)

Soovitame lugejal näidet ise välja töötada. Seal on kolme kanaliga sidejaam ( n= 3), rakenduste voo intensiivsus λ = 1,5 (rakendusi minutis); keskmine teenindusaeg taotluse kohta t v = 2 (min.), on kõik sündmuste vood (nagu kogu selles lõigus) kõige lihtsamad. Leidke QS-i lõppoleku tõenäosused ja jõudlusnäitajad: A, Q, P otk, k. Igaks juhuks vastused siin: lk 0 = 1/13, lk 1 = 3/13, lk 2 = 9/26, lk 3 = 9/26 ≈ 0,346,

AGA≈ 0,981, K ≈ 0,654, P avatud ≈ 0,346, k ≈ 1,96.

Vastustest on muide näha, et meie QS on suures osas ülekoormatud: kolmest kanalist on keskmiselt hõivatud umbes kaks ja umbes 35% sissetulevatest rakendustest jääb teenindamata. Kutsume lugejat, kui ta on uudishimulik ja mitte laisk, välja selgitama: mitu kanalit on vaja, et rahuldada vähemalt 80% sissetulevatest taotlustest? Ja kui suur osa kanalitest jääb samal ajal jõude?

Mingi vihje on juba olemas optimeerimine. Tegelikult maksab iga kanali sisu ajaühiku kohta teatud summa. Samas toob iga hooldatud rakendus omajagu tulu. Korrutades selle sissetuleku keskmise taotluste arvuga AGA, teenindatakse ajaühiku kohta, saame ühise turukorralduse keskmise tulu ajaühiku kohta. Kanalite arvu kasvuga see tulu loomulikult kasvab, kuid kasvavad ka kanalite ülalpidamisega seotud kulud.

Mis kaalub üles – tulude või kulude kasv? See sõltub operatsiooni tingimustest, "rakenduse teenuse tasust" ja kanali ülalpidamiskuludest. Neid väärtusi teades saate leida optimaalse kanalite arvu, mis on kõige kuluefektiivsem. Sellist probleemi me ei lahenda, jättes samale "mittelaisale ja uudishimulikule lugejale" näite välja mõtlema ja seda lahendama. Üldiselt arendab probleemide väljamõtlemine rohkem kui kellegi poolt juba püstitatud probleemide lahendamine.

Ühe kanaliga QS piiramatu järjekorraga.

Praktikas on üsna levinud ühekanaliline järjekorraga QS (patsiente teenindav arst; ühe kabiiniga taksotelefon; kasutaja tellimusi täitev arvuti). Järjekorrateoorias on erilisel kohal ka ühe kanaliga QS koos järjekorraga (selliste QS-i alla kuulub enamik seni mitte-Markovi süsteemide kohta saadud analüütilisi valemeid). Seetõttu pöörame erilist tähelepanu ühe kanaliga järjekorraga QS-idele.

Olgu siis ühe kanaliga QS järjekorraga, millele piiranguid ei sea (ei järjekorra pikkusele ega ooteajale). See QS võtab vastu päringute voo intensiivsusega λ ; teenusevoo intensiivsus μ on päringu keskmise teenindusaja pöördvõrdeline t umbes.

On vaja leida QS-i olekute lõplikud tõenäosused ja selle efektiivsuse omadused:

L süsteem — keskmine rakenduste arv süsteemis,

W süsteem on päringu keskmine süsteemis viibimise aeg,

^L jah- järjekorras olevate taotluste keskmine arv,

W och — keskmine aeg, mille rakendus järjekorras veedab,

P zan — tõenäosus, et kanal on hõivatud (kanali koormuse aste).

Mis puudutab absoluutset läbilaskevõimet AGA ja suhteline K, siis pole vaja neid arvutada:

kuna järjekord on piiramatu, siis iga avaldus varem või hiljem kätte toimetatakse, seega A \u003d λ, samal põhjusel Q= 1.

Lahendus. Süsteemi olekud, nagu varemgi, nummerdatakse vastavalt QS-is olevate rakenduste arvule:

S 0 — kanal on tasuta

S 1 - kanal on hõivatud (teenidab päringut), järjekorda pole,

S 2 — kanal on hõivatud, üks päring on järjekorras,

S k - kanal on hõivatud, k - 1 taotlust on järjekorras,

Teoreetiliselt ei piira olekute arvu miski (lõpmatult). Olekugraafikul on joonisel fig. 20.2. See on surma ja paljunemise skeem, kuid lõpmatu arvu olekutega. Kõigis nooltes edastab taotluste voog intensiivsusega λ süsteemi vasakult paremale ja paremalt vasakule teenusevoo intensiivsusega μ.

Kõigepealt küsigem endalt, kas sel juhul on lõplikud tõenäosused? Lõppude lõpuks on süsteemi olekute arv lõpmatu ja põhimõtteliselt at t → ∞ järjekord võib kasvada lõputult! Jah, see on tõsi: sellise QS-i lõplikud tõenäosused ei eksisteeri alati, vaid ainult siis, kui süsteem pole ülekoormatud. Võib tõestada, et kui ρ on rangelt väiksem kui üks (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ kasvab lõputult.

See asjaolu tundub eriti "arusaamatu" ρ = 1 korral. Tundub, et süsteemile pole võimatuid nõudeid: ühe päringu teenindamise ajal saabub keskmiselt üks päring ja kõik peaks olema korras, kuid tegelikult on ei ole. Kui ρ = ​​1, saab QS päringute vooga hakkama ainult siis, kui see voog on regulaarne ja teenindusaeg pole samuti juhuslik, võrdne päringute vahelise intervalliga. Sellisel "ideaalsel" juhul ei teki QS-is üldse järjekorda, kanal on pidevalt hõivatud ja väljastab regulaarselt teenindatud päringuid.

Kuid niipea, kui päringute voog või teenusevoog muutub vähemalt veidi juhuslikuks, kasvab järjekord juba määramatult. Praktikas ei juhtu see ainult seetõttu, et "lõpmatu arv rakendusi järjekorras" on abstraktsioon. Need on jämedad vead, milleni võib juhuslike muutujate asendamine nende matemaatiliste ootustega kaasa tuua!

Kuid pöördume tagasi meie piiramatu järjekorraga ühe kanaliga QS-i juurde. Rangelt võttes tuletasime surma ja taastootmise skeemi lõpptõenäosuste valemid ainult lõpliku arvu olekute korral, kuid võtame vabadused - me kasutame neid lõpmatu arvu olekute jaoks. Arvutame olekute lõpptõenäosused valemite (19.8), (19.7) järgi. Meie puhul on valemis (19.8) olevate liikmete arv lõpmatu. Saame väljendi jaoks p 0:

lk 0 \u003d -1 \u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)

Seeria valemis (20.11) on geomeetriline progressioon. Me teame seda ρ puhul< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... eksisteerivad ainult r jaoks<1).

Oletame nüüd, et see tingimus on täidetud ja ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

lk 0 = 1 - lk. (20.12)

Tõenäosused p 1 , p 2 , ..., p k ,... leiad valemitega:

p1 = ρ p 0, lk 2= ρ2 p 0,…,p k = ρ p0, ...,

Kust (20.12) arvesse võttes leiame lõpuks:

p1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ k(1 - p), . . .(20.13)

Nagu näete, tõenäosus p0, p1, ..., p k , ... moodustavad geomeetrilise progressiooni nimetajaga p. Kummalisel kombel suurim neist p 0 — tõenäosus, et kanal üldse tasuta saab. Olenemata sellest, kui koormatud süsteem järjekorraga on, kui see ainult rakenduste vooga üldse hakkama saab (ρ<1), самое вероятное число заявок в системе будет 0.

Leidke QS-is rakenduste keskmine arv ^L süsteem. . Siin tuleb natuke nokitseda. Juhuslik väärtus Z- taotluste arv süsteemis - on võimalikud väärtused 0, 1, 2, .... k,... tõenäosustega p0, p 1 , p 2 , ..., p k , ... Selle matemaatiline ootus on

L syst = 0? p 0 + 1 ? lk 1 + 2 ? lk 2 +…+k ? lk k +…= (20.14)

(summat ei võeta 0-st ∞-ni, vaid 1-st ∞-ni, kuna nullliige on võrdne nulliga).

Asendame valemisse (20.14) avaldise p k (20.13):

L süsteem =

Nüüd võtame välja summa ρ (1-ρ) märgi:

L süsteem = ρ(1-ρ)

Siin rakendame taas "väikest trikki": kρ k-1 pole midagi muud kui avaldise ρ tuletis ρ suhtes k; tähendab,

L süsteem = ρ(1-ρ)

Diferentseerimise ja liitmise tehteid vahetades saame:

L süsteem = ρ (1-ρ) (20,15)

Kuid summa valemis (20.15) pole midagi muud kui lõpmatult kahaneva geomeetrilise progressiooni summa esimese liikmega ρ ja nimetajaga ρ; see summa

on võrdne , ja selle tuletis on . Asendades selle avaldise (20.15), saame:

L syst = . (20.16)

Noh, nüüd rakendame Little'i valemit (19.12) ja leiame rakenduse keskmise viibimisaja süsteemis:

W syst = (20.17)

Leidke järjekorras olevate rakenduste keskmine arv L och. Me vaidleme järgmiselt: järjekorras olevate rakenduste arv võrdub süsteemis olevate rakenduste arvuga, millest on lahutatud teenuses olevate rakenduste arv. Seega (vastavalt matemaatiliste ootuste liitmise reeglile) keskmine taotluste arv järjekorras L pt võrdub süsteemis olevate rakenduste keskmise arvuga L syst miinus teenindatavate päringute keskmine arv.

Teenuse all olevate päringute arv võib olla kas null (kui kanal on vaba) või üks (kui see on kinni). Sellise juhusliku muutuja matemaatiline ootus on võrdne tõenäosusega, et kanal on hõivatud (me tähistasime seda R zan). Ilmselgelt R zan on võrdne ühega miinus tõenäosus p 0 et kanal on tasuta:

R zan = 1 - R 0 = lk. (20.18)

Seetõttu on teenindatavate päringute keskmine arv võrdne

^L umbes= ρ, (20,19)

L oh = L syst - ρ =

ja lõpuks

L pt = (20.20)

Little'i valemit (19.13) kasutades leiame keskmise aja, mille rakendus järjekorras veedab:

(20.21)

Seega on leitud kõik QS efektiivsuse omadused.

Teeme lugejale ettepaneku lahendada näide iseseisvalt: ühe kanaliga QS on raudtee sorteerimisjaam, mis võtab vastu kõige lihtsama rongide voolu intensiivsusega λ = 2 (ronge tunnis). Teenindus (laialiminek)

kompositsioon kestab juhusliku (demonstratiivse) aja keskmise väärtusega t umbes = 20(min.). Jaama saabumispargis on kaks rada, millel saabuvad rongid saavad teenust oodata; kui mõlemad rajad on hõivatud, on rongid sunnitud ootama välimistel rööbasteedel.

On vaja leida (jaama piirava, statsionaarse töörežiimi jaoks): keskmine, rongide arv l jaamaga seotud süsteem, keskmine aeg W rongipeatussüsteem jaamas (siseteedel, välisteedel ja hoolduses), keskmine arv L pts laialimineku järjekorras ootavaid ronge (pole vahet, millistel rööbastel), keskmine aeg W Pts jääb koosseis ootenimekirja. Püüdke leida ka välimistel rööbasteedel laiali saatmist ootavate rongide keskmine arv. L väline ja selle ootamise keskmine aeg W väline (kaks viimast suurust on seotud Little'i valemiga).

Lõpuks leidke päevane kogutrahv W, mille jaam peab tasuma rongide seisaku eest välistel rööbasteedel, kui jaam maksab trahvi a (rubla) ühe rongi ühetunnise seisaku eest. Igaks juhuks vastused siin: L süsteem = 2 (koostis), W süsteem = 1 (tund), L punktid = 4/3 (koosseis), W pt = 2/3 (tunnid), L väline = 16/27 (koostis), W väline = 8/27 ≈ 0,297 (tunnid). Keskmine päevatrahv W rongide välistel rööbasteedel ootamise eest saadakse, kui korrutatakse ööpäevas jaama saabuvate rongide keskmine arv, keskmine välisteedel rongide ooteaeg ja tunnitasu. a: W ≈ 14,2 a.

piiramatu järjekorraga QS-i uuesti kanaliseerimine.

Täiesti sarnane probleemiga 2, kuid veidi keerulisem, probleem n-channel QS piiramatu järjekorraga.

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

Surma ja paljunemise skeem on olemas, kuid lõpmatu arvu olekutega. Esitagem ilma tõestuseta lõplike tõenäosuste olemasolu loomulik tingimus: ρ/ n n ≥ 1, järjekord kasvab lõpmatuseni.

Oletame, et tingimus ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 seal on rida termineid, mis sisaldavad faktoriaale, millele lisandub lõpmatult kahaneva geomeetrilise progressiooni summa nimetajaga ρ/ n. Kokkuvõtteks leiame

(20.22)

Nüüd leiame QS-i efektiivsuse omadused. Nendest on kõige lihtsam leida keskmine hõivatud kanalite arv k= λ/μ, = ρ (see kehtib üldiselt iga piiramatu järjekorraga QS-i kohta). Leidke keskmine rakenduste arv süsteemis L süsteem ja keskmine rakenduste arv järjekorras L och. Neist teist on valemi järgi lihtsam arvutada

L oh =

vastavate teisenduste sooritamine vastavalt ülesande 2 näidisele

(koos seeriate eristamisega) saame:

L oh = (20.23)

Lisades sellele keskmine teenuses olevate rakenduste arv (see on ka keskmine hõivatud kanalite arv) k =ρ, saame:

L syst = L och + ρ. (20.24)

Avaldiste jagamine L och ja L syst on λ , Little'i valemit kasutades saame rakenduse keskmise viibimisaja järjekorras ja süsteemis:

(20.25)

Nüüd lahendame huvitava näite. Kahe aknaga raudteepiletikassa on kahe kanaliga piiramatu järjekorraga QS, mis moodustatakse kohe kahele aknale (kui üks aken on vaba, võtab selle järjekorras järgmine reisija). Kassa müüb pileteid kahes punktis: A ja AT. Taotluste voo intensiivsus (reisijad, kes soovivad piletit osta) mõlema punkti kohta A ja B on sama: λ A = λ B = 0,45 (reisija minutis) ja kokku moodustavad nad üldise rakenduste voo intensiivsusega λ A + λB = 0,9. Kassapidaja kulutab reisija teenindamiseks keskmiselt kaks minutit.

Kogemus näitab, et piletikassas kogunevad järjekorrad, reisijad kurdavad teeninduse aegluse üle. AGA ja sisse AT, luua kaks spetsialiseeritud piletikassat (üks aken mõlemas), müües pileteid üks - ainult punktini AGA, teine ​​- ainult punktini AT. Selle ettepaneku põhjendatus on vastuoluline – mõned väidavad, et järjekorrad jäävad samaks. Ettepaneku kasulikkust tuleb kontrollida arvutuste teel. Kuna karakteristikuid saame arvutada ainult kõige lihtsama QS jaoks, siis oletame, et kõik sündmuste vood on kõige lihtsamad (see ei mõjuta järelduste kvalitatiivset poolt).

Noh, asume siis asja kallale. Piletimüügi korraldamiseks kaaluge kahte võimalust - olemasolevat ja pakutavat.

Variant I (olemasolev). Kahe kanaliga QS võtab vastu rakenduste voo, mille intensiivsus on λ = 0,9; hooldusvoolu intensiivsus μ = 1/2 = 0,5; ρ = λ/μ = l.8. Kuna ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. Keskmine, järjekorras olevate taotluste arv leitakse valemiga (20,23): L och ≈ 7,68; kliendi keskmine järjekorras viibitud aeg (vastavalt esimesele valemitest (20.25)) on võrdne W pts ≈ 8,54 (min).

II variant (pakutud). On vaja arvestada kahe ühe kanaliga QS-iga (kaks spetsiaalset akent); igaüks saab päringute voo intensiivsusega λ = 0,45; μ . ikka võrdne 0,5-ga; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8,1.

Siin on üks teile! Selgub, et järjekorra pikkus mitte ainult ei vähenenud, vaid suurenes! Ehk on keskmine ooteaeg järjekorras vähenenud? Vaatame. Delya L punktid λ = 0,45, saame W pts ≈ 18 (minutit).

See on ratsionaliseerimine! Vähenemise asemel kasvas nii keskmine järjekorra pikkus kui ka keskmine ooteaeg selles!

Proovime arvata, miks see juhtus? Mõeldes oma ajudele, jõuame järeldusele: see juhtus seetõttu, et esimeses variandis (kahe kanaliga QS) on kahe kassapidaja keskmine jõudeoleku osa väiksem: kui ta ei tegele reisija teenindamisega, ostab pileti AGA, ta saab hoolitseda reisija eest, kes ostab pileti punkti AT, ja vastupidi. Teises variandis sellist vahetatavust pole: tühi kassapidaja istub lihtsalt käed rüpes...

- Noh , OK, lugeja on valmis nõustuma, kasv on seletatav, aga miks see nii märkimisväärne on? Kas siin on valearvestus?

Ja me vastame sellele küsimusele. Viga ei ole. Fakt , et meie näites töötavad mõlemad QS-id oma võimaluste piiril; kui teenindusaega veidi pikendate (st vähendate μ), ei tule nad enam reisijatevoogudega toime ja järjekord hakkab lõputult kasvama. Ja kassapidaja "lisa seisakuaeg" on teatud mõttes võrdne tema tootlikkuse vähenemisega μ.

Seega osutub algul paradoksaalsena (või isegi lihtsalt valena) tunduv arvutustulemus õigeks ja seletatavaks.

Sedalaadi paradoksaalsed järeldused, mille põhjus pole sugugi ilmne, on järjekorra teoorias rikas. Autorit ennast tuli korduvalt "üllatuda" arvutuste tulemustest, mis hiljem õigeks osutusid.

Viimasele ülesandele mõeldes võib lugeja küsimuse esitada nii: kui kassa müüb pileteid ainult ühte punkti, siis loomulikult peaks teenindusaeg vähenema, noh, mitte poole võrra, aga vähemalt mõnevõrra, aga arvasime, et ikkagi keskmine on 2 (min.). Kutsume nii valivat lugejat vastama küsimusele: kui palju tuleks seda vähendada, et “ratsionaliseerimisettepanek” kasumlikuks muutuks?

Taas kohtume, kuigi elementaarne, kuid siiski optimeerimisprobleem. Esialgsete arvutuste abil on ka kõige lihtsamate, Markovi mudelite puhul võimalik selgitada nähtuse kvalitatiivset poolt – kuidas on tulus tegutseda ja kuidas kahjumlik. Järgmises osas tutvustame mõningaid elementaarseid mitte-Markovi mudeleid, mis avardavad veelgi meie võimalusi.

Pärast seda, kui lugeja on tutvunud kõige lihtsama QS lõppseisundi tõenäosuste ja jõudlusnäitajate arvutamise meetoditega (ta on selgeks saanud surma- ja paljunemisskeemi ning Little'i valemi), võib talle pakkuda iseseisvaks kaalumiseks veel kaks lihtsat QS-i.

Ühe kanaliga QS piiratud järjekorraga. Probleem erineb ülesandest 2 ainult selle poolest, et taotluste arv järjekorras on piiratud (ei tohi ületada mõnda antud t). Kui uus päring saabub hetkel, mil kõik kohad järjekorras on hõivatud, jätab see QS-i teenindamata (tagasilükatud).

On vaja leida olekute lõplikud tõenäosused (muide, need on selles ülesandes olemas mis tahes ρ korral - olekute arv on ju lõplik), ebaõnnestumise tõenäosus R otk, absoluutne ribalaius AGA, tõenäosus, et kanal on hõivatud R zan, keskmine järjekorra pikkus L och, ühise turukorralduse keskmine taotluste arv L süsteem , keskmine ooteaeg järjekorras W och , taotluse keskmine ühises turukorralduses viibimise aeg W süsteem Järjekorra karakteristikute arvutamisel saate kasutada sama tehnikat, mida kasutasime ülesandes 2, selle erinevusega, et kokkuvõte on vajalik mitte lõpmatu, vaid lõpliku progressiooni kohta.

Suletud ahelaga QS ühe kanaliga ja m rakenduste allikad. Konkreetsuse huvides püstitame ülesande järgmisel kujul: üks töötaja teenib t masinad, millest igaüks vajab aeg-ajalt reguleerimist (parandust). Iga töömasina nõudlusvoo intensiivsus on võrdne λ-ga . Kui masin on hetkel tööst väljas, kui töötaja on vaba, läheb ta kohe teenindusse.

Kui ta on hetkel, kui töötaja on hõivatud, rivist väljas, seab ta järjekorda ja ootab, et töötaja vabaneks. Keskmine seadistamise aeg t pööre = 1/μ. Töötajale saabuvate päringute voo intensiivsus sõltub sellest, kui palju masinaid töötab. Kui see töötab k tööpingid, on see võrdne kλ. Leidke lõppseisundi tõenäosused, töötavate masinate keskmine arv ja tõenäosus, et töötaja on hõivatud.

Pange tähele, et selles QS-is eksisteerivad lõplikud tõenäosused ka mis tahes väärtustele λ ja μ = 1/ t o, kuna süsteemi olekute arv on lõplik.