Jonon teoria. Käytännön oppitunnilla pohditaan tätä polkua ja verrataan simulaatiotuloksia teoreettiseen ratkaisuun

Esimerkkejä jonojärjestelmien ongelmien ratkaisemisesta

Sitä tarvitaan tehtävien 1–3 ratkaisemiseen. Alkutiedot on esitetty taulukossa. 2–4.

Joitakin merkintöjä, joita käytetään jonoteoriassa kaavoille:

n on kanavien lukumäärä QS:ssä;

λ on sisääntulevan sovellusvirran P in intensiteetti;

v on lähtevän sovellusvirran P out intensiteetti;

μ on palveluvirran P noin intensiteetti;

ρ on järjestelmän kuormituksen ilmaisin (liikenne);

m on jonossa olevien paikkojen enimmäismäärä, mikä rajoittaa hakemusjonon pituutta;

i on pyyntölähteiden lukumäärä;

p k on järjestelmän k:nnen tilan todennäköisyys;

p o - koko järjestelmän joutotilanteen todennäköisyys, ts. todennäköisyys, että kaikki kanavat ovat vapaita;

p syst on todennäköisyys hyväksyä hakemus järjestelmään;

p ref - hakemuksen hylkäämisen todennäköisyys sen hyväksyessä järjestelmään;

р noin - todennäköisyys, että sovellus huolletaan;

A on järjestelmän absoluuttinen suorituskyky;

Q on järjestelmän suhteellinen suorituskyky;

och - jonossa olevien sovellusten keskimääräinen lukumäärä;

r on käytössä olevien hakemusten keskimääräinen lukumäärä;

syst on järjestelmän sovellusten keskimääräinen lukumäärä;

pt on jonossa olevan sovelluksen keskimääräinen odotusaika;

r on pyynnön keskimääräinen palveluaika, joka liittyy vain palveltuihin pyyntöihin;

sys on sovelluksen keskimääräinen viipymäaika järjestelmässä;

oj on jonossa olevan hakemuksen odotusaikaa rajoittava keskimääräinen aika;

on varattujen kanavien keskimääräinen määrä.

QS A:n absoluuttinen suorituskyky on sovellusten keskimääräinen määrä, ĸᴏᴛᴏᴩᴏᴇ järjestelmä voi palvella aikayksikköä kohti.

Suhteellinen QS-läpäisykyky Q on järjestelmän keskimääräisen palvelemien sovellusten lukumäärän aikayksikköä kohti suhde tänä aikana vastaanotettujen sovellusten keskimääräiseen määrään.

Jonoongelmia ratkaistaessa on erittäin tärkeää noudattaa seuraavaa järjestystä:

1) QS-tyypin määrittäminen taulukon mukaan. 4,1;

2) kaavojen valinta QS-tyypin mukaan;

3) ongelmanratkaisu;

4) johtopäätösten muotoilu ongelmasta.

1. Kuoleman ja lisääntymisen kaavio. Tiedämme, että nimetyn tilagraafin avulla voimme helposti kirjoittaa Kolmogorov-yhtälöitä tilatodennäköisyyksiä varten sekä kirjoittaa ja ratkaista algebrallisia yhtälöitä lopullisille todennäköisyyksille. On syytä sanoa, että joissakin tapauksissa viimeiset yhtälöt

päättää etukäteen, kirjaimellisesti. Tämä voidaan tehdä erityisesti, jos järjestelmän tilagraafi on ns. ʼʼkuoleman ja lisääntymisen kaavioʼʼ.

Kuoleman ja lisääntymisen kaavion tilakaavio on kuvan 2 mukaisessa muodossa. 19.1. Tämän graafin erikoisuus on, että kaikki järjestelmän tilat voidaan laajentaa yhdeksi ketjuksi, jossa jokainen keskimääräinen tila ( S 1 , S 2 ,…,S n-1) on yhdistetty eteen- ja taaksepäin osoittavalla nuolella jokaiseen naapuritilaan - oikeaan ja vasempaan sekä ääritiloihin (S 0 , S n) - vain yhden naapurivaltion kanssa. Termi ʼʼkuoleman ja lisääntymisen kaavioʼʼ on peräisin biologisista ongelmista, joissa tällainen kaavio kuvaa väestön koon muutosta.

Kuoleman ja lisääntymisen järjestelmä löytyy hyvin usein erilaisista käytännön ongelmista, erityisesti - jonoteoriassa tässä suhteessa on hyödyllistä kerta kaikkiaan löytää tilojen lopulliset todennäköisyydet sille.

Oletetaan, että kaikki tapahtumavirrat, jotka siirtävät järjestelmää kaavion nuolia pitkin, ovat yksinkertaisimpia (lyhyyden vuoksi kutsumme myös järjestelmää S ja siinä tapahtuva prosessi - yksinkertaisin).

Käyttämällä kuvion kaaviota. 19.1, muodostamme ja ratkaisemme algebrallisia yhtälöitä tilan lopullisille todennäköisyyksille), olemassaolo seuraa siitä, että jokaisesta tilasta voi mennä joka toiseen, tilojen määrä on äärellinen). Ensimmäiselle osavaltiolle S 0 meillä on:

(19.1)

Toiselle osavaltiolle S1:

Johtuen (19.1) viimeinen yhtälö pelkistyy muotoon

missä k ottaa kaikki arvot 0:sta P. Lopulliset todennäköisyydet siis p0, p1,..., p n täyttävät yhtälöt

(19.2)

lisäksi meidän on otettava huomioon normalisointiehto

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

Ratkaistaan ​​tämä yhtälöjärjestelmä. Ensimmäisestä yhtälöstä (19.2) ilmaisemme s 1 kautta R 0 :

s 1 = s 0. (19.4)

Toisesta, ottaen huomioon (19.4), saamme:

(19.5)

‣‣‣ kolmannesta, ottaen huomioon (19.5),

(19.6)

ja yleensä mille tahansa k(1 - n):

(19.7)

Kiinnitetään huomiota kaavaan (19.7). Osoittaja on kaikkien vasemmalta oikealle johtavien nuolien intensiteetit (alusta tiettyyn tilaan S k) ja nimittäjässä - kaikkien oikealta vasemmalle johtavien nuolien intensiteettien tulo (alusta Sk).

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, kaikki tilatodennäköisyydet R 0 , s 1 , ..., р n ilmaistaan ​​yhden heistä ( R 0). Korvataan nämä lausekkeet normalisointiehtoon (19.3). Saamme sulkeiden avulla R 0:

tästä syystä saamme ilmaisun for R 0 :

(nostimme sulkeet potenssiin -1, jotta emme kirjoita kaksikerroksisia murtolukuja). Kaikki muut todennäköisyydet ilmaistaan R 0 (katso kaavat (19.4) - (19.7)). Huomaa, että kertoimet for R 0 kussakin niistä on vain sarjan peräkkäisiä jäseniä kaavan (19.8) yksikön jälkeen. Joten lasketaan R 0 , olemme jo löytäneet kaikki nämä kertoimet.

Saadut kaavat ovat erittäin hyödyllisiä jonoteorian yksinkertaisimpien ongelmien ratkaisemisessa.

^ 2. Pieni kaava. Nyt johdetaan yksi tärkeä kaava, joka liittyy (rajoittavaan, kiinteään järjestelmään) sovellusten keskimääräiseen määrään L syst, joka sijaitsee jonojärjestelmässä (eli palvellaan tai seisoo jonossa) ja sovelluksen keskimääräinen viipymäaika järjestelmässä W syst.

Tarkastellaan mitä tahansa QS:tä (yksikanavainen, monikanavainen, markolainen, ei-markolainen, rajoittamattomalla tai rajoitetulla jonolla) ja kaksi siihen liittyvää tapahtumavirtaa: QS:ään saapuvien asiakkaiden virta ja sieltä poistuvien asiakkaiden virta. QS. Jos järjestelmään on muodostettu rajoittava, stationäärinen tila, niin QS:ään saapuvien sovellusten keskimäärä aikayksikköä kohti on yhtä suuri kuin sieltä lähtevien sovellusten keskimääräinen määrä: molemmilla virroilla on sama intensiteetti λ.

Merkitse: X(t) - hakemusten määrä, jotka saapuivat yhteiseen markkinajärjestelyyn ennen tätä hetkeä t. Y(t) - yhteisestä markkinajärjestelystä lähteneiden hakemusten määrä

hetkeen asti t. Molemmat toiminnot ovat satunnaisia ​​ja muuttuvat äkillisesti (nousevat yhdellä) pyyntöjen saapuessa (X(t)) ja hakemusten lähdöt (Y(t)). Toimintojen tyyppi X(t) ja Y(t) esitetty kuvassa. 19,2; molemmat rivit ovat porrastettuja, ylempi on X(t), alempi- Y(t). Ilmeisesti hetkeksi tahansa t niiden ero Z(t)= X(t) - Y(t) on vain QS-sovellusten määrä. Kun linjat X(t) ja K(t) yhdistä, järjestelmässä ei ole pyyntöjä.

Harkitse hyvin pitkää ajanjaksoa T(jatkamalla kaaviota mielessään paljon piirustuksen jälkeen) ja laskea sille QS:n sovellusten keskimääräinen määrä. Se on yhtä suuri kuin funktion integraali Z(t) tällä aikavälillä jaettuna välin pituudella T:

L syst. = . (19.9) o

Mutta tämä integraali ei ole mitään muuta kuin kuvassa 1 varjostetun kuvan alue. 19.2. Katsotaanpa tätä kuvaa hyvin. Kuvio koostuu suorakulmioista, joiden jokaisen korkeus on yhtä ja kanta, joka vastaa viipymisaikaa vastaavan järjestyksen järjestelmässä (ensimmäinen, toinen jne.). Merkitään nämä ajat t1, t2,... Totta, väliajan lopussa T jotkut suorakulmiot tulevat varjostettuun kuvioon ei kokonaan, vaan osittain, mutta riittävän suurella T näillä pienillä asioilla ei ole väliä. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, voimme olettaa, että

(19.10)

jossa summa koskee kaikkia aikana saatuja tilauksia T.

Jaa oikea ja vasen puoli (.19.10) välin pituudella T. Saamme, ottaen huomioon (19.9),

L syst. = . (19.11)

Jaamme ja kerromme (19.11):n oikean puolen intensiteetillä X:

L syst. = .

Mutta suuruus Tλ on vain kyseisenä aikana vastaanotettujen hakemusten keskimääräinen määrä ^ T. Jos jaamme kaikkien aikojen summan t i hakemusten keskimääräisestä määrästä, niin saamme sovelluksen keskimääräisen viipymisajan järjestelmässä W syst. Niin,

L syst. = λ W syst. ,

W syst. = . (19.12)

Tämä on Littlen upea kaava: mille tahansa QS:lle, minkä tahansa tyyppiselle sovellusvirralle, mille tahansa palveluajan jakautumiselle, mille tahansa palvelualalle asiakkaan keskimääräinen viipymäaika järjestelmässä on yhtä suuri kuin keskimääräinen asiakkaiden lukumäärä järjestelmässä jaettuna asiakasvirran intensiteetillä.

Täsmälleen samalla tavalla johdetaan Littlen toinen kaava, joka kertoo keskimääräisen ajan, jonka sovellus viettää jonossa ^ Oho ja jonossa olevien hakemusten keskimääräinen määrä L oho:

W oho = . (19.13)

Tulosta varten se riittää kuvan alimman rivin sijaan. 19.2 ota funktio U(t)- tähän mennessä jäljellä olevien hakemusten määrä t ei järjestelmästä, vaan jonosta (jos järjestelmään tullut sovellus ei jono, vaan menee heti palveluun, voidaan silti olettaa, että se tulee jonoon, mutta pysyy siinä nollan ajan).

Littlen kaavoilla (19.12) ja (19.13) on tärkeä rooli jonoteoriassa. Valitettavasti useimmissa olemassa olevissa käsikirjoissa näitä kaavoja (joka on todistettu yleisessä muodossa suhteellisen hiljattain) ei ole annettu 1).

§ 20. Yksinkertaisimmat jonojärjestelmät ja niiden ominaisuudet

Tässä osiossa tarkastelemme joitain yksinkertaisimmista QS:istä ja johdamme lausekkeita niiden ominaisuuksille (suorituskykyindikaattorit). Samalla esitellään tärkeimmät metodologiset tekniikat, jotka ovat ominaisia ​​alkeisjonoteorialle, ʼʼʼʼʼʼʼ. Emme etsi niiden QS-näytteiden määrää, joille ominaisuuksien lopulliset lausekkeet johdetaan; tämä kirja ei ole opas jonotuksen teoriaan (tällainen rooli on paljon paremmin suoritettu erityiskäsikirjoilla). Tavoitteenamme on esitellä lukijalle joitain ʼʼtemppujaʼʼ, jotka helpottavat jonoteorian läpikulkua, mikä useissa saatavilla olevissa (jopa suosituissa) kirjoissa voi tuntua vauhdikkaalta esimerkkikokoelmalta.

Kaikki tapahtumavirrat, jotka siirtävät QS:n tilasta tilaan, tässä osiossa tarkastelemme yksinkertaisinta (ilman että tätä joka kerta erikseen määrätään). Niiden joukossa on niin sanottu ʼʼpalveluvirtaʼʼ. Se tarkoittaa yhden jatkuvasti varatun kanavan palvelemaa pyyntöjen virtaa. Tässä vuossa tapahtumien välisellä aikavälillä, kuten aina yksinkertaisimmassa virtauksessa, on eksponentiaalinen jakauma (monissa käsikirjoissa sen sijaan sanotaan: ʼʼpalveluaika on eksponentiaalinenʼʼ, käytämme itse tätä termiä jatkossa).

1) Suositussa kirjassa on esitetty hieman erilainen, yllä olevaan verrattuna, johtaminen Littlen kaavasta. Yleisesti ottaen tähän kirjaan (ʼʼKeskustelu kaksiʼʼ) tutustuminen on hyödyllistä jonoteoriaan tutustumisessa.

Tässä osiossa eksponentiaalinen palveluaikajakauma pidetään itsestäänselvyytenä, kuten aina "yksinkertaisimmassa" järjestelmässä.

Esittelemme esityksen aikana tarkasteltavan QS:n tehokkuusominaisuudet.

^ 1. P-kanava QS, jossa on vikoja(Erlangin ongelma). Tässä tarkastellaan jonoteorian yhtä ensimmäisistä ajallisesti ʼʼklassisistaʼʼ ongelmista;

tämä ongelma syntyi puhelimen käytännön tarpeista ja sen ratkaisi vuosisadamme alussa tanskalainen matemaatikko Erlant. Tehtävä on asetettu seuraavasti: on P kanavat (viestintälinjat), jotka vastaanottavat sovellusvirran intensiteetillä λ. Palveluvirran intensiteetti on μ (keskimääräisen palveluajan käänteisluku t noin). Etsi QS-tilojen lopulliset todennäköisyydet sekä sen tehokkuuden ominaisuudet:

^A- absoluuttinen suorituskyky, eli keskimääräinen palveltujen sovellusten lukumäärä aikayksikköä kohti;

Q- suhteellinen läpimeno, eli järjestelmän palvelemien saapuvien pyyntöjen keskimääräinen osuus;

^ R otk- epäonnistumisen todennäköisyys, eli se, että sovellus jättää QS:n käyttämättä;

k- keskimääräinen varattujen kanavien määrä.

Ratkaisu. Järjestelmän tilat ^S(QS) numeroidaan järjestelmän pyyntöjen määrän mukaan (tässä tapauksessa se on sama kuin varattujen kanavien lukumäärä):

S 0 - yhteisessä markkinajärjestelyssä ei ole hakemuksia,

S 1 - QS:ssä on yksi pyyntö (yksi kanava on varattu, loput ovat vapaita),

Sk- SMO:ssa on k sovellukset ( k kanavat ovat varattuja, loput ovat ilmaisia),

S n - SMO:ssa on P sovellukset (kaikki n kanavat ovat varattu).

QS-tilakaavio vastaa lisääntymiskuoleman kaaviota (kuva 20.1). Merkitään tämä kaavio - lasketaan tapahtumavirtojen intensiteetti nuolien lähelle. From S 0 tuumaa S1 järjestelmää siirtää pyyntöjen virta, jonka intensiteetti on λ (niin kun pyyntö saapuu, järjestelmä hyppää S0 sisään S1). Sama sovellusvirta kääntää

