Studiul sistemelor de aşteptare prin modelare statistică.
Citeste si
Teoria cozilor este un domeniu al matematicii aplicate care folosește metodele teoriei proceselor aleatoare și teoria probabilității pentru a studia natură diferită sisteme complexe. Teoria cozilor de aşteptare nu este direct legată de optimizare. Scopul său este de a, pe baza rezultatelor observațiilor „intrarii” în sistem, să prezică capacitățile acestuia și să organizeze cel mai bun serviciu pentru o anumită situație și să înțeleagă modul în care acesta din urmă va afecta costul sistemului în ansamblu. Pentru sistemele legate de sistemele de așteptare, există o anumită clasă de probleme, a căror soluție permite răspunsul la întrebări relevante pentru astăzi. Cu ce ritm ar trebui efectuat un serviciu sau un proces efectuat la un ritm dat și alți parametri ai fluxului de cerințe de intrare pentru a minimiza coada sau întârzierea în pregătirea unui document sau a unui alt tip de informații? Care este probabilitatea unei întârzieri sau coadă și amploarea acesteia? Cât de lungă este solicitarea în coadă și cum să îi minimizăm întârzierea? Care este probabilitatea de a pierde o revendicare (client)? Care ar trebui să fie încărcătura optimă a canalelor de servicii? La ce parametri de sistem sunt atinși pierderi minime a sosit? O serie de alte sarcini pot fi adăugate la această listă.
Sistemul de așteptare (QS) include următoarele obiecte care formează structura: sursa cerințelor; fluxul de intrare al cerințelor (primirea cererilor); coadă; sistem de service, ca set de canale pentru aplicații de service; flux de ieșire (aplicații deservite sau cerințe satisfăcute). Să aruncăm o privire la modelele lor.
Sursa cerințelor. În funcție de locația sursei care formează cerințele, QS-urile sunt împărțite în deschise, când sursa este în afara sistemului, și închise, când sursa este în interiorul sistemului.
Flux de intrare de cerințe. Marea majoritate a dezvoltărilor teoretice în studiul sistemelor de așteptare sunt făcute pentru condiția când fluxul de intrare al cerințelor este Poisson (cel mai simplu). Acest flux are o serie de proprietăți importante. Este staționar, obișnuit și nu are consecințe.
Modelul fluxului Poisson de intrare este reprezentat de o funcție de forma:
Următoarea proprietate a fluxului Poisson care este important de studiat este că procedura de împărțire și combinare dă din nou fluxuri Poisson. Apoi, dacă fluxul de intrare este format din N surse independente, fiecare dintre acestea generând un flux Poisson cu intensitate λ i (i=1,2,…, N) , atunci intensitatea sa va fi determinată de formula:
|
|
.În cazul scindării pârâului Poisson în N fluxuri independente, se obţine că intensitatea curgerii λ i va fi egal cu r i λ , Unde r i - acțiune i – al-lea flux în fluxul de intrare cerințe.
Coadă. Cozile, definite ca un ansamblu de solicitări care așteaptă să fie deservite, sunt reprezentate de mai multe modele: o coadă cu defecțiuni, o coadă cu un timp de așteptare limitat (un client așteaptă un anumit timp), o lungime limitată și, în final, un timp de așteptare nelimitat. Ordinea în care sunt primite cererile de servicii se numește disciplină în coadă. Cerințele pot fi acceptate pe măsură ce vin, aleatoriu, cu prioritate, pe o bază „ultimul-primul”, prin anumite canale.
Procesul de întreținere. Parametrul principal al procesului de serviciu este considerat a fi timpul de serviciu al cerinței de către canal j- t j (j=1,2,…, m) . Valoare τ j în fiecare caz este determinat de o serie de factori: intensitatea primirii cererilor, calificările antreprenorului, tehnologia de lucru, mediul etc. Legile distribuției unei variabile aleatoare τ j poate fi foarte diferită, dar cea mai utilizată în aplicații practice este legea distribuției exponențiale. Funcția de distribuție a unei variabile aleatoare τ j se pare ca:
Cea mai importantă proprietate a distribuției exponențiale este următoarea. În prezența mai multor canale de servicii de același tip și cu o probabilitate egală de selecție a acestora la primirea unei cereri, distribuirea timpului de serviciu de către toți m canale este o funcție exponențială de forma:
Dacă QS-ul constă din canale eterogene, atunci 
, dacă toate canalele sunt omogene, atunci 
.
Fluxul de ieșire al cererilor deservite. Un flux de ieșire este un flux de rezultate ale activităților reprezentate de cerințele îndeplinite în ideea unui anumit produs sau serviciu. Principalii parametri ai fluxului de ieșire includ intensitatea ieșirii din sistemul de cerințe deservite și natura distribuției timpului între momentele de producție. În cazul general, acești parametri sunt determinați de modelul fluxului de intrare, disciplina de coadă și modelul de serviciu. Pentru un QS cu canale paralele și serviciu monofazat, există o teoremă conform căreia pentru un flux de intrare Poisson cu parametrul λ și aceeași distribuție a timpului de serviciu pentru fiecare canal cu parametrul μ în stare staționară, fluxul de ieșire are o distribuție Poisson cu parametrul g. În sistemele monofazice, fluxul de ieșire de la un canal servește ca flux de intrare către alt canal. Parametrul g în cel mai simplu caz este determinat de formula:
|
|
|
|
W S - timpul mediu de rezidență al unei cerințe în sistem. |
|
,O caracteristică a modelelor QS este asociată cu o descriere matematică destul de riguroasă a funcționării sistemelor, care se realizează datorită unificării lor în mai multe moduri. Deci, în funcție de modelul de așteptare, următoarele QS-uri se disting prin cerința de a începe întreținerea:
sistem cu pierderi sau defecțiuni;
sistem de așteptare;
sistem cu timp de așteptare limitat (VO);
un sistem cu o lungime limitată de coadă (DO).
În funcție de numărul de canale de servicii, sistemele sunt împărțite în un singur canal ( m=1 ) și multicanal ( m>1 ). Structura QS-ului și caracteristicile obiectelor sale sunt prezentate în Figura 1.21.
Una dintre formele de clasificare QS este clasificarea codului lui D. Kendall. În conformitate cu această clasificare, caracteristica QS este scrisă ca trei, patru sau cinci simboluri. De exemplu, A/ b/ c, Unde A– tipul de distribuție a fluxului de intrare de cerințe, b– tipul de distribuție a timpului de serviciu, c– numărul de canale de servicii. Pentru Poisson și distribuțiile exponențiale luați simbolul M, pentru orice distribuție arbitrară G. De exemplu, intrarea M/M/2înseamnă că fluxul de intrare al cerințelor este Poisson, timpul de serviciu este distribuit conform legii exponențiale și există două canale în sistem. Al patrulea caracter (d) indică lungimea permisă a cozii, al cincilea (e) indică ordinea în care sunt selectate cererile.
Figura 1.21 - Structura și caracteristicile obiectelor QS
Modelele QS pot fi deterministe sau probabiliste. În primul caz, parametrii și variabilele modelului sunt constante, în al doilea - aleatoriu.
Studiul QS este de a găsi indicatori care caracterizează calitatea și condițiile de lucru ale sistemului de servicii și indicatori care reflectă consecințele economice. deciziile luate conform primilor indicatori. Indicatorii primului grup includ următorii.
1. Cu parametri stabiliți sau de proiectare ai fluxului de intrare:
a) probabilitatea de primire a n cerințe în sistem pentru perioada respectivă t (P n (T)) ;
b) probabilitatea de a avea n cerințele din sistem (P n ) .
2. Cu parametrii de service stabiliți sau de proiectare:
a) probabilitatea ca toate serviciile m canalele sunt gratuite (P 0 ) ;
b) probabilitatea ca un anumit număr de canale (manageri, agenți) să fie ocupate cu serviciul (P m ) ;
c) probabilitatea ca r cerințele sunt în coadă (P m + r ) .
3. Cu parametrii stabiliți sau de proiectare ai fluxului de intrare și a sistemului de servicii:
b) numărul mediu de canale m angajat de serviciu: E(m)= m k ;
c) numărul mediu de canale inactive: E(m 0 )=(m- m k ) ;
d) utilizarea canalului (ocuparea) (K S ) ;
e) raportul timpului de nefuncţionare a canalului (defecţiune). (K 0 ) ;
f) relativă (Q) și absolută (A) Debit QS;
g) numărul mediu de cerinţe din sistem (L S ) ;
h) numărul mediu de cereri în așteptare în coadă (L q ) ;
i) timpul mediu de așteptare pentru o solicitare în coadă (W q ) ;
j) timpul mediu de rezidenţă al unei cerinţe în sistem (W S ) .
Luați în considerare metodele de calcul a indicatorilor primului grup pe exemplul celui mai comun model QS ( M/ M/ m≥2 ) cu o așteptare care conține m canale de servicii paralele. Aici, cererile primite nu se pierd și părăsesc sistemul numai după service. Canalele efectuează operațiuni uniforme și timpul de serviciu pentru fiecare canal t distribuite conform legii exponenţiale cu parametrul m, iar fluxul de intrare este Poisson cu parametru λ ; disciplina la coadă nu este reglementată și nu există o limită a numărului de solicitări primite. Modelul QS este reprezentat ca un sistem de ecuații pentru o stare staționară.
Determinarea probabilității de a avea n cerințe (P n ) în sistem depinde de raportul dintre numărul de cereri primite ( n) pe unitatea de timp și numărul de canale de servicii ( m).
1. Pentru condiția când m=1, P n este determinată de formula așteptării matematice a unei variabile aleatoare discrete.
2. Pentru condiţia când 1≤ n≤ m (probabilitatea ca toate cererile să fie în serviciu sau să nu existe coadă), P n calculat prin formula:
Dacă ρ/ m<1 , apoi probabilitatea absenței cerințelor în sistem P 0 este determinată de formula pentru modul staționar:
sau prin formula așteptării matematice a unei variabile aleatoare discrete:
Coeficienții de utilizare (încărcare) ai canalelor și, respectiv, timpul de nefuncționare a canalelor sunt determinați prin formulele:
Și 
.
Numărul mediu de cereri care așteaptă în coadă se găsește din expresia:
.
Timpul mediu de așteptare în coadă va fi:
.
Timpul mediu de rezidență al unei cerințe în sistem este calculat prin formula:
.
Numărul mediu de cerințe din sistem este determinat de în felul următor:
.
Pentru cazul general L S este determinată de formula așteptării matematice a unei variabile aleatoare discrete:
.
Pentru a estima parametrii unui sistem probabilistic și procesele sale aleatoare din punct de vedere al stabilității, se oferă utilizarea valorilor găsite ale caracteristicilor funcțiilor aleatoare, care sunt funcții non-aleatoare ale argumentului. t. Acestea includ așteptarea matematică, varianța, funcția de corelație, coeficientul de variație, care caracterizează o implementare medie a unui proces aleatoriu (sau funcție aleatoare) pe un set de observații. Statisticile sunt găsite prin intermediul parametrilor QS. De exemplu, dispersia (D) pentru numărul de cerințe din sistem se calculează prin formula:
.
Indicatorii care caracterizează consecințele economice ale luării deciziilor de îmbunătățire a serviciului clienților (consumator) se reduc la determinarea eficienței economice și a pierderilor datorate refuzului serviciului și așteptării serviciului.
Eficiența economică a sistemului de așteptare va fi:
Valoarea pierderilor este determinată de următoarele expresii:
a) sistem cu defecțiuni:
b) sistem cu așteptare:
Pentru a demonstra utilitatea utilizării metodelor teoriei cozilor de așteptare pentru rezolvarea problemelor de management, luați în considerare un exemplu de estimare a unui QS de dimensiune mică.
Exemplul 1.9. Se cere evaluarea eficacității centralizării mai multor departamente sau servicii cu funcții omogene. Ca obiect sunt avute în vedere două servicii de taxi, care au fost achiziționate de firma Avtoservis. Aplicațiile clienților între servicii sunt distribuite în mod egal. Cererea de taxi către dispecerat vine cu o frecvență de 10 apeluri pe oră. Timpul mediu de service per client este de 11,5 minute. Apelurile la taxi sunt distribuite în timp conform legii Poisson, iar durata serviciului pentru un client este distribuită conform legii exponențiale. Fiecare serviciu de taxi este echipat cu două mașini.
Se pune întrebarea cu privire la fezabilitatea economică a centralizării managementului parcului de taxiuri. Pentru a face acest lucru, trebuie să comparați două opțiuni:
1) opțiune cu service independent prin sisteme de tip ( M/M/2) la λ=10 apeluri/oră, τ=11,5 min. Și m= 2;
2) variantă cu o singură coadă de tip ( M/M/4) la λ=10*2=20 apeluri/oră, τ=11,5 min. Și m= 4;
Pentru început, să determinăm factorii de încărcare ai serviciului pentru prima și a doua opțiune. La m= 2 avem:
După cum se poate observa din calcul, factorul de încărcare al serviciului de taxi este destul de mare. Evident, nu se schimba in varianta cu m= 4, deoarece atât numărătorul cât și numitorul sunt dublate. La prima vedere, asocierea nu duce la un efect economic, iar din moment ce studiul eficacității funcționării QS este axat pe îmbunătățirea calității satisfacerii cerințelor consumatorilor, este necesar să se evalueze parametrii care caracterizează acest domeniu al activitate.
Calcula W q(timpul mediu de așteptare pentru un taxi).
Pentru primul caz cu m= 2 avem ρ=1,917. Să determinăm probabilitatea ca în sistem să nu existe cerințe ( P 0 ):
Utilizarea valorii P 0 defini W q :
h.
Pentru al doilea caz cu m= 4 avem ρ=3,83 și definim P 0 :
Cu o valoare P 0 =0,0042, obținem asta
h.
Estimările de mai sus arată că centralizarea serviciilor face posibilă reducerea timpului mediu de așteptare pentru un apel de taxi de către un client cu aproximativ jumătate. Aceasta nu este o garanție că clientul va refuza comanda, ci o reducere semnificativă a timpului de așteptare. Pe viitor, pe lângă crearea unui serviciu de taxi unificat, este necesar să se ia în considerare problema creșterii flotei de taxiuri.
1. Concepte de bază ale teoriei cozilor.
2. Enunțarea problemei teoriei cozilor.
3. Abordări pentru rezolvarea problemelor din teoria cozilor.
Scurt continutul subiectului
Activitatea practică a unei persoane este strâns legată de diferite tipuri de sisteme de așteptare. În domeniul economiei, acestea sunt serviciile bancare, utilizarea facilităților comerciale și a serviciilor în sectorul serviciilor și multe alte tipuri de activitate economică.
Orice sistem de așteptare poate include următoarele elemente:
Un flux primit de solicitări sau solicitări de servicii. Acest element este principalul. Studiul fluxului de cerințe de intrare și descrierea acestuia este necesar atunci când se organizează orice sistem de așteptare.
Coadă. În cazurile în care solicitările care intră în sistemul de așteptare nu pot fi satisfăcute imediat, apare o coadă. Într-o astfel de situație, lungimea acestei cozi, ordinea în care cererile în așteptare sunt trimise spre serviciu (cum se spune, disciplina cozii), timpul de așteptare poate fi de interes.
În unele cazuri, sistemele de așteptare nu sunt permise, de exemplu. cererea care a făcut sistemul ocupat nu este deservită (respinsă).
Dispozitiv de service. Acest element este prezent în orice sistem de așteptare. Nu numai timpul necesar pentru deservirea unei cereri, ci și lungimea cozii și timpul de așteptare depind de caracteristicile și parametrii, metodele de organizare a dispozitivului de service.
Flux de ieșire de cereri deservite. Acest element poate fi foarte important în cazurile în care fluxul de ieșire de cereri deservite este primit pentru un alt sistem de așteptare.
De regulă, numărul de cerințe la intrarea sistemului de așteptare pentru orice perioadă de timp și timpul de deservire a unei cerințe sunt variabile aleatorii. Funcționarea sistemului de așteptare în acest caz este un proces aleatoriu, iar metodele de studiere a unor astfel de sisteme folosesc simularea. Cu toate acestea, se poate înțelege esența problemelor și metodelor teoriei cozilor de așteptare folosind exemplele de modele deterministe ale sistemelor de cozi de așteptare și, mai presus de toate, modele de teoria cozilor de așteptare.
Principalele componente ale modelului de coadă sunt:
descrierea fluxului de cerințe de intrare;
o descriere a modului în care este prestat serviciul (adică, o descriere a disciplinei de serviciu);
descrierea disciplinei cozii (adică modul în care clienții sunt selectați din coadă pentru serviciu: „primul venit - primul servit”, „ultimul venit - primul servit”, „după prioritățile specificate”, etc.).
La construirea unui model de coadă, sarcina principală este reprezentarea simbolică a componentelor principale, după care sunt studiate relațiile dintre ele.
Principalele caracteristici ale cozii sunt:
lungimea cozii la momente diferite;
durata totală a cerinței în sistemul de servicii (adică timpul petrecut în așteptare în coadă, plus timpul de serviciu propriu);
timpul în care dispozitivul de service a fost liber.
Scopul principal al studiului sistemelor de coadă este de a stabili un echilibru între sarcinile admisibile ale dispozitivului de servire, capacitatea limitată a sistemului și enervarea clientului, pe de o parte, și costul admisibil al punctelor de servire, pe de o parte. celălalt.
Luați în considerare un sistem de așteptare care are o singură sursă de revendicări care trec printr-un singur server. Să aibă loc următoarele ipoteze:
1. Solicitările ajung la intervale regulate. Fiecare interval are o lungime de o unitate.
2. Cererile sunt deservite pentru aceleași intervale de timp, fiecare interval având o lungime de b unități. În acest caz, de îndată ce service-ul pentru o cerință este finalizat, dispozitivul de service este gata să deservească următoarea cerință.
3. Disciplina la coadă se stabilește conform regulii „Primul venit - primul servit”. Cu alte cuvinte, cererile de așteptare formează o coadă, iar atunci când serverul devine liber, solicitarea cu cel mai lung timp de așteptare ajunge pentru service.
Să definim lungimea cozii ca numărul total de solicitări deservite și care așteaptă în coadă. Să reprezentăm problema formulată sub forma următoarei scheme:
Comportamentul sistemului depinde de modul în care sunt legate mărimile a și b. Sunt posibile trei cazuri: 1) b > a; 2) b = a; 3) b< a. Рассмотрим каждый из этих случаев.
1) Cazul b > a. Aceasta înseamnă că rata serviciului 1/b este mai mică decât rata de primire a cererilor 1/a, adică. cererile sunt servite și părăsesc sistemul mai încet decât ajung. Prin urmare, în acest caz, se va forma o coadă și va crește constant.
2) Cazul b = a. Dacă nu există cereri în coadă, atunci prima cerere primită va începe imediat să fie servită. Serviciul său se va încheia în același moment în care sosește următoarea cerință pentru service. Prin urmare, nu vor exista cereri care să aștepte să fie deservite.
Dacă inițial există o coadă, atunci lungimea acesteia va rămâne constantă.
3) Cazul b< a. Это значит, что скорость обслуживания больше, чем скорость поступления требований. Следовательно, какое бы ни было начальное число ожидающих обслуживания требований, длина очереди будет сокращаться до 1 или 0.
Lăsați la începutul procesului numărul de cereri din coada r 2 (dacă inițial există o singură cerere (r = 1), atunci aceasta va fi deservită înainte ca următoarele solicitări să ajungă pentru service, iar coada va fi goală) .
În cazul general, să presupunem că avem r clienți care stau la coadă înainte de începerea serviciului. Apoi, numărul de solicitări (N) primite după începerea procesului de service până când coada este păstrată poate fi determinat prin formula:
unde notația [x] înseamnă partea întreagă a numărului x. Într-adevăr, coada va fi absentă dacă N + r cereri trec complet prin server. Acest lucru va necesita (N+r)b unități de timp. În acest timp, N clienți vor fi deserviți, astfel încât până la sosirea celui de-al (N + 1) al-lea client, serverul va fi liber și gata să îl servească imediat, fără nicio coadă. Dar a (N + 1)-a cerință va ajunge pentru serviciu după (N + 1)a unități de timp, în timp ce relația va fi satisfăcută:
Să demonstrăm că N în relația obținută este mai mare decât partea dreaptă cu cel mult 1. Într-adevăr, primul client care se află în coadă va fi deja deservit, iar primul client care sosește pentru service nu va apărea încă în coadă. (a > b). Prin urmare, următoarea relație este adevărată:
aN (N+r-1)b sau.
Astfel, dacă adăugăm 1 în partea dreaptă a raportului, atunci acesta va fi identic egal cu partea dreaptă a raportului. Adică, adăugarea lui 1 în partea dreaptă a raportului îl duce la raport - sensul inegalității este inversat. Acesta este ceea ce trebuia dovedit.
Este evident că N este un număr întreg. Prin urmare, dacă luăm partea întreagă din partea dreaptă în relația (10.2) și îi adăugăm 1, atunci, pe baza raționamentului anterior, obținem expresia (10.1) pentru a calcula N.
Prin raționament similar și folosind (10.1), putem constata că pentru a calcula timpul necesar pentru deservirea tuturor cererilor în așteptare, formula este valabilă:
În teoria stării de așteptare, o funcție importantă este funcția de timp de așteptare a serviciului. Se notează cu W(t). Să definim W(t) ca timpul care trebuie petrecut în așteptarea serviciului unei cereri care a sosit la momentul t (presupunem că t = 0 corespunde începutului procesului de deservire).
Să definim o formulă pentru W(t). Este ușor de observat că un client care sosește pentru service la momentul t T-b (valoarea lui T este determinată folosind formula (10.3)) va găsi sistemul de așteptare gol sau doar eliberat. O astfel de cerere nu trebuie să stea la coadă. O revendicare care sosește la ora tT-b va găsi înaintea ei revendicările în coadă, iar prima dintre ele va ajunge la server în același moment. Această valoare se obține astfel:
(inițial (număr de cerințe, deservite- (număr de primite-
coada) - al doilea până la momentul t) + leniya)
Astfel, timpul de așteptare W(t) pentru cerința considerată poate fi exprimat prin formula:
Considera i-a cerințăîn coada inițială (0
Generalizând rezultatele obținute cu privire la funcția W(t), obținem următoarea expresie pentru aceasta:
unde i este numărul i-a cerință din coada inițială; cererile ajung la orele a, 2a, ...; b = na (n = 1, 2, ...).
Studiul sistemelor de aşteptare prin modelare statistică
1. Prevederi de bază pentru efectuarea lucrărilor de laborator
Utilizarea metodelor analitice și numerice pentru studierea QS este limitată la cazurile în care sistemul este markovian și este descris de ecuațiile de naștere și moarte sau poate fi redus la acesta. În caz contrar, studiul QS este posibil cu ajutorul metodei de simulare bazată pe simularea multiplă computerizată a proceselor care au loc în sistem, urmată de prelucrarea statistică a rezultatelor obținute.
Estimările așteptărilor matematice ale numărului de canale ocupate, lungimea cozii, timpul de așteptare pentru solicitările în coadă, probabilitățile de deservire a cererilor etc. sunt utilizate ca principale cantități care caracterizează funcționarea QS-ului studiat. , pentru momentul de timp t (o £ t £ T n ), unde T n - timpul de simulare, poate fi calculat.
Estimarea așteptării matematice a numărului de canale ocupate:
aici - numărul de canale ocupate la momentul t în implementarea j-a; N este numărul de implementări (execuții de model);
Estimarea probabilității ca în sistem la momentul t:
iată numărul de implementări în care la momentul t existau k cerințe în sistem;
Estimarea probabilității ca cererea să fie respinsă:
unde este numărul total de cerințe care au apărut până la momentul t în implementarea j-a; - numărul de cerinţe care au fost respinse de timpul t;
Estimarea dispersiei numărului de canale ocupate la momentul t:
Pentru a vă face o idee despre acuratețea și fiabilitatea acestor estimări, intervalele de încredere Ib pot fi găsite pentru un anumit nivel de încredere b.
Pentru așteptarea matematică a numărului de canale ocupate
Aici tb se găsește din distribuția lui Student la (N-1) grade de libertate. Pentru N mare (N>30), în loc de distribuția Student, puteți folosi legea normală. În acest caz
unde Ф(х) este integrala probabilităților:
2. Pentru probabilităţi
Pentru N mare, aproximativ
unde - S.K.O. estimări de probabilitate:
În plus, limitele intervalelor de încredere pentru probabilități pot fi găsite cu ușurință din nomograme.
2. Pentru o anumită versiune (de bază) a QS, obțineți rezultatele modelării QS. Valoarea lui tOhtimp de așteptare la coadă pentru a luanon-aleatoriu tOh>TMaud.TMaud luați în funcție de rezultatele contabilității lucrărilor de laborator nr. 1 (timpul final al procesului de tranziție înmulțit cu 2). Numărul realizărilor N=50. Construiți grafice ale schimbării m L, An, Pserviciuși intervalele lor de încredere în funcție de timp. Valoarea probabilității de încredere este luată egală cu?=0,9
Rezolvarea sistemului ecuatii diferentiale prin metoda Runge-Kutta (părțile drepte ale ecuațiilor sunt scrise în vectorul D, condițiile inițiale sunt în vectorul x):
Modelare
Timp de simulareT Maud = 3 (conform rezultatelor lucrărilor de laborator, timpul de încheiere a procesului tranzitoriu este de 1,3 s).
Timp de asteptarealege din condiția T aștepta >T Maud , deci Tojid = 4 s.
Parametrii modelului:
Flux de intrare (interval de timp dintre cereri):
Intensitate: 7
Coadă:
Lungimea cozii: 3
E timpul să părăsești coada:
Legea distribuției: deterministă
Valoare: 4
Canale de servicii:
Numar de canale: 3
Timp de service:
Legea distribuției: exponențială
Intensitate: 2
Rezultatele programului:
Estimări ale așteptărilor matematice:
| 1,00 | 6,940 | 0,320 | 0,000 | 3,500 | 0,720 | 0,029 | 2,400 |
| 2,00 | 14,060 | 1,640 | 0,000 | 8,540 | 1,280 | 0,107 | 2,600 |
| 3,00 | 21,040 | 3,480 | 0,000 | 13,500 | 1,440 | 0,169 | 2,620 |
| 4,00 | 28,220 | 5,560 | 0,000 | 18,620 | 1,300 | 0,213 | 2,740 |
| 5,00 | 35,060 | 7,060 | 0,000 | 24,200 | 1,080 | 0,235 | 2,720 |
| 6,00 | 42,460 | 8,860 | 0,000 | 29,240 | 1,660 | 0,244 | 2,700 |
| 7,00 | 49,440 | 10,620 | 0,000 | 35,000 | 1,180 | 0,252 | 2,640 |
| 8,00 | 56,300 | 11,960 | 0,000 | 40,680 | 1,060 | 0,258 | 2,600 |
| 9,00 | 63,040 | 13,480 | 0,000 | 45,720 | 1,220 | 0,264 | 2,620 |
| 10,00 | 69,920 | 14,940 | 0,000 | 50,940 | 1,300 | 0,269 | 2,740 |
| 11,00 | 76,800 | 16,220 | 0,000 | 56,640 | 1,220 | 0,273 | 2,720 |
| 12,00 | 83,780 | 17,500 | 0,000 | 62,380 | 1,300 | 0,274 | 2,600 |
| 13,00 | 90,720 | 19,640 | 0,000 | 67,240 | 1,300 | 0,276 | 2,540 |
| 14,00 | 98,060 | 21,320 | 0,000 | 72,700 | 1,340 | 0,280 | 2,700 |
| 15,00 | 105,420 | 22,960 | 0,000 | 78,400 | 1,360 | 0,283 | 2,700 |
| 16,00 | 112,620 | 24,640 | 0,000 | 84,280 | 1,080 | 0,284 | 2,620 |
| 17,00 | 120,200 | 25,880 | 0,000 | 90,300 | 1,460 | 0,284 | 2,560 |
| 18,00 | 126,640 | 27,500 | 0,000 | 95,300 | 1,260 | 0,287 | 2,580 |
| 19,00 | 133,680 | 28,920 | 0,000 | 100,840 | 1,180 | 0,290 | 2,740 |
| 20,00 | 140,340 | 30,300 | 0,000 | 106,260 | 1,180 | 0,291 | 2,600 |
Estimări RMS:
| Timp | Numărul de cereri | Numărul de defecțiuni | Numărul de pierderi | Numărul de servicii | Lungimea cozii | Timp de așteptare | Canale ocupate |
| 1,00 | 2,745 | 0,785 | 0,000 | 1,941 | 1,000 | 0,046 | 0,916 |
| 2,00 | 3,722 | 2,197 | 0,000 | 3,054 | 1,200 | 0,086 | 0,774 |
| 3,00 | 4,906 | 3,067 | 0,000 | 3,822 | 1,235 | 0,105 | 0,718 |
| 4,00 | 5,231 | 4,176 | 0,000 | 4,151 | 1,204 | 0,100 | 0,558 |
| 5,00 | 5,984 | 5,131 | 0,000 | 4,507 | 1,110 | 0,097 | 0,530 |
| 6,00 | 6,548 | 5,830 | 0,000 | 4,773 | 1,210 | 0,088 | 0,670 |
| 7,00 | 7,518 | 6,495 | 0,000 | 5,355 | 1,125 | 0,085 | 0,624 |
| 8,00 | 7,759 | 6,971 | 0,000 | 5,773 | 1,173 | 0,082 | 0,692 |
| 9,00 | 7,725 | 7,278 | 0,000 | 6,000 | 1,237 | 0,080 | 0,718 |
| 10,00 | 8,143 | 7,882 | 0,000 | 6,077 | 1,100 | 0,080 | 0,558 |
| 11,00 | 9,361 | 8,367 | 0,000 | 6,802 | 1,118 | 0,076 | 0,722 |
| 12,00 | 10,286 | 8,690 | 0,000 | 6,831 | 1,268 | 0,075 | 0,824 |
| 13,00 | 10,438 | 8,885 | 0,000 | 6,553 | 1,204 | 0,070 | 0,780 |
| 14,00 | 10,887 | 9,321 | 0,000 | 6,394 | 1,193 | 0,067 | 0,670 |
| 15,00 | 10,398 | 8,991 | 0,000 | 6,587 | 1,179 | 0,065 | 0,670 |
| 16,00 | 10,805 | 9,333 | 0,000 | 6,600 | 1,110 | 0,063 | 0,745 |
| 17,00 | 11,144 | 9,704 | 0,000 | 7,108 | 1,152 | 0,063 | 0,875 |
| 18,00 | 11,704 | 10,425 | 0,000 | 7,566 | 1,261 | 0,062 | 0,776 |
| 19,00 | 11,853 | 10,665 | 0,000 | 7,606 | 1,089 | 0,061 | 0,521 |
| 20,00 | 11,969 | 10,562 | 0,000 | 8,009 | 1,107 | 0,059 | 0,800 |
Deoarece N = 50, apoi pentru a construi intervale de încredere, având în vedere că valoarea probabilității de încredere ? = 0.9, apoi t ?calculate folosind legea normală:
Așteptări matematice privind numărul de canale ocupate:
Mn - din L.R. 1
a - modelare
Așteptări matematice privind lungimea medie a cozii:
Calcul intervalului de încredere:
Pentru lungimea medie a cozii:
Lm - de la L.R. 1
m - simulare
Probabilitatea serviciului:
Probabilitatea serviciului este egală cu probabilitatea ca în sistem să nu existe încă n+m clienți, adică. P o = 1 - Pn+m = 1 - P 6
Calcul intervalului de încredere:
Pentru probabilitatea serviciului:
Po1 - din L.R. 1
Po - modelare
3. Pentru o variantă QS dată (de bază), investigați influențatașteptaasupra caracteristicilor sistemului în regim staţionar
a) H( t ) - determinat, t aștepta =T aşteptări_medie
b) H( t ) este supusă legii distribuției exponențiale. Valorea estimata t aștepta egal cu T aşteptări_medie*(0,25; 0,5; 1; 2).
concluzii
În munca de laborator nr. 2 s-au obținut rezultatele modelării versiunii de bază a QS. Conform rezultatelor obținute, au fost reprezentate grafice ale dependențelor numărului de canale ocupate, lungimea medie a cozii și probabilitatea de serviciu și intervalele de încredere ale acestora în timp. Curbele construite pe baza rezultatelor lucrărilor de laborator nr. 1 s-au încadrat în intervalele de încredere corespunzătoare.
In acest munca de laborator au fost investigate posibilităţile de utilizare a metodei de simulare pentru studiul sistemelor de aşteptare. Analizând rezultatele obținute, putem trage următoarea concluzie: utilizarea metodei de simulare este acceptabilă, dar este mai de preferat să se utilizeze un aparat analitic pentru studiul QS, deoarece acest mod de a studia QS este mai simplu și oferă rezultate mai precise.
simulare simulare coadă
Îndrumare
Ai nevoie de ajutor pentru a învăța un subiect?
Experții noștri vă vor sfătui sau vă vor oferi servicii de îndrumare pe subiecte care vă interesează.
Trimiteți o cerere indicând subiectul chiar acum pentru a afla despre posibilitatea de a obține o consultație.
Subiectul TMS este sistemele de așteptare (QS) și rețelele de așteptare. Un QS este înțeles ca un sistem dinamic conceput pentru a deservi eficient un flux aleatoriu de aplicații cu resurse limitate de sistem. Structura generalizată a QS este prezentată în Figura 3.1.
Orez. 3.1. Schema SMO.
Aplicațiile omogene care intră în intrarea QS sunt împărțite în tipuri în funcție de motivul generator, intensitatea fluxului de aplicații de tip i (i=1…M) se notează cu i . Setul de aplicații de toate tipurile este fluxul QS de intrare.
Aplicațiile sunt deservite m canale. Distingeți între canalele de servicii universale și specializate. Pentru un canal universal de tip j, funcțiile de distribuție F ji () ale duratei deservirii revendicărilor de tip arbitrar sunt considerate a fi cunoscute. Pentru canalele specializate, funcțiile de distribuție pe durata serviciului canalelor unor tipuri de revendicări sunt nedefinite, atribuirea acestor revendicări către un canal dat.
Ca un proces de serviciu, diverse în lor natura fizica procesele de funcționare a sistemelor economice, industriale, tehnice și de altă natură, de exemplu, fluxuri de livrări de produse către o anumită întreprindere, fluxuri de piese și componente pe linia de asamblare a unui atelier, solicitări de prelucrare a informațiilor informatice de la terminale la distanță etc. În același timp, funcționarea unor astfel de obiecte este caracterizată de comportamentul aleatoriu al solicitărilor (cerințelor) pentru service și finalizarea service-ului în momente aleatorii.
Schemele Q pot fi investigate analitic și prin modele de simulare. Acesta din urmă oferă o mai mare versatilitate.
Luați în considerare conceptul de coadă.
În orice act de serviciu elementar, se pot distinge două componente principale: așteptarea serviciului de către o aplicație și serviciul efectiv al unei aplicații. Acesta poate fi afișat sub forma unui i-lea dispozitiv de serviciu P i , constând dintr-un acumulator de cereri, în care l i =0...L i H cererile pot fi localizate simultan, unde L i H este capacitatea i-lea. acumulator și un canal de service de solicitare, k i .
Orez. 3.2. Diagrama dispozitivului SMO
Fluxurile de evenimente ajung la fiecare element al dispozitivului de serviciu P i: fluxul de cereri w i intră în acumulatorul Hi , iar fluxul de serviciu u i intră în canalul k i .
Fluxul evenimentelor(PS) este o succesiune de evenimente care au loc unul după altul la un moment dat aleatoriu. Există fluxuri de evenimente omogene și neomogene. Omogen PS este caracterizat doar de momentele de sosire a acestor evenimente (momente cauzatoare) și este dat de succesiunea (t n )=(0t 1 t 2 …t n …), unde t n este momentul sosirii al n-lea eveniment - un număr real nenegativ. OPS poate fi specificat și ca o secvență de intervale de timp între evenimentele n-lea și n-1-lea ( n ).
Eterogen PS se numește șirul (t n , f n ) , unde t n - momente cauzatoare; f n - set de caracteristici ale evenimentului. De exemplu, se poate preciza apartenența la una sau alta sursă de solicitări, prezența unei priorități, posibilitatea deservirii de către unul sau altul tip de canal etc.
Luați în considerare OPS, pentru care i ( n ) sunt variabile aleatoare independente unele de altele. Atunci PS se numește flux cu efect secundar limitat.
se numeste PS comun, dacă probabilitatea ca mai mult de un eveniment P 1 (t, t) să cadă pe un interval mic de timp t adiacent timpului t este neglijabil de mică.
Dacă pentru orice interval t evenimentul P 0 (t, t) + P 1 (t, t) + Р 1 (t, t)=1, P 1 (t, t) este probabilitatea de lovind intervalul t exact unui eveniment. Ca sumă a probabilităților evenimentelor care formează un grup complet și sunt incompatibile, atunci pentru un flux obișnuit de evenimente P 0 (t, t) + P 1 (t, t) 1, Р 1 (t, t)=(t ), unde (t) este o valoare a cărei ordin de micime este mai mare decât t, adică. lim((t))=0 pentru t0.
Substație staționară se numeste flux pentru care probabilitatea aparitiei unuia sau altuia de evenimente intr-un interval de timp depinde de lungimea acestei secțiuni și nu depinde de locul în care este luată această secțiune pe axa timpului 0 - t. Pentru OPS, 0*P 0 (t, t) + 1*P 1 (t, t)= P 1 (t, t) este numărul mediu de evenimente din intervalul t. Numărul mediu de evenimente care au loc în secțiunea t pe unitatea de timp este P 1 (t, t)/t. Se consideră limita acestei expresii la t0
lim P 1 (t, t)/t=(t)*(1/unitate).
Dacă această limită există, atunci se numește intensitatea (densitatea) OPS. Pentru PS standard (t)==const.
În ceea ce privește canalul de serviciu elementar k i, putem presupune că fluxul de cereri w i W, i.e. intervalele de timp dintre momentele de apariţie a cererilor la intrarea k i formează un subset de variabile necontrolabile, iar fluxul de servicii u i U, adică. intervalele de timp dintre începutul și sfârșitul cererii de serviciu formează un subset de variabile controlate.
Pretențiile deservite de canalul k i și revendicările care au părăsit dispozitivul P i din diverse motive nu au fost deservite, formează fluxul de ieșire y i Y.
Procesul de funcționare a dispozitivului de serviciu P i poate fi reprezentat ca un proces de modificare a stărilor elementelor sale în timpul Z i (t). Trecerea la o nouă stare pentru P i înseamnă o modificare a numărului de solicitări care sunt în acesta (în canalul k i și acumulatorul H i). Acea. vectorul de stare pentru P i are forma: ocupat).
Schemele Q ale obiectelor reale sunt formate din compoziția multor dispozitive elementare de serviciu P i . Dacă k i diferite dispozitive de serviciu sunt conectate în paralel, atunci are loc serviciul multicanal (circuit Q multicanal), iar dacă dispozitivele P i și compozițiile lor paralele sunt conectate în serie, atunci are loc serviciul multifazic (multi-canal Q-circuit). -circuit Q de fază).
Acea. pentru a specifica o schemă Q, este necesar operatorul de conjugare R, care reflectă relația elementelor structurii.
Legăturile din schema Q sunt reprezentate ca săgeți (linii de curgere care reflectă direcția de mișcare a aplicațiilor). Există circuite Q deschise și închise. ÎN deschis fluxul de ieșire nu poate ajunge din nou la niciun element, adică. nu există feedback.
Parametrii proprii (interni) ai schemei Q vor fi numărul de faze L Ф, numărul de canale în fiecare fază, L kj , j=1 ... L Ф, numărul de unități ale fiecărei faze L kj , k =1 ... L Ф, capacitatea i-a unitate L i H . De remarcat faptul că în teoria cozilor, în funcție de capacitatea de stocare, se folosește următoarea terminologie:
sisteme cu pierderi (L i H =0, nu există stocare);
sisteme de așteptare (L i H );
sisteme cu capacitate de stocare limitată H i (mixte).
Să desemnăm întregul set de parametri proprii ai schemei Q ca submulțime H.
Pentru a specifica schema Q, este de asemenea necesar să se descrie algoritmii de funcționare a acesteia, care determină regulile de comportare a aplicațiilor în diverse situații ambigue.
În funcție de locul de apariție a unor astfel de situații, există algoritmi (discipline) pentru așteptarea aplicațiilor în depozitul H i și pentru deservirea aplicațiilor cu canalul k i . Eterogenitatea fluxului de cereri este luată în considerare prin introducerea unei clase de priorități.
În funcție de dinamica priorităților, schemele Q se disting între statice și dinamice. Prioritățile statice sunt atribuite în avans și nu depind de stările schemei Q, adică. ele sunt fixate în soluția unei anumite probleme de modelare. Prioritățile dinamice apar în timpul simulării. Pe baza regulilor de selectare a cererilor din depozitul H i pentru service pe canalul k i, putem selecta relativȘi absolut priorități. Prioritate relativăînseamnă că o revendicare cu o prioritate mai mare, care a ajuns în depozitul H, așteaptă ca serviciul cererii de depunere de către canalul k i să se termine și numai după aceea ocupă canalul. Prioritate absolutăînseamnă că un client cu o prioritate mai mare care a intrat în acumulator întrerupe serviciul unui client cu o prioritate mai mică prin canalul k i și ocupă canalul însuși (în acest caz, clientul eliminat din k i poate fie să părăsească sistemul, fie să fie rescris). într-un loc în H i).
De asemenea, este necesar să se cunoască setul de reguli după care clienții părăsesc H i și k i : pentru H i , fie reguli de depășire, fie reguli de ieșire asociate cu expirarea timpului de așteptare al clientului în H i ; pentru k i - reguli pentru alegerea rutelor sau a direcțiilor de evacuare. În plus, este necesar să se stabilească regulile pentru cereri, conform cărora acestea rămân în canalul k i , adică. regulile de blocare a canalelor. În același timp, blocajele k i se disting prin ieșire și prin intrare. Astfel de blocări reflectă prezența legăturilor de control în schema Q care reglează fluxul de cereri în funcție de stările schemei Q. Setul de algoritmi posibili pentru comportamentul revendicărilor în schema Q poate fi reprezentat ca un anumit operator de algoritmi pentru comportamentul revendicărilor A.
Acea. Schema Q care descrie procesul de funcționare QS de orice complexitate este specificată în mod unic ca un set de mulțimi: Q =
procese stocastice Markov
Ele sunt numite după remarcabilul matematician rus A.A. Markov, care a început primul studiul conexiunii probabilistice a variabilelor aleatoare și a creat o teorie care poate fi numită „dinamica probabilității”. În prezent, teoria proceselor Markov și aplicațiile sale sunt utilizate pe scară largă în diverse domenii, inclusiv cercetarea operațională și teoria luării optime a deciziilor.
procesul Markov- discret sau continuu proces aleatoriu X(t), care poate fi complet specificat folosind două mărimi:
· probabilități P(X,t) că variabila aleatoare X(t) la timp t este egal cu X, Și
probabilități P(X 2 , t 2 |X 1 ,t 1) ce dacă X la t = t 1 este egal X 1, atunci t = t 2 este egal cu X 2 .
A doua dintre aceste mărimi se numește probabilitatea de tranziție in afara statului X 1 la t = t 1 pe stat X 2 la t = t 2 .
lanțuri Markov numit discret după timp şi valoare Markov
proceselor.
Exemplul 1
Să presupunem că vorbim despre aruncarea succesivă a unei monede când se joacă „aruncare”; moneda este aruncată la momente condiționale t = 0, 1, ... și la fiecare pas jucătorul poate câștiga ±1 cu aceeași probabilitate 1/2, deci la momentul t câștigul total este o variabilă aleatorie ξ(t) cu valori posibile j = 0, ±1, ... Cu condiția ca ξ(t) = k, la pasul următor, câștigul va fi deja egal cu ξ(t+1) = k± 1, luând valorile indicate j = k ± 1 cu aceeași probabilitate 1/2. În mod convențional, putem spune că aici, cu probabilitatea corespunzătoare, are loc o tranziție de la starea ξ(t) = k la starea ξ(t+1) = k± 1.
19.5.1. Formule și definiții ale lanțurilor Markov
Generalizând acest exemplu, ne putem imagina un „sistem” cu un număr numărabil de stări posibile de „fază”, care trece aleatoriu de la o stare la alta într-un timp discret t = 0, 1, ....
Fie ξ(t) poziția sa la momentul t ca rezultat al unui lanț de tranziții aleatorii ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)
Să notăm formal toate stările posibile prin numere întregi i = 0, ±1, ... Să presupunem că pentru o stare cunoscută ξ(t) = k la pasul următor, sistemul intră în starea ξ(t+1) = j cu probabilitate condiționată
p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)
indiferent de comportamentul său în trecut, mai precis, indiferent de lanțul de tranziții (1) până la momentul t:
P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) pentru toate t, k, j ... (3) - proprietatea Markov.
O astfel de schemă probabilistică se numește lanț Markov omogen cu un număr numărabil de stări- omogenitatea sa constă în faptul că definit la (2) probabilități de tranziție p kj, ∑ j p kj = 1, k = 0, ±1, ..., nu depind de timp, adică
P(ξ(t+1) = j|ξ(t) = k) = P ij - matricea probabilității de tranzițieîntr-un singur pas nu depinde de n. Este clar că P ij este o matrice pătrată cu intrări nenegative și sume unitare peste rânduri. O astfel de matrice (finită sau infinită) se numește matrice stocastică. Orice matrice stocastică poate servi ca o matrice a probabilităților de tranziție.
Să presupunem că o anumită companie livrează echipamente în Moscova: în districtul de nord (să notăm A), sud (B) și central (C). Firma are un grup de curieri care deservesc aceste zone. Este clar ca pentru urmatoarea livrare, curierul se deplaseaza in zona respectiva acest moment mai aproape de el. S-au determinat statistic următoarele:
1) după livrarea către A, următoarea livrare în 30 de cazuri se efectuează în A, în 30 de cazuri - în B și în 40 de cazuri - în C;
2) după livrare la B, următoarea livrare este în 40 de cazuri la A, în 40 de cazuri la B și în 20 de cazuri la C;
3) după livrarea la C, următoarea livrare este în 50 de cazuri la A, în 30 de cazuri la B și în 20 de cazuri la C.
Astfel, aria următoarei livrări este determinată doar de livrarea anterioară.
Matricea probabilității de tranziție va arăta astfel:
De exemplu, p 12 = 0,4 este probabilitatea ca după o livrare în zona B, următoarea livrare să fie în zona A. Să presupunem că fiecare livrare și apoi trecerea în zona următoare durează 15 minute. Apoi, conform statisticilor, după 15 minute, 30% dintre curierii care au fost în A vor fi în A, 30% vor fi în B și 40% în C. Întrucât în momentul următor fiecare dintre curieri va fi neapărat să fie într-unul dintre districte, atunci suma peste coloane este 1. Și deoarece avem de-a face cu probabilități, fiecare element al matricei este 0<р ij <1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени t+1 зависит numai din locația la ora t.
Acum să punem o întrebare simplă: dacă curierul pleacă de la C, care este probabilitatea ca, după ce a făcut două livrări, să fie în B, adică. Cum poți obține B în 2 pași? Deci, există mai multe căi de la C la B în 2 pași:
1) mai întâi de la C la C și apoi de la C la B;
2) C-->B și B-->B;
3) C-->A și A-->B.
Ținând cont de regula înmulțirii evenimentelor independente, obținem că probabilitatea dorită este egală cu:
P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)
Înlocuirea valorilor numerice:
P = 0,5*0,3 + 0,3*0,4 + 0,2*0,3 = 0,33
Rezultatul obtinut spune ca daca curierul a inceput lucrul de la C, atunci in 33 de cazuri din 100 va fi in B dupa doua livrari. Este clar că calculele sunt simple, dar dacă trebuie să determinați probabilitatea după 5 sau 15 livrări, acest lucru poate dura destul de mult.
Să luăm în considerare o modalitate mai simplă de a calcula astfel de probabilități. Pentru a obține probabilitățile de tranziție din diferite stări în 2 pași, pătratăm matricea P:
Atunci elementul (2, 3) este probabilitatea de a trece de la C la B în 2 pași, care a fost obținută mai sus într-un mod diferit. Rețineți că și elementele din matricea P2 variază de la 0 la 1, iar suma dintre coloane este 1.
Acea. dacă trebuie să determinați probabilitățile de tranziție de la C la B în 3 pași:
1 cale. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0,37*0,3 + 0,33*0,4 + 0,3*0,3 = 0,333 unde p(CA) - probabilitatea trecerii de la C la A în 2 pași (adică acesta este un element (1, 3) al matricei P 2).
2 sensuri. Calculați matricea P 3:
Matricea probabilităților de tranziție la a 7-a putere va arăta astfel:
Este ușor de observat că elementele fiecărui rând tind spre anumite numere. Aceasta înseamnă că după suficient un numar mare livrare, nu contează în ce raion a început curierul să lucreze. Acea. la sfârșitul săptămânii, aproximativ 38,9% vor fi în A, 33,3% vor fi în B și 27,8% vor fi în C. O astfel de convergență este garantată dacă toate elementele matricei probabilității de tranziție aparțin intervalului (0 , 1).
Teoria cozilor
Aceasta este secțiunea cercetare operațională care consideră diverse proceselorîn economie, precum și în comunicațiile telefonice, asistența medicală și alte domenii, ca procese de servicii, adică satisfacerea unor solicitări, comenzi (de exemplu, deservirea navelor în port - descărcarea și încărcarea acestora, întreținerea strunjitorilor în depozitul de scule din atelier - eliberarea tăietorilor acestora, deservirea clienților în spălătorie - spălarea rufelor etc.).
În ciuda diversităţii lor, aceste procese au aspecte comune: cerințe service neregulat (accidental) canal de servicii(loc la dană, o fereastră în camera de transfer) și, în funcție de angajarea acestuia, durata serviciului și alți factori, forma coada de cerinte.
Teoria cozilor studiază tiparele statistice de primire a cerințelor și, pe această bază, dezvoltă solutii, adică astfel de caracteristici sub care timpul petrecut cu așteptarea în coadă, pe de o parte, și pe canalele de servicii inactive, pe de altă parte, ar fi cel mai mic. Întregul sistem de producție și consum de bunuri poate fi interpretat ca un sistem de așteptare în care oamenii (clienții) și mărfurile se întâlnesc. Suma timpului pierdut de așteptare la cozi și a timpului de nefuncționare a canalelor de servicii (depozitarea mărfurilor în depozite) este considerată ca măsură eficienţă studiat sistem economic.
Metode de analiza a sistemelor de asteptare
Metodele și modelele utilizate în teoria stării de așteptare pot fi împărțite condiționat în analitice și simulare.
Metode de analiză teoriile de coadă fac posibilă obținerea caracteristicilor sistemului ca unele funcții ale parametrilor funcționării acestuia. Acest lucru face posibilă efectuarea unei analize calitative a influenței factorilor individuali asupra eficienței QS.
Metode de simulare se bazează pe modelarea proceselor de așteptare pe un computer și sunt utilizate dacă este imposibil să se utilizeze modele analitice.
În prezent, cele mai dezvoltate teoretic și mai convenabile în aplicațiile practice sunt metodele de rezolvare a problemelor de coadă în care fluxul de cerințe de intrare este cel mai simplu (Poisson).
Pentru cel mai simplu flux, frecvența cererilor care intră în sistem respectă legea Poisson, adică. probabilitatea de a ajunge la timp t neted La cerințele sunt date de formula:
Cel mai simplu flux are trei proprietăți principale:
1) obișnuit,
2) staţionare şi
3) lipsa efectelor secundare.
Ordinaritatea flux înseamnă imposibilitatea practică a primirii simultane a două sau mai multe cerințe. De exemplu, probabilitatea ca mai multe utilaje dintr-un grup de mașini deservite de o echipă de reparatori să se defecteze în același timp este destul de mică.
Staționar se numește un flux, pentru care așteptarea matematică a numărului de cerințe care intră în sistem pe unitatea de timp (notăm A, este parametrul distribuției Poisson) nu se modifică în timp. Astfel, probabilitatea de a intra în sistem o anumită sumă cerințe într-o anumită perioadă de timp La depinde de valoarea sa și nu depinde de originea referinței sale pe axa timpului.
Nici un efect secundarînseamnă că numărul de solicitări primite de sistem înainte t, nu determină câte solicitări vor intra în sistem într-o perioadă de timp de la t inainte de t + Dt
De exemplu, dacă o rupere a firului are loc la un anumit moment de timp și este eliminată de țesător, atunci aceasta nu determină dacă va avea loc sau nu o nouă rupere pe acest răzător în momentul următor, cu atât mai mult. nu afectează probabilitatea unei întreruperi la alte mașini.
Caracteristica importanta SMO - timpul de serviciu al cererilor în sistem. Durata de service pentru o cerință este, de regulă, variabilă aleatorieși, prin urmare, poate fi descris printr-o lege de distribuție. Cel mai utilizat în teorie și mai ales în aplicații practice este legea exponențială a distribuției timpului de serviciu. Funcția de distribuție pentru această lege este:
acestea. probabilitatea ca timpul de serviciu să nu depășească o anumită valoare t, este definit prin formula (5.2), unde µ - parametrul legii exponențiale de distribuție a timpului de serviciu al cerințelor în sistem, i.e. reciproca timpului mediu de serviciu
Sistemele de așteptare sunt clasificate:
1. În funcţie de conditii de asteptareînceperea serviciului:
QS cu pierderi (eșecuri)
CMO cu așteptări
În SMO cu eșecuri cererile care sosesc în momentul în care toate canalele de servicii sunt ocupate sunt respinse și părăsesc sistemul. Un exemplu clasic de sistem cu defecțiuni este centrala telefonică. Dacă persoana apelată este ocupată, atunci cererea de conectare este refuzată și părăsește sistemul.
În SMO cu asteptare o solicitare, după ce a găsit toate canalele de difuzare ocupate, se pune la coadă și așteaptă până când unul dintre canalele de difuzare devine liber.
Este apelat un QS care permite o coadă, dar cu un număr limitat de solicitări în ea sisteme cu lungime limitată la coadă.
Se apelează un QS care permite o coadă, dar cu un timp de rezidență limitat pentru fiecare client din acesta sisteme de latență.
2. În funcție de numărul de canale de servicii, QS sunt împărțite în:
Un singur canal;
Multicanal.
3. În funcție de locația sursei cerințelor, QS-urile sunt împărțite în:
deschis, când sursa cerinței este în afara sistemului;
închis, când sursa se află în sistemul propriu-zis.
19.7. Probleme de analiză a sistemelor de așteptare închise și deschise
Inchis si deschis sisteme, in functie din timpul de așteptare pot fi și sisteme de așteptare cu așteptare. Acestea sunt cele mai comune SMO-uri. Ele sunt studiate folosind modele analitice.
sistem de așteptare Un sistem se numește sistem în care cererile primite într-un moment în care toate canalele de difuzare sunt ocupate sunt puse în coadă și deservite pe măsură ce canalele devin libere.
Un exemplu de sistem cu buclă deschisă este un atelier de reparații TV. Aici, televizoarele defecte sunt sursa cerințelor de întreținere, ele sunt în afara sistemului în sine, astfel încât numărul de cerințe poate fi considerat nelimitat. QS închis include, de exemplu, un atelier de mașini, în care mașinile sunt o sursă de defecțiuni și, în consecință, o sursă de cerințe pentru întreținerea lor, de exemplu, de către o echipă de reglatori.
Declarația generală a problemei este următoarea. Sistemul are P canale de servire, fiecare dintre acestea putând servi doar o singură cerință la un moment dat.
Sistemul primește cel mai simplu flux (Poisson) de cereri cu parametrul A. P cerințe, adică toate canalele sunt ocupate, apoi această solicitare este pusă în coadă și așteaptă să înceapă serviciul. Timpul de serviciu al fiecărei cerințe este o variabilă aleatoare care respectă legea distribuției exponențiale cu parametrul µ .
QS-ul așteptat poate fi împărțit în două grupuri mari: închisși deschis. LA închis include sisteme în care fluxul de cerințe de intrare apare în sistemul însuși și este limitat. De exemplu, un maistru a cărui sarcină este să monteze mașini în atelier trebuie să le întrețină periodic. Fiecare mașină configurată devine o sursă potențială de cerințe de configurare. În astfel de sisteme, numărul total de revendicări circulante este finit și cel mai adesea constant.
Dacă sursa de alimentare are un număr infinit de cerințe și este situată în afara sistemului, atunci sistemul este apelat deschis. Exemple de sisteme deschise sunt magazinele, casele de bilete din stații, porturi etc. Pentru aceste sisteme, fluxul de cerințe de intrare poate fi considerat nelimitat. În plus, QS în buclă deschisă cu așteptare și o lungime limitată la coadă, cu un timp limitat petrecut în coadă etc., sunt destul de comune.
Caracteristicile remarcate ale funcționării QS cu așteptare, datorită tipurilor lor, impun anumite condiții aparatului matematic utilizat. Calculul caracteristicilor de funcționare a tuturor acestor QS poate fi efectuat pe baza calculului probabilităților stărilor QS (așa-numitele formule Erlang).
Luați în considerare procedura de calcul a caracteristicilor muncii sisteme în buclă deschisă cu așteptare și lungime limitată la coadă.
Aceste SMO-uri sunt formate din P canale de servire, fiecare dintre acestea putând servi doar o singură cerință la un moment dat. Sistemul primește cel mai simplu flux de cereri cu parametrul A., iar timpul de serviciu al cererii este o variabilă aleatorie care se supune unei legi de distribuție exponențială cu parametrul c. Dacă în momentul primirii următoarei cereri toate P canalele sunt ocupate, iar coada nu este mai mică T cerințe, cererea este pusă în coadă. Dacă este deja în coadă T cerințe, apoi cerința primită părăsește QS. Cu alte cuvinte, cererea este respinsă dacă sistemul are n + t cerințe. Din ecuațiile care descriu starea unor astfel de sisteme, se pot obține următoarele formule pentru calcularea principalelor caracteristici ale acestora.
1. Probabilitatea ca toate canalele de difuzare să fie gratuite,
(5.14)
2. Probabilitatea ca sistemul să fie La cerințe, cu condiția ca numărul total al acestor cerințe să nu depășească numărul de canale de difuzare; cu alte cuvinte, probabilitatea de a fi ocupat La canale,
 |
