Teoria cozilor

Teoria cozilor de așteptare , sau teoria cozilor de așteptare, este o secțiune a teoriei probabilităților , al cărei scop este alegerea rațională a structurii sistemului de așteptare și a procesului de serviciu bazat pe studiul fluxului cerințelor de servicii care intră și ies din sistem, timp de așteptare și lungimi de coadă [1] . Teoria de așteptare folosește metode din teoria probabilității și statistica matematică .

Istorie

Teoria fluxului de evenimente omogene , care a stat la baza teoriei cozilor de aşteptare, a fost dezvoltată de matematicianul sovietic A. Ya. Khinchin [2] .

Primele probleme în teoria cozilor de așteptare ( QMT ) au fost luate în considerare de către omul de știință al companiei de telefonie din Copenhaga Agner Erlang între 1908 și 1922. Sarcina a fost de a eficientiza activitatea centrală telefonică și de a calcula în avans calitatea serviciului clienți în funcție de numărul de dispozitive utilizate.

Există un nod telefonic ( dispozitiv de service ), unde operatorii de telefonie conectează din când în când numere de telefon individuale. Sistemele de așteptare (QS) pot fi de două tipuri: cu așteptare și fără așteptare (adică cu pierderi). În primul caz, un apel ( cerere, cerere ), care a sosit la stație în momentul în care linia necesară este ocupată, trebuie să aștepte momentul conectării. În al doilea caz, el „părăsește sistemul” și nu necesită atenția QS-ului.

Sistemele de așteptare sunt un instrument matematic eficient pentru studierea unei game largi de procese socio-economice [3] și demografice reale [4] .

Flux

Flux uniform

Fluxul de aplicații este omogen dacă:

toate aplicațiile sunt egale
sunt luate în considerare doar momentele primirii cererilor, adică faptele cererilor fără precizarea detaliilor fiecărei cereri specifice.

Flux fără efect secundar

Un flux fără efect secundar , dacă numărul de evenimente din orice interval de timp ( , ) nu depinde de numărul de evenimente din orice alt interval de timp care nu se intersectează cu al nostru ( , ). $t$ $t+x$ $t$ $t+x$

Flux staționar

Fluxul de cereri este staționar dacă probabilitatea de apariție a n evenimente în intervalul de timp ( , ) nu depinde de timp , ci depinde doar de lungimea acestei secțiuni. $t$ $t+x$ $t$ $X$

Cel mai simplu flux

Un flux staționar omogen fără efecte secundare este cel mai simplu flux Poisson .

Numărul de evenimente ale unui astfel de flux care se încadrează pe intervalul de lungime , este distribuit conform Legii lui Poisson : $n$ $X$

P(n,x)={\frac {(\lambda x)^{n}e^{-\lambda x}}{n!}}.

Fluxul de cereri Poisson este convenabil pentru rezolvarea problemelor TMT. Strict vorbind, cele mai simple fluxuri sunt rare în practică, dar multe fluxuri simulate pot fi considerate ca fiind cele mai simple.

Debit normal

Un flux staționar fără efecte secundare, pentru care intervalele dintre evenimente sunt distribuite conform legii normale, se numește flux normal [5] : . $f(t)={\frac {1}{{\sqrt {2\pi }}\sigma _{t}}}\exp {-{\frac {1}{2}}\left({ \frac {t-m_{t}}{\sigma _{t}}}\right)^{2}}$

Fluxul Erlang

Un flux Erlang de ordinul al treilea este un flux staționar fără efecte secundare, în care intervalele dintre evenimente sunt suma variabilelor aleatoare independente distribuite identic conform unei legi exponențiale cu un parametru [6] . Când pârâul Erlang este cel mai simplu flux. $k$ $k+1$ $\lambda$ $k=0$

Densitatea de distribuție a valorii aleatoare a intervalului T între două evenimente învecinate în fluxul Erlang de ordinul al treilea este: , . $k$ $f_{k}(t)={\frac {\lambda (\lambda t)^{k)}{\Gamma (\alpha )))\exp {-\beta t)$ $t>0,\alpha \geqslant 1$

Gamma Flux

Un flux gamma este un flux staționar fără efecte secundare, în care intervalele dintre evenimente sunt variabile aleatorii supuse unei distribuții gamma cu parametri și : , , unde [7] . $\alfa$ $\beta$ $f(t)={\frac {\beta ^{\alpha }t^{\alpha -1}}{k!}}\exp {-\lambda t}$ $t>0$ $\Gamma (\alpha )=\int _{0}^{\infty }x^{\alpha -1}\exp {-x}dx$