järjestelmä mistä tahansa vasemmasta tilasta viereiseen oikeaan tilaan (katso ylänuolet kuvassa 20.1).

Laitetaan alas alempien nuolien voimakkuus. Anna järjestelmän olla tilassa ^S 1 (yksi kanava toimii). Se tuottaa μ palveluita aikayksikköä kohden. Astuimme alas nuolen kohdalle S 1 →S 0 intensiteetti μ. Kuvittele nyt, että järjestelmä on tilassa S2(kaksi kanavaa toimii). Jotta hän menisi S 1, on välttämätöntä, että joko ensimmäinen tai toinen kanava lopettaa huollon; niiden palveluvirtojen kokonaisintensiteetti on 2μ; laita se vastaavan nuolen kohdalle. Kolmen kanavan antaman kokonaispalveluvirran intensiteetti on 3 μ, k kanavat - km. Laitamme nämä intensiteetit alas kuvan 1 alempien nuolien kohdalle. 20.1.

Ja nyt, kun tiedämme kaikki intensiteetit, käytämme valmiita kaavoja (19.7), (19.8) lopullisille todennäköisyyksille kuoleman ja lisääntymisen kaaviossa. Kaavan (19.8) mukaan saamme:

Hajotustermit ovat kertoimet p 0 ilmaisuissa for p1

Huomaa, että kaavat (20.1), (20.2) eivät sisällä intensiteettejä λ ja μ erikseen, vaan vain suhteena λ/μ. Merkitse

λ/μ = ρ (20,3)

ja kutsumme р:n arvoa ʼʼpyyntövirran vähentyneeksi intensiteetiksiʼʼ. Sen merkitys on yhden pyynnön keskimääräiselle palveluajalle saapuvien pyyntöjen keskimääräinen määrä. Tätä merkintää käyttämällä kirjoitamme kaavat (20.1), (20.2) uudelleen muotoon:

Lopullisten tilatodennäköisyyksien kaavoja (20.4), (20.5) kutsutaan Erlangin kaavoiksi - jonoteorian perustajan kunniaksi. Suurin osa tämän teorian muista kaavoista (nykyään niitä on enemmän kuin sieniä metsässä) ei kanna mitään erityisiä nimiä.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, lopulliset todennäköisyydet löytyvät. Niiden perusteella laskemme QS-tehokkuusominaisuudet. Ensin löydämme ^ R otk. - todennäköisyys, että saapuva pyyntö hylätään (ei toimiteta). Tätä varten on välttämätöntä, että kaikki P kanavat olivat kiireisiä, joten

R otk = R n = . (20.6)

Täältä löydämme suhteellisen suorituskyvyn - todennäköisyyden, että sovellus palvellaan:

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

Saamme absoluuttisen suorituskyvyn kertomalla pyyntöjen virran intensiteetin λ:lla K:

A = λQ = λ. (20.8)

Jää vain löytää kiireisten kanavien keskimääräinen määrä k. Tämä arvo voidaan löytää ʼʼsuoraanʼʼ, diskreetin satunnaismuuttujan matemaattisena odotuksena mahdollisilla arvoilla 0, 1, ..., P ja näiden arvojen todennäköisyydet p 0 p 1 , ..., p n:

k = 0 · p 0+ yksi · p 1 + 2 · p 2 + ... + n · p n .

Korvaa tässä lausekkeet (20.5) for R k , (k = 0, 1, ..., P) ja suorittamalla sopivat muunnokset, saisimme lopulta oikean kaavan k. Mutta tulostamme sen paljon helpommin (tässä se on, yksi ʼʼpienistä temppuistaʼʼ!) Todellakin, tiedämme absoluuttisen kaistanleveyden MUTTA. Tämä ei ole muuta kuin järjestelmän palvelemien sovellusten virtauksen intensiteetti. Jokainen käytetty i .shal aikayksikköä kohden palvelee keskimäärin |l pyyntöä. Keskimääräinen varattujen kanavien määrä on siis

k = A/μ, (20.9)

tai annettu (20.8),

k = (20.10)

Kannustamme lukijaa laatimaan esimerkin itse.
Isännöi osoitteessa ref.rf
Siellä on viestintäasema, jossa on kolme kanavaa ( n= 3), sovellusvirran intensiteetti λ = 1,5 (applikaatiota minuutissa); keskimääräinen palveluaika pyyntöä kohti t tilavuus = 2 (min.), kaikki tapahtumavirrat (kuten tässä koko kappaleessa) ovat yksinkertaisimpia. Etsi QS:n lopulliset tilatodennäköisyydet ja suorituskykyominaisuudet: A, Q, P otk, k. Varmuuden vuoksi tässä vastaukset: s 0 = 1/13, s 1 = 3/13, s 2 = 9/26, p 3 = 9/26 ≈ 0,346,

MUTTA≈ 0,981, K ≈ 0,654, P avoin ≈ 0,346, k ≈ 1,96.

Vastauksista näkyy muuten, että CMO on suurelta osin ylikuormitettu: kolmesta kanavasta keskimäärin noin kaksi on varattu ja noin 35 % saapuvista sovelluksista jää palvelematta. Pyydämme lukijaa, jos hän on utelias eikä laiska, ottamaan selvää: kuinka monta kanavaa tarvitaan, jotta vähintään 80% saapuvista hakemuksista voidaan tyydyttää? Ja mikä osa kanavista on yhtä aikaa käyttämättömänä?

Siitä on jo jonkinlainen vihje optimointi. Itse asiassa kunkin kanavan sisältö maksaa tietyn summan aikayksikköä kohden. Samalla jokainen huollettu sovellus tuo jonkin verran tuloja. Kerrotaan nämä tulot hakemusten keskimääräisellä määrällä MUTTA, huollettu aikayksikköä kohti, saamme keskimääräiset CMO-tulot aikayksikköä kohti. Luonnollisesti kanavien määrän kasvaessa nämä tulot kasvavat, mutta myös kanavien ylläpitokustannukset kasvavat. Mikä painaa enemmän - tulojen tai menojen kasvu? Se riippuu toiminnan ehdoista, ʼʼsovelluspalvelumaksustaʼʼʼ sekä kanavan ylläpitokustannuksista. Kun tiedät nämä arvot, voit löytää optimaalisen kanavien määrän, kustannustehokkaimman. Emme ratkaise tällaista ongelmaa, vaan jätämme kaiken saman "ei-laiskalle ja uteliaalle lukijalle" keksimään esimerkin ja ratkaisemaan sen. Yleensä ongelmien keksiminen kehittää enemmän kuin jonkun jo asettamien ratkaiseminen.

^ 2. Yksikanavainen QS rajoittamattomalla jonolla. Käytännössä yksikanavainen jonollinen QS on varsin yleistä (potilaita palveleva lääkäri; yhden kopin maksupuhelin; käyttäjien tilauksia täyttävä tietokone). Jonoteoriassa yksikanavaiset QS:t, joissa on jono, ovat myös erityisellä paikalla (useimmat tähän mennessä saaduista analyyttisistä kaavoista ei-Markovin järjestelmille kuuluvat sellaiseen QS:ään). Tästä syystä kiinnitämme erityistä huomiota yksikanavaiseen QS:ään, jossa on jono.

Olkoon yksikanavainen QS, jossa on jono, jolle ei ole asetettu rajoituksia (ei jonon pituuden eikä odotusajan suhteen). Tämä QS vastaanottaa pyyntöjen virran, jonka intensiteetti on λ ; palveluvirran intensiteetti on μ, joka on käänteinen pyynnön keskimääräiseen palveluaikaan t noin. On löydettävä QS-tilojen lopulliset todennäköisyydet sekä sen tehokkuuden ominaisuudet:

L syst. - järjestelmässä olevien sovellusten keskimääräinen määrä,

W syst. - sovelluksen keskimääräinen viipymäaika järjestelmässä,

^L och- jonossa olevien hakemusten keskimääräinen määrä,

W och - keskimääräinen aika, jonka sovellus viettää jonossa,

P zan - todennäköisyys, että kanava on varattu (kanavan kuormitusaste).

Mitä tulee absoluuttiseen tehokkuuteen MUTTA ja suhteellinen Q, niin niitä ei tarvitse laskea:

koska jono on rajoittamaton, jokainen hakemus palvellaan ennemmin tai myöhemmin tämän yhteydessä A \u003d λ, samasta syystä Q= 1.

Ratkaisu. Järjestelmän tilat, kuten ennenkin, numeroidaan QS:n sovellusten määrän mukaan:

S 0 - kanava on ilmainen

S 1 - kanava on varattu (palvelee pyyntöä), ei ole jonoa,

S 2 - kanava on varattu, yksi pyyntö on jonossa,

S k - kanava on varattu, k- 1 hakemusta on jonossa,

Teoreettisesti tilojen määrää ei rajoita mikään (äärettä). Tilakaavion muoto on kuvan mukainen. 20.2. Tämä on kuoleman ja lisääntymisen järjestelmä, mutta siinä on ääretön määrä tiloja. Kaikilla nuolilla pyyntöjen virta, jonka intensiteetti on λ, siirtää järjestelmän vasemmalta oikealle ja oikealta vasemmalle - palveluvirran intensiteetillä μ.

Ensinnäkin kysykäämme itseltämme, onko tässä tapauksessa olemassa lopullisia todennäköisyyksiä? Loppujen lopuksi järjestelmän tilojen lukumäärä on ääretön, ja periaatteessa on t → ∞ jono voi kasvaa loputtomiin! Kyllä, se on totta: lopulliset todennäköisyydet tällaiselle QS:lle eivät aina ole olemassa, mutta vain silloin, kun järjestelmä ei ole ylikuormitettu. Voidaan osoittaa, että jos ρ on ehdottomasti pienempi kuin yksi (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ kasvaa loputtomasti. Tämä seikka vaikuttaa erityisen "käsittämättömältä" ρ = 1:lle. Vaikuttaa siltä, ​​​​että järjestelmälle ei ole mahdottomia vaatimuksia: yhden pyynnön palvelemisen aikana saapuu keskimäärin yksi pyyntö ja kaiken pitäisi olla kunnossa, mutta todellisuudessa se on ei ole. Kun ρ = 1, QS käsittelee pyyntöjen virtaa vain, jos annettu virta on säännöllinen, eikä palveluaika ole myöskään satunnainen, yhtä suuri kuin pyyntöjen välinen aika. Tässä ʼʼʼʼʼ tapauksessa QS:ssä ei ole lainkaan jonoa, kanava on jatkuvasti varattu ja lähettää säännöllisesti palvelupyyntöjä. Mutta heti kun pyyntöjen virta tai palveluvirta tulee ainakin hieman satunnaiseksi, jono kasvaa jo loputtomasti. Käytännössä näin ei tapahdu vain siksi, että ʼʼääretön määrä sovelluksia jonossaʼʼ on abstraktio. Nämä ovat karkeita virheitä, joihin satunnaismuuttujien korvaaminen niiden matemaattisilla odotuksilla voi johtaa!

Mutta palataanpa yksikanavaiseen QS:ään, jossa on rajoittamaton jono. Tarkkaan ottaen lopullisten todennäköisyyksien kaavat kuoleman ja lisääntymisen kaaviossa johdimme vain rajallisen määrän tiloja varten, mutta otetaan vapaudet - käytämme niitä äärettömälle määrälle tiloja. Lasketaan tilojen lopulliset todennäköisyydet kaavojen (19.8), (19.7) mukaan. Meidän tapauksessamme termien määrä kaavassa (19.8) on ääretön. Saamme ilmaisun p 0:

s 0 = -1 =

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

Kaavan (20.11) sarja on geometrinen progressio. Tiedämme, että ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателœем р.
Isännöi osoitteessa ref.rf
Jos p ≥ 1, sarja poikkeaa (mikä on epäsuora, vaikkakaan ei tiukka todiste siitä, että lopullisen tilan todennäköisyydet p 0 , p 1 , ..., p k , ... olemassa vain r:lle<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

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

s 0 = 1 - s. (20.12)

Todennäköisyydet p 1 , p 2 , ..., p k ,... löytyy kaavoilla:

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

mistä, ottaen huomioon (20.12), löydämme lopulta:

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

Kuten näet, todennäköisyydet p0, p1, ..., p k,... muodostavat geometrisen progression nimittäjällä p.
Isännöi osoitteessa ref.rf
Kummallista kyllä, suurin niistä p 0 - todennäköisyys, että kanava on ilmainen. Riippumatta siitä, kuinka kuormitettu järjestelmä jonolla on, jos se vain pystyy selviytymään sovellusvirrasta (ρ<1), самое вероятное число заявок в системе будет 0.

Etsi hakemusten keskimääräinen määrä QS:stä ^L syst. . Tässä pitää vähän puuhailla. Satunnainen arvo Z- pyyntöjen määrä järjestelmässä - on mahdollisia arvoja 0, 1, 2, .... k,... todennäköisyyksien kanssa p0, p 1 , p 2 , ..., p k , ... Sen matemaattinen odotus on

L syst = 0 p 0+ yksi · s 1 + 2 s 2 +…+k · s k +…= (20.14)

(summaa ei oteta arvosta 0 arvoon ∞, vaan arvosta 1 arvoon ∞, koska nollatermi on yhtä suuri kuin nolla).

Korvataan kaavaan (20.14) lauseke for p k (20.13):

L syst. =

Nyt otetaan pois summan ρ (1-ρ) etumerkki:

L syst. = ρ(1-ρ)

Tässä käytämme jälleen ʼʼtemppuaʼʼ: kρ k-1 ei ole muuta kuin derivaatta lausekkeen ρ suhteen ρ:n suhteen k; tarkoittaa,

L syst. = ρ(1-ρ)

Vaihtamalla differentioinnin ja summauksen operaatiot keskenään saamme:

L syst. = ρ (1-ρ) (20.15)

Mutta summa kaavassa (20.15) ei ole mitään muuta kuin äärettömästi pienenevän geometrisen progression summa ensimmäisellä termillä ρ ja nimittäjällä ρ; Tämä summa

yhtä suuri kuin , ja sen johdannainen . Korvaa tämä lauseke lausekkeella (20.15), saamme:

L syst = . (20.16)

No, nyt sovelletaan Littlen kaavaa (19.12) ja etsitään sovelluksen keskimääräinen viipymäaika järjestelmästä:

W syst = (20.17)

Etsi jonossa olevien sovellusten keskimääräinen määrä L och. Väittelemme seuraavasti: jonossa olevien sovellusten määrä on yhtä suuri kuin järjestelmän sovellusten määrä miinus palvelussa olevien sovellusten määrä. Joten (matemaattisten odotusten lisäyssäännön mukaan) jonossa olevien hakemusten keskimääräinen määrä L pt on yhtä suuri kuin järjestelmän sovellusten keskimääräinen lukumäärä L syst miinus palvelussa olevien pyyntöjen keskimääräinen määrä. Palvelun alla olevien pyyntöjen määrän on oltava joko nolla (jos kanava on vapaa) tai yksi (jos se on varattu). Tällaisen satunnaismuuttujan matemaattinen odotus on yhtä suuri kuin todennäköisyys, että kanava on varattu (merkitsimme sitä R zan). Ilmeisesti R zan on yhtä suuri kuin yksi miinus todennäköisyys p 0 että kanava on vapaa: L ext ja tämän odotuksen keskimääräinen aika W ulkoinen (kaksi viimeistä määrää liittyvät Littlen kaavan mukaan). Lopuksi selvitetään päiväsakko W, jonka asema joutuu maksamaan junien seisonnasta ulkoisilla raiteilla, jos asema maksaa sakkoa (ruplaa) yhden junan tunnin seisomisesta. Varmuuden vuoksi tässä vastaukset: L syst. = 2 (koostumus), W syst. = 1 (tunti), L pisteet = 4/3 (koostumus), W pt = 2/3 (tuntia), L ulkoinen = 16/27 (koostumus), W ulkoinen = 8/27 ≈ 0,297 (tuntia). Keskimääräinen päiväsakko W junien odottamisesta ulkoraiteilla saadaan kertomalla asemalle saapuvien junien keskimäärä vuorokaudessa, junien keskimääräinen odotusaika ulkoraiteilla ja tuntisakko a: W ≈ 14,2 a.

^ 3. Kanava QS uudelleen rajoittamattomalla jonolla. Täysin samanlainen kuin ongelma 2, mutta hieman monimutkaisempi ongelma n-kanava QS rajoittamattomalla jonolla. Tilojen numerointi on jälleen järjestelmän sovellusten määrän mukaan:

N<1. В случае если ρ/n≥ 1, jono kasvaa äärettömään.

Oletetaan, että ehto ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя всœе те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 tulee joukko termejä, jotka sisältävät kertoimia plus loputtomasti pienenevän geometrisen progression summan nimittäjällä ρ/ n. Yhteenvetona löydämme

(20.22)

Etsitään nyt QS-tehokkuuden ominaisuudet. Näistä on helpoin löytää keskimääräinen varattujen kanavien määrä k== λ/μ, = ρ (tämä pätee yleensä kaikille QS:ille, joissa on rajoittamaton jono). Etsi järjestelmän sovellusten keskimääräinen määrä L järjestelmä ja jonossa olevien sovellusten keskimääräinen määrä L och. Näistä on helpompi laskea toinen kaavan mukaan

L oho =

suorittaa vastaavat muunnokset tehtävän 2 näytteen mukaisesti

(sarjan eriyttämisellä) saamme:

L oho = (20.23)

Kun siihen lisätään palvelussa olevien sovellusten keskimääräinen määrä (se on myös varattujen kanavien keskimääräinen määrä) k =ρ, saamme:

L syst = L och + ρ. (20.24)

Jakolausekkeet for L och ja L syst on λ , Littlen kaavalla saadaan sovelluksen keskimääräinen viipymäaika jonossa ja järjestelmässä:

(20.25)

Ratkaistaan ​​nyt mielenkiintoinen esimerkki.
Isännöi osoitteessa ref.rf
Kahden ikkunan junalippukassa on kaksikanavainen QS, jossa on rajoittamaton jono, joka muodostetaan välittömästi kahteen ikkunaan (jos yksi ikkuna on vapaa, jonossa seuraava matkustaja ottaa sen). Lippukassa myydään lippuja kahdessa paikassa: A ja AT. Hakemusvirran intensiteetti (matkustajat, jotka haluavat ostaa lipun) molemmille kohdille A ja B on sama: λ A = λ B = 0,45 (matkustaja minuutissa), ja yhteensä ne muodostavat yleisen sovellusvirran, jonka intensiteetti on λ A + λB = 0,9. Kassa käyttää matkustajan palvelemiseen keskimäärin kaksi minuuttia. Kokemus osoittaa, että lippukassalle kertyy jonoja, matkustajat valittavat palvelun hitaudesta. MUTTA ja sisään AT, luoda kaksi erikoistunutta lipputoimistoa (yksi ikkuna kummassakin), myymällä yksi lippu - vain asiaan MUTTA, toinen - vain asiaan AT. Tämän ehdotuksen järkevyys on kiistanalainen - jotkut väittävät, että jonot pysyvät ennallaan. Ehdotuksen hyödyllisyys on tarkistettava laskennallisesti. Koska voimme laskea ominaisuudet vain yksinkertaisimmalle QS:lle, oletetaan, että kaikki tapahtumavirrat ovat yksinkertaisimpia (tämä ei vaikuta johtopäätösten laadulliseen puoleen).

No sitten mennään asiaan. Harkitse kahta vaihtoehtoa lipunmyynnin järjestämiseen - nykyistä ja ehdotettua.

Vaihtoehto I (olemassa). Kaksikanavainen QS vastaanottaa sovellusvirran, jonka intensiteetti on λ = 0,9; ylläpitovirtauksen intensiteetti μ = 1/2 = 0,5; ρ = λ/μ = l.8. Koska ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. Keskiarvo, jonossa olevien sovellusten lukumäärä saadaan kaavalla (20.23): L och ≈ 7.68; asiakkaan keskimääräinen jonossa viettämä aika (ensimmäisen kaavan (20.25) mukaan) on yhtä suuri kuin W pts ≈ 8,54 (min.).

Vaihtoehto II (ehdotettu). On tarpeen harkita kahta yksikanavaista QS:ää (kaksi erikoisikkunaa); kukin vastaanottaa pyyntövirran, jonka intensiteetti on λ = 0,45; μ . edelleen yhtä suuri kuin 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8.1.

Tässä yksi sinulle! Osoittautuu, että jonon pituus ei vain vähentynyt, vaan kasvoi! Ehkä keskimääräinen odotusaika jonossa on lyhentynyt? Katsotaan. Delya L pisteet λ = 0,45, saamme W pts ≈ 18 (minuuttia).

Siinä se rationalisointi! Vähenemisen sijaan sekä keskimääräinen jonon pituus että keskimääräinen odotusaika siinä kasvoivat!

Yritetään arvata miksi näin tapahtui? Aivojamme pohdittuamme päädymme siihen tulokseen: tämä tapahtui, koska ensimmäisessä versiossa (kaksikanavainen QS) keskimääräinen vapaa-ajan osuus on pienempi.

Esimerkkejä jonojärjestelmien ongelmien ratkaisemisesta - käsite ja tyypit. Luokittelu ja ominaisuudet "Esimerkkejä jonojärjestelmien ongelmien ratkaisemisesta" 2017, 2018.

Usein talousjärjestelmiä analysoitaessa joudutaan ratkaisemaan ns. jonoongelmia, jotka syntyvät seuraavassa tilanteessa. Analysoidaan autohuoltojärjestelmä, joka koostuu tietystä määrästä eri kapasiteetin asemia. Jokaisella asemalla (järjestelmäelementillä) voi esiintyä vähintään kaksi tyypillistä tilannetta:

1. hakemusten määrä on liian suuri tälle asemalle, on jonoja ja joudut maksamaan palvelun viivästyksistä;
2. asema vastaanottaa liian vähän pyyntöjä ja nyt on jo otettava huomioon asemakatkon aiheuttamat häviöt.

On selvää, että järjestelmäanalyysin tavoitteena on tässä tapauksessa määrittää jokin suhde tulonmenetysten välillä jonoja ja tappiot vain minä asemat.

Jonotuksen teoria– Järjestelmäteorian erityinen osa on todennäköisyysteorian osa, jossa jonojärjestelmiä tutkitaan matemaattisten mallien avulla.

Jonojärjestelmä (QS)- tämä on malli, joka sisältää: 1) satunnaisen tarpeiden, puheluiden tai huoltoa tarvitsevien asiakkaiden kulun; 2) tämän palvelun toteuttamisalgoritmi; 3) kanavat (laitteet) huoltoa varten.