3. Probabilitatea ca sistemul să fie La cerințe, atunci când numărul acestor cerințe este mai mare decât numărul de canale de difuzare,
(5.16)
4. Probabilitatea ca toate canalele de difuzare să fie ocupate,
(5.17)
5. Probabilitatea de eșec
(5.18)
6. Lungimea medie a cozii
7. Numărul mediu de canale gratuite
Exemplul 2 Compania se ocupă de livrarea mărfurilor la comenzi și are patru mașini care lucrează non-stop. Fluxul de comenzi este cel mai simplu și, în medie, se primește o cerere pe oră. Timpul de transport al mărfurilor este supus unei legi de distribuție exponențială și, în medie, transportul unei mărfuri durează o oră. Când numărul de comenzi pentru transport este de 10, compania nu mai acceptă cereri până când coada scade.
Este necesar să se determine caracteristicile companiei.
Soluţie. Acest sistem se referă la tipul de QS cu așteptare și lungime limitată la coadă. Să găsim parametrii sistemului, luând o oră ca unitate de timp:
Probabilitatea ca toate mașinile să fie libere de la transportul mărfurilor se găsește prin formula (5.14):
Probabilitatea ca toate mașinile să fie ocupate este determinată de formula (5.17) și este
Atunci probabilitatea refuzului de a accepta o comandă de transport, calculată prin formula (5.18) va fi egală cu
, iar lungimea medie a cozii în conformitate cu formula (5.19) va fi
Atunci probabilitatea refuzului de a accepta un ordin de transport, calculată prin formula (5.18), va fi egală cu
iar lungimea medie a cozii în conformitate cu formula (5.19) va fi
Astfel, clientul nu va primi aproape niciodată un refuz de a accepta o cerere de transport, cu toate acestea, încărcarea vehiculelor va fi destul de mică. De exemplu, în doar două cazuri din o sută vor fi ocupate toate cele patru mașini.
Să trecem la luarea în considerare a algoritmilor pentru calcularea caracteristicilor funcționării QS închis cu așteptări. Deoarece sistemul este închis, la declarația problemei ar trebui adăugată o condiție: fluxul de cereri primite este limitat, de exemplu. nu mai pot fi în sistemul de service în același timp T cerințe (T - numărul de obiecte servite). Astfel de SMO-uri mai sunt numite sisteme cu așteptare și un flux limitat de cereri.
Ca un criteriu care caracterizează calitatea funcționării sistemului luat în considerare, vom lua raportul dintre lungimea medie a cozii de așteptare și cel mai mare număr de cerințe care sunt simultan în sistemul de deservire sau raportul de nefuncționare a obiectelor deservite. Ca un alt criteriu, luăm raportul dintre numărul mediu de canale de difuzare inactive și numărul lor total sau raportul de inactivitate al canalelor de difuzare.
Primul dintre criterii caracterizează pierderea de timp din cauza așteptării începerii serviciului. Al doilea criteriu arată caracterul complet al sarcinii sistemului de servicii și este important în sarcinile de organizare a muncii.
Evident, o coadă poate apărea numai atunci când numărul de canale este mai mic decât cel mai mare număr cerințe care se află simultan în sistemul de servicii (P< т).
Prezentăm succesiunea de calcule a caracteristicilor QS închis cu așteptare și formulele necesare.
1. Parametru α=α/µ. -
indicator de încărcare a sistemului, de ex. așteptarea matematică a numărului de solicitări care intră în sistem într-un timp egal cu timpul mediu de serviciu 
2. Probabilitatea de a fi ocupat La canale de difuzare, cu condiția ca numărul de cerințe din sistem să nu depășească numărul de canale de difuzare ale sistemului,