La , fluxul gamma este un flux Erlang de ordinul al treilea. $\alpha =k+1$ $k$

Densitatea instantanee

Densitatea ( intensitatea ) instantanee a fluxului este egală cu limita raportului dintre numărul mediu de evenimente pe interval de timp elementar ( , ) și lungimea intervalului ( ), când acesta din urmă tinde spre zero. $t$ $t+x$ $X$

\lambda (t)=\lim _{{x\to 0}}\left({\frac {M(t+x)-M(t)}{x}}\right)

sau, pentru cel mai simplu flux,

\lambda ={\frac {M(x)}{x)),

unde este egal cu așteptarea matematică a numărului de evenimente din intervalul . $M(x)$ $X$

Formula lui Little

N^{*}=\lambda T.

Numărul mediu de cereri din sistem este egal cu produsul dintre intensitatea fluxului de intrare și timpul mediu de rezidență al cererii în sistem.

Vezi și

Note

↑ Teoria cozilor // Dicţionar enciclopedic matematic. - M .: „Enciclopedia Sovietică”, 1988, p. 327-328
↑ Dicționar de cibernetică / Editat de academicianul V. S. Mikhalevich . - al 2-lea. - Kiev: Ediția principală a Enciclopediei sovietice ucrainene numită după M.P.Bazhan, 1989. - S. 486. - 751 p. - (C48). — 50.000 de exemplare. - ISBN 5-88500-008-5 .
↑ Afanasyeva L. G., Rudenko I. V. Sisteme de servicii GI|G|∞ și aplicațiile lor la analiza modelelor de transport // Teoria probabilității și aplicarea acesteia. - 2012. T. 57 Numărul. 3. - S. 427-452.
↑ Nosova M. G. Sistem autonom non-markovian de așteptare și aplicarea lui în probleme demografice: dis. … cand. fizică.matematică. Științe: 13.05.18. - Tomsk, 2010. - S. 204.
↑ Ovcharov, 1969 , p. 22.
↑ Ovcharov, 1969 , p. 24.
↑ Ovcharov, 1969 , p. 40.

Literatură

Ivchenko G.I., Kashtanov V.A., Kovalenko I.N. Teoria cozilor. — Manual pentru universități. - M . : Şcoala superioară, 1982. - 256 p. — 20.000 de exemplare.
Kleinrock L. Teoria stării de aşteptare. Pe. din engleza. / Per. I. I. Grushko; ed. V. I. Neiman. - M . : Mashinostroenie, 1979. - 432 p. — 10.000 de exemplare.
Matveev VF, Ushakov VG Sisteme de așteptare. - M. : MGU, 1984. - 240 p.
Dicţionar Enciclopedic Matematic / Ch. ed. Yu. V. Prohorov. - M . : Enciclopedia Sovietică, 1988. - 847 p.
Lifshits A. L., Malts E. A. Modelarea statistică a sistemelor de așteptare / Prefață. membru corespondent Academia de Științe a URSS N. P. Buslenko . - M . : Sov. Radio, 1978. - 248 p.
Ventzel E. S. , Ovcharov L. A. Teoria probabilității (Capitolul 10. Procese Markov. Fluxuri de evenimente. Teoria cozilor). - M .: „Știință”. Editura principală de literatură fizică și matematică, 1969. - 368 p. — 100.000 de exemplare.
Borovkov AA Procese probabilistice în teoria stării de așteptare. - M .: „Știință”. Editura principală de literatură fizică și matematică, 1972. - 368 p. - (Teoria Probabilității și Statistica Matematică). - 13.000 de exemplare.
Ovcharov L. A. Probleme aplicate ale teoriei cozilor. - M . : Mashinostroenie, 1969. - 323 p. - 7500 de exemplare.
Gnedenko B. V. , Kovalenko I. N. Introducere în teoria cozilor. - M .: Editura „Nauka”, Ediția principală de literatură fizică și matematică, 1966. - 432 p. - 12000 de exemplare.

Dicționare și enciclopedii

În cataloagele bibliografice
BNF : 12647707b GND : 4255044-0 J9U : 987007553435905171 LCCN : sh85109832 NDL : 00567524 NKC : ph276803