Esimerkkejä yhteisistä markkinajärjestelyistä ovat kassat, huoltoasemat, lentokentät, myyjät, kampaajat, lääkärit, puhelinkeskukset ja muut tilat, jotka palvelevat tiettyjä sovelluksia.

Jonoteoriaongelma koostuu suositusten laatimisesta QS:n järkevään rakentamiseen ja niiden työn järkevään organisointiin korkean palvelun tehokkuuden varmistamiseksi optimaalisilla kustannuksilla.

Tämän luokan ongelmien pääpiirre on analyysin tulosten ja saatujen suositusten ilmeinen riippuvuus kahdesta ulkoisesta tekijästä: vastaanottotiheydestä ja tilausten monimutkaisuudesta (ja siten niiden toteuttamisajasta).

Jonoteorian aiheena on selvittää sovellusvirran luonteen, erillisen palvelukanavan suorituskyvyn, kanavien lukumäärän ja palvelun tehokkuuden välinen suhde.

Kuten QS ominaisuudet harkittu:

• niiden hakemusten keskimääräinen prosenttiosuus, jotka hylätään ja jätetään järjestelmää käyttämättä;
• yksittäisten kanavien ja koko järjestelmän keskimääräinen seisokkiaika;
• keskimääräinen odotusaika jonossa;
• todennäköisyys, että vastaanotettu hakemus huolletaan välittömästi;
• jononpituuden jakautumislaki ja muut.

Lisäämme, että pyynnöt (vaatimukset) tulevat QS:ään satunnaisesti (satunnaisina aikoina) kondensaatio- ja harventumispisteineen. Jokaisen vaatimuksen palveluaika on myös satunnainen, minkä jälkeen palvelukanava vapautuu ja on valmis täyttämään seuraavan vaatimuksen. Jokaisella QS:llä on tietty kapasiteetti kanavien lukumäärästä ja niiden suorituskyvystä riippuen. SMO-läpäisykyky voi olla ehdoton(toimitettujen hakemusten keskimääräinen määrä aikayksikköä kohti) ja suhteellinen(käsiteltyjen hakemusten lukumäärän keskimääräinen suhde jätettyjen hakemusten lukumäärään).

3.1 Jonojärjestelmien mallit.

Jokainen QS voidaan luonnehtia lausekkeella: (A B C D E F) , missä

a - sovellusten syöttövirran jakelu;

b - sovellusten tulosvirran jakautuminen;

c – palvelumekanismin konfigurointi;

d – jonokuri;

e – odotuslohko;

f on lähteen kapasiteetti.

Tarkastellaan nyt jokaista ominaisuutta tarkemmin.

Sovellusten syöttövirta- järjestelmän vastaanottamien hakemusten määrä. Tunnusomaista tulovirran intensiteetillä l.

Sovellusten lähtövirta– järjestelmän palvelemien sovellusten määrä. Ominaista ulostulovirran intensiteetillä m.

järjestelmän kokoonpano tarkoittaa kanavien ja palvelusolmujen kokonaismäärää. SMO voi sisältää:

1. yksi kanava palvelut (yksi kiitorata, yksi myyjä);
2. yksi palvelukanava, mukaan lukien useita sarjasolmuja(ruokala, klinikka, kuljetin);
3. useita samanlaisia ​​kanavia rinnakkaiset palvelut (huoltoasemat, infopiste, rautatieasema).

Siten voidaan erottaa yksi- ja monikanavainen QS.

Toisaalta, jos kaikki QS:n palvelukanavat ovat varattuja, voi lähestytty sovellus jäädä jonoon tai poistua järjestelmästä (esimerkiksi säästöpankki ja puhelinkeskus). Tässä tapauksessa puhumme järjestelmistä, joissa on jono (odottaa) ja järjestelmistä, joissa on vikoja.

Vuoro on joukko sovelluksia, jotka ovat tulleet järjestelmään huollettavaksi ja odottavat palvelua. Jonolle on ominaista jonon pituus ja sen kurinalaisuus.

Jonon kurinalaisuus on sääntö jonosta tulevien pyyntöjen käsittelylle. Tärkeimmät jonotyypit ovat seuraavat:

1. PERPPO (ensin tullutta palvellaan ensin) on yleisin tyyppi;
2. POSPPO (viimeksi tullutta palvellaan ensin);
3. SOP (satunnainen sovellusvalinta) - tietopankista.
4. PR - prioriteettipalvelu.

Jonon pituus voi olla

• rajoittamaton - silloin puhutaan järjestelmästä, jolla on puhdas odotus;
• yhtä suuri kuin nolla - silloin he puhuvat järjestelmästä, jossa on vikoja;
• rajoitettu pituus (sekatyyppinen järjestelmä).

odotuslohko– järjestelmän "kapasiteetti" - järjestelmän sovellusten kokonaismäärä (jonossa ja palvelussa). Tällä tavalla, e=c+d.

Lähteen kapasiteetti joka luo palvelupyyntöjä, on pyyntöjen enimmäismäärä, joka voi tulla QS:ään. Esimerkiksi lentoasemalla lähdekapasiteettia rajoittaa kaikkien olemassa olevien lentokoneiden lukumäärä ja puhelinkeskuksen lähdekapasiteetti on yhtä suuri kuin maapallon asukkaiden lukumäärä, ts. sitä voidaan pitää rajoittamattomana.

QS-mallien lukumäärä vastaa näiden komponenttien mahdollisten yhdistelmien määrää.

3.2 Vaatimusten syöttövirta.

Jokaisella aikajaksolla a, a+ T ], liitetään satunnaismuuttuja X, joka on yhtä suuri kuin järjestelmän kyseisenä aikana vastaanottamien pyyntöjen määrä T.

Pyyntöjen virtaa kutsutaan paikallaan, jos jakautumislaki ei riipu välin alkupisteestä a, mutta riippuu vain tietyn aikavälin pituudesta T. Esimerkiksi sovellusten virtaus puhelinkeskukseen päivän aikana ( T\u003d 24 tuntia) ei voida pitää paikallaan, mutta 13-14 tuntia ( T\u003d 60 minuuttia) - voit.

Virtausta kutsutaan ei jälkivaikutusta, jos virtauksen historia ei vaikuta vaatimusten vastaanottamiseen tulevaisuudessa, ts. vaatimukset ovat toisistaan ​​riippumattomia.

Virtausta kutsutaan tavallinen, jos järjestelmään voi saapua vain yksi pyyntö hyvin lyhyessä ajassa. Esimerkiksi virtaus kampaajalle on tavallista, mutta ei maistraatille. Mutta jos satunnaismuuttujana X harkitse rekisteritoimistoon saapuvien sovellusten paria, niin tällainen virta on tavallinen (eli joskus ylimääräinen virta voidaan vähentää tavalliseksi).

Virtausta kutsutaan yksinkertaisin, jos se on paikallaan, ilman jälkivaikutuksia ja tavallinen.

Päälause. Jos virtaus on yksinkertaisin, niin r.v. X [a. + T] levitetään Poisson-lain mukaan, ts. .

Seuraus 1. Yksinkertaisinta virtausta kutsutaan myös Poisson-virtaukseksi.

Seuraus 2. M(X)= M(X [ a , a + T ] )= lT, eli aikana T lT sovellukset. Siksi järjestelmä vastaanottaa keskimäärin yhden aikayksikön l sovellukset. Tätä arvoa kutsutaan intensiteetti syöttövirta.

Harkitse EXAMPLE .

Studio saa keskimäärin 3 hakemusta päivässä. Olettaen, että kulku on yksinkertaisin, määritä todennäköisyys, että pyyntöjen määrä on vähintään 5 seuraavan kahden päivän aikana.

Ratkaisu.

Tehtävän mukaan mm. l=3, T=2 päivää, Poisson-syöttövirta, n ³5. ratkaistaessa on kätevää esitellä päinvastainen tapahtuma, joka koostuu siitä, että ajan kuluessa T Hakemuksia tulee alle 5. Siksi Poissonin kaavan mukaan saamme

^

3.3 Järjestelmän tila. Siirtymien matriisi ja graafi.

Satunnaisella hetkellä QS siirtyy tilasta toiseen: varattujen kanavien määrä, pyyntöjen ja jonojen määrä jne. muuttuvat. Näin ollen QS, jolla on n kanavat ja jonon pituus yhtä suuri kuin m, voi olla jossakin seuraavista tiloista:

E 0 – kaikki kanavat ovat ilmaisia;

E 1 – yksi kanava on varattu;

E n– kaikki kanavat ovat varattu;

E n +1 – kaikki kanavat ovat varattuja ja yksi pyyntö on jonossa;

E n + m– kaikki kanavat ja kaikki jonon paikat ovat varattuja.

Samanlainen järjestelmä vikoineen voi olla valtioissa E 0 – E n .

QS:lle, jolla on puhdas odotus, on ääretön joukko tiloja. Tällä tavalla, kunto E n QS aikaan t on määrä n sovellukset (vaatimukset), jotka ovat järjestelmässä tiettynä ajankohtana, ts. n= n(t) - satunnainen arvo, E n (t) ovat tämän satunnaismuuttujan tulokset, ja P n (t) on todennäköisyys, että järjestelmä on tilassa E n .

Tunnemme jo järjestelmän tilan. Huomaa, että kaikki järjestelmän tilat eivät ole samanarvoisia. Järjestelmän tilaa kutsutaan lähde jos järjestelmä voi poistua tästä tilasta, mutta ei voi palata siihen. Järjestelmän tilaa kutsutaan eristetty, jos järjestelmä ei voi poistua tai siirtyä tähän tilaan.

Järjestelmän tilojen kuvien visualisoimiseksi käytetään kaavioita (ns. siirtymäkaavioita), joissa nuolet osoittavat järjestelmän mahdollisia siirtymiä tilasta toiseen sekä tällaisten siirtymien todennäköisyyksiä.

Kuva 3.1 - siirtymäkaavio

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

Joskus on myös kätevää käyttää siirtymämatriisia. Tässä tapauksessa ensimmäinen sarake tarkoittaa järjestelmän alkutiloja (virta), ja sitten annetaan todennäköisyydet siirtyä näistä tiloista muihin.

