Procesul QS este un proces aleatoriu. Un proces aleatoriu (probabilistic sau stocastic) este înțeles ca un proces de schimbare a stării unui sistem în timp în conformitate cu legile probabilistice.
Un proces se numește proces cu stări discrete dacă stările sale posibile S1, S2, S3... pot fi enumerate în prealabil, iar tranzițiile sistemului de la stare la stare au loc instantaneu (salt). Un proces se numește proces cu timp continuu dacă momentele posibilelor tranziții ale sistemului de la stare la stare nu sunt fixate în prealabil, ci sunt aleatorii.
Procesul de operare QS este un proces aleatoriu cu stări discrete și timp continuu.
Un proces aleatoriu se numește Markov sau proces aleatoriu fără consecințe dacă, pentru orice moment de timp t0, caracteristicile probabilistice ale procesului în viitor depind doar de starea lui la un moment dat t0 și nu depind de când și cum sistemul ajuns în această stare.
Un exemplu de proces Markov: sistemul S este un taximetru. Starea sistemului în momentul t este caracterizată de numărul de kilometri parcurși de mașină până în acest moment. Lăsați contorul să arate S0 la momentul t0. Probabilitatea ca în momentul t>t0 contorul să arate acest sau acel număr de kilometri (mai precis, numărul corespunzător de ruble) S1 depinde de S0, dar nu depinde de momentele în care s-au schimbat citirile contorului înainte de momentul t0.
În unele cazuri, preistoria proceselor luate în considerare poate fi pur și simplu neglijată și modelele Markov pot fi folosite pentru a le studia.
Când se analizează procese aleatoare cu stări discrete, este convenabil să se folosească o schemă geometrică - așa-numitul grafic de stare. În mod obișnuit, stările sistemului sunt descrise prin dreptunghiuri (cercuri), iar posibilele tranziții de la stare la stare sunt reprezentate prin săgeți (arce orientate) care leagă stările (Fig. 1).
Figura 1 - Graficul de stare
Pentru a descrie matematic un proces aleatoriu Markov cu stări discrete și timp continuu care curge într-un QS, ne vom familiariza cu unul dintre conceptele importante ale teoriei probabilităților - conceptul de flux de evenimente.
Fluxul evenimentelor este înțeles ca o succesiune de evenimente omogene care urmează unul după altul în anumite momente aleatorii în timp.
Exemple ar putea fi:
Fluxul se caracterizează prin intensitatea n - frecvența de apariție a evenimentelor sau numărul mediu de evenimente care intră în QS pe unitatea de timp.
Fluxul evenimentelor se numește regulat dacă evenimentele se succed la anumite intervale. Un astfel de flux este relativ rar în practică, dar prezintă un anumit interes ca caz extrem.
Un flux de evenimente se numește staționar dacă caracteristicile sale probabilistice nu depind de timp. În special, intensitatea unui flux staționar este o valoare constantă: .
Un flux de evenimente se numește flux fără efect secundar dacă, pentru oricare două secțiuni de timp care nu se suprapun și _, numărul de evenimente care se încadrează pe una dintre ele nu depinde de numărul de evenimente care cad pe celelalte. De exemplu, fluxul de pasageri care intră în metrou nu are practic niciun impact. Și, să zicem, fluxul de clienți care părăsesc ghișeul cu achiziții are deja consecințe (fie și doar pentru că intervalul de timp dintre clienții individuali nu poate fi mai mic decât timpul minim de service pentru fiecare dintre aceștia).
Un flux de evenimente se numește obișnuit dacă probabilitatea ca două sau mai multe evenimente să apară într-un interval de timp mic (elementar) este neglijabilă în comparație cu probabilitatea ca un eveniment să se producă. Cu alte cuvinte, un flux de evenimente este obișnuit dacă evenimentele apar în el individual și nu în grupuri.
Se spune că un flux de evenimente este cel mai simplu (sau Poisson staționar) dacă este atât staționar, obișnuit și fără consecințe.
Cel mai simplu flux ca limită apare în teoria proceselor aleatorii la fel de firesc ca în teoria probabilității distribuția normală se obține prin suprapunerea (suprapunerea) a unui număr suficient de mare n de fluxuri independente, staționare și obișnuite (comparabile între ele în intensitate), rezultă un flux apropiat de cel mai simplu cu intensitatea l, egal cu suma intensităților fluxurilor de intrare:
Să considerăm cel mai simplu flux de evenimente pe axa timpului ca o secvență nelimitată de puncte aleatorii. (Fig. 2)
Figura 2 - Fluxul evenimentelor
Se poate demonstra că pentru cel mai simplu flux, numărul m de evenimente (puncte) care se încadrează pe un segment de timp arbitrar φ este distribuit conform legii lui Poisson.
pentru care așteptarea matematică a unei variabile aleatoare este egală cu varianța acesteia:
În special, probabilitatea ca niciun eveniment să nu aibă loc în timpul φ (m = 0) este egală cu
Să găsim distribuția intervalului de timp T între două evenimente învecinate arbitrare ale fluxului cel mai simplu.
În conformitate cu formula, probabilitatea ca într-o perioadă de timp de lungime t să nu se producă niciunul dintre evenimentele ulterioare este egală cu
și probabilitatea evenimentului opus, i.e. funcţia de distribuţie a variabilei aleatoare T, este
Densitatea de probabilitate a unei variabile aleatoare este derivata funcției sale de distribuție:
Distribuția dată de densitatea de probabilitate sau funcția de distribuție se numește exponențială (sau exponențială). Astfel, intervalul de timp dintre două evenimente arbitrare vecine are o distribuție exponențială, pentru care așteptarea matematică este egală cu abaterea standard a variabilei aleatoare.
şi invers după intensitatea debitului de l.
Cea mai importantă proprietate a distribuției exponențiale (inerentă numai distribuției exponențiale) este următoarea: dacă o perioadă de timp distribuită conform legii exponențiale a durat deja de ceva timp φ, atunci aceasta nu afectează în niciun fel legea distribuției. a părții rămase a intervalului (T-φ): va fi aceeași, precum și legea de distribuție a întregului interval T.
Cu alte cuvinte, pentru un interval de timp T între două evenimente consecutive învecinate ale unui flux care are o distribuție exponențială, orice informație despre cât a durat acest interval nu afectează legea distribuției părții rămase.
Pentru cel mai simplu flux cu intensitatea l, probabilitatea ca cel puțin un eveniment de curgere să se producă într-un interval de timp elementar (mic) t este egală cu
Când se cercetează operațiuni, se întâlnesc adesea sisteme concepute pentru utilizare reutilizabilă atunci când se rezolvă probleme similare. Procesele care apar în acest caz sunt numite procese de service, si sisteme - sisteme de așteptare (QS). Exemple de astfel de sisteme sunt sistemele de telefonie, atelierele de reparații, complexele de calculatoare, casele de bilete, magazinele, coaforele etc.Ca indicatori de performanță Se utilizează QS: mediu (în continuare, valorile medii sunt înțelese ca așteptări matematice ale variabilelor aleatoare corespunzătoare) număr de cereri deservite pe unitatea de timp; numărul mediu de aplicații în coadă; timpul mediu de așteptare pentru serviciu; posibilitatea de a refuza serviciul fără așteptare; probabilitatea ca numărul de aplicații din coadă să depășească o anumită valoare etc.
QS este împărțit în două tipuri principale (clase): CMO cu erori și href="cmo_length.php">CMO cu așteptare (coadă). Într-un QS cu refuzuri, o cerere primită într-un moment în care toate canalele sunt ocupate primește un refuz, părăsește QS și nu participă la procesul ulterioar de servicii (de exemplu, o solicitare pentru o conversație telefonică într-un moment în care toate canalele sunt ocupat, primește un refuz și lasă QS-ul neservit). Într-un QS în așteptare, o solicitare care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci devine în coadă pentru service.
Cozile cu așteptare sunt împărțite în diferite tipuri în funcție de modul în care este organizată coada: cu lungime de coadă limitată sau nelimitată, cu timp de așteptare limitat etc.
Procesul de lucru al QS este proces aleatoriu.
Sub proces aleatoriu (probabilistic sau stocastic). se referă la procesul de schimbare a stării unui sistem în timp în conformitate cu legile probabilistice.
Procesul este numit proces cu stări discrete, dacă stările sale posibile S 1, S 2, S 3 ... pot fi enumerate în prealabil, iar trecerea sistemului de la stare la stare are loc instantaneu (într-un salt). Procesul este numit proces în timp continuu dacă momentele posibilelor tranziții ale sistemului de la stare la stare nu sunt fixate în prealabil, ci sunt aleatorii.
Procesul de operare QS este un proces aleatoriu cu stări discrete și timp continuu. Aceasta înseamnă că starea QS-ului se schimbă brusc în momente aleatorii când apar anumite evenimente (de exemplu, sosirea unei noi solicitări, încetarea serviciului etc.).
Analiza matematică a funcționării unui QS este simplificată semnificativ dacă procesul acestei operații este Markovian. Procesul aleatoriu este numit Markovian sau proces aleatoriu fără consecințe, dacă pentru orice moment de timp t 0 caracteristicile probabilistice ale procesului în viitor depind numai de starea lui la momentul dat t 0 şi nu depind de când şi cum a ajuns sistemul în această stare.
Un exemplu de proces Markov: sistemul S este un taximetru. Starea sistemului la momentul t este caracterizată de numărul de kilometri (zecimi de kilometri) parcurși de mașină până în acest moment. Fie ca contorul să arate S 0 în momentul t 0 . Probabilitatea ca în momentul t > t 0 contorul să arate acest sau acel număr de kilometri (mai precis, numărul corespunzător de ruble) S 1 depinde de S 0 , dar nu depinde de momentele în care citirile contorului schimbat înainte de momentul t 0 .
Multe procese pot fi considerate aproximativ markoviene. De exemplu, procesul de a juca șah; sistemul S -
grup de piese de șah. Starea sistemului este caracterizată de numărul de piese inamice rămase pe tablă la momentul t 0 . Probabilitatea ca în momentul t > t 0 avantajul material să fie de partea unuia dintre adversari depinde în primul rând de starea sistemului la momentul t 0, și nu de când și în ce ordine au dispărut piesele din bord până la t 0 .
În unele cazuri, preistoria proceselor luate în considerare poate fi pur și simplu neglijată și modelele Markov pot fi folosite pentru a le studia.
Când se analizează procese aleatorii cu stări discrete, este convenabil să se folosească o schemă geometrică - așa-numita grafic de stare.În mod obișnuit, stările sistemului sunt descrise prin dreptunghiuri (cercuri), iar posibilele tranziții de la stare la stare sunt descrise prin săgeți (arce orientate) care conectează stările.
Sarcina 1.
Construiți un grafic de stare al următorului proces aleatoriu: dispozitivul S este format din două noduri, fiecare dintre ele putând eșua într-un moment aleator, după care începe imediat repararea nodului, continuând pentru un timp aleatoriu necunoscut anterior.
Soluţie.
Stări posibile ale sistemului: S 0 - ambele noduri sunt operaționale; S 1 - prima unitate este în curs de reparare, a doua este operațională; S 2 - a doua unitate este in reparatie, prima functioneaza; S 3 - ambele unitati sunt in reparatie. Graficul sistemului este prezentat în Fig. 1.
Orez. 1
O săgeată direcționată, de exemplu, de la S 0 la S 1 înseamnă o tranziție a sistemului în momentul defectării primului nod, de la S 1 la S 0 - o tranziție în momentul finalizării reparației acestui nod.
Nu există săgeți pe grafic de la S 0 la S 3 și de la S 1 la S 2. Acest lucru se explică prin faptul că defecțiunile nodurilor se presupune că sunt independente unele de altele și, de exemplu, probabilitatea defecțiunii simultane a două noduri (tranziția de la S 0 la S 3) sau finalizarea simultană a reparațiilor a două noduri (tranziție). de la S 3 la S 0) poate fi neglijată.
, (1)
(5)
În prelegerile anterioare am învățat cum să simulăm apariția unor evenimente aleatorii. Adică ne putem juca care de evenimente posibile vor avea loc şi în care cantitate. Pentru a determina acest lucru, trebuie să cunoașteți caracteristicile statistice ale apariției evenimentelor, de exemplu, o astfel de valoare ar putea fi probabilitatea ca un eveniment să se producă sau distribuția probabilității diferitelor evenimente, dacă există infinit de tipuri de aceste evenimente.
Dar de multe ori este important să știi Când acest sau acel eveniment va avea loc în mod specific în timp.
Când sunt multe evenimente și se succed, se formează curgere. Rețineți că evenimentele trebuie să fie omogene, adică oarecum asemănătoare între ele. De exemplu, apariția șoferilor la benzinării care doresc să își alimenteze mașina. Adică evenimente omogene formează o anumită serie. În acest caz, se presupune că este dată caracteristica statistică a acestui fenomen (intensitatea fluxului de evenimente). Intensitatea fluxului de evenimente indică câte în medie astfel de evenimente apar pe unitatea de timp. Dar exact când va avea loc fiecare eveniment specific trebuie determinat folosind metode de modelare. Este important ca atunci când generăm, de exemplu, 1000 de evenimente în 200 de ore, numărul acestora va fi aproximativ egal cu intensitatea medie de apariție a evenimentelor 1000/200 = 5 evenimente pe oră, care este o valoare statistică care caracterizează acest flux ca un întreg.
Intensitatea fluxului într-un sens este așteptarea matematică a numărului de evenimente pe unitatea de timp. Dar în realitate se poate dovedi că într-o oră apar 4 evenimente, 6 într-o alta, deși în medie sunt 5 evenimente pe oră, deci o valoare nu este suficientă pentru a caracteriza fluxul. A doua mărime care caracterizează cât de mare este răspândirea evenimentelor în raport cu așteptările matematice este, ca și înainte, dispersia. De fapt, această valoare este cea care determină caracterul aleatoriu al apariției unui eveniment, predictibilitatea slabă a momentului producerii acestuia. Despre această valoare vom vorbi în următoarea prelegere.
Un flux de evenimente este o succesiune de evenimente omogene care au loc unul după altul la intervale aleatorii. Pe axa timpului, aceste evenimente arată ca în fig. 28.1.
Un exemplu de flux de evenimente este succesiunea momentelor în care avioanele care sosesc la un aeroport aterizează pe pistă.
Intensitatea fluxului
λ acesta este numărul mediu de evenimente pe unitatea de timp. Intensitatea debitului poate fi calculată experimental folosind formula: λ = N/T n, Unde N numărul de evenimente care au avut loc în timpul observării T n.Dacă intervalul dintre evenimente τ j egal cu o constantă sau definit de o formulă sub forma: t j = f(t j 1), atunci fluxul este numit determinist. În caz contrar, fluxul se numește aleatoriu.
Există fluxuri aleatorii:
Este obișnuit să se ia fluxul Poisson ca standard de flux în modelare..
Fluxul Poisson acesta este un flux obișnuit fără efecte secundare.
După cum sa menționat anterior, probabilitatea ca într-un interval de timp (t 0 , t 0 + τ ) se va întâmpla m evenimentele sunt determinate din legea lui Poisson:
Unde o Parametrul Poisson.
Dacă λ (t) = const( t) , apoi asta flux staționar de Poisson(cel mai simplu). În acest caz o = λ · t . Dacă λ = var( t), apoi aceasta curgere Poisson instabilă.
Pentru cel mai simplu flux, probabilitatea de apariție m evenimentele din timpul τ este egal cu:
Probabilitatea de neapariție (adică niciuna, m= 0 ) evenimente de-a lungul timpului τ este egal cu:
Orez. 28.2 ilustrează dependența P 0 din timp. Evident, cu cât timpul de observare este mai lung, cu atât este mai puțin probabil ca niciun eveniment să nu aibă loc. Mai mult, cu cât valoarea este mai mare λ , cu cât graficul este mai abrupt, adică cu atât probabilitatea scade mai repede. Acest lucru corespunde faptului că, dacă intensitatea apariției evenimentelor este mare, atunci probabilitatea ca evenimentul să nu se producă rapid scade odată cu timpul de observare.
Probabilitatea ca cel puțin un eveniment să se producă ( PХБ1С) se calculează după cum urmează:
deoarece P HB1S + P 0 = 1 (fie va apărea cel puțin un eveniment, fie nu va apărea niciunul, celălalt nu este dat).
Din graficul din fig. 28.3 este clar că probabilitatea de apariție a cel puțin unui eveniment tinde spre unitate în timp, adică cu o observare corespunzătoare pe termen lung a evenimentului, cu siguranță se va întâmpla mai devreme sau mai târziu. Cu cât observăm mai mult un eveniment (cu atât mai mult t), cu atât este mai mare probabilitatea ca evenimentul să se producă; graficul funcției crește monoton.
Cu cât este mai mare intensitatea apariției evenimentului (cu atât mai mult λ ), cu cât acest eveniment are loc mai repede și funcția tinde mai rapid spre unitate. Parametru pe diagramă λ reprezentată de abruptul dreptei (panta tangentei).
Dacă creșteți λ , apoi la observarea unui eveniment în același timp τ , probabilitatea ca un eveniment să se producă crește (vezi Fig. 28.4). Evident, graficul începe de la 0, deoarece dacă timpul de observare este infinitezimal, atunci probabilitatea ca evenimentul să se producă în acest timp este neglijabilă. Și invers, dacă timpul de observare este infinit de lung, atunci evenimentul va avea loc cu siguranță cel puțin o dată, ceea ce înseamnă că graficul tinde către o valoare a probabilității egală cu 1.
Studiind legea, puteți determina că: m x = 1/λ , σ = 1/λ , adică pentru cel mai simplu flux m x = σ . Egalitatea așteptărilor matematice cu abaterea standard înseamnă că acest flux este un flux fără efecte secundare. Dispersia (mai precis, abaterea standard) a unui astfel de flux este mare. Din punct de vedere fizic, aceasta înseamnă că timpul de apariție a unui eveniment (distanța dintre evenimente) este slab previzibil, aleatoriu și se află în interval m x σ < τ j < m x + σ . Deși este clar că, în medie, este aproximativ egal cu: τ j = m x = T n/ N . Un eveniment poate avea loc oricând, dar în intervalul acestui moment τ j relativ m x la [ σ ; +σ ] (amploarea efectului secundar). În fig. Figura 28.5 prezintă pozițiile posibile ale evenimentului 2 în raport cu axa timpului pentru un dat σ . În acest caz, ei spun că primul eveniment nu îl afectează pe al doilea, al doilea nu îl afectează pe al treilea și așa mai departe, adică nu există niciun efect secundar.
Prin sens P egal r(vezi prelegerea 23. Modelarea unui eveniment aleatoriu. Modelarea unui grup complet de evenimente incompatibile), prin urmare, exprimând τ din formula (*) , în sfârșit, pentru a determina intervalele dintre două evenimente aleatoare avem:
τ = 1/ λ Ln( r) ,
Unde r un număr aleatoriu distribuit uniform de la 0 la 1, care este luat din RNG, τ interval dintre evenimente aleatoare (variabilă aleatoare τ j ).
Exemplul 1. Să luăm în considerare fluxul de produse care ajung la o operațiune tehnologică. Produsele sosesc aleatoriu în medie opt bucăți pe zi (debit λ = 8/24 [unități/oră]). Este necesar să se simuleze acest proces în interior T n = 100 ore. m = 1/λ = 24/8 = 3 , adică, în medie, o parte la trei ore. Rețineți că σ = 3 . În fig. Figura 28.6 prezintă un algoritm care generează un flux de evenimente aleatorii.
În fig. În figura 28.7 se prezintă rezultatul algoritmului: momentele în timp în care piesele au ajuns pentru operație. După cum se vede, doar în perioada T n = 100 unități de producție prelucrate N= 33 de produse. Dacă rulăm algoritmul din nou, atunci N se poate dovedi a fi egal, de exemplu, 34, 35 sau 32. Dar, în medie, pentru K algoritmul rulează N va fi egal cu 33,33 Dacă se calculează distanţele dintre evenimente t Cu iși puncte de timp definite ca 3 i, atunci în medie valoarea va fi egală cu σ = 3 .
Dacă se știe că fluxul nu este obișnuit, atunci este necesar să se modeleze, pe lângă momentul producerii evenimentului, și numărul de evenimente care ar putea apărea în acest moment. De exemplu, mașinile ajung la o gară ca parte a unui tren la ore aleatorii (flux regulat de tren). Dar, în același timp, un tren poate avea un număr diferit (aleatoriu) de vagoane. În acest caz, se vorbește despre fluxul trăsurilor ca despre un flux de evenimente extraordinare.
Să presupunem că M k = 10 , σ = 4 (adică, în medie, în 68 de cazuri din 100, în tren sunt de la 6 la 14 vagoane) iar numărul acestora este repartizat conform legii normale. În locul marcat (*) în algoritmul anterior (vezi Fig. 28.6), trebuie să introduceți fragmentul prezentat în Fig. 28.8.
Exemplul 2. Soluția la următoarea problemă este foarte utilă în producție. Care este timpul mediu zilnic de nefuncționare al echipamentului unui nod tehnologic dacă nodul prelucrează fiecare produs pentru un timp aleator specificat de intensitatea fluxului de evenimente aleatoare λ 2? În același timp, s-a stabilit experimental că produsele sunt aduse și pentru prelucrare la momente aleatorii specificate de flux λ 1 în loturi de 8 bucăți, iar dimensiunea lotului fluctuează aleatoriu conform legii normale cu m = 8 , σ = 2 (vezi prelegerea 25). Înainte de modelare T= 0 nu existau produse in stoc. Este necesar să se simuleze acest proces în interior T n = 100 ore.
În fig. Figura 28.9 prezintă un algoritm care generează aleatoriu un flux de sosiri de loturi de produse pentru prelucrare și un flux de evenimente aleatorii de ieșire a loturii de produse din procesare.
În fig. Figura 28.10 prezintă rezultatul algoritmului: momentele în timp în care piesele au ajuns la operație și momentele în timp în care piesele au părăsit operațiunea. A treia linie arată câte piese au fost în coadă pentru procesare (se afla în depozitul nodului) în momente diferite.
Notând pentru nodul de procesare timpii în care acesta a fost inactiv în așteptarea următoarei părți (vezi în Fig. 28.10 secțiunile de timp evidențiate cu roșu), putem calcula timpul total de nefuncționare al nodului pentru întreg timpul de observare și apoi calculam timpul mediu de nefuncţionare în timpul zilei. Pentru această implementare, acest timp se calculează după cum urmează:
T etc. Mier. = 24 · ( t 1 + t 2 + t 3 + t 4 + + t N etc.)/ T n.
Sarcina 1. Schimbarea valorii σ , instalați dependența T etc. Mier. ( σ ) . Stabilirea costului pentru oprirea nodului la 100 de euro/oră, determinați pierderile anuale ale întreprinderii din nereguli în activitatea furnizorilor. Propuneți formularea clauzei contractului întreprinderii cu furnizorii „Cuantumul amenzii pentru întârzierea livrării produselor”.
Sarcina 2. Prin modificarea cantității de umplere inițială a depozitului, determinați cum se vor modifica pierderile anuale ale întreprinderii din neregulile în activitatea furnizorilor, în funcție de cantitatea de stoc acceptată la întreprindere.
În unele cazuri, intensitatea fluxului se poate modifica în timp λ (t) . Un astfel de flux se numește instabil. De exemplu, numărul mediu de ambulanțe pe oră care părăsesc stația ca răspuns la apelurile din partea populației unui oraș mare poate varia pe parcursul zilei. Se știe, de exemplu, că cel mai mare număr de apeluri se încadrează pe intervalele de la 23 la 01 am și de la 05 la 07 am, în timp ce în alte ore este la jumătate (vezi Fig. 28.11).
În acest caz, distribuția λ (t) poate fi specificat fie printr-un grafic, o formulă sau un tabel. Și în algoritmul prezentat în Fig. 28.6, în locul marcat (**), va trebui să introduceți fragmentul prezentat în Fig. 28.12.
Agenția Federală pentru Educație a Federației Ruse
FGOU SPO „Colegiul de construcții Perevozsky”
Lucrări de curs
la disciplina „Metode matematice”
pe tema „SMO cu timp de așteptare limitat. QS închis"
Introducere................................................. ....... ................................................. ............. ....... 2
1. Fundamentele teoriei cozilor de așteptare.................................................. ................ ...... 3
1.1 Conceptul de proces aleatoriu............................................. ......... ................. 3
1.2 Proces aleatoriu Markov.............................................. ...... ................ 4
1.3 Fluxuri de evenimente.................................................. ............................. ................................. ............. 6
1.4 Ecuații Kolmogorov pentru probabilități de stare. Probabilități de stare finală.................................................. ............................................................... ..................... ........ 9
1.5 Probleme ale teoriei cozilor de așteptare............................................. ....... .. 13
1.6 Clasificarea sistemelor de așteptare.................................................. ..... 15
2. Sisteme de așteptare cu așteptare.................................................. ........ 16
2.1 QS cu un singur canal cu așteptare............................................. ......... .......... 16
2.2 QS multicanal cu așteptare............................................. ......... ......... 25
3. QS închis.............................................. ...................................................... ... 37
Rezolvarea problemei.................................................................. ..... ................................................. 45
Concluzie................................................. .................................................. ...... .50
Referințe.................................................................. ....................................................... 51
În acest curs ne vom uita la diferite sisteme de așteptare (QS) și rețele de așteptare (Queuing).
Sistemul de așteptare (QS) este înțeles ca un sistem dinamic conceput pentru a deservi eficient fluxul de cereri (cerințe de serviciu) sub restricții asupra resurselor sistemului.
Modelele QS sunt convenabile pentru descrierea subsistemelor individuale ale sistemelor de calcul moderne, cum ar fi subsistemul procesorului - memoria principală, canalul de intrare-ieșire etc. Un sistem de calcul în ansamblu este un set de subsisteme interconectate, a căror interacțiune este probabilistică. O aplicație pentru rezolvarea unei anumite probleme de intrare într-un sistem de calcul parcurge o succesiune de etape de numărare, accesarea dispozitivelor de stocare externe și a dispozitivelor de intrare-ieșire. După finalizarea unei anumite secvențe de astfel de etape, numărul și durata cărora depind de complexitatea programului, cererea este considerată deservită și părăsește sistemul informatic. Astfel, sistemul de calcul în ansamblu poate fi reprezentat printr-un set de QS, fiecare dintre acestea reflectând procesul de funcționare a unui dispozitiv individual sau a unui grup de dispozitive similare care fac parte din sistem.
Un set de QS-uri interconectate se numește rețea de așteptare (rețea stocastică).
Pentru început, ne vom uita la elementele de bază ale teoriei QS, apoi vom trece la familiarizarea cu conținutul detaliat cu QS cu așteptare și QS închis. Cursul include și o parte practică, în care vom învăța în detaliu cum să aplicăm teoria în practică.
Teoria cozilor este una dintre ramurile teoriei probabilităților. Această teorie consideră probabilistică probleme și modele matematice (înainte de aceasta am considerat modele matematice deterministe). Să vă reamintim că:
Model matematic determinist reflectă comportamentul unui obiect (sistem, proces) din perspectivă certitudine deplină in prezent si viitor.
Model matematic probabilist ia în considerare influența factorilor aleatori asupra comportamentului unui obiect (sistem, proces) și, prin urmare, evaluează viitorul din punctul de vedere al probabilității anumitor evenimente.
Aceste. aici, ca, de exemplu, în teoria jocurilor sunt luate în considerare problemele in conditii incertitudine .
Să luăm în considerare mai întâi câteva concepte care caracterizează „incertitudinea stocastică”, atunci când factorii nesiguri incluși în problemă sunt variabile aleatoare (sau funcții aleatoare), ale căror caracteristici probabilistice fie sunt cunoscute, fie pot fi obținute din experiență. O astfel de incertitudine este numită și „favorabilă”, „benignă”.
Strict vorbind, tulburările aleatorii sunt inerente oricărui proces. Este mai ușor să dai exemple de proces aleatoriu decât un proces „nealeatoriu”. Chiar și, de exemplu, procesul de rulare a unui ceas (pare a fi o lucrare strict calibrată - „funcționează ca un ceas”) este supus unor modificări aleatorii (înainte, rămânere în urmă, oprire). Dar atâta timp cât aceste perturbări sunt nesemnificative și au un efect redus asupra parametrilor care ne interesează, le putem neglija și considera procesul ca fiind determinist, non-aleatoriu.
Să existe un sistem S(dispozitiv tehnic, grup de astfel de dispozitive, sistem tehnologic - mașină, șantier, atelier, întreprindere, industrie etc.). În sistem S scurgeri proces aleatoriu, dacă își schimbă starea în timp (trece de la o stare la alta), mai mult, într-o manieră aleatorie necunoscută anterior.
Exemple:
1. Sistem S– sistem tehnologic (secțiunea mașini). Mașinile se defectează din când în când și sunt reparate. Procesul care are loc în acest sistem este aleatoriu.
2. Sistem S- o aeronavă care zboară la o altitudine dată de-a lungul unei anumite rute. Factori deranjanți - condițiile meteorologice, erorile echipajului etc., consecințe - accidentare, încălcarea programului de zbor etc.
Se numește un proces aleatoriu care are loc într-un sistem Markovsky, dacă pentru orice moment de timp t 0 caracteristicile probabilistice ale unui proces în viitor depind numai de starea acestuia în momentul de față t 0 și nu depind de când și cum a ajuns sistemul în această stare.
Fie ca sistemul să fie într-o anumită stare în momentul t 0 S 0 . Cunoaștem caracteristicile stării sistemului în prezent și tot ce s-a întâmplat în timpul t <t 0 (istoricul procesului). Putem prezice (prevaza) viitorul, de ex. ce se va întâmpla când t >t 0 ? Nu tocmai, dar unele caracteristici probabilistice ale procesului pot fi găsite în viitor. De exemplu, probabilitatea ca după ceva timp sistemul S va putea S 1 sau va rămâne în stare S 0, etc.
Exemplu. Sistem S- un grup de aeronave care participă la lupte aeriene. Lasă x– numărul de avioane „roșii”, y– numărul de aeronave „albastre”. Până când t 0 număr de aeronave supraviețuitoare (nu doborâte), respectiv – x 0 , y 0 . Ne interesează probabilitatea ca la un moment dat superioritatea numerică să fie de partea „roșiilor”. Această probabilitate depinde de starea în care se afla sistemul la momentul respectiv t 0, și nu când și în ce secvență cei doborâți au murit până în momentul de față t 0 avioane.
În practică, procesele Markov în forma lor pură nu sunt de obicei întâlnite. Dar există procese pentru care influența „preistoriei” poate fi neglijată. Și atunci când se studiază astfel de procese, pot fi folosite modele Markov (teoria cozilor de așteptare nu ia în considerare sistemele de așteptare Markov, dar aparatul matematic care le descrie este mult mai complex).
În cercetarea operațională, procesele aleatoare Markov cu stări discrete și timp continuu sunt de mare importanță.
Procesul este numit proces de stare discretă, dacă este posibil S 1 , S 2, ... poate fi determinat în avans, iar tranziția sistemului de la stare la stare are loc „într-un salt”, aproape instantaneu.
Procesul este numit proces în timp continuu, dacă momentele posibilelor tranziții de la stare la stare nu sunt fixate în prealabil, ci sunt incerte, aleatorii și pot apărea în orice moment.
Exemplu. Sistem tehnologic (secțiune) S constă din două mașini, fiecare dintre acestea putând defecta (eșua) la un moment aleatoriu, după care începe imediat reparația unității, care continuă și pentru un timp necunoscut, aleatoriu. Sunt posibile următoarele stări ale sistemului:
S 0 - ambele mașini funcționează;
S 1 - prima mașină este în curs de reparare, a doua funcționează;
S 2 - a doua mașină este în curs de reparare, prima funcționează;
S 3 - ambele mașini sunt în curs de reparare.
Tranziții de sistem S de la stare la stare apar aproape instantaneu, în momente aleatorii când o anumită mașină eșuează sau o reparație este finalizată.
Când se analizează procese aleatoare cu stări discrete, este convenabil să se folosească o schemă geometrică - grafic de stare. Vârfurile graficului sunt stările sistemului. Arcele graficului sunt posibile tranziții de la stare la stare. Pentru exemplul nostru, graficul de stare este prezentat în Fig. 1.
Orez. 1. Graficul stării sistemului
Nota. Trecerea de la stat S 0 in S 3 nu este indicat în figură, deoarece se presupune că mașinile eșuează independent unele de altele. Neglijăm posibilitatea defecțiunii simultane a ambelor mașini.
Flux de evenimente– o succesiune de evenimente omogene care urmează unul după altul în anumite momente aleatorii în timp.
În exemplul anterior, acesta este un flux de eșecuri și un flux de restaurări. Alte exemple: fluxul de apeluri la o centrală telefonică, fluxul de clienți într-un magazin etc.
Fluxul evenimentelor poate fi reprezentat vizual printr-o serie de puncte de pe axa timpului O t- orez. 2.
Orez. 2. Imagine a fluxului de evenimente pe axa timpului
Poziția fiecărui punct este aleatorie și aici este descrisă o singură implementare a fluxului.
Intensitatea fluxului evenimentului ( ) este numărul mediu de evenimente pe unitatea de timp.
Să ne uităm la unele proprietăți (tipuri) de fluxuri de evenimente.
Fluxul de evenimente este numit staţionar, dacă caracteristicile sale probabilistice nu depind de timp.
În special, intensitatea fluxului staționar este constantă. Fluxul evenimentelor are inevitabil condensări sau rarefacții, dar acestea nu sunt de natură obișnuită, iar numărul mediu de evenimente pe unitatea de timp este constant și nu depinde de timp.
Fluxul de evenimente este numit curge fara consecinte, dacă pentru oricare două secțiuni de timp care nu se suprapun și (vezi Fig. 2) numărul de evenimente care cad pe una dintre ele nu depinde de câte evenimente cad pe celălalt. Cu alte cuvinte, aceasta înseamnă că evenimentele care formează fluxul apar în anumite momente în timp independent unul de altulși fiecare sunt cauzate de propriile sale cauze.
Fluxul de evenimente este numit comun, dacă evenimentele apar în el unul câte unul, și nu în grupuri de mai multe simultan.
Fluxul de evenimente este numit cel mai simplu (sau staționar Poisson), dacă are trei proprietăți simultan:
1) staționar;
2) obișnuit;
3) nu are consecințe.
Cel mai simplu flux are cea mai simplă descriere matematică. Ea joacă același rol special între fluxuri ca și legea distribuției normale între alte legi de distribuție. Și anume, la suprapunerea unui număr suficient de mare de fluxuri independente, staționare și obișnuite (comparabile între ele ca intensitate), se obține un flux apropiat de cel mai simplu.
Pentru cel mai simplu debit cu interval de intensitate Tîntre evenimente învecinate are o așa-numită distribuție exponențială cu densitate:
unde este parametrul legii exponenţiale.
Pentru o variabilă aleatorie T, care are o distribuție exponențială, așteptarea matematică este reciproca parametrului, iar abaterea standard este egală cu așteptarea matematică:
Luând în considerare procesele Markov cu stări discrete și timp continuu, se presupune că toate tranzițiile sistemului S de la stare la stare apar sub influența fluxurilor de evenimente simple (fluxuri de apel, fluxuri de defecțiuni, fluxuri de recuperare etc.). Dacă toate fluxurile de evenimente transferă sistemul S de la starea la starea cea mai simplă, atunci procesul care are loc în sistem va fi Markovian.
Deci, un sistem în stare este afectat de un simplu flux de evenimente. De îndată ce apare primul eveniment al acestui flux, sistemul „sare” de la o stare la alta (pe graficul de stare de-a lungul săgeții).
Pentru claritate, pe graficul stării sistemului, pentru fiecare arc, este indicată intensitatea fluxului de evenimente care mișcă sistemul de-a lungul acestui arc (săgeată). - intensitatea fluxului de evenimente care transferă sistemul din stare în . Un astfel de grafic se numește marcat. Pentru exemplul nostru, graficul etichetat este prezentat în Fig. 3.
Orez. 3. Graficul de stare a sistemului etichetat
În această figură - intensitatea fluxului de defecțiune; - intensitatea fluxului de recuperare.
Presupunem că timpul mediu de reparare a unei mașini nu depinde de faptul dacă o mașină este reparată sau ambele simultan. Aceste. Fiecare mașină este reparată de un specialist separat.
Lăsați sistemul să fie în stat S 0 . În stare S 1 se traduce prin fluxul de defecțiuni ale primei mașini. Intensitatea sa este egală cu:
unde este timpul mediu de funcționare fără defecțiuni a primei mașini.
De la stat S 1 in S 0 sistemul este transferat prin fluxul de „finalizări de reparații” al primei mașini. Intensitatea sa este egală cu:
unde este timpul mediu de reparație pentru prima mașină.
Intensitățile fluxurilor de evenimente care transferă sistemul de-a lungul tuturor arcelor graficului sunt calculate într-un mod similar. Având la dispoziție un grafic etichetat al stărilor sistemului, construim model matematic a acestui proces.
Lăsați sistemul luat în considerare S are -stări posibile. Probabilitatea celei de-a-a stări este probabilitatea ca în momentul de timp, sistemul să fie în starea. Este evident că pentru orice moment în timp suma tuturor probabilităților de stare este egală cu unu:
Pentru a găsi toate probabilitățile stărilor în funcție de timp, compuneți și rezolvați Ecuații Kolmogorov– un tip special de ecuație în care funcțiile necunoscute sunt probabilitățile stărilor. Regula pentru alcătuirea acestor ecuații este prezentată aici fără dovezi. Dar înainte de a o introduce, să explicăm conceptul probabilitatea finală de stare .
Ce se va întâmpla cu probabilitățile de stare la? Se vor strădui ei pentru vreo limită? Dacă aceste limite există și nu depind de starea inițială a sistemului, atunci ele sunt numite probabilitățile de stare finală .
unde este numărul finit de stări ale sistemului.
Probabilități de stare finală– acestea nu mai sunt cantități variabile (funcții ale timpului), ci numere constante. Este evident că:
Probabilitatea de stare finală este în esență timpul relativ mediu în care sistemul rămâne în această stare.
De exemplu, sistemul S are trei stări S 1 , S 2 și S 3. Probabilitățile lor finale sunt, respectiv, 0,2; 0,3 și 0,5. Aceasta înseamnă că un sistem în stare limită staționară își petrece în medie 2/10 din timpul său în stat S 1, 3/10 – capabil S 2 și 5/10 – capabil S 3 .
Regula pentru alcătuirea sistemului de ecuații Kolmogorov: în fiecare ecuație a sistemului pe partea stângă este probabilitatea finală a unei stări date, înmulțită cu intensitatea totală a tuturor fluxurilor, conducând din această stare, A în dreptul lui piese– suma produselor intensităților tuturor fluxurilor, incluse în -a stare, asupra probabilităţilor stărilor din care provin aceste fluxuri.
Folosind această regulă, scriem un sistem de ecuații pentru exemplul nostru :
.
Acest sistem de patru ecuații cu patru necunoscute, s-ar părea, poate fi rezolvat complet. Dar aceste ecuații sunt omogene (nu au termen liber) și, prin urmare, determină necunoscutele doar până la un factor arbitrar. Cu toate acestea, puteți utiliza condiția de normalizare: 
și folosiți-l pentru a rezolva sistemul. În acest caz, una (oricare) ecuații poate fi aruncată (urmează ca o consecință a celorlalte).
Continuarea exemplului. Fie intensitățile debitului egale cu: .
Renunțăm la a patra ecuație și adăugăm în schimb o condiție de normalizare:
.
Aceste. în modul de limitare, staționar sistemul Sîn medie 40% din timp va fi petrecut în stare de S 0 (ambele utilaje sunt operaționale), 20% - în stare bună S 1 (prima mașină este în curs de reparare, a doua funcționează), 27% - în stare S 2 (a doua mașină este în curs de reparare, prima funcționează), 13% - în stare S 3 (ambele utilaje sunt în curs de reparare). Cunoașterea acestor probabilități finale poate ajuta la estimarea eficienței medii a sistemului și a volumului de muncă al organelor de reparare.
Lasă sistemul S capabil S 0 (complet operațional) aduce un venit de 8 unități convenționale pe unitatea de timp, capabil S 1 – venit 3 unitati conventionale, capabil S 2 – venit 5 unitati conventionale, capabil S 3 – nu generează venituri. Apoi, în modul limitativ, staționar, venitul mediu pe unitatea de timp va fi egal cu: unități convenționale.
Mașina 1 este reparată într-o fracțiune de timp egală cu: . Mașina 2 este reparată într-o fracțiune de timp egală cu: . Apare problema de optimizare. Chiar dacă putem reduce timpul mediu de reparare a primei sau a doua mașini (sau ambelor), ne va costa o anumită sumă. Întrebarea este: veniturile crescute asociate cu reparațiile mai rapide vor plăti costurile crescute de reparații? Va trebui să rezolvați un sistem de patru ecuații cu patru necunoscute.
Exemple de sisteme de așteptare (QS): centrale telefonice, ateliere de reparații, case de bilete, birouri de informații, mașini-unelte și alte sisteme tehnologice, sisteme de control ale sistemelor flexibile de producție etc.
Fiecare QS constă dintr-un anumit număr de unități de serviciu, care sunt numite canale de servicii(acestea sunt mașini, cărucioare de transport, roboți, linii de comunicare, casierii, vânzători etc.). Fiecare QS este conceput pentru a servi un fel de fluxul de aplicații(cerințe) sosind la unele momente aleatorii în timp.
Servirea cererii continuă pentru un timp, în general, aleatoriu, după care canalul este eliberat și gata să primească următoarea solicitare. Natura aleatorie a fluxului de aplicații și a timpului de service duce la faptul că, în anumite perioade de timp, la intrarea QS-ului se acumulează un număr excesiv de mare de aplicații (fie pun la coadă, fie lasă QS-ul neservit). În alte perioade, sistemul va funcționa cu subîncărcare sau va fi complet inactiv.
Procesul de operare QS este un proces aleatoriu cu stări discrete și timp continuu. Starea QS-ului se schimbă brusc atunci când apar anumite evenimente (sosirea unei noi aplicații, încetarea serviciului, momentul în care o aplicație obosită de așteptare iese din coadă).
Subiectul teoriei cozilor– construirea de modele matematice care conectează condițiile de funcționare date ale QS (numărul de canale, productivitatea acestora, regulile de funcționare, natura fluxului de solicitări) cu caracteristicile care ne interesează - indicatori ai eficacității QS. Acești indicatori descriu capacitatea CMO de a face față fluxului de aplicații. Acestea pot fi: numărul mediu de aplicații deservite de QS pe unitatea de timp; numărul mediu de canale ocupate; numărul mediu de aplicații în coadă; timpul mediu de așteptare pentru serviciu etc.
Analiza matematică a muncii unui QS este mult facilitată dacă procesul acestei lucrări este Markovian, adică. fluxurile de evenimente care transferă sistemul de la stat la stat sunt cele mai simple. În caz contrar, descrierea matematică a procesului devine foarte complicată și rareori este posibil să o aducem la dependențe analitice specifice. În practică, procesele non-Markov sunt reduse la procese Markov cu aproximare. Următorul aparat matematic descrie procesele Markov.
Prima diviziune (pe baza prezenței cozilor):
1. QS cu defecțiuni;
2. Coadă cu o coadă.
În QS cu eșecuri o aplicație primită într-un moment în care toate canalele sunt ocupate este respinsă, părăsește QS și nu este deservită în viitor.
În SMO cu o coadă o aplicație care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci se pune la coadă și așteaptă să fie servită oportunitatea.
QS cu cozi sunt subdivizateîn diferite tipuri, în funcție de modul în care este organizată coada - limitat sau nelimitat. Restricțiile pot viza atât lungimea cozii, cât și timpul de așteptare, „disciplina de serviciu”.
Deci, de exemplu, sunt luate în considerare următoarele QS:
· CMO cu cereri nerăbdătoare (lungimea cozii și timpul de service sunt limitate);
· QS cu serviciu prioritar, de ex. unele cereri sunt procesate în afara rândului etc.
În plus, QS-urile sunt împărțite în QS-uri deschise și QS-uri închise.
Într-un QS deschis caracteristicile fluxului de aplicații nu depind de starea QS-ului în sine (cate canale sunt ocupate). Într-un QS închis– depind. De exemplu, dacă un lucrător deservește un grup de mașini care necesită ajustare din când în când, atunci intensitatea fluxului de „cereri” de la mașini depinde de câte dintre ele sunt deja operaționale și așteaptă ajustarea.
Clasificarea SMO este departe de a fi limitată la soiurile de mai sus, dar acest lucru este suficient.
Să considerăm cel mai simplu QS cu așteptare - un sistem cu un singur canal (n - 1), care primește un flux de solicitări cu intensitate; intensitatea serviciului (adică, în medie, un canal ocupat continuu va emite solicitări deservite pe unitate (de timp). O solicitare primită la un moment în care canalul este ocupat este pusă în coadă și așteaptă serviciul.
Sistem cu lungime limitată la coadă. Să presupunem mai întâi că numărul de locuri din coadă este limitat de numărul m, adică. dacă o aplicație ajunge într-un moment în care există deja m-aplicații în coadă, ea lasă sistemul neservit. În viitor, prin direcționarea m către infinit, vom obține caracteristicile unui QS cu un singur canal fără restricții privind lungimea cozii.
Vom numerota stările QS-ului în funcție de numărul de aplicații din sistem (atât în curs de service, cât și în așteptare):
Canalul este gratuit;
Canalul este ocupat, nu există coadă;
Canalul este ocupat, o cerere este în coadă;
Canalul este ocupat, aplicațiile k-1 sunt în coadă;
Canalul este ocupat, aplicațiile sunt la coadă.
GSP este prezentat în Fig. 4. Toate intensitățile fluxurilor de evenimente care se deplasează în sistem de-a lungul săgeților de la stânga la dreapta sunt egale cu și de la dreapta la stânga - . Într-adevăr, fluxul de solicitări mută sistemul de-a lungul săgeților de la stânga la dreapta (de îndată ce sosește o solicitare, sistemul trece la următoarea stare), de la dreapta la stânga - fluxul de „eliberări” ale unui canal ocupat, care are o intensitate (de îndată ce următoarea solicitare este deservită, canalul fie va deveni liber, fie va reduce numărul de aplicații din coadă).
Orez. 4. QS cu un singur canal cu așteptare
Arată în Fig. Diagrama 4 este o diagramă a reproducerii și a morții. Să scriem expresii pentru probabilitățile limită ale stărilor:
(5)
sau folosind: :
(6)
Ultima linie din (6) conține o progresie geometrică cu primul termen 1 și numitorul p, din care obținem:
(7)
în legătură cu care probabilitățile limitative iau forma:
(8).
Expresia (7) este valabilă numai pentru< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Să determinăm caracteristicile QS: probabilitatea de eșec, debitul relativ q, debitul absolut A, lungimea medie a cozii, numărul mediu de aplicații asociate sistemului, timpul mediu de așteptare în coadă, timpul mediu petrecut de o aplicație în QS .
Probabilitatea de eșec. Evident, aplicația este respinsă doar dacă canalul este ocupat și toate locurile t din coadă sunt de asemenea ocupate:
(9).
Lățime de bandă relativă:
(10).
Lungimea medie a cozii. Să găsim numărul mediu de aplicații din coadă ca așteptarea matematică a unei variabile aleatoare discrete R-număr de aplicații din coadă:
Cu probabilitate există o aplicație în coadă, cu probabilitate sunt două aplicații, în general cu probabilitate sunt k-1 aplicații în coadă etc., din care:
(11).
Deoarece , suma din (11) poate fi interpretată ca o derivată a sumei progresiei geometrice:
Înlocuind această expresie în (11) și folosind din (8), obținem în final:
(12).
Numărul mediu de aplicații din sistem. În continuare, obținem o formulă pentru numărul mediu de solicitări asociate sistemului (atât în coadă, cât și deservite). Deoarece , unde este numărul mediu de aplicații aflate în serviciu și k este cunoscut, rămâne de determinat . Deoarece există un singur canal, numărul de cereri deservite poate fi 0 (cu probabilitate ) sau 1 (cu probabilitate 1 - ), din care:
.
iar numărul mediu de aplicații asociate cu QS este:
(13).
Timp mediu de așteptare pentru o aplicație în coadă. Să o notăm; dacă o solicitare intră în sistem la un moment dat, atunci cu probabilitate canalul de serviciu nu va fi ocupat și nu va trebui să aștepte la coadă (timpul de așteptare este zero). Cel mai probabil, ea va intra în sistem în timp ce o cerere este servită, dar nu va fi nicio coadă în fața ei, iar cererea va aștepta începerea deservirii acesteia pentru o perioadă de timp (timpul mediu de deservire a uneia cerere). Există probabilitatea ca o altă aplicație să fie în coadă înainte de aplicația luată în considerare, iar timpul mediu de așteptare va fi egal cu , etc.
Dacă k=m+1, adică. când o cerere nou sosită găsește canalul de serviciu ocupat și m-cereri în coadă (probabilitatea acestui lucru), atunci în acest caz cererea nu se află în coadă (și nu este servită), deci timpul de așteptare este zero. Timpul mediu de așteptare va fi:
dacă substituim expresii pentru probabilitățile (8) aici, obținem:
(14).
Aici folosim relațiile (11), (12) (derivată a unei progresii geometrice), precum și din (8). Comparând această expresie cu (12), observăm că, cu alte cuvinte, timpul mediu de așteptare este egal cu numărul mediu de cereri din coadă împărțit la intensitatea fluxului de aplicații.
(15).
Timpul mediu de păstrare a unei aplicații în sistem. Să notăm așteptarea matematică a unei variabile aleatoare ca timpul în care o cerere rămâne în QS, care este suma timpului mediu de așteptare în coadă și timpul mediu de serviciu. Dacă încărcarea sistemului este de 100%, evident, în caz contrar:
.
Exemplul 1. O benzinărie (benzinărie) este o stație de benzină cu un canal de serviciu (o pompă).
Zona de la stație permite nu mai mult de trei mașini să fie la rând pentru realimentare în același timp (m = 3). Dacă sunt deja trei mașini în coadă, următorul vagon care sosește în stație nu se alătură la coadă. Fluxul de mașini care sosesc pentru realimentare are o intensitate = 1 (mașină pe minut). Procesul de realimentare durează în medie 1,25 minute.
Defini:
probabilitatea de eșec;
capacitatea relativă și absolută a benzinăriilor;
numărul mediu de mașini care așteaptă să realimenteze;
numărul mediu de mașini la o benzinărie (inclusiv cele deservite);
timpul mediu de așteptare pentru o mașină la coadă;
timpul mediu pe care îl petrece o mașină la o benzinărie (inclusiv service).
Cu alte cuvinte, timpul mediu de așteptare este egal cu numărul mediu de cereri din coadă împărțit la intensitatea fluxului de aplicații.
Găsim mai întâi intensitatea redusă a fluxului de aplicații: =1/1,25=0,8; =1/0,8=1,25.
Conform formulelor (8):
Probabilitatea de eșec este de 0,297.
Capacitatea relativă a QS: q=1-=0,703.
Debit absolut al QS: A==0,703 mașini pe minut.
Găsim numărul mediu de mașini din coadă folosind formula (12):
aceste. Numărul mediu de mașini care așteaptă la coadă pentru a umple benzinăria este de 1,56.
Adăugând la această valoare numărul mediu de vehicule în service:
obținem numărul mediu de mașini asociate unei benzinării.
Timp mediu de așteptare pentru o mașină la coadă conform formulei (15):
Adăugând la această valoare, obținem timpul mediu pe care îl petrece o mașină la o benzinărie:
Sisteme cu așteptare nelimitată. În astfel de sisteme, valoarea lui m nu este limitată și, prin urmare, caracteristicile principale pot fi obținute prin trecerea la limită în expresiile obținute anterior (5), (6) etc.
Rețineți că numitorul din ultima formulă (6) este suma unui număr infinit de termeni ai progresiei geometrice. Această sumă converge atunci când progresia este în scădere infinită, adică. la<1.
Se poate dovedi că<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
Dacă, atunci relațiile (8) iau forma:
(16).
Dacă nu există restricții privind lungimea cozii, fiecare aplicație care intră în sistem va fi deservită, deci q=1, 
.
Obținem numărul mediu de aplicații din coadă de la (12) la:
Numărul mediu de aplicații în sistem conform formulei (13) la:
.
Timpul mediu de așteptare se obține din formula (14) cu:
.
În cele din urmă, timpul mediu pe care o aplicație rămâne în QS este:
Sistem cu lungime limitată la coadă. Să considerăm un canal QS cu așteptare, care primește un flux de solicitări cu intensitate; intensitatea serviciului (pentru un canal); numărul de locuri în coadă.
Stările sistemului sunt numerotate în funcție de numărul de solicitări asociate sistemului:
fara coada:
Toate canalele sunt gratuite;
Un canal este ocupat, restul sunt libere;
-canale sunt ocupate, restul nu;
Toate canalele sunt ocupate, nu există canale libere;
exista o coada:
Toate canalele n sunt ocupate; o aplicație este în coadă;
Toate n-canalele, r-cererile din coada sunt ocupate;
Toate n-canalele, r-cererile din coadă sunt ocupate.
GSP este prezentat în Fig. 17. Fiecare săgeată este marcată cu intensitățile corespunzătoare ale fluxurilor de evenimente. De-a lungul săgeților de la stânga la dreapta, sistemul este întotdeauna transferat de același flux de cereri cu o intensitate de
Orez. 17. QS multicanal cu așteptare
Graficul este tipic pentru procesele de reproducere și moarte, pentru care soluția a fost obținută anterior. Să scriem expresii pentru probabilitățile limită ale stărilor folosind notația: (aici folosim expresia pentru suma unei progresii geometrice cu numitor).
Astfel, au fost găsite toate probabilitățile de stare.
Să determinăm caracteristicile de performanță ale sistemului.
Probabilitatea de eșec. O solicitare primită este respinsă dacă toate canalele n și toate locurile m din coadă sunt ocupate:
(18)
Debitul relativ completează probabilitatea de eșec la unul:
Debit absolut al QS:
(19)
Numărul mediu de canale ocupate. Pentru QS cu refuzuri, acesta a coincis cu numărul mediu de cereri din sistem. Pentru un QS cu o coadă, numărul mediu de canale ocupate nu coincide cu numărul mediu de aplicații din sistem: ultima valoare diferă de prima prin numărul mediu de aplicații din coadă.
Să notăm numărul mediu de canale ocupate cu . Fiecare canal ocupat servește în medie revendicări A pe unitatea de timp, iar QS în ansamblu servește în medie cereri A pe unitatea de timp. Împărțind unul la altul, obținem:
Numărul mediu de cereri din coadă poate fi calculat direct ca așteptarea matematică a unei variabile aleatoare discrete:
(20)
Din nou (expresia dintre paranteze) apare derivata sumei progresiei geometrice (vezi mai sus (11), (12) - (14)), folosind relația pentru aceasta, obținem:
Numărul mediu de aplicații în sistem:
Timp mediu de așteptare pentru o aplicație în coadă. Să luăm în considerare o serie de situații care diferă în funcție de starea în care o cerere nou sosită va găsi sistemul și de cât timp va trebui să aștepte pentru service.
Dacă o solicitare nu găsește toate canalele ocupate, nu va trebui să aștepte deloc (termenii corespunzători din așteptarea matematică sunt egali cu zero). Dacă o solicitare sosește într-un moment în care toate n-canalele sunt ocupate și nu există coadă, va trebui să aștepte în medie un timp egal cu (deoarece „fluxul de lansare” al -canalelor are o intensitate de ). Dacă o solicitare găsește toate canalele ocupate și o solicitare în fața ei în coadă, va trebui să aștepte în medie o perioadă de timp (pentru fiecare cerere din față), etc. Dacă o solicitare se găsește într-o coadă de - cereri, va trebui să aștepte în medie timp Dacă o cerere nou sosită găsește m-cereri deja în coadă, atunci nu va aștepta deloc (dar nu va fi servită). Găsim timpul mediu de așteptare înmulțind fiecare dintre aceste valori cu probabilitățile corespunzătoare:
(21)
La fel ca și în cazul unui QS cu un singur canal cu așteptare, observăm că această expresie diferă de expresia pentru lungimea medie a cozii (20) doar prin factorul , i.e.
.
Timpul mediu pe care o cerere rămâne în sistem, precum și pentru un QS cu un singur canal, diferă de timpul mediu de așteptare cu timpul mediu de serviciu înmulțit cu debitul relativ:
.
Sisteme cu lungime nelimitată la coadă. Am considerat un canal QS cu așteptare, când nu pot fi în coadă mai mult de m-cereri în același timp.
La fel ca înainte, atunci când se analizează sisteme fără restricții, este necesar să se ia în considerare relațiile obținute pentru .
Obținem probabilitățile stărilor din formule trecând la limită (la ). Rețineți că suma progresiei geometrice corespunzătoare converge la și diverge la >1. Presupunând că<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Probabilitatea de eșec, debit relativ și absolut. Deoarece fiecare cerere va fi deservită mai devreme sau mai târziu, caracteristicile debitului QS vor fi:
Numărul mediu de aplicații din coadă se obține din (20):
,
iar timpul mediu de așteptare este de la (21):
.
Numărul mediu de canale ocupate, ca și înainte, este determinat prin debitul absolut:
.
Numărul mediu de aplicații asociate cu QS este definit ca numărul mediu de aplicații din coadă plus numărul mediu de aplicații aflate în serviciu (numărul mediu de canale ocupate):
Exemplul 2. O benzinărie cu două pompe (n = 2) deservește un flux de mașini cu o intensitate de =0,8 (mașini pe minut). Durata medie de service pe mașină:
Nu există altă benzinărie în zonă, așa că șirul de mașini din fața benzinăriei poate crește aproape nelimitat. Găsiți caracteristicile QS.
Din moment ce<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
etc.
Vom găsi numărul mediu de canale ocupate împărțind capacitatea absolută a QS A = = 0,8 la intensitatea serviciului = 0,5:
Probabilitatea să nu fie coadă la o benzinărie va fi:
Numărul mediu de mașini în coadă:
Numărul mediu de mașini la benzinării:
Timp mediu de așteptare la coadă:
Timpul mediu pe care îl petrece o mașină la o benzinărie:
QS cu timp de așteptare limitat. Anterior, am considerat sisteme cu așteptare limitată doar de lungimea cozii (numărul de m-cereri simultan în coadă). Într-un astfel de QS, o aplicație care a crescut într-o coadă nu o părăsește până nu așteaptă service-ul. În practică, există și alte tipuri de QS în care o aplicație, după ce a așteptat ceva timp, poate părăsi coada (așa-numitele aplicații „nerăbdătoare”).
Să considerăm un QS de acest tip, presupunând că constrângerea timpului de așteptare este o variabilă aleatorie.
Să presupunem că există un QS de așteptare pe canale n în care numărul de locuri în coadă este nelimitat, dar timpul în care o cerere rămâne în coadă este o variabilă aleatorie cu o valoare medie, astfel, fiecare cerere din coadă este supus unui fel de „flux de îngrijire” Poisson cu intensitate:
Dacă acest flux este Poisson, atunci procesul care are loc în QS va fi Markovian. Să găsim probabilitățile de stare pentru aceasta. Numerotarea stărilor sistemului este asociată cu numărul de aplicații din sistem - atât deservite, cât și de stat la coadă:
fara coada:
Toate canalele sunt gratuite;
Un canal este ocupat;
Două canale sunt ocupate;
Toate canalele n sunt ocupate;
exista o coada:
Toate canalele n sunt ocupate, o cerere este în coadă;
Toate canalele n sunt ocupate, cererile r sunt în coadă etc.
Graficul stărilor și tranzițiilor sistemului este prezentat în Fig. 23.
Orez. 23. QS cu timp de așteptare limitat
Să marchem acest grafic ca înainte; toate săgețile care conduc de la stânga la dreapta vor indica intensitatea fluxului de aplicații. Pentru statele fără coadă, săgețile care duc de la ele de la dreapta la stânga vor indica, ca și înainte, intensitatea totală a fluxului care deservește toate canalele ocupate. În ceea ce privește stările cu coadă, săgețile care duc de la ele de la dreapta la stânga vor avea intensitatea totală a fluxului de serviciu al tuturor canalelor n plus intensitatea corespunzătoare a fluxului de plecări din coadă. Dacă în coadă există aplicații r, atunci intensitatea totală a fluxului de plecări va fi egală cu .
După cum se poate observa din grafic, există un model de reproducere și moarte; folosind expresii generale pentru probabilitățile limită ale stărilor din această schemă (folosind notații abreviate, scriem:
(24)
Să notăm câteva caracteristici ale unui QS cu așteptare limitată în comparație cu QS-ul considerat anterior cu cereri „pacient”.
Dacă lungimea cozii nu este limitată și cererile sunt „răbdătoare” (nu părăsiți coada), atunci regimul limită staționar există doar în cazul (la progresia geometrică infinită corespunzătoare diverge, ceea ce corespunde fizic creșterii nelimitate al cozii de la ).
Dimpotrivă, într-un QS cu cereri „nerăbdătoare” care părăsesc coada mai devreme sau mai târziu, se realizează întotdeauna modul de service stabilit la, indiferent de intensitatea redusă a fluxului de cereri. Aceasta rezultă din faptul că seria pentru în numitorul formulei (24) converge pentru orice valori pozitive ale și .
Pentru un QS cu cereri „nerăbdătoare”, conceptul de „probabilitate de eșec” nu are sens - fiecare solicitare este în linie, dar poate să nu aștepte serviciul, plecând din timp.
Debit relativ, numărul mediu de cereri din coadă. Capacitatea relativă q a unui astfel de QS poate fi calculată după cum urmează. Evident, toate aplicațiile vor fi deservite, cu excepția celor care părăsesc coada înainte de program. Să calculăm numărul mediu de aplicații care părăsesc coada mai devreme. Pentru a face acest lucru, calculăm numărul mediu de aplicații din coadă:
Fiecare dintre aceste aplicații este supusă unui „flux de plecări” cu o intensitate de . Aceasta înseamnă că din numărul mediu de -aplicații din coadă, în medie, -aplicațiile vor pleca fără a aștepta serviciul, -aplicațiile pe unitatea de timp și în total pe unitatea de timp, în medie -aplicațiile vor fi servite. Capacitatea relativă a QS va fi:
Obținem în continuare numărul mediu de canale ocupate împărțind lățimea de bandă absolută A la:
(26)
Numărul mediu de aplicații în coadă. Relația (26) vă permite să calculați numărul mediu de aplicații din coadă fără să însumați seria infinită (25). Din (26) obținem:
iar numărul mediu de canale ocupate incluse în această formulă poate fi găsit ca așteptarea matematică a unei variabile aleatoare Z, luând valori 0, 1, 2,..., n cu probabilități ,:
În concluzie, observăm că dacă în formulele (24) mergem la limita la (sau, ceea ce este același, la ), atunci se vor obține formulele (22), adică aplicațiile „nerăbdătoare” vor deveni „răbdătoare”.
Până acum am luat în considerare sisteme în care fluxul de intrare nu este în niciun fel legat de fluxul de ieșire. Astfel de sisteme se numesc buclă deschisă. În unele cazuri, solicitările deservite sunt din nou primite la intrare după o întârziere. Astfel de QS-uri sunt numite închise. O clinică care deservește o zonă dată, o echipă de muncitori repartizată unui grup de mașini, sunt exemple de sisteme închise.
Într-un QS închis circulă același număr finit de cerințe potențiale. Până când o cerință potențială a fost realizată ca cerere de serviciu, se consideră că se află într-un bloc de întârziere. În momentul implementării, acesta intră în sistem propriu-zis. De exemplu, lucrătorii întrețin un grup de mașini. Fiecare mașină este o cerință potențială, transformându-se într-una reală în momentul defecțiunii sale. În timp ce mașina funcționează, se află în blocul de întârziere, iar din momentul defecțiunii până la sfârșitul reparației, se află în sistemul propriu-zis. Fiecare lucrător este un canal de servicii.
Lasă n- numărul de canale de servicii, s- numărul de aplicații potențiale, n <s , - intensitatea fluxului de aplicații pentru fiecare cerință potențială, μ - intensitatea serviciului:
Probabilitatea de oprire a sistemului este determinată de formulă
R
0
= 
.
Probabilitățile finale ale stărilor sistemului:
Pk= la k
Numărul mediu de canale ocupate este exprimat prin aceste probabilități
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) sau
=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Folosind aceasta găsim debitul absolut al sistemului:
precum și numărul mediu de aplicații din sistem
M=s- =s- .
Exemplul 1. Intrarea unui QS cu trei canale cu defecțiuni primește un flux de solicitări cu o intensitate =4 solicitări pe minut, timp pentru deservirea unei cereri de către un canal t obs =1/μ =0,5 min. Din punct de vedere al capacității QS, este profitabil să forțați toate cele trei canale să depună cereri de serviciu simultan, iar timpul mediu de service este redus de trei ori? Cum va afecta acest lucru timpul mediu petrecut de o aplicație în CMO?
Soluţie. Găsim probabilitatea de oprire a unui QS cu trei canale folosind formula
ρ = /μ =4/2=2, n=3,
P 0 = = = 0,158.
Probabilitatea de eșec este determinată de formula:
P deschis = P n ==
P deschis = 0,21.
Debit relativ al sistemului:
R obsl = 1-R deschis 1-0,21=0,79.
Debitul absolut al sistemului:
A= P obsl 3,16.
Numărul mediu de canale ocupate este determinat de formula:
1.58, cota de canale ocupate de service,
q = 0,53.
Timpul mediu pe care o aplicație rămâne în QS se găsește ca probabilitatea ca cererea să fie acceptată pentru serviciu, înmulțită cu timpul mediu de serviciu: t SMO 0,395 min.
Combinând toate cele trei canale într-unul singur, obținem un sistem cu un singur canal cu parametri μ= 6, ρ= 2/3. Pentru un sistem cu un singur canal, probabilitatea de oprire este:
R 0 = = =0,6,
probabilitatea de eșec:
P deschis =ρ P 0 = = 0,4,
debit relativ:
R obsl = 1-R deschis =0,6,
debit absolut:
A=P obs =2,4.
t SMO =P obsl= =0,1 min.
Ca urmare a combinării canalelor într-unul singur, debitul sistemului a scăzut pe măsură ce a crescut probabilitatea de defecțiune. Timpul mediu petrecut de o aplicație în sistem a scăzut.
Exemplul 2. Intrarea unui QS cu trei canale cu o coadă nelimitată primește un flux de solicitări cu o intensitate =4 aplicații pe oră, timp mediu de service pentru o aplicație t=1/μ=0,5 h Găsiți indicatorii de performanță a sistemului.
Pentru sistemul luat în considerare n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
Găsim numărul mediu de aplicații din coadă folosind formula:
L
=
.
L = = .
Calculăm timpul mediu de așteptare pentru o aplicație în coadă folosind formula:
t= = 0,22 ore.
Timpul mediu de păstrare a unei aplicații în sistem:
T=t+ 0,22+0,5=0,72.
Exemplul 3. În salonul de coafură lucrează 3 coafori, iar în sala de așteptare sunt 3 scaune. Fluxul de clienți este intens =12 clienți pe oră. Timp mediu de service t obsl =20 min. Determinați debitul relativ și absolut al sistemului, numărul mediu de scaune ocupate, lungimea medie a cozii, timpul mediu pe care clientul îl petrece la coafor.
Pentru această sarcină n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. Probabilitatea de oprire este determinată de formula:
R
0
=
.
P
0
= 
0,012.
Probabilitatea de refuz al serviciului este determinată de formulă
P deschis =P n+m = .
P deschide =Pn + m 0,307.
Capacitatea relativă a sistemului, adică probabilitate de serviciu:
P obsl =1-P deschis 1-0,307=0,693.
Debit absolut:
A= P obsl 12 .
Numărul mediu de canale ocupate:
.
Lungimea medie a cozii este determinată de formula:
L
=
L= 
1,56.
Timp mediu de așteptare pentru serviciul la coadă:
t= h.
Numărul mediu de cereri către CMO:
M=L + .
Timpul mediu pe care o aplicație rămâne în CMO:
T=M/ 0,36 ore
Exemplul 4. Un muncitor operează 4 mașini. Fiecare mașină eșuează cu intensitate =0,5 defecțiuni pe oră, timp mediu de reparație t rem=1/μ=0,8 h. Determinați debitul sistemului.
Această problemă consideră un QS închis, μ =1,25, ρ=0,5/1,25=0,4. Probabilitatea de oprire a lucrătorului este determinată de formula:
R
0
=
.
P
0
= 
.
Probabilitatea angajării lucrătorilor R zan = 1-P 0 . A=( 1-P 0 )μ =0,85μ mașini pe oră.
Sarcină:
Doi muncitori operează un grup de patru mașini. Opririle unei mașini de lucru au loc în medie după 30 de minute. Timpul mediu de configurare este de 15 minute. Timpul de funcționare și de configurare este distribuit conform unei legi exponențiale.
Găsiți ponderea medie a timpului liber pentru fiecare lucrător și timpul mediu de funcționare al mașinii.
Găsiți aceleași caracteristici pentru un sistem în care:
a) fiecărui muncitor i se atribuie două utilaje;
b) doi muncitori întrețin întotdeauna mașina împreună, și cu intensitate dublă;
c) singura mașină defectă este întreținută de ambii muncitori simultan (cu intensitate dublă), iar când mai apare cel puțin o altă mașină defectă, aceștia încep să funcționeze separat, fiecare deservind câte o mașină (descrieți mai întâi sistemul din punct de vedere al proceselor de moartea şi naşterea).
Soluţie:
Următoarele stări ale sistemului S sunt posibile:
S 0 – toate mașinile sunt operaționale;
S 1 – 1 utilaj este in reparatie, restul sunt in stare buna de functionare;
S 2 – 2 utilaj este în reparație, restul sunt în stare de funcționare;
Mașina S 3 – 3 este în curs de reparație, restul sunt în stare de funcționare;
Mașina S 4 – 4 este în curs de reparație, restul sunt în stare bună de funcționare;
S 5 – (1, 2) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;
S 6 – (1, 3) utilajele sunt în curs de reparare, restul sunt în stare de funcționare;
S 7 – (1, 4) utilajele sunt în reparație, restul sunt în stare de funcționare;
S 8 – (2, 3) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;
S 9 – (2, 4) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;
S 10 – (3, 4) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;
S 11 – (1, 2, 3) utilaje sunt în curs de reparare, 4 utilaj este în funcțiune;
S 12 – (1, 2, 4) utilaje sunt în curs de reparare, 3 utilaj este în funcțiune;
S 13 – (1, 3, 4) utilajele sunt în curs de reparare, utilajul 2 este în funcțiune;
S 14 – (2, 3, 4) utilaje sunt în curs de reparare, 1 utilaj este în funcțiune;
S 15 – toate utilajele sunt reparate.
Graficul stării sistemului...
Acest sistem S este un exemplu de sistem închis, deoarece fiecare mașină este o cerință potențială, transformându-se într-una reală în momentul defecțiunii sale. În timp ce mașina funcționează, se află în blocul de întârziere, iar din momentul defecțiunii până la sfârșitul reparației, se află în sistemul propriu-zis. Fiecare lucrător este un canal de servicii.
Dacă un muncitor este ocupat, el instalează μ-mașini pe unitate de timp, capacitatea sistemului:
Răspuns:
Ponderea medie a timpului liber pentru fiecare lucrător este ≈ 0,09.
Timp mediu de funcționare a mașinii ≈ 3,64.
a) Fiecărui lucrător i se atribuie două utilaje.
Probabilitatea de oprire a lucrătorului este determinată de formula:
Probabilitatea angajării lucrătorului:
Dacă un muncitor este ocupat, el instalează μ-mașini pe unitate de timp, capacitatea sistemului:
Răspuns:
Ponderea medie a timpului liber pentru fiecare lucrător este ≈ 0,62.
Timp mediu de funcționare a mașinii ≈ 1,52.
b) Doi lucrători întrețin întotdeauna mașina împreună și cu intensitate dublă.
c) Singura mașină defectă este întreținută de ambii muncitori deodată (cu intensitate dublă), iar când mai apare cel puțin o altă mașină defectă, aceștia încep să lucreze separat, fiecare deservind câte o mașină (descrieți mai întâi sistemul din punct de vedere al proceselor de moartea şi naşterea).
Comparație a 5 răspunsuri:
Cea mai eficientă modalitate de a organiza lucrătorii la mașini va fi versiunea inițială a sarcinii.
Exemple ale celor mai simple sisteme de așteptare (QS) au fost discutate mai sus. Termenul „protozoare” nu înseamnă „elementar”. Modelele matematice ale acestor sisteme sunt aplicabile și utilizate cu succes în calculele practice.
Posibilitatea aplicării teoriei deciziei în sistemele de așteptare este determinată de următorii factori:
1. Numărul de aplicații din sistem (care este considerat un QS) trebuie să fie destul de mare (masiv).
2. Toate cererile primite la intrarea QS trebuie să fie de același tip.
3. Pentru a calcula folosind formule, trebuie să cunoașteți legile care determină primirea cererilor și intensitatea procesării acestora. Mai mult, fluxurile de ordine trebuie să fie Poisson.
4. Structura QS, i.e. setul de cerințe de intrare și succesiunea procesării cererii trebuie să fie strict fixate.
5. Este necesar să se excludă subiecții din sistem sau să le descrie ca cerințe cu o intensitate constantă de procesare.
La restricțiile enumerate mai sus, mai putem adăuga una, care are un impact puternic asupra dimensiunii și complexității modelului matematic.
6. Numărul de priorități utilizate ar trebui să fie minim. Prioritățile aplicațiilor trebuie să fie constante, adică nu se pot schimba în timpul procesării în cadrul QS.
În cursul lucrării, obiectivul principal a fost atins - a fost studiat materialul principal de „QS cu timp de așteptare limitat” și „Closed QS”, care a fost stabilit de profesorul disciplinei academice. Ne-am familiarizat și cu aplicarea în practică a cunoștințelor dobândite, adică. consolidat materialul acoperit.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revoluție..
5) Fomin G.P. Metode și modele matematice în activități comerciale. M: Finanțe și Statistică, 2001.
6) Gmurman V.E. Teoria probabilității și statistica matematică. M: Liceu, 2001.
7) Sovetov B.A., Yakovlev S.A. Modelarea sistemelor. M: Liceu, 1985.
8) Lifshits A.L. Modelarea statistică a QS. M., 1978.
9) Ventzel E.S. Cercetare operațională. M: Nauka, 1980.
10) Ventzel E.S., Ovcharov L.A. Teoria probabilității și aplicațiile sale de inginerie. M: Nauka, 1988.
Fluxuri de evenimente Aceasta este o succesiune de evenimente care au loc unul după altul la anumite intervale de timp. T este timpul mediu dintre evenimentele învecinate. Dacă T=const, atunci evenimentele din flux sunt distribuite uniform. - intensitatea fluxului, adică numărul mediu de evenimente care au loc pe unitatea de timp.
Fluxuri de evenimente Staționare Numărul de evenimente care se încadrează pe orice interval de timp arbitrar nu depinde de poziția pe axa numerică, ci depinde doar de lățimea acesteia. Fără efect secundar Pentru oricare două intervale de timp care nu se suprapun, numărul de evenimente care se încadrează pe unul dintre ele nu depinde de câte evenimente au avut loc la un interval diferit Regular Opus fluxului fără efecte secundare (cu efect secundar)
Fluxuri de evenimente Obișnuit În orice moment în timp, are loc unul și un singur eveniment, adică probabilitatea apariției a două sau mai multe evenimente într-un interval de timp infinitezimal este neglijabilă în comparație cu probabilitatea apariției unui eveniment Poisson Non-staționar, flux obișnuit fără efect secundar Cel mai simplu Flux staționar, obișnuit fără efect secundar, pentru care numărul de evenimente care apar într-o perioadă de timp este distribuit conform legii lui Poisson, iar intervalele de timp dintre două evenimente consecutive sunt caracterizate printr-o distribuție exponențială. Acesta este un flux Poisson staționar.
Aplicație economică Operațiunile financiare și bancare moderne presupun rambursarea în rate a datoriilor și primirea periodică a veniturilor din investiții. Acest tip de secvență sau serie de plăți poate fi numit flux de plată. Un flux de plăți în care toți membrii sunt valori pozitive, iar intervalele de timp dintre plăți sunt aceleași, se numește chirie financiară. Chiria este succesiunea de primire a dobânzii la obligațiuni, a plăților pentru un împrumut de consum și a plăților în rate a primelor de asigurare. Caracteristicile fluxului de plată: intervalul dintre două plăți adiacente, probabilitatea de plată a plății, sunt utilizate pe scară largă în diverse calcule financiare. Fără ele, este imposibil să se dezvolte un plan de rambursare consistentă a datoriilor, să se măsoare eficiența financiară a proiectului, să se facă comparații sau să se modifice pragul de rentabilitate în termenii contractului.
Problemă Pentru a analiza modificările în timp ale mărimii fondului actual al unei bănci angajate în acordarea de împrumuturi pe termen lung, este important să aveți informații despre procesul de primire a plăților de împrumut către bancă. Observarea băncii în perioada anterioară a arătat că numărul de plăți primite de bancă pentru orice perioadă de timp nu depinde de momentul de la care a început numărătoarea inversă a perioadei de timp, ci depinde doar de durata acesteia. Numărul așteptat de plăți către bancă pe săptămână este de 2. Să examinăm probabilitatea ca banca să primească 7 plăți pe lună și să aflăm probabilitatea ca intervalul de timp dintre două plăți adiacente să fie mai mic de 2 zile.
Soluție În funcție de condițiile problemei, fluxul de plată poate fi considerat cel mai simplu cu intensitate = 2 (pe săptămână). Prin urmare, numărul de plăți primite pe o perioadă de timp = 4 săptămâni (1 lună) este distribuit conform legii lui Poisson. Intervalele de timp dintre două plăți consecutive în cel mai simplu flux au o lege de distribuție exponențială.
Soluție Fie X() o variabilă aleatoare discretă reprezentând numărul de plăți primite într-o perioadă de timp. Este distribuit conform legii lui Poisson. M(X)=D(X)= Atunci - probabilitatea ca exact m evenimente să apară în flux într-o perioadă de timp este egală cu Prin urmare, cu intensitatea fluxului de plăți =2, probabilitatea ca banca să primească 7 plăți pe lună (=4) (m=7 ) este egal cu
Soluție Fie o variabilă aleatoare continuă T intervalul de timp dintre oricare două plăți adiacente (evenimente ale celui mai simplu flux). Are o lege de distribuție exponențială. M(T)=1/ , D(T)=1/ 2 Atunci probabilitatea P(T
Probleme pentru rezolvarea independentă 1. De regulă, un student ajunge la stația de autobuz exact la ora 8 dimineața și, după ce s-a urcat în primul autobuz care ajunge în direcția universității, ajunge la timp la cursuri, care încep exact la ora 9 dimineața. Intervalele cu autobuzul sunt în medie de 10 minute, iar durata călătoriei cu autobuzul este de 30 de minute. Lasă fluxul autobuzului să fie cel mai simplu. Găsiți probabilitatea ca elevul să întârzie în continuare la curs.
Probleme pentru rezolvarea independentă 2. Fluxul de cereri care intră într-un anumit sistem de așteptare este suficient de modelat de cei mai simpli. La studierea datelor experimentale, au fost luate în considerare 200 de perioade de timp selectate aleatoriu de 2 minute în lungime. S-a dovedit că numărul celor în care nu s-a înregistrat o singură cerere a fost de 27. Aflați așteptarea matematică și abaterea standard a numărului de cereri în 1 oră.
Concepte de bază Prin sistemul S înțelegem orice set integral de elemente interconectate care nu poate fi împărțit în submulțimi independente. Dacă un sistem S își schimbă aleatoriu stările S(t) în timpul t, atunci se spune că are loc un proces aleatoriu în sistemul S. În orice moment de timp, sistemul se află doar într-una dintre stări, adică pentru orice moment de timp t există o stare unică Si astfel încât S(t) = Si. Setul de stări poate fi discret (starea tehnică a unui obiect: deservibil - defect, încărcat - inactiv; număr de personal; număr de obiecte care așteaptă la coadă pentru service) sau continuu (venit, volum de producție).
Concepte de bază În cazul unui set discret de stări, sistemul își schimbă stările brusc (instantaneu). În cazul unui set continuu de stări, tranziția sistemului are loc continuu (lini). În funcție de timpul în care sistemul rămâne în fiecare stare, se disting procese cu timp discret (o grilă de timp numerică artificială) și cu timp continuu (timp fizic, trecerea sistemului de la o stare la alta poate avea loc în orice moment). Un proces aleatoriu care are loc într-un sistem S se numește markovian dacă are proprietatea de a nu avea consecințe, constând în faptul că pentru fiecare moment de timp t 0 probabilitatea oricărei stări S(t) a sistemului S în viitor (la t>t 0) depinde numai de starea sa S(t 0) în prezent (la t=t 0) și nu depinde de cât și cât timp s-a dezvoltat acest proces în trecut (la t>t 0).
A. A. Markov (1856 - 1922) Andrei Andreevich Markov - Sr. - este un matematician rus remarcabil care a dezvoltat bazele teoriei proceselor aleatorii fără efecte secundare, care în matematică sunt numite procese Markov în onoarea sa. A. A. Markov, Sr., este cunoscut și ca a dat o justificare probabilistică pentru metoda celor mai mici pătrate (LSM), oferind una dintre dovezile teoremei limitei a teoriei probabilităților și multe altele.
Tipuri de procese Markov Stări discrete și timp discret (lanț Markov) Stări continue și timp discret (secvențe Markov) Stări discrete și timp continuu (lanț Markov continuu) Stări continue și timp continuu. În practică, majoritatea problemelor procesului Markov sunt descrise folosind lanțuri Markov în timp discret sau continuu.
Lanțuri Markov Un lanț Markov este o succesiune de evenimente aleatoare în care probabilitatea fiecărui eveniment depinde doar de starea în care se află procesul în prezent și nu depinde de stările anterioare.
Definind un lanț Markov cu o mulțime de stări S = (s 1, ..., sn), evenimentul este o tranziție de la o stare la alta ca urmare a unui test aleator cu un vector de probabilități inițiale (distribuție inițială) p (0) = (p(0)(1), ... , p(0)(n)), care determină probabilitatea p(0)(i) ca la momentul inițial t = 0 procesul să fie în starea si prin matricea probabilităților de tranziție P = (pij), care caracterizează probabilitatea tranziției procesului cu starea curentă si la următoarea stare sj, în timp ce suma probabilităților tranzițiilor dintr-o stare este egală cu 1
Tipuri de lanțuri Markov Un lanț Markov se numește omogen dacă probabilitățile de tranziție nu depind de timp, adică nu se schimbă de la pasul k la pas (k+1). Lanțurile Markov descompuse conțin stări irevocabile numite stări absorbante. Este imposibil să treci de la o stare absorbantă la alta. În grafic, starea absorbantă corespunde unui vârf din care nu iese niciun arc. Lanțurile Markov ergodice sunt descrise printr-un grafic puternic conectat. Într-un astfel de sistem, o tranziție de la orice stare la orice stare este posibilă într-un număr finit de pași.
Scopul simulării este de a determina probabilitatea ca sistemul să fie în a j-a stare după pasul k-a. Să notăm această probabilitate - lanț Markov omogen - lanț Markov neomogen
Sarcina nr. 1 Un anumit set de familii muncitoare este împărțit în trei grupe: 1 – familii care nu au mașină și nu intenționează să-și cumpere; 2 – familii care nu au mașină, dar plănuiesc să-și cumpere una și, în sfârșit, 3 – familii care au mașină. Anchetele statistice au permis estimarea probabilității ca familiile să treacă de la un grup la altul pe parcursul unui an. În acest caz, matricea de tranziție s-a dovedit a fi:
Sarcina nr. 1 Aflați: a) probabilitatea ca o familie care nu avea mașină și nu intenționa să-și cumpere una să fie în aceeași situație în 2 ani; b) probabilitatea ca o familie care nu avea mașină și intenționează să-și cumpere una să aibă mașină în 2 ani. (rezolvați singur punctul (b) al acestei probleme)
Rezolvarea problemei nr. 1 a) Având în vedere: adică vectorul probabilităților inițiale p(0) = (1, 0, 0) (acum sistemul este în starea 1) Aflați: (în 2 ani în starea 1) Aflați probabilitatea ca sistemul să fie în fiecare dintre stările după 1 an (înmulțirea vectorului probabilităților inițiale cu 1 coloană a matricei probabilităților de tranziție) (înmulțirea vectorului probabilităților inițiale cu 2 coloane a matricei probabilităților de tranziție) (înmulțirea vectorului a probabilităților inițiale cu 3 coloane din matricea probabilităților de tranziție)
Soluția problemei nr. 1 Să obținem vectorul probabilităților după 1 an În cazul nostru, acesta este primul rând al matricei probabilităților de tranziție Să găsim probabilitatea ca sistemul să fie în starea 1 după 2 ani (înmulțind vectorul de probabilități după 1 an, adică primul rând al matricei de probabilități de tranziție la prima coloană a matricei de probabilități de tranziție)
Soluția problemei nr. 1 Calcule: Răspuns: probabilitatea ca o familie care nu avea mașină și nu intenționa să-și cumpere una să fie în aceeași situație în 2 ani este de 0,64
Problema nr. 2 Să presupunem că o anumită companie livrează echipamente în toată Moscova: în districtul de nord (notat cu A), sud (B) și central (C). Compania are o echipa de curieri care deservesc aceste zone. Este clar ca pentru a face urmatoarea livrare, curierul merge in zona care este momentan mai aproape de el. S-a determinat statistic: după livrarea la A, următoarea livrare se efectuează în 30 de cazuri în A, în 30 de cazuri în B și în 40 de cazuri în C; după livrare la B, următoarea livrare se efectuează în 40 de cazuri în A, în 40 de cazuri în B și în 20 de cazuri în C; după ce livrarea se face la C, următoarea livrare se efectuează în 50 de cazuri în A, în 30 de cazuri în B și în 20 de cazuri în C. Astfel, aria următoarei livrări este determinată doar de livrarea anterioară.
Problema nr. 2 Dacă un curier pleacă din raionul central, care este probabilitatea ca după două livrări să fie în raionul de sud? Rezolvați singur problema: Creați o matrice de probabilități de tranziție Desenați un grafic al acestui proces Calculați probabilitatea dorită
Probabilități limită Pentru lanțurile ergodice, cu un timp de funcționare suficient de mare (t tinde spre infinit), se instalează un regim staționar, în care probabilitățile stărilor sistemului nu depind de timp și nu depind de distribuția probabilității la momentul inițial. . Astfel de probabilități sunt numite probabilități de stare limită (sau finale, staționare), ele arată timpul relativ mediu în care sistemul rămâne într-o anumită stare. De exemplu, dacă probabilitatea marginală a stării i este pi=0. 5, aceasta înseamnă că, în medie, jumătate din timp sistemul este în starea i-a.
Probabilități limită Fie xi probabilitățile limită (i=1. . n), unde n este numărul de stări. Atunci xi sunt singura soluție a sistemului de ecuații liniare. Acest sistem include ecuațiile:
Exemplu Matricea probabilității de tranziție (număr de stări n=2) și reprezentarea grafică a procesului Markov: Probabilitățile limită x 1 și x 2 pot fi găsite prin rezolvarea sistemului
Problema nr. 3 Două mașini A și B sunt închiriate la același preț. Aceste mașini au următoarele matrice de probabilitate de tranziție: unde 1 este starea când mașina funcționează bine; 2 – indicați când mașina necesită reglare. Determinați probabilitățile pentru ambele mașini. Ce mașină ar trebui să închiriezi?
Sarcina nr. 4 Un vizitator de bancă cu intenția de a obține un împrumut este supus unui număr de verificări (condiții): e 1 – documente; e 2 – istoric de credit; e 3 – recidiva; e 4 – solvabilitate. Pe baza rezultatelor verificării, sunt posibile două rezultate: refuzul de a acorda un împrumut (e 6) și primirea unui împrumut (e 5).
Sarcina nr. 4 Necesită: a) descrieți acest proces ca un lanț Markov și construiți o matrice de tranziție (fă-o singur); b) găsiți timpul mediu pentru a obține un rezultat pozitiv și negativ (soluție în Excel).
Structura companiei de administrare a locuințelor și serviciilor comunale, structura acesteia și prezența anumitor diviziuni și poziții în ea depind de mărimea...
În primul rând, profitul trebuie considerat ca o categorie economică, o abstractizare științifică care exprimă anumite...
La un anumit nivel de preț, o scădere a costurilor duce la o creștere a veniturilor, adică reversul costurilor...
Guvernul a luat o decizie pe care toți contabilii o vor experimenta singuri în 10 zile. Și anume: acum, pe lângă SZV-M...
Va fi necesar să se calculeze personalul mediu pentru 2016 în mai multe cazuri. În primul rând, pentru a completa informațiile...
Orice întreprindere operează într-un macro- și micromediu. Are o gamă întreagă de resurse care sunt folosite în...
Dezvoltarea metodologică a unei lecții de lectură literară în clasa a III-a (UMK „Școala Rusiei”) „L. N. Tolstoi „Rechin”...
Tehnologiile informaționale pătrund în diverse domenii ale afacerii cu o viteză atât de mare încât uneori este dificil să le evaluezi...
Un vânt umed și rece a suflat dinspre mare, purtând peste stepă melodia gânditoare a stropii unui val care curgea pe țărm și...
Calitate, calitate, calitate... Cât de diferit este perceput și definit acest concept! În fig. 1...
La 13 septembrie 2012, în legătură cu retragerea lui Stanislav Vladimirovici Hramenkov, noul general...
Istoria olăritului cunoaște două tipuri principale de roți de ceramică - mână și picior. Amândoi lucrează...
În fiecare an, sute de asistente studiază pentru a deveni cosmetologi. După pregătire cu persoane cu studii medii medicale. Sunt trei educații...
Kazakova Daria, Emelyanova Ksenia, Sidorin Andrey Relevanța subiectului: fiecărui copil mic îl iubește când...
În primul rând, profitul trebuie considerat ca o categorie economică, o abstractizare științifică care exprimă...
La un anumit nivel de preț, o scădere a costurilor duce la o creștere a veniturilor, adică reversul costurilor...