Koska järjestelmä välttämättä kulkee yhdestä

tila toiseen, niin kunkin rivin todennäköisyyksien summa on aina yhtä suuri kuin yksi.

3.4 Yksikanavainen QS.

3.4.1 Yksikanavainen QS, jossa on vikoja.

Harkitsemme järjestelmiä, jotka täyttävät vaatimukset:

(P/E/1):(–/1/¥) . Oletetaan myös, että asiakkaan palveluaika ei riipu järjestelmään tulevien asiakkaiden määrästä. Tässä ja alla "P" tarkoittaa, että tulovirta on jakautunut Poissonin lain mukaan, ts. yksinkertaisin "E" tarkoittaa, että lähtövirta on jakautunut eksponentiaalisesti. Myös tässä ja alla pääkaavat on annettu ilman todisteita.

Tällaiselle järjestelmälle on mahdollista kaksi tilaa: E 0 - järjestelmä on ilmainen ja E 1 – järjestelmä on varattu. Luodaan siirtymämatriisi. Otetaan Dt on äärettömän vähän aikaa. Olkoon tapahtuma A siinä, että järjestelmässä aikana Dt saanut yhden pyynnön. Tapahtuma B koostuu siitä, että aikana Dt yksi pyyntö on toimitettu. Tapahtuma MUTTA i , k- aikana Dt järjestelmä lähtee tilasta E i tilaan E k. Koska l on tulovirran intensiteetti, sitten ajan kuluessa Dt tulee järjestelmään keskimäärin l*Dt vaatimukset. Eli yhden vaatimuksen saamisen todennäköisyys P(A)=l* Dt, ja päinvastaisen tapahtuman todennäköisyys Р(А)=1-l*Dt.P(B)=F(Dt)= P(b< D t)=1- e - m D t = m Dt- todennäköisyys, että pyyntö käsitellään ajoissa Dt. Sitten A 00 - hakemusta ei vastaanoteta tai se vastaanotetaan, mutta se toimitetaan. A 00 \u003d Ā + A * V. R 00 \u003d 1 - l*Dt. (Otimme sen huomioon (Dt) 2 on äärettömän pieni arvo)

A 01 - hakemus vastaanotetaan, mutta sitä ei toimiteta. A 01 = A * . R 01 = l*Dt.

Ja 10 - hakemus toimitetaan eikä uutta tule. A 10 \u003d B * a. R 10 = m*Dt.

Ja 11 - hakemusta ei toimiteta tai saapuu uusi, jota ei ole vielä toimitettu. A 11 = +V * A. R 01 = 1- m*Dt.

Siten saamme siirtymämatriisin:

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

Järjestelmän seisokkien ja vikojen todennäköisyys.

Etsitään nyt todennäköisyys, että järjestelmä on tilassa E 0 milloin tahansa t(nuo. R 0 ( t) ). Funktiokaavio
näkyy kuvassa 3.2.

Kaavion asymptootti on suora viiva
.

Ilmeisesti jostain kohtaa t,

1

Kuva 3.2

Vihdoin saamme sen
ja
, missä R 1 (t) on todennäköisyys, että sillä hetkellä t järjestelmä on varattu (eli on tilassa E 1 ).

On selvää, että QS-toiminnan alussa käynnissä oleva prosessi ei ole paikallaan: se on "siirtymävaihe", ei-stationaarinen tila. Jonkin ajan kuluttua (joka riippuu tulo- ja lähtövirtojen intensiteetistä) tämä prosessi sammuu ja järjestelmä siirtyy kiinteään, vakaaseen toimintatilaan, eivätkä todennäköisyysominaisuudet enää riipu ajasta.

Kiinteä toimintatila ja järjestelmän kuormituskerroin.

Jos todennäköisyys, että järjestelmä on tilassa E k, eli R k (t), ei riipu ajasta t, sitten he sanovat, että QS on vakiintunut paikallaan oleva tila työ. Samalla arvo
nimeltään järjestelmän kuormituskerroin(tai sovellusvirran vähentynyt tiheys). Sitten todennäköisyyksiin R 0 (t) ja R 1 (t) saamme seuraavat kaavat:
,
. Voit myös päätellä: mitä suurempi järjestelmän kuormituskerroin, sitä todennäköisemmin järjestelmä epäonnistuu (eli todennäköisyys, että järjestelmä on varattu).

Autopesulassa on yksi huoltoyksikkö. Autot saapuvat Poisson-jakaumaan nopeudella 5 autoa/tunti. Yhden auton keskimääräinen huoltoaika on 10 minuuttia. Selvitä todennäköisyys, että lähestyvä auto löytää järjestelmän varattuna, jos QS on paikallaan.

Ratkaisu. Tehtävän mukaan mm. l=5, m y =5/6. Meidän on löydettävä todennäköisyys R 1 on järjestelmävian todennäköisyys.
.

3.4.2 Yksikanavainen QS rajoittamattomalla jonon pituudella.

Otamme huomioon järjestelmät, jotka täyttävät vaatimukset: (Р/Е/1):(d/¥/¥). Järjestelmä voi olla jossakin tilassa E 0 , …, E k, … Analyysi osoittaa, että jonkin ajan kuluttua tällainen järjestelmä alkaa toimia kiinteässä tilassa, jos lähtövirran intensiteetti ylittää tulovirran intensiteetin (eli järjestelmän kuormituskerroin on pienempi kuin yksi). Kun tämä ehto otetaan huomioon, saadaan yhtälöjärjestelmä

ratkaisemaan, jonka löydämme sen. Siis sillä edellytyksellä y<1, получим
Lopuksi,
ja
on todennäköisyys, että QS on tilassa E k satunnaisena ajankohtana.

Järjestelmän keskimääräiset ominaisuudet.

Järjestelmässä olevien vaatimusten epätasaisesta vastaanotosta ja palveluajan vaihteluista johtuen järjestelmään muodostuu jono. Tällaista järjestelmää varten voit tutkia:

• n – vaatimusten määrä QS:ssä (jonossa ja käytössä);
• v – jonon pituus;
• w – palvelun alkamisen odotusaika;
• w 0 on järjestelmässä käytetty kokonaisaika.

Olemme kiinnostuneita keskimääräiset ominaisuudet(eli otamme matemaattiset odotukset tarkasteltaville satunnaismuuttujille ja muistamme sen y<1).

on järjestelmän sovellusten keskimääräinen määrä.

on jonon keskimääräinen pituus.

on keskimääräinen odotusaika palvelun alkamiseen, ts. odotusaika jonossa.

- keskimääräinen aika, jonka sovellus viettää järjestelmässä - jonossa ja palvelussa.

Autopesulassa on yksi kortteli huoltoa varten ja siellä on paikka jonolle. Autot saapuvat Poisson-jakaumaan nopeudella 5 autoa/tunti. Yhden auton keskimääräinen huoltoaika on 10 minuuttia. Etsi kaikki keskimääräiset QS-ominaisuudet.

Ratkaisu. l=5, m=60min/10min = 6. Kuormituskerroin y =5/6. Sitten keskimääräinen autojen lukumäärä järjestelmässä
, jonon keskimääräinen pituus
, keskimääräinen odotusaika palvelun alkamiseen
tuntia = 50 minuuttia ja lopuksi keskimääräinen järjestelmässä käytetty aika
tunnin.

3.4.3 Sekatyyppiset yksikanavaiset QS:t.

Oletetaan, että jonon pituus on m vaatimukset. Siis mille tahansa s£ m, todennäköisyys löytää QS tilasta E 1+ s, lasketaan kaavalla
, eli yksi hakemus käsitellään ja toinen s hakemukset ovat jonossa.

Järjestelmän seisokkien todennäköisyys on
,

ja järjestelmävian todennäköisyys on
.

Jokaiselle on annettu kolme yksikanavaista järjestelmää l=5, m =6. Mutta ensimmäisessä järjestelmässä on vikoja, toisessa pelkkää odottelua ja kolmannessa rajoitettu jonon pituus, m=2. Etsi ja vertaa näiden kolmen järjestelmän seisokkien todennäköisyyksiä.

Ratkaisu. Kaikille järjestelmille kuormituskerroin y=5/6. Järjestelmälle, jossa on vikoja
. Järjestelmälle, jolla on puhtaat odotukset
. Järjestelmälle, jossa on rajoitettu jonon pituus
. Johtopäätös on ilmeinen: mitä enemmän sovelluksia on jonossa, sitä pienempi on järjestelmän seisokkien todennäköisyys.

3.5 Monikanavainen QS.

3.5.1 Monikanavainen QS, jossa on vikoja.

Tarkastellaan järjestelmiä (Р/Е/s):(-/s/¥) sillä oletuksella, että palveluaika ei riipu tulovirrasta ja kaikki linjat toimivat itsenäisesti. Monikanavajärjestelmiä voidaan luonnehtia kuormituskertoimen lisäksi myös kertoimella
, missä s– palvelukanavien määrä. Tutkimalla monikanavaista QS:ää saamme seuraavat kaavat (Erlang-kaavat) todennäköisyydelle, että järjestelmä on tilassa E k satunnaiseen aikaan:

, k = 0, 1, …

kustannustoiminto.

Kuten yksikanavaisissa järjestelmissä, kuormituskertoimen kasvu lisää järjestelmän vian todennäköisyyttä. Toisaalta palvelulinjojen määrän kasvu johtaa järjestelmän tai yksittäisten kanavien seisokkien todennäköisyyden kasvuun. Siten on välttämätöntä löytää optimaalinen määrä palvelukanavia tälle QS:lle. Maksuttomien palvelulinjojen keskimääräinen lukumäärä löytyy kaavasta
. Esittelemme C( s) – kustannustoiminto QS riippuen Kanssa 1 – yhden epäämisen kustannukset (sakko hakemuksesta, jota ei ole täytetty) ja alkaen Kanssa 2 - yhden linjan seisokkien hinta aikayksikköä kohti.

Optimaalisen vaihtoehdon löytämiseksi sinun on löydettävä (ja tämä voidaan tehdä) kustannusfunktion vähimmäisarvo: FROM(s) = kanssa 1* l * s s +c 2*, jonka kaavio on esitetty kuvassa 3.3:

Kuva 3.3

Kustannusfunktion vähimmäisarvon haku on se, että löydämme sen arvot ensin s =1, sitten for s =2, sitten varten s =3 jne. kunnes jossain vaiheessa funktion arvo С( s) ei ole suurempi kuin edellinen. Tämä tarkoittaa, että toiminto on saavuttanut miniminsä ja alkanut kasvaa. Vastaus on palvelukanavien määrä (arvo s), jonka kustannusfunktio on minimaalinen.

ESIMERKKI .

Kuinka monella palvelurivillä tulee sisältää QS, jossa on vikoja, jos l\u003d 2 reb/tunti, m\u003d 1 reb / ​​tunti, sakko jokaisesta viasta on 7 tuhatta ruplaa, yhden linjan seisokkien hinta on 2 tuhatta ruplaa. tunnissa?

Ratkaisu. y = 2/1=2. Kanssa 1 =7, Kanssa 2 =2.

Oletetaan, että QS:llä on kaksi palvelukanavaa, ts. s =2. Sitten
. Näin ollen C(2) = c 1 *l*s 2 +c 2 *(2- y*(1-s 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Teeskennetäänpä sitä s =3. Sitten
, C(3) = c 1 *l*s 3 +c 2 *
=5.79.

Oletetaan, että kanavaa on neljä, ts. s =4. Sitten
,
, C(4) = c 1 *l*s 4 +c 2 *
=5.71.

Oletetaan, että QS:llä on viisi palvelukanavaa, ts. s =5. Sitten
, C(5) = 6,7 - enemmän kuin edellinen arvo. Siksi optimaalinen palvelukanavien lukumäärä on neljä.

3.5.2 Monikanavainen QS jonolla.

Tarkastellaan järjestelmiä (Р/Е/s):(d/d+s/¥) sillä oletuksella, että palveluaika ei riipu tulovirrasta ja kaikki linjat toimivat itsenäisesti. Sanomme, että järjestelmä on asennettu kiinteä toiminta, jos saapuvien reklamaatioiden keskimäärä on pienempi kuin järjestelmän kaikilla linjoilla käsiteltyjen korvausten keskimääräinen määrä, ts. l

P(w>0) on todennäköisyys odottaa palvelun alkamista,
.

Viimeinen ominaisuus mahdollistaa palvelukanavien optimaalisen lukumäärän määrittämisongelman ratkaisemisen siten, että todennäköisyys odottaa palvelun alkamista on pienempi kuin tietty määrä. Tätä varten riittää, kun lasketaan odotustodennäköisyys peräkkäin s =1, s =2, s=3 jne.

ESIMERKKI .

SMO - pienen mikropiirin ambulanssiasema. l= 3 puhelua tunnissa ja m= 4 puhelua tunnissa yhdelle joukkueelle. Kuinka monta miehistöä pitää olla asemalla, jotta ulostulon odottamisen todennäköisyys on pienempi kuin 0,01?

Ratkaisu. Järjestelmän kuormituskerroin y =0,75. Oletetaan, että käytettävissä on kaksi joukkuetta. Selvitetään todennäköisyys odottaa palvelun alkamista klo s =2.
,
.

Oletetaan, että on kolme prikaatia, ts. s=3. Kaavojen mukaan saamme sen R 0 =8/17, P(w>0)=0.04>0.01 .

Oletetaan, että asemalla on neljä miehistöä, ts. s=4. Sitten saamme sen R 0 =416/881, P(w>0)=0.0077<0.01 . Siksi asemalla pitäisi olla neljä prikaatia.

3.6 Itsehillintäkysymyksiä

1. Jonoteorian aihe ja tehtävät.
2. QS, niiden mallit ja nimitykset.
3. Vaatimukset syöttövirta. Syöttövirran intensiteetti.
4. Järjestelmän tila. Siirtymien matriisi ja graafi.
5. Yksikanavainen QS, jossa on vikoja.
6. Yksikanavainen QS jonolla. Ominaisuudet.
7. Kiinteä toimintatila. Järjestelmän kuormituskerroin.
8. Monikanavainen QS vioilla.
9. Kustannusfunktion optimointi.
10. Monikanavainen QS jonolla. Ominaisuudet.

3.7 Harjoitukset itsenäiseen työskentelyyn

1. Huoltoaseman välipalabaarissa on yksi tiski. Autot saapuvat Poisson-jakauman mukaan, keskimäärin 2 autoa 5 minuutissa. Keskimäärin 1,5 minuuttia riittää tilauksen tekemiseen, vaikka palvelun kesto jakaantuu eksponentiaalisen lain mukaan. Selvitä: a) todennäköisyys, että pysähtyminen on tyhjäkäynnillä; b) keskimääräinen suorituskyky; c) todennäköisyys, että saapuvien autojen määrä on vähintään 10.
2. Röntgenlaitteen avulla voit tutkia keskimäärin 7 henkilöä tunnissa. Vierailijaintensiteetti on 5 henkilöä tunnissa. Olettaen, että toiminta on paikallaan, määritä keskimääräiset ominaisuudet.
3. Palveluaika QS:ssä noudattaa eksponentiaalista lakia,
   m = 7 vaatimusta tunnissa. Laske todennäköisyys, että a) palveluaika on 3 - 30 minuuttia; b) vaatimus annetaan tiedoksi tunnin kuluessa. Käytä funktion arvotaulukkoa e X .
4. Jokisatamassa on yksi laituripaikka, sisääntulovirran intensiteetti on 5 alusta päivässä. Lastaus- ja purkuoperaatioiden intensiteetti on 6 alusta päivässä. Pidä mielessä kiinteä toimintatila, määritä kaikki järjestelmän keskimääräiset ominaisuudet.
5. l=3, m=2, sakko jokaisesta viasta on 5 ja seisokkikustannus linjaa kohti on 2?
6. Mikä on optimaalinen palvelukanavien määrä, jonka QS:llä pitäisi olla, jos? l=3, m =1, sakko jokaisesta viasta on 7 ja seisokkikustannus linjaa kohti on 3?
7. Mikä on optimaalinen palvelukanavien määrä, jonka QS:llä pitäisi olla, jos? l=4, m=2, sakko jokaisesta viasta on 5 ja seisokkikustannus linjaa kohti on 1?
8. Määritä lentokoneiden kiitoteiden lukumäärä edellyttäen, että odotustodennäköisyys on pienempi kuin 0,05. Samaan aikaan syöttövirran intensiteetti on 27 lentokonetta vuorokaudessa ja niiden palvelun intensiteetti 30 lentokonetta vuorokaudessa.
9. Kuinka monta vastaavaa itsenäistä kuljetinlinjoja työpajalla tulee olla varmistaakseen työrytmin, jossa tuotteiden käsittelyn odottamisen todennäköisyyden tulee olla alle 0,03 (jokaista tuotetta valmistetaan yhdellä linjalla). Tiedetään, että tilausten vastaanottointensiteetti on 30 tuotetta tunnissa ja tuotteen käsittelyn intensiteetti yhdellä rivillä on 36 tuotetta tunnissa.
10. Jatkuva satunnaismuuttuja X jaetaan eksponentiaalisen lain mukaan parametrilla l=5. Etsi jakaumafunktio, ominaisuudet ja todennäköisyys osua r.v. X välillä 0,17 - 0,28.
11. Keskimääräinen puhelinvaihteeseen saapuvien puhelujen määrä minuutissa on 3. Olettaen, että virta on Poisson, lasketaan todennäköisyys, että 2 minuutin kuluttua tulee: a) kaksi puhelua; b) vähemmän kuin kaksi puhelua; c) vähintään kaksi puhelua.
12. Laatikossa on 17 osaa, joista 4 on viallisia. Kokoaja arpaa 5 kappaletta satunnaisesti. Laske todennäköisyys, että a) kaikki irrotetut osat ovat korkealaatuisia; b) irrotettujen osien joukossa 3 viallista.
13. Kuinka monta kanavaa vikaantuneessa QS:ssä pitäisi olla jos l\u003d 2 reb/tunti, m\u003d 1 reb / ​​tunti, sakko jokaisesta viasta on 8 tuhatta ruplaa, yhden linjan seisokkien hinta on 2 tuhatta ruplaa. tunnissa?

Tehtävä 1. Lähetyskonsoli vastaanottaa pyyntövirran, joka on toisen asteen Erlang-kulku. Levitysvirran intensiteetti on 6 levitystä tunnissa. Jos lähettäjä poistuu konsolista satunnaisella hetkellä, hänen on palattava konsoliin ensimmäisellä seuraavalla pyynnöstä. Etsi seuraavan pyynnön odotusajan jakautumistiheys ja piirrä sen kaavio. Laske todennäköisyys, että lähettäjä voi olla poissa 10-20 minuuttia. Ratkaisu. Koska toisen asteen Erlang-virtaus on kiinteä virtaus, jolla on rajoitettu jälkivaikutus, niin Palm-kaava pätee siihen

missä f1(θ)- ensimmäisen lähimmän tapahtuman odotusajan todennäköisyysjakauman tiheys;
λ - virtauksen intensiteetti;
- virtausjärjestys;
(θ) on todennäköisyysjakaumafunktio ajalle, joka on kahden vierekkäisen tapahtuman välillä Erlangin järjestyksessä (E).
Tiedetään, että virtauksen E jakautumisfunktiolla on muoto

. (2)

Tehtävän ehtojen mukaan sovellusten kulku on Erlang, kertaluokkaa =2. Sitten (1) ja (2) saamme
.
Viimeisestä suhteesta λ=6 saamme

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

Piirretään funktio f1(θ) . klo θ <0 meillä on f1(θ) =0 . klo θ =0 , f1(0)=3. Harkitse rajaa

Tyypin epäselvyyden paljastamisen rajaa laskettaessa käytettiin L'Hopital-sääntöä. Tutkimuksen tulosten perusteella rakennamme funktiosta graafin f1(θ) (Kuva 1).

Kiinnitetään huomiota tehtävän tekstin ajan mittasuhteisiin: intensiteetille nämä ovat sovelluksia tunnissa, ajalla, minuutteissa. Siirrytään yhteen aikayksikköön: 10 minuuttia = 1/6 tuntia, 20 minuuttia = 1/3 tuntia. Näille arvoille voidaan laskea f1(θ) ja tarkentaa käyrän luonnetta

Nämä ordinaatit on esitetty kaaviossa vastaavien käyräpisteiden yläpuolella.
Todennäköisyysteorian aikana tiedetään, että todennäköisyys osua satunnaismuuttujaan X segmenttiin [α, β] on numeerisesti yhtä suuri kuin todennäköisyystiheyskäyrän alla oleva pinta-ala f(x). Tämä alue ilmaistaan ​​määrätyllä integraalilla

Siksi haluttu todennäköisyys on yhtä suuri kuin

Tämä integraali voidaan helposti laskea osittain, jos laitamme
U=1+6θ ja dV = e-69dθ. Sitten dU=6dθ ja V= .
Käyttämällä kaavaa saamme

Vastaus: todennäköisyys, että lähettäjä voi olla poissa 10-20 minuuttia, on 0,28.

Tehtävä 2. Näyttelyhuoneessa on 5 näyttöä. Käyttäjävirta on yksinkertaisin. Esittelysalissa vierailee keskimäärin 140 käyttäjää päivässä. Yhden käyttäjän tietojen käsittelyaika yhdellä näytöllä jakautuu eksponentiaalisen lain mukaan ja on keskimäärin 40 minuuttia. Selvitä, onko hallilla paikallaan oleva toimintatila; todennäköisyys, että käyttäjä löytää kaikki näytöt varattuina; käyttäjien keskimääräinen määrä esittelytilassa; jonossa olevien käyttäjien keskimääräinen määrä; keskimääräinen tyhjäkäynnin näyttöaika; käyttäjän keskimääräinen näyttöhuoneessa viettämä aika. Ratkaisu. Tehtävässä tarkasteltu QS kuuluu monikanavaisten järjestelmien luokkaan, joissa on rajoittamaton jono. Kanavien määrä =5. Selvitetään pyyntövirran λ-intensiteetti: missä (tuntia) - saapuvan käyttäjävirran keskimääräinen aika kahden peräkkäisen sovelluksen välillä. Sitten käyttäjä/tunti

Selvitetään - palveluvirran intensiteetti: , jossa M[T service]=40 min=0,67 tuntia – keskimääräinen palveluaika yhdelle käyttäjälle yhdellä näytöllä,

sitten käyttäjä/tunti

Siten tämän järjestelmän luokitin on muotoa CMO (5, ∞; 5,85; 1,49).
Laske QS-kuormituskerroin . Tiedetään, että tämän luokan QS:llä on paikallaan pysyvä tila, jos järjestelmän kuormituskertoimen suhde kanavien lukumäärään on pienempi kuin yksi. Tämän suhteen löytäminen
.
Siksi kiinteä järjestelmä on olemassa. Rajatilan todennäköisyysjakauma lasketaan kaavoilla

Koska =5, meillä on

Lasketaan P* - todennäköisyys, että käyttäjä löytää kaikki näytöt varattuina. Ilmeisesti se on yhtä suuri kuin tällaisten tapahtumien todennäköisyyksien summa: kaikki näytöt ovat varattuja, jonoa ei ole (p5); kaikki näytöt varattu, yksi käyttäjä jonossa (p6); kaikki näytöt ovat varattuja, kaksi käyttäjää on jonossa (p7) ja niin edelleen. Koska kokonaiselle tapahtumaryhmälle näiden tapahtumien todennäköisyyksien summa on yhtä suuri kuin yksi, niin yhtälö

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

Etsitään nämä todennäköisyydet: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Ottamalla yhteisen tekijän suluista saamme
P*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Käytätkö kaavoja suoritusindikaattoreiden laskemiseen? löytö:

• 1. jonossa olevien käyttäjien keskimääräinen määrä

2. käyttäjien keskimääräinen määrä esittelytilassa

3. Keskimääräinen ilmaisen näytön odotusaika

4. keskimääräinen aika, jonka käyttäjä viettää esittelytilassa

Vastaus: näyttöhuoneen kiinteä toimintatila on olemassa ja sille on tunnusomaista seuraavat indikaattorit R*= 0,54; käyttäjä; käyttäjä; ; .

Tehtävä 3. Pysyvä Poisson-pyyntövirta saapuu kaksikanavaiseen jonojärjestelmään (QS) virheineen. Kahden peräkkäisen pyynnön saapumisaika jaetaan eksponentiaalisen lain mukaan parametrilla λ=5 pyyntöä minuutissa. Jokaisen pyynnön huollon kesto on 0,5 min. Etsi Monte Carlo -menetelmällä keskimääräinen huollettujen pyyntöjen määrä 4 minuutin ajalta. Vihje: tee kolme testiä. Ratkaisu. Kuvataan tietyn QS:n toiminnan tilastollinen mallinnus aikakaavioiden avulla. Otetaan käyttöön seuraava aika-akseleiden merkintä:
Vx- saapuva sovellusvirta täällä ti- hakemusten vastaanottohetki; Ti- kahden peräkkäisen sovelluksen väliset aikavälit. Se on selvää ti=ti-1 +Ti.
K1 - ensimmäinen palvelukanava;
K2-toinen palvelukanava; tässä aika-akselin paksut viivat edustavat kanavan varattuja aikavälejä. Jos molemmat kanavat ovat vapaita, pyyntö palvellaan kanavalla K1, jos se on varattu, pyyntö palvelee kanavaa K2.
Jos molemmat kanavat ovat varattuja, pyyntö jättää QS:n palvelematta.
Out OB - lähtevä huollettujen pyyntöjen virta.
Out PT on QS-vioista johtuvien kadonneiden pyyntöjen lähtevä virta (molemmat kanavat ovat varattuja).
Tilastollinen testaus jatkuu tietyn ajan. Ilmeisesti kaikki ylityöt tmax edellyttää pyynnön pudottamista lähtevään streamiin Out PT. Joten kuvassa 3 hakemus nro 10, joka tuli järjestelmään tuolloin t10, ei ole aikaa tarjoilla tähän hetkeen asti tmax, koska t10+Tmont.>tmax. Siksi ilmainen kanava K1 ei hyväksy sitä palveluun, ja se palautetaan Out PT:hen, jolloin se vastaanottaa kieltäytymisen.

Riisi. 3

Ajoituskaavioista voidaan nähdä, että intervallien mallintaminen on välttämätöntä Ti. Käytämme käänteisfunktioiden menetelmää. Koska satunnaismuuttuja Ti jaetaan eksponentiaalisen lain mukaan parametrin kanssa λ =5, silloin jakautumistiheydellä on muoto f(τ) = 5е-5τ. Sitten arvo F(Ti) todennäköisyysjakaumafunktion määrittää integraali

.

Tiedetään, että jakelufunktion alue F(T) on leikkaus. Valitsemme luvun satunnaislukutaulukosta ja määritämme Ti tasa-arvosta, mistä. Kuitenkin, jos. Siksi voit saada toteutukset välittömästi satunnaislukutaulukosta. Näin ollen
e-5Ti= ri, tai -5Ti= lnri, missä . On kätevää syöttää laskelmien tulokset taulukkoon.
Testiä nro 1 varten satunnaisluvut otettiin liitteestä 2 alkaen ensimmäisen rivin ensimmäisestä numerosta. Lisänäytteenotto suoritettiin riveittäin. Tehdään vielä kaksi testiä.
Kiinnitä huomiota satunnaislukujen valintaan liitteen 2 taulukosta, jos testissä nro 1 viimeinen satunnaisluku hakemukselle nro 16 oli 0,37 (ensimmäinen satunnaisluku toisella rivillä), niin testi nro 2 alkaa seuraava satunnaisluku 0,54 . Koe 2 sisältää viimeisen satunnaisluvun 0,53 (viides numero kolmannella rivillä). Siksi kolmas testi alkaa numerolla 0.19. Yleensä yhden testisarjan sisällä valitaan satunnaiset luvut taulukosta ilman aukkoja ja lisäyksiä tietyssä järjestyksessä, esimerkiksi riveissä.

Taulukko 1. TESTI #1

Hakemus nro i	Sl. määrä ri		-In ri Ti	Hakemuksen vastaanottohetki ti=ti-1+Ti	Palveluajan päättyminen. ti+0,50		Sovelluslaskuri
					K1

Taulukko 2 TESTI #2

Hakemus nro i	Sl. määrä ri		-In ri Ti	Hakemuksen vastaanottohetki ti=ti-1+Ti	Palveluajan päättyminen. ti+0,50		Sovelluslaskuri

Taulukko #3 TESTI #3

Hakemus nro i		Sl. määrä ri		-In ri Ti	Hakemuksen vastaanottohetki ti=ti-1+Ti	Palveluajan päättyminen. ti+0,50		Sovelluslaskuri
						K1

Siten kolmen testin tulosten mukaan huollettujen sovellusten määrä oli vastaavasti: x1=9, x2=9, x3=8. Etsi huollettujen pyyntöjen keskimääräinen määrä:

Vastaus: QS:n keskimääräinen hakemusten määrä neljässä minuutissa on 8,6(6).

Yksinkertaisin käytännön tehtävien kulku ja soveltaminen.

Ei-kiinteät Poisson-virtaukset.

Virtaa rajoitetuilla seurauksilla (Palma virtaa).

Palautusvirrat.

1. Esittely.

1.1. Historiallinen viittaus.

Useimmat järjestelmät, joiden kanssa ihminen käsittelee, ovat stokastisia. Yritys kuvata niitä matemaattisesti determinististen mallien avulla johtaa todellisen asioiden karkenemiseen. Tällaisten järjestelmien analyysi- ja suunnitteluongelmia ratkaistaessa on otettava huomioon asioiden tila milloin satunnaisuus on ratkaiseva järjestelmissä tapahtuville prosesseille. Samaan aikaan satunnaisuuden laiminlyönti, yritys "puristaa" lueteltujen ongelmien ratkaisu deterministiseen kehykseen johtaa vääristymiin, virheisiin päätelmissä ja käytännön suosituksissa.

Kööpenhaminan puhelinyhtiön työntekijä, tanskalainen tiedemies A.K., pohti jonojärjestelmien teorian (TSMO) ensimmäisiä ongelmia. Erlang (1878-1929) vuosina 1908-1922. Näitä tehtäviä elävöitti halu tehostaa puhelinverkon toimintaa ja kehittää menetelmiä asiakaspalvelun laadun parantamiseksi etukäteen riippuen käytettyjen laitteiden määrästä. Kävi ilmi, että puhelinkeskuksissa syntyvät tilanteet eivät ole tyypillisiä vain puhelinviestinnälle. Lentokenttien, meri- ja jokisatamien, myymälöiden, terminaaliluokkien, elektronisten laskentajärjestelmien, tutka-asemien jne. voidaan kuvata TSMO:lla.

1.2. Esimerkkejä jonojärjestelmistä. TSMO-tehtävien analyysi.

Esimerkki 1 Erlangin puhelinliikenne oli puhelinkeskus, johon liittyi suuri määrä tilaajia. Aseman puhelinoperaattorit yhdistivät puhelinnumerot toisiinsa, kun puheluja saapui.

Tehtävä: Kuinka monta puhelinoperaattoria (olettaen, että he ovat täysin työllisiä) tulee työskennellä asemalla, jotta korvausmenojen menetys olisi mahdollisimman pieni.

Esimerkki 2 Tietyn kaupunkialueen ambulanssijärjestelmä koostuu pisteestä (joka ottaa vastaan ​​täyttöpyynnöt), useista ambulansseista ja useista lääkintäryhmistä.

Tavoite: Määrittää lääkäreiden, tukihenkilöstön ja ajoneuvojen määrä siten, että puhelun odotusaika on potilaille optimaalinen, minimoiden samalla järjestelmän käyttökustannukset ja maksimoimalla palvelun laadun.

Esimerkki 3 Tärkeä tehtävä on tavaroiden meri- ja jokikuljetusten järjestäminen. Tässä suhteessa laivojen ja satamarakenteiden optimaalinen käyttö on erityisen tärkeää.

Tavoite: Tarjota tietty määrä liikennettä pienin kustannuksin. Samalla vähentää alusten seisokkeja lastaus- ja purkuoperaatioiden aikana.

Esimerkki 4 Tietojenkäsittelyjärjestelmä sisältää multipleksikanavan ja useita tietokoneita. Antureiden signaalit lähetetään multipleksikanavalle, jossa ne puskuroidaan ja esikäsitellään. Sitten he tulevat tietokoneeseen, jossa jono on minimaalinen.

Tehtävä: Varmistaa signaalinkäsittelyn kiihtyvyys annetulla jonon kokonaispituudella.

Esimerkki 5. Kuvassa 1.1. lohkokaavio tyypillisestä jonojärjestelmästä - korjausyritys (esimerkiksi PC:n korjaamiseksi) näytetään. Sen toimintajärjestys on selkeä kaaviosta, eikä se vaadi selvennystä.

kuva 1.1.

Ei ole vaikeaa mainita monia muita esimerkkejä eri toimialoista.

Tyypillisiä tällaisille tehtäville ovat:

1. "kaksinkertaisen" satunnaisuuden ehdot -

• huoltotilauksen vastaanottohetki on satunnainen (puhelinkeskuksessa, ambulanssiasemalla, prosessorin sisääntulossa aluksen saapumishetki lastaukseen jne. on satunnainen);
• palveluajan pituus on satunnainen.

2) aikamme vitsauksen ongelma - jonot: laivat lukkojen edessä, autot tiskien edessä, tehtävät tietokonekompleksin prosessorien sisääntulossa jne.

A.K. Erlang kiinnitti huomiota siihen, että QS voidaan jakaa kahteen tyyppiin, nimittäin: järjestelmät, joissa on odotuksia ja järjestelmiä, joissa on häviöitä. Ensimmäisessä tapauksessa järjestelmän sisääntuloon saatu pyyntö "odottelee" suoritusjonoa, toisessa se hylätään, koska palvelukanava on varattu ja kadonnut QS:lle.

Tulevaisuudessa näemme, että klassisiin Erlang-ongelmiin lisätään uusia ongelmia:

Todelliset järjestelmät, joita on käsiteltävä käytännössä, ovat pääsääntöisesti erittäin monimutkaisia ​​ja sisältävät useita ylläpitovaiheita (vaiheita) (kuva 1.1.). Lisäksi jokaisessa vaiheessa saattaa esiintyä epäonnistumisen mahdollisuus suoritukseen tai on olemassa tilanne, jossa palvelu on etusijalla suhteessa muihin vaatimuksiin. Tässä tapauksessa yksittäiset palvelulinkit voivat keskeyttää toimintansa (korjausta, säätöä jne. varten) tai lisävaroja voidaan liittää. Saattaa olla tilanteita, joissa hylätyt pyynnöt tuodaan uudelleen järjestelmään (tätä voi tapahtua tietojärjestelmissä).

1.3. Käsitteet, määritelmät, terminologia.

Kaikilla QS:illä on hyvin määritelty rakenne, joka näkyy kuvassa 1.2

kuva 1.2

Määritelmät, termit

• Virta on tapahtumasarja. Palvelupyyntöjen virtaa kutsutaan kysyntävirraksi.
• Palvelujärjestelmään tulevien pyyntöjen virtaa kutsutaan saapuvaksi virtaukseksi.
• Palveltujen pyyntöjen virtaa kutsutaan lähteväksi virraksi.
• Jonojen ja palvelulaitteiden (kanavien) joukkoa kutsutaan palvelujärjestelmäksi.
• Jokainen pyyntö saapuu omalle kanavalleen, jossa se käy läpi palveluoperaation.
• Jokaisella CMO:lla on tietyt säännöt jonotusta ja sääntöjä tai palvelukuria varten.

1.4. Yhteisen markkinajärjestelyn luokittelu.

1.4.1. Vaatimuslähteen luonteen mukaan erotetaan QS:t, joissa on äärellinen ja ääretön määrä vaatimuksia sisääntulossa.

Ensimmäisessä tapauksessa järjestelmässä kiertää äärellinen, yleensä vakio määrä vaatimuksia, jotka palvelun valmistuttua palaavat lähteeseen.

Toisessa tapauksessa lähde tuottaa äärettömän määrän pyyntöjä.

Esimerkki 1 Korjaamo, jossa on vakiomäärä koneita tai tietty määrä pääteluokassa olevia PC:itä, jotka vaativat jatkuvaa ennakoivaa tarkastusta ja korjausta.

Esimerkki 2. Internet-verkko, jolla on loputon kysyntä sisäänkäynnillä, missä tahansa kaupassa, kampaajassa jne.

Ensimmäistä tyyppiä QS kutsutaan suljetuksi, toista - avoimeksi.

SMO erottaa:

1.4.2. Palvelukuri:

1. palvelu saapumisjärjestyksessä;
2. palvelu satunnaisessa järjestyksessä (tietyn jakelulain mukaisesti);
3. ensisijainen palvelu.

1.4.3. organisaation luonteen mukaan:

1. epäonnistumisten kanssa;
2. odotusten kanssa;
3. rajoitetulla odotuksella.

Ensimmäisessä tapauksessa pyyntö hylätään, kun kanava on varattu. Toisessa tapauksessa se asetetaan jonoon ja odottaa kanavan vapauttamista. Kolmannessa tapauksessa otetaan käyttöön odotusajan rajoituksia.

1.4.4. Palveluyksiköiden lukumäärän mukaan:

1. yksikanavainen;
2. kaksikanavainen;
3. monikanavainen.

1.4.5. Palvelun vaiheiden (vaiheiden) lukumäärän mukaan - yksi- ja monivaiheisille. (Mikä tahansa tuotantolinja voi toimia esimerkkinä monivaiheisesta QS:stä).

1.4.6. Kanavan ominaisuudet: homogeenisiksi, kun kanavilla on samat ominaisuudet, ja heterogeenisiksi muutoin.

Sitä tarvitaan tehtävien 1-3 ratkaisemiseen. Alkutiedot on esitetty taulukossa. 2-4.

Joitakin merkintöjä, joita käytetään jonoteoriassa kaavoille:

n on kanavien lukumäärä QS:ssä;

λ - saapuvan sovellusvirran P in intensiteetti;

v - lähtevän sovellusvirran P out intensiteetti;

μ - palveluvirran P noin intensiteetti;

ρ - järjestelmän kuormituksen ilmaisin (liikenne);

m - jonon paikkojen enimmäismäärä rajoittaen hakemusjonon pituutta;

i - sovelluslähteiden lukumäärä;

p to - järjestelmän k:nnen tilan todennäköisyys;

p noin - koko järjestelmän joutoajan todennäköisyys, ts. todennäköisyys, että kaikki kanavat ovat vapaita;

p syst - hakemuksen hyväksymisen todennäköisyys järjestelmässä;

p otk - hakemuksen hylkäämisen todennäköisyys sen hyväksyessä järjestelmään;

p noin - todennäköisyys, että hakemus toimitetaan;

A on järjestelmän absoluuttinen suorituskyky;

Q on järjestelmän suhteellinen suorituskyky;

och - jonossa olevien sovellusten keskimääräinen lukumäärä;

o - käytössä olevien hakemusten keskimääräinen määrä;

syst - järjestelmän sovellusten keskimääräinen lukumäärä;

pt - hakemuksen keskimääräinen odotusaika jonossa;

o - hakemuksen keskimääräinen tiedoksiantoaika, joka koskee vain käsiteltyjä pyyntöjä;

sys - sovelluksen keskimääräinen viipymisaika järjestelmässä;

exp - keskimääräinen aika, joka rajoittaa hakemuksen odottamista jonossa;

Keskimääräinen varattujen kanavien määrä.

QS A:n absoluuttinen suorituskyky on sovellusten keskimääräinen määrä, jonka järjestelmä voi palvella aikayksikköä kohti.

Suhteellinen QS-läpäisykyky Q on järjestelmän keskimääräisen palvelemien sovellusten lukumäärän aikayksikköä kohti suhde tänä aikana vastaanotettujen sovellusten keskimääräiseen määrään.

Jonoongelmia ratkaistaessa on noudatettava seuraavaa järjestystä:

1) QS-tyypin määrittäminen taulukon mukaan. 4,1;

2) kaavojen valinta QS-tyypin mukaan;

3) ongelmanratkaisu;

4) johtopäätösten muotoilu ongelmasta.

1. Kuoleman ja lisääntymisen kaavio.

Tiedämme, että nimetyn tilagraafin avulla voimme helposti kirjoittaa Kolmogorov-yhtälöitä tilatodennäköisyyksiä varten sekä kirjoittaa ja ratkaista algebrallisia yhtälöitä lopullisille todennäköisyyksille. Joissakin tapauksissa on mahdollista ratkaista viimeiset yhtälöt etukäteen kirjaimellisessa muodossa. Tämä voidaan tehdä erityisesti, jos järjestelmän tilakaavio on ns. "kuolema- ja lisääntymiskaavio".

Kuoleman ja lisääntymisen kaavion tilakaavio on kuvan 2 mukaisessa muodossa. 19.1. Tämän graafin erikoisuus on, että kaikki järjestelmän tilat voidaan vetää yhdeksi ketjuksi, jossa jokainen keskimääräinen tila ( S 1 , S 2 , …, S n-1) on yhdistetty eteen- ja taaksepäin osoittavalla nuolella jokaiseen naapuritilaan - oikeaan ja vasempaan sekä ääritiloihin (S 0 , S n) — vain yhden naapurivaltion kanssa. Termi "kuoleman ja lisääntymisen suunnitelma" juontaa juurensa biologisista ongelmista, joissa populaation koon muutosta kuvataan tällaisella kaavalla.

Kuoleman ja lisääntymisen järjestelmä kohdataan hyvin usein erilaisissa käytännön ongelmissa, erityisesti - jonoteoriassa, joten on hyödyllistä kerta kaikkiaan löytää tilojen lopulliset todennäköisyydet sille.

Oletetaan, että kaikki tapahtumavirrat, jotka siirtävät järjestelmää kaavion nuolia pitkin, ovat yksinkertaisimpia (lyhyyden vuoksi kutsumme myös järjestelmää S ja siinä tapahtuva prosessi ovat yksinkertaisimmat).

Käyttämällä kuvion kaaviota. 19.1, muodostamme ja ratkaisemme algebrallisia yhtälöitä tilan lopullisille todennäköisyyksille), olemassaolo seuraa siitä, että jokaisesta tilasta voi mennä joka toiseen, tilojen määrä on äärellinen).

Ensimmäiselle osavaltiolle S 0 meillä on:

(19.1)

Toiselle osavaltiolle S1:

Johtuen (19.1) viimeinen yhtälö pelkistyy muotoon

missä k ottaa kaikki arvot 0:sta P. Lopulliset todennäköisyydet siis p0, p1,..., p n täyttävät yhtälöt

(19.2)

lisäksi meidän on otettava huomioon normalisointiehto

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

Ratkaistaan ​​tämä yhtälöjärjestelmä. Ensimmäisestä yhtälöstä (19.2) ilmaisemme s 1 kautta R 0 :

s 1 = s 0. (19.4)

Toisesta, ottaen huomioon (19.4), saamme:

(19.5)

kolmannesta, kun otetaan huomioon (19.5),

(19.6)

ja yleensä mille tahansa k(1 - n):

(19.7)

Kiinnitetään huomiota kaavaan (19.7). Osoittaja on kaikkien vasemmalta oikealle johtavien nuolien intensiteetit (alusta tiettyyn tilaan S k), ja nimittäjä on kaikkien oikealta vasemmalle johtavien nuolien intensiteettien tulo (alusta Sk).

Eli kaikki tilatodennäköisyydet R 0 , s 1 , ..., р n ilmaistaan ​​yhden heistä ( R 0). Korvataan nämä lausekkeet normalisointiehtoon (19.3). Saamme sulkeiden avulla R 0:

tästä syystä saamme ilmaisun for R 0 :

(nostimme sulkeet potenssiin -1, jotta emme kirjoita kaksikerroksisia murtolukuja). Kaikki muut todennäköisyydet ilmaistaan R 0 (katso kaavat (19.4)-(19.7)). Huomaa, että kertoimet for R 0 kussakin niistä ei ole muuta kuin sarjan peräkkäisiä jäseniä kaavan (19.8) yksikön jälkeen. Joten lasketaan R 0 , olemme jo löytäneet kaikki nämä kertoimet.

Saadut kaavat ovat erittäin hyödyllisiä jonoteorian yksinkertaisimpien ongelmien ratkaisemisessa.

2. Pieni kaava.

Nyt johdetaan yksi tärkeä kaava, joka liittyy (rajoittavaan, kiinteään järjestelmään) sovellusten keskimääräiseen määrään L syst, joka sijaitsee jonojärjestelmässä (eli palvellaan tai seisoo jonossa) ja sovelluksen keskimääräinen viipymäaika järjestelmässä W syst.

Tarkastellaan mitä tahansa QS:tä (yksikanavainen, monikanavainen, markolainen, ei-markolainen, rajoittamattomalla tai rajoitetulla jonolla) ja kaksi siihen liittyvää tapahtumavirtaa: QS:ään saapuvien asiakkaiden virta ja sieltä poistuvien asiakkaiden virta. QS. Jos järjestelmään on muodostettu rajoittava, stationäärinen järjestelmä, niin QS:ään saapuvien sovellusten keskimäärä aikayksikköä kohti on yhtä suuri kuin sieltä lähtevien sovellusten keskimääräinen määrä: molemmilla virroilla on sama intensiteetti λ.

Merkitse: X(t) — hakemusten määrä, jotka saapuivat yhteiseen markkinajärjestelyyn ennen tätä hetkeä t. Y(t) — yhteisestä markkinajärjestelystä lähteneiden hakemusten määrä

hetkeen asti t. Molemmat toiminnot ovat satunnaisia ​​ja muuttuvat äkillisesti (nousevat yhdellä) pyyntöjen saapuessa (X(t)) ja hakemusten lähdöt (Y(t)). Toimintojen tyyppi X(t) ja Y(t) esitetty kuvassa. 19,2; molemmat rivit ovat porrastettuja, ylempi on X(t), alempi- Y(t). Ilmeisesti hetkeksi tahansa t niiden ero Z(t)= X(t) - Y(t) on vain QS-sovellusten määrä. Kun linjat X(t) ja K(t) yhdistä, järjestelmässä ei ole pyyntöjä.

Harkitse hyvin pitkää ajanjaksoa T(jatkamalla kaaviota mielessään paljon piirustuksen jälkeen) ja laskea sille QS:n sovellusten keskimääräinen määrä. Se on yhtä suuri kuin funktion integraali Z(t) tällä aikavälillä jaettuna välin pituudella T:

L syst. = . (19.9) o

Mutta tämä integraali ei ole mitään muuta kuin kuvassa 1 varjostetun kuvan alue. 19.2. Katsotaanpa tätä piirrosta hyvin. Kuvio koostuu suorakulmioista, joiden jokaisen korkeus on yhtä ja kanta, joka vastaa viipymisaikaa vastaavan järjestyksen järjestelmässä (ensimmäinen, toinen jne.). Merkitään nämä ajat t1, t2,... Totta, väliajan lopussa T jotkut suorakulmiot tulevat varjostettuun kuvioon ei kokonaan, vaan osittain, mutta riittävän suurella T näillä pienillä asioilla ei ole väliä.

(19.10)

jossa määrä koskee kaikkia kyseisenä aikana vastaanotettuja hakemuksia T.

Jaa oikea ja vasen puoli (.19.10) välin pituudella T. Saamme, ottaen huomioon (19.9),

L syst. = . (19.11)

Jaamme ja kerromme (19.11):n oikean puolen intensiteetillä X:

L syst. = .

Mutta suuruus Tλ on vain kyseisenä aikana vastaanotettujen hakemusten keskimääräinen määrä ^ T. Jos jaamme kaikkien aikojen summan t i hakemusten keskimääräisestä määrästä, niin saamme sovelluksen keskimääräisen viipymisajan järjestelmässä W syst. Niin,

L syst. = λ W syst. ,

W syst. = . (19.12)

Tämä on Littlen upea kaava: mille tahansa QS:lle, minkä tahansa tyyppiselle sovellusvirralle, mille tahansa palveluajan jakautumiselle, mille tahansa palvelualalle pyynnön keskimääräinen viipymäaika järjestelmässä on yhtä suuri kuin järjestelmässä olevien pyyntöjen keskimääräinen lukumäärä jaettuna pyyntövirran intensiteetillä.

Täsmälleen samalla tavalla johdetaan Littlen toinen kaava, joka kertoo keskimääräisen ajan, jonka sovellus viettää jonossa ^ Oho ja jonossa olevien hakemusten keskimääräinen määrä L oho:

W oho = . (19.13)

Tulosta varten se riittää kuvan alimman rivin sijaan. 19.2 ota funktio U(t)- tähän mennessä jäljellä olevien hakemusten määrä t ei järjestelmästä, vaan jonosta (jos järjestelmään tullut sovellus ei pääse jonoon, vaan menee heti palveluun, voidaan silti katsoa, ​​että se joutuu jonoon, mutta pysyy siinä nollaksi) .

Littlen kaavoilla (19.12) ja (19.13) on tärkeä rooli jonoteoriassa. Valitettavasti useimmissa olemassa olevissa käsikirjoissa näitä kaavoja (joka on todistettu yleisessä muodossa suhteellisen hiljattain) ei ole annettu 1).

Yksinkertaisimmat jonojärjestelmät ja niiden ominaisuudet

Tässä osiossa tarkastelemme joitain yksinkertaisimmista QS:istä ja johdamme lausekkeita niiden ominaisuuksille (suorituskykyindikaattorit). Samalla esittelemme alkeelliselle, "markovilaiselle" jonoteorialle tyypillisiä metodologisia tekniikoita.

Emme etsi niiden QS-näytteiden määrää, joille ominaisuuksien lopulliset lausekkeet johdetaan; tämä kirja ei ole opas jonoteoriaan (erikoisoppaat täyttävät tämän roolin paljon paremmin). Tavoitteenamme on esitellä lukijalle joitain "pieniä temppuja", jotka helpottavat jonoteorian läpikulkua, mikä useissa saatavilla olevissa (jopa suosituissa) kirjoissa voi tuntua hämmentävältä esimerkkikokoelmalta.

Kaikki tapahtumavirrat, jotka siirtävät QS:n tilasta tilaan, tässä osiossa tarkastelemme yksinkertaisinta (ilman että tätä joka kerta erikseen määrätään). Niiden joukossa on niin sanottu "palveluvirta". Se tarkoittaa yhden jatkuvasti varatun kanavan palvelemaa pyyntöjen virtaa. Tässä virrassa tapahtumien välisellä aikavälillä, kuten aina yksinkertaisimmassa virrassa, on eksponentiaalinen jakauma (monissa käsikirjoissa sanotaan sen sijaan: "palveluaika on eksponentiaalinen", me itse käytämme tätä termiä jatkossa).

Suositussa kirjassa esitetään hieman erilainen, yllä olevaan verrattuna, johtaminen Littlen kaavasta. Yleensä tutustuminen tähän kirjaan ("Second Conversation") on hyödyllinen jonoteoriaan tutustumiselle.

Tässä osiossa käyttöajan eksponentiaalinen jakautuminen pidetään itsestäänselvyytenä, kuten aina "yksinkertaisimmassa" järjestelmässä.

Esittelemme esityksen aikana tarkasteltavan QS:n tehokkuusominaisuudet.

1. P- kanava QS vioilla(Erlangin ongelma). Tässä tarkastelemme yhtä ensimmäisistä ajallisesti "klassisista" jonoteorian ongelmista; tämä ongelma syntyi puhelimen käytännön tarpeista ja sen ratkaisi vuosisadamme alussa tanskalainen matemaatikko Erlant. Tehtävä on asetettu seuraavasti: on P kanavat (viestintälinjat), jotka vastaanottavat sovellusvirran intensiteetillä λ. Palveluvirran intensiteetti on μ (keskimääräisen palveluajan käänteisluku t noin).

Etsi QS-tilojen lopulliset todennäköisyydet sekä sen tehokkuuden ominaisuudet:

^ A - absoluuttinen suorituskyky, eli keskimääräinen palveltujen sovellusten lukumäärä aikayksikköä kohti;

Q- suhteellinen läpimeno, eli järjestelmän palvelemien saapuvien pyyntöjen keskimääräinen osuus;

^ R otk- epäonnistumisen todennäköisyys, eli se, että sovellus jättää QS:n käyttämättä;

k - keskimääräinen varattujen kanavien määrä.

Ratkaisu. Järjestelmän tilat ^S(QS) numeroidaan järjestelmän pyyntöjen määrän mukaan (tässä tapauksessa se on sama kuin varattujen kanavien lukumäärä):

S 0 — yhteisessä markkinajärjestelyssä ei ole hakemuksia,

S 1 - QS:ssä on yksi pyyntö (yksi kanava on varattu, loput ovat vapaita),

Sk - SMO:ssa on k sovellukset ( k kanavat ovat varattuja, loput ovat ilmaisia),

S n - SMO:ssa on P sovellukset (kaikki n kanavat ovat varattu).

QS-tilakaavio vastaa lisääntymiskuoleman kaaviota (kuva 20.1). Merkitään tämä kaavio - lasketaan tapahtumavirtojen intensiteetti nuolien lähelle. From S 0 tuumaa S1 järjestelmää siirtää pyyntöjen virta, jonka intensiteetti on λ (niin kun pyyntö saapuu, järjestelmä hyppää S0 sisään S1). Sama pyyntövirta siirtää järjestelmän mistä tahansa vasemmasta tilasta viereiseen oikeaan tilaan (katso ylempiä nuolia kuvassa 20.1).

Laitetaan alas alempien nuolien voimakkuus. Anna järjestelmän olla tilassa ^S 1 (yksi kanava toimii). Se tuottaa μ palveluita aikayksikköä kohden. Astuimme alas nuolen kohdalle S 1 →S 0 intensiteetti μ. Kuvittele nyt, että järjestelmä on tilassa S2(kaksi kanavaa toimii). Jotta hän menisi S 1, on välttämätöntä, että joko ensimmäinen tai toinen kanava lopettaa huollon; niiden palveluvirtojen kokonaisintensiteetti on 2μ; laita se vastaavan nuolen kohdalle. Kolmen kanavan antaman kokonaispalveluvirran intensiteetti on 3 μ, k kanavat - km. Laitamme nämä intensiteetit alas kuvan 1 alempien nuolien kohdalle. 20.1.

Ja nyt, kun tiedämme kaikki intensiteetit, käytämme valmiita kaavoja (19.7), (19.8) lopullisille todennäköisyyksille kuoleman ja lisääntymisen kaaviossa.

Kaavan (19.8) mukaan saamme:

Hajotustermit ovat kertoimet p 0 ilmaisuissa for p1

Huomaa, että kaavat (20.1), (20.2) eivät sisällä intensiteettejä λ ja μ erikseen, vaan vain suhteena λ/μ. Merkitse

λ/μ = ρ (20,3)

Ja me kutsumme p:n arvoa "sovellusvirran vähentyneeksi intensiteetiksi". Sen merkitys on yhden pyynnön keskimääräiselle palveluajalle saapuvien pyyntöjen keskimääräinen määrä. Tätä merkintää käyttämällä kirjoitamme kaavat (20.1), (20.2) uudelleen muotoon:

Lopullisten tilatodennäköisyyksien kaavoja (20.4), (20.5) kutsutaan Erlang-kaavoiksi jonoteorian perustajan kunniaksi. Suurin osa tämän teorian muista kaavoista (nykyään niitä on enemmän kuin sieniä metsässä) ei kanna mitään erityisiä nimiä.

Siten lopulliset todennäköisyydet löytyvät. Niiden perusteella laskemme QS-tehokkuusominaisuudet. Ensin löydämme ^ R otk. - todennäköisyys, että saapuva pyyntö hylätään (ei toimiteta). Tätä varten on välttämätöntä, että kaikki P kanavat olivat kiireisiä, joten

R otk = R n = . (20.6)

Täältä löydämme suhteellisen suorituskyvyn - todennäköisyyden, että sovellus palvellaan:

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

Saamme absoluuttisen suorituskyvyn kertomalla pyyntöjen virran intensiteetin λ:lla K:

A = λQ = λ. (20.8)

Jää vain löytää kiireisten kanavien keskimääräinen määrä k. Tämä arvo voidaan löytää "suoraan" diskreetin satunnaismuuttujan matemaattisena odotuksena mahdollisilla arvoilla 0, 1, ..., P ja näiden arvojen todennäköisyydet p 0 p 1 , ..., p n:

k = 0 · p 0+ yksi · p 1 + 2 · p 2 + ... + n · p n .

Korvaa tässä lausekkeet (20.5) for R k , (k = 0, 1, ..., P) ja suorittamalla sopivat muunnokset, saisimme lopulta oikean kaavan k. Mutta me johdamme sen paljon helpommin (tässä se on, yksi "pienistä temppuista"!) Todellakin, tiedämme absoluuttisen suorituskyvyn MUTTA. Tämä ei ole muuta kuin järjestelmän palvelemien sovellusten virtauksen intensiteetti. Jokainen käytetty i .shal aikayksikköä kohden palvelee keskimäärin |l pyyntöä. Keskimääräinen varattujen kanavien määrä on siis

k = A/μ, (20.9)

tai annettu (20.8),

k = (20.10)

Kannustamme lukijaa laatimaan esimerkin itse. Siellä on viestintäasema, jossa on kolme kanavaa ( n= 3), sovellusvirran intensiteetti λ = 1,5 (applikaatiota minuutissa); keskimääräinen palveluaika pyyntöä kohti t v = 2 (min.), kaikki tapahtumavirrat (kuten tässä koko kappaleessa) ovat yksinkertaisimpia. Etsi QS:n lopulliset tilatodennäköisyydet ja suorituskykyominaisuudet: A, Q, P otk, k. Varmuuden vuoksi tässä vastaukset: s 0 = 1/13, s 1 = 3/13, s 2 = 9/26, p 3 = 9/26 ≈ 0,346,

MUTTA≈ 0,981, K ≈ 0,654, P avoin ≈ 0,346, k ≈ 1,96.

Vastauksista näkyy muuten, että CMO on suurelta osin ylikuormitettu: kolmesta kanavasta keskimäärin noin kaksi on varattu ja noin 35 % saapuvista sovelluksista jää palvelematta. Pyydämme lukijaa, jos hän on utelias eikä laiska, ottamaan selvää: kuinka monta kanavaa tarvitaan, jotta vähintään 80% saapuvista hakemuksista voidaan tyydyttää? Ja mikä osa kanavista on yhtä aikaa käyttämättömänä?

Siitä on jo jonkinlainen vihje optimointi. Itse asiassa kunkin kanavan sisältö aikayksikköä kohti maksaa tietyn summan. Samalla jokainen huollettu sovellus tuo jonkin verran tuloja. Kerrotaan nämä tulot hakemusten keskimääräisellä määrällä MUTTA, huollettu aikayksikköä kohti, saamme keskimääräiset CMO-tulot aikayksikköä kohti. Luonnollisesti kanavien määrän kasvaessa nämä tulot kasvavat, mutta myös kanavien ylläpitokustannukset kasvavat.

Mikä painaa enemmän - tulojen tai menojen kasvu? Se riippuu toiminnan ehdoista, "sovelluspalvelumaksusta" ja kanavan ylläpitokustannuksista. Kun tiedät nämä arvot, voit löytää optimaalisen kanavien määrän, kustannustehokkaimman. Emme ratkaise tällaista ongelmaa, vaan jätämme saman "laiskalle ja uteliaalle lukijalle" keksimään esimerkin ja ratkaisemaan sen. Yleensä ongelmien keksiminen kehittää enemmän kuin jonkun jo asettamien ratkaiseminen.

Yksikanavainen QS rajoittamattomalla jonolla.

Käytännössä yksikanavainen jonollinen QS on varsin yleistä (potilaita palveleva lääkäri; yhden kopin maksupuhelin; käyttäjien tilauksia täyttävä tietokone). Jonoteoriassa yksikanavaiset QS:t, joissa on jono, ovat myös erityisellä paikalla (useimmat tähän mennessä saaduista analyyttisistä kaavoista ei-Markovin järjestelmille kuuluvat sellaiseen QS:ään). Siksi kiinnitämme erityistä huomiota yksikanavaiseen QS:ään, jossa on jono.

Olkoon yksikanavainen QS, jossa on jono, jolle ei ole asetettu rajoituksia (ei jonon pituuden eikä odotusajan suhteen). Tämä QS vastaanottaa pyyntöjen virran, jonka intensiteetti on λ ; palveluvirran intensiteetti on μ, joka on käänteinen pyynnön keskimääräiseen palveluaikaan t noin.

On löydettävä QS-tilojen lopulliset todennäköisyydet sekä sen tehokkuuden ominaisuudet:

L syst. — järjestelmässä olevien sovellusten keskimääräinen määrä,

W syst. on pyynnön keskimääräinen viipymäaika järjestelmässä,

^L och- jonossa olevien hakemusten keskimääräinen määrä,

W och — keskimääräinen aika, jonka sovellus viettää jonossa,

P zan — todennäköisyys, että kanava on varattu (kanavan kuormitusaste).

Mitä tulee absoluuttiseen tehokkuuteen MUTTA ja suhteellinen Q, niin niitä ei tarvitse laskea:

koska jono on rajoittamaton, jokainen hakemus toimitetaan ennemmin tai myöhemmin A \u003d λ, samasta syystä Q= 1.

Ratkaisu. Järjestelmän tilat, kuten ennenkin, numeroidaan QS:n sovellusten määrän mukaan:

S 0 — kanava on ilmainen

S 1 - kanava on varattu (palvelee pyyntöä), ei ole jonoa,

S 2 — kanava on varattu, yksi pyyntö on jonossa,

S k - kanava on varattu, k - 1 hakemusta on jonossa,

Teoreettisesti tilojen määrää ei rajoita mikään (äärettä). Tilakaavion muoto on kuvan mukainen. 20.2. Tämä on kuoleman ja lisääntymisen järjestelmä, mutta siinä on ääretön määrä tiloja. Kaikissa nuolissa pyyntöjen virta, jonka intensiteetti on λ, siirtää järjestelmän vasemmalta oikealle ja oikealta vasemmalle palveluvirran intensiteetillä μ.

Ensinnäkin kysykäämme itseltämme, onko tässä tapauksessa olemassa lopullisia todennäköisyyksiä? Loppujen lopuksi järjestelmän tilojen lukumäärä on ääretön, ja periaatteessa on t → ∞ jono voi kasvaa loputtomiin! Kyllä, se on totta: lopulliset todennäköisyydet tällaiselle QS:lle eivät aina ole olemassa, mutta vain silloin, kun järjestelmä ei ole ylikuormitettu. Voidaan osoittaa, että jos ρ on ehdottomasti pienempi kuin yksi (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ kasvaa loputtomasti.

Tämä tosiasia vaikuttaa erityisen "käsittämättömältä" ρ = 1:lle. Vaikuttaa siltä, ​​​​että järjestelmälle ei ole mahdottomia vaatimuksia: yhden pyynnön palvelemisen aikana saapuu keskimäärin yksi pyyntö ja kaiken pitäisi olla kunnossa, mutta todellisuudessa se on ei ole. Kun ρ = 1, QS käsittelee pyyntöjen virtaa vain, jos tämä vuo on säännöllinen, eikä palveluaika ole myöskään satunnainen, yhtä suuri kuin pyyntöjen välinen aika. Tässä "ihanteellisessa" tapauksessa QS:ssä ei ole lainkaan jonoa, kanava on jatkuvasti varattu ja lähettää säännöllisesti palvelupyyntöjä.

Mutta heti kun pyyntöjen virta tai palveluvirta tulee ainakin hieman satunnaiseksi, jono kasvaa jo loputtomasti. Käytännössä näin ei tapahdu vain siksi, että "ääretön määrä sovelluksia jonossa" on abstraktio. Nämä ovat karkeita virheitä, joihin satunnaismuuttujien korvaaminen niiden matemaattisilla odotuksilla voi johtaa!

Mutta palataanpa yksikanavaiseen QS:ään, jossa on rajoittamaton jono. Tarkkaan ottaen lopullisten todennäköisyyksien kaavat kuoleman ja lisääntymisen kaaviossa johdimme vain rajallisen määrän tiloja varten, mutta otetaan vapaudet - käytämme niitä äärettömälle määrälle tiloja. Lasketaan tilojen lopulliset todennäköisyydet kaavojen (19.8), (19.7) mukaan. Meidän tapauksessamme termien määrä kaavassa (19.8) on ääretön. Saamme ilmaisun p 0:

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

Kaavan (20.11) sarja on geometrinen progressio. Tiedämme, että ρ< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... olemassa vain r:lle<1).

Oletetaan nyt, että tämä ehto täyttyy ja ρ1 + ρ + ρ 2 + ... + ρ k + ... = ,

s 0 = 1 - s. (20.12)

Todennäköisyydet p 1 , p 2 , ..., p k ,... löytyy kaavoilla:

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

Mistä, ottaen huomioon (20.12), löydämme lopulta:

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

Kuten näet, todennäköisyydet p0, p1, ..., p k,... muodostavat geometrisen progression nimittäjällä p. Kummallista kyllä, suurin niistä p 0 — todennäköisyys, että kanava on ilmainen. Riippumatta siitä, kuinka kuormitettu järjestelmä jonolla on, jos se vain pystyy selviytymään sovellusvirrasta (ρ<1), самое вероятное число заявок в системе будет 0.

Etsi hakemusten keskimääräinen määrä QS:stä ^L syst. . Tässä pitää vähän puuhailla. Satunnainen arvo Z- pyyntöjen määrä järjestelmässä - on mahdollisia arvoja 0, 1, 2, .... k,... todennäköisyyksien kanssa p0, p 1 , p 2 , ..., p k , ... Sen matemaattinen odotus on

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

(summaa ei oteta arvosta 0 arvoon ∞, vaan arvosta 1 arvoon ∞, koska nollatermi on yhtä suuri kuin nolla).

Korvataan kaavaan (20.14) lauseke for p k (20.13):

L syst. =

Nyt otetaan pois summan ρ (1-ρ) etumerkki:

L syst. = ρ(1-ρ)

Käytämme tässä taas "pientä temppua": kρ k-1 ei ole muuta kuin derivaatta lausekkeen ρ suhteen ρ:n suhteen k; tarkoittaa,

L syst. = ρ(1-ρ)

Vaihtamalla differentioinnin ja summauksen operaatiot keskenään saamme:

L syst. = ρ (1-ρ) (20.15)

Mutta summa kaavassa (20.15) ei ole mitään muuta kuin äärettömästi pienenevän geometrisen progression summa ensimmäisellä termillä ρ ja nimittäjällä ρ; Tämä summa

on yhtä suuri kuin , ja sen johdannainen on . Kun tämä lauseke korvataan lausekkeella (20.15), saadaan:

L syst = . (20.16)

No, nyt sovelletaan Littlen kaavaa (19.12) ja etsitään sovelluksen keskimääräinen viipymäaika järjestelmästä:

W syst = (20.17)

Etsi jonossa olevien sovellusten keskimääräinen määrä L och. Väittelemme seuraavasti: jonossa olevien sovellusten määrä on yhtä suuri kuin järjestelmän sovellusten määrä miinus palvelussa olevien sovellusten määrä. Joten (matemaattisten odotusten lisäyssäännön mukaan) jonossa olevien hakemusten keskimääräinen määrä L pt on yhtä suuri kuin järjestelmän sovellusten keskimääräinen lukumäärä L syst miinus palvelussa olevien pyyntöjen keskimääräinen määrä.

Palvelun alla olevien pyyntöjen määrä voi olla joko nolla (jos kanava on vapaa) tai yksi (jos se on varattu). Tällaisen satunnaismuuttujan matemaattinen odotus on yhtä suuri kuin todennäköisyys, että kanava on varattu (merkitsimme sitä R zan). Ilmeisesti R zan on yhtä suuri kuin yksi miinus todennäköisyys p 0 että kanava on ilmainen:

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

Siksi palvelussa olevien pyyntöjen keskimääräinen määrä on yhtä suuri kuin

^L noin= ρ, (20.19)

L oho = L syst - ρ =

ja lopuksi

L pt = (20.20)

Littlen kaavan (19.13) avulla löydämme sovelluksen jonossa viettämän keskimääräisen ajan:

(20.21)

Siten kaikki QS-tehokkuuden ominaisuudet on löydetty.

Ehdotetaan lukijaa ratkaisemaan esimerkki itse: yksikanavainen QS on ratapiha, joka vastaanottaa yksinkertaisimman junavirran intensiteetillä λ = 2 (junia tunnissa). Palvelu (lakkautuminen)

sävellys kestää satunnaisen (demonstratiivisen) ajan keskiarvolla t noin = 20(min.). Aseman tulopuistossa on kaksi rataa, joilla saapuvat junat voivat odottaa palvelua; jos molemmat radat ovat ruuhkaisia, junat joutuvat odottamaan uloimmilla raiteilla.

On löydettävä (aseman rajoittavaa, paikallaan olevaa toimintatapaa varten): keskiarvo, junien lukumäärä l asemaan liittyvä järjestelmä, keskiaika W junan seisontajärjestelmä asemalla (sisäisillä radoilla, ulkoraiteilla ja huollettavana), keskimääräinen määrä L pt junia jonossa purkamista varten (ei väliä millä raiteilla), keskimääräinen aika W Pts pysyy kokoonpanossa jonotuslistalla. Yritä myös selvittää niiden junien keskimääräinen lukumäärä, jotka odottavat purkamista uloimmilla raiteilla. L ulkoinen ja tämän odotuksen keskimääräinen aika W ulkoinen (kaksi viimeistä määrää liittyvät Littlen kaavan mukaan).

Lopuksi selvitetään päiväsakko W, jonka asema joutuu maksamaan junien seisonnasta ulkoisilla raiteilla, jos asema maksaa sakkoa (ruplaa) yhden junan tunnin seisomisesta. Varmuuden vuoksi tässä vastaukset: L syst. = 2 (koostumus), W syst. = 1 (tunti), L pisteet = 4/3 (koostumus), W pt = 2/3 (tuntia), L ulkoinen = 16/27 (koostumus), W ulkoinen = 8/27 ≈ 0,297 (tuntia). Keskimääräinen päiväsakko W junien odottamisesta ulkoraiteilla saadaan kertomalla asemalle saapuvien junien keskimäärä vuorokaudessa, junien keskimääräinen odotusaika ulkoraiteilla ja tuntisakko a: W ≈ 14,2 a.

kanava QS uudelleen rajoittamattomalla jonolla.

Täysin samanlainen kuin ongelma 2, mutta hieman monimutkaisempi ongelma n-kanava QS rajoittamattomalla jonolla.

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

On olemassa kuoleman ja lisääntymisen järjestelmä, mutta siinä on ääretön määrä tiloja. Ilmoitetaan ilman todisteita lopullisten todennäköisyyksien olemassaolon luonnollinen ehto: ρ/ n n ≥ 1, jono kasvaa äärettömään.

Oletetaan, että ehto ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 tulee joukko termejä, jotka sisältävät kertoimia plus loputtomasti pienenevän geometrisen progression summan nimittäjällä ρ/ n. Yhteenvetona löydämme

(20.22)

Etsitään nyt QS-tehokkuuden ominaisuudet. Näistä on helpoin löytää keskimääräinen varattujen kanavien lukumäärä k= λ/μ, = ρ (tämä pätee yleensä kaikille QS:ille, joissa on rajoittamaton jono). Etsi järjestelmän sovellusten keskimääräinen määrä L järjestelmä ja jonossa olevien sovellusten keskimääräinen määrä L och. Näistä on helpompi laskea toinen kaavan mukaan

L oho =

suorittaa vastaavat muunnokset tehtävän 2 näytteen mukaisesti

(sarjan eriyttämisellä) saamme:

L oho = (20.23)

Kun siihen lisätään palvelussa olevien sovellusten keskimääräinen määrä (se on myös varattujen kanavien keskimääräinen määrä) k =ρ, saamme:

L syst = L och + ρ. (20.24)

Jakolausekkeet for L och ja L syst on λ , Littlen kaavalla saadaan sovelluksen keskimääräinen viipymäaika jonossa ja järjestelmässä:

(20.25)

Ratkaistaan ​​nyt mielenkiintoinen esimerkki. Kahden ikkunan junalippukassa on kaksikanavainen QS, jossa on rajoittamaton jono, joka muodostetaan välittömästi kahteen ikkunaan (jos yksi ikkuna on vapaa, jonossa seuraava matkustaja ottaa sen). Lippukassa myydään lippuja kahdessa paikassa: A ja AT. Hakemusvirran intensiteetti (matkustajat, jotka haluavat ostaa lipun) molemmille kohdille A ja B on sama: λ A = λ B = 0,45 (matkustaja minuutissa), ja yhteensä ne muodostavat yleisen sovellusvirran, jonka intensiteetti on λ A + λB = 0,9. Kassa käyttää matkustajan palvelemiseen keskimäärin kaksi minuuttia.

Kokemus osoittaa, että lippukassalle kertyy jonoja, matkustajat valittavat palvelun hitaudesta. MUTTA ja sisään AT, luoda kaksi erikoistunutta lipputoimistoa (yksi ikkuna kummassakin), myymällä yksi lippu - vain asiaan MUTTA, toinen - vain asiaan AT. Tämän ehdotuksen järkevyys on kiistanalainen - jotkut väittävät, että jonot pysyvät ennallaan. Ehdotuksen hyödyllisyys on tarkistettava laskennallisesti. Koska voimme laskea ominaisuudet vain yksinkertaisimmalle QS:lle, oletetaan, että kaikki tapahtumavirrat ovat yksinkertaisimpia (tämä ei vaikuta johtopäätösten laadulliseen puoleen).

No sitten mennään asiaan. Harkitse kahta vaihtoehtoa lipunmyynnin järjestämiseen - nykyistä ja ehdotettua.

Vaihtoehto I (olemassa). Kaksikanavainen QS vastaanottaa sovellusvirran, jonka intensiteetti on λ = 0,9; ylläpitovirtauksen intensiteetti μ = 1/2 = 0,5; ρ = λ/μ = l.8. Koska ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим p 0 ≈ 0,0525. Keskiarvo, jonossa olevien sovellusten lukumäärä saadaan kaavalla (20.23): L och ≈ 7.68; asiakkaan keskimääräinen jonossa viettämä aika (ensimmäisen kaavan (20.25) mukaan) on yhtä suuri kuin W pts ≈ 8,54 (min.).

Vaihtoehto II (ehdotettu). On tarpeen harkita kahta yksikanavaista QS:ää (kaksi erikoisikkunaa); kukin vastaanottaa pyyntövirran, jonka intensiteetti on λ = 0,45; μ . edelleen yhtä suuri kuin 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8.1.

Tässä yksi sinulle! Osoittautuu, että jonon pituus ei vain vähentynyt, vaan kasvoi! Ehkä keskimääräinen odotusaika jonossa on lyhentynyt? Katsotaan. Delya L pisteet λ = 0,45, saamme W pts ≈ 18 (minuuttia).

Siinä se rationalisointi! Vähenemisen sijaan sekä keskimääräinen jonon pituus että keskimääräinen odotusaika siinä kasvoivat!

Yritetään arvata miksi näin tapahtui? Ajatteltuamme asiaa tulemme siihen johtopäätökseen: tämä tapahtui, koska ensimmäisessä versiossa (kaksikanavainen QS) keskimääräinen osa ajasta, jonka kumpikin kassasta on vapaana, on pienempi: jos hän ei ole kiireinen palvelemaan matkustajaa, joka ostaa. lippu asiaan MUTTA, hän voi huolehtia matkustajasta, joka ostaa lipun pisteeseen AT, ja päinvastoin. Toisessa versiossa tällaista vaihtokelpoisuutta ei ole: tyhjä kassa vain istuu joutilaina...

- Hyvin , OK, lukija on valmis samaa mieltä, kasvu voidaan selittää, mutta miksi se on niin merkittävä? Onko tässä joku laskuvirhe?

Ja me vastaamme tähän kysymykseen. Virhettä ei ole. tosiasia , että esimerkissämme molemmat QS:t toimivat kykyjensä rajoilla; palveluaikaa kannattaa hieman pidentää (eli pienentää μ), sillä he eivät enää kestä matkustajavirtoja ja jono alkaa kasvaa loputtomasti. Ja kassan "ylimääräinen seisokki" on tavallaan sama kuin hänen tuottavuuden lasku μ.

Näin ollen laskelmien tulos, joka vaikuttaa aluksi paradoksaalliselta (tai jopa yksinkertaisesti väärältä), osoittautuu oikeaksi ja selitettäväksi.

Tällaiset paradoksaaliset johtopäätökset, joiden syy ei ole mitenkään ilmeinen, on rikas jonotusteoriassa. Kirjoittaja itse joutui toistuvasti "yllättämään" laskelmien tuloksista, jotka myöhemmin osoittautuivat oikeiksi.

Viimeistä tehtävää pohdiskellessaan lukija voi esittää kysymyksen näin: loppujen lopuksi, jos lipputulot myyvät lippuja vain yhteen pisteeseen, niin luonnollisesti palveluajan pitäisi laskea, ei puoleen, mutta ainakin jonkin verran, mutta ajattelimme, että se oli silti keskiarvo on 2 (min.). Pyydämme niin nirsoa lukijaa vastaamaan kysymykseen: kuinka paljon sitä pitäisi pienentää, jotta "rationalisointiehdotuksesta" tulisi kannattava?

Taas tapaamme, vaikkakin alkeellisen, mutta silti optimointiongelman. Summittaisten laskelmien avulla voidaan jopa yksinkertaisimmilla, Markovin malleilla, selvittää ilmiön laadullinen puoli - kuinka kannattavaa on toimia ja miten se on kannattamatonta. Seuraavassa osiossa esittelemme joitain alkeellisia ei-markovialaisia ​​malleja, jotka laajentavat mahdollisuuksiamme entisestään.

Kun lukija on tutustunut yksinkertaisimman QS:n lopputilan todennäköisyyksien ja tehokkuusominaisuuksien laskentamenetelmiin (hän ​​on hallinnut kuolema- ja lisääntymiskaavion sekä Pikku-kaavan), hänelle voidaan tarjota kaksi muuta yksinkertaista QS:tä itsenäiseen tarkasteluun.

Yksikanavainen QS rajoitetulla jonolla. Ongelma eroaa tehtävästä 2 vain siinä, että pyyntöjen määrä jonossa on rajoitettu (ei voi ylittää tiettyä t). Jos uusi pyyntö saapuu sillä hetkellä, kun kaikki jonon paikat ovat varattu, se jättää QS:n palvelematta (hylätty).

On tarpeen löytää tilojen lopulliset todennäköisyydet (muuten, ne ovat olemassa tässä tehtävässä mille tahansa ρ:lle - tilojen lukumäärä on loppujen lopuksi äärellinen), epäonnistumisen todennäköisyys R otk, absoluuttinen kaistanleveys MUTTA, todennäköisyys, että kanava on varattu R zan, keskimääräinen jonon pituus L och, hakemusten keskimääräinen määrä yhteisessä markkinajärjestelyssä L syst , keskimääräinen odotusaika jonossa W och , hakemuksen keskimääräinen viipymäaika yhteisessä markkinajärjestelyssä W syst. Jonon ominaisuuksia laskettaessa voidaan käyttää samaa tekniikkaa, jota käytimme tehtävässä 2, sillä erolla, että ei tarvitse tehdä yhteenvetoa äärettömästä etenemisestä, vaan äärellisestä.

Suljetun piirin QS yhdellä kanavalla ja m sovelluslähteet. Konkreettisuuden vuoksi asetetaan tehtävä seuraavaan muotoon: yksi työntekijä palvelee t koneet, joista jokainen vaatii säätöä (korjausta) aika ajoin. Kunkin työkoneen kysyntävirran intensiteetti on yhtä suuri kuin λ . Jos kone on epäkunnossa sillä hetkellä, kun työntekijä on vapaana, hän menee heti huoltoon.

Jos hän on epäkunnossa sillä hetkellä, kun työntekijällä on kiire, hän asettuu jonoon ja odottaa työntekijän vapautumista. Keskimääräinen asennusaika t kierrosluku = 1/μ. Työntekijälle tulevien pyyntöjen intensiteetti riippuu siitä, kuinka monta konetta toimii. Jos se toimii k työstökoneet, se on yhtä suuri kuin kλ. Selvitä lopullisen tilan todennäköisyydet, työkoneiden keskimääräinen lukumäärä ja todennäköisyys, että työntekijä on kiireinen.

Huomaa, että tässä QS:ssä lopulliset todennäköisyydet ovat olemassa myös kaikille arvoille λ ja μ = 1/ t o, koska järjestelmän tilojen määrä on äärellinen.