Köteori

Köteori , eller köteori , är en del av sannolikhetsteorin , vars syfte är det rationella valet av kösystemets struktur och tjänsteprocessen baserat på studiet av flödet av tjänstekrav som kommer in i och ut ur systemet. väntetid och kölängder [1] . I köteori används metoder från sannolikhetslära och matematisk statistik .

Historik

Teorin om flödet av homogena händelser , som låg till grund för teorin om köande, utvecklades av den sovjetiske matematikern A. Ya Khinchin [2] .

De första problemen i köteorin ( QMT ) övervägdes av vetenskapsmannen Agner Erlang från Köpenhamns telefonbolag mellan 1908 och 1922. Uppdraget var att effektivisera telefonväxelns arbete och i förväg beräkna kvaliteten på kundtjänsten beroende på antalet apparater som användes.

Det finns en telefonnod ( serviceapparat ), där telefonoperatörer då och då kopplar individuella telefonnummer till varandra. Kösystem (QS) kan vara av två typer: med väntan och utan väntan (det vill säga med förluster). I det första fallet måste ett samtal ( efterfrågan, begäran ), som anlände till stationen i det ögonblick då den önskade linjen är upptagen, vänta på anslutningsögonblicket. I det andra fallet "lämnar han systemet" och kräver inte QS:s uppmärksamhet.

Kösystem är ett effektivt matematiskt verktyg för att studera en lång rad verkliga socioekonomiska [3] och demografiska processer [4] .

Flöde

Enhetligt flöde

Ansökningsflödet är homogent om:

alla applikationer är lika
endast ögonblicken för mottagandet av ansökningar beaktas, det vill säga fakta om ansökningar utan att specificera detaljerna för varje specifik ansökan.

Flöde utan efterverkan

Ett flöde utan efterverkan , om antalet händelser i något tidsintervall ( , ) inte beror på antalet händelser i något annat tidsintervall som inte skär med vårt ( , ). $t$ $t+x$ $t$ $t+x$

Stationärt flöde

Flödet av förfrågningar är stationärt om sannolikheten för att n händelser inträffar i tidsintervallet ( , ) inte beror på tiden , utan bara beror på längden på detta segment. $t$ $t+x$ $t$ $x$

Det enklaste flödet

Ett homogent stationärt flöde utan efterverkningar är det enklaste , Poisson- flödet .

Antalet händelser i en sådan ström som faller på längdintervallet fördelas enligt Poissons lag : $n$ $x$

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

Poisson-flödet av förfrågningar är bekvämt för att lösa TMT-problem. Strängt taget är de enklaste flödena sällsynta i praktiken, men många simulerade flöden kan betraktas som de enklaste.

Normalt flöde

Ett stationärt flöde utan efterverkningar, för vilket intervallen mellan händelserna är fördelade enligt normallagen, kallas normalt flöde [5] : . $f(t)={\frac {1}{{\sqrt {2\pi }}\sigma _{t}}}\exp {-{\frac {1}{2}}\left({ \frac {t-m_{t}}{\sigma _{t}}}\right)^{2}}$

Erlang stream

Ett Erlang-flöde av ordningen är ett stationärt flöde utan efterverkningar, där intervallen mellan händelser är summan av oberoende slumpvariabler fördelade identiskt enligt en exponentiell lag med en parameter [6] . När Erlang-strömmen är den enklaste strömmen. $k$ $k+1$ $\lambda$ $k=0$

Fördelningstätheten för det slumpmässiga värdet av T-intervallet mellan två angränsande händelser i Erlang-flödet av den e ordningen är: , . $k$ ${\displaystyle f_{k}(t)={\frac {\lambda (\lambda t)^{k)){\Gamma (\alpha )))\exp {-\beta t))$ $t>0,\alpha \geqslant 1$

Gamma Flux

Ett gammaflöde är ett stationärt flöde utan efterverkningar, där intervallen mellan händelser är slumpvariabler föremål för en gammafördelning med parametrar och : , , där [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$

Vid är gammaflödet ett Erlang-flöde av ordningen. $\alpha =k+1$ $k$

Momentan densitet

Den momentana densiteten ( intensiteten ) av flödet är lika med gränsen för förhållandet mellan det genomsnittliga antalet händelser per elementärt tidsintervall ( , ) och längden av intervallet ( ), när det senare tenderar mot noll. $t$ $t+x$ $x$

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

eller, för det enklaste flödet,

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

där är lika med den matematiska förväntan av antalet händelser i intervallet . $M(x)$ $x$

Littles formel

N^{*}=\lambda T.

Det genomsnittliga antalet förfrågningar i systemet är lika med produkten av ingående flödesintensitet och den genomsnittliga uppehållstiden för begäran i systemet.

Se även

Anteckningar

↑ Queuing Theory // Mathematical Encyclopedic Dictionary. - M .: "Soviet Encyclopedia", 1988, s. 327-328
↑ Dictionary of Cybernetics/Redigerad av akademikern V. S. Mikhalevich . - 2:a. - Kiev: Huvudupplagan av den ukrainska sovjetiska uppslagsboken uppkallad efter M.P. Bazhan, 1989. - S. 486. - 751 s. - (C48). — 50 000 exemplar. - ISBN 5-88500-008-5 .
↑ Afanasyeva L. G., Rudenko I. V. Servicesystem GI|G|∞ och deras tillämpningar för analys av transportmodeller // Sannolikhetsteori och dess tillämpning. - 2012. T. 57 Nummer. 3. - S. 427-452.
↑ Nosova M. G. Autonoma icke-markoviska kösystem och dess tillämpning i demografiska problem: dis. … cand. fys.math. Vetenskaper: 05.13.18. - Tomsk, 2010. - S. 204.
↑ Ovcharov, 1969 , sid. 22.
↑ Ovcharov, 1969 , sid. 24.
↑ Ovcharov, 1969 , sid. 40.

Litteratur

Ivchenko G.I., Kashtanov V.A., Kovalenko I.N. Queuing Theory. — Lärobok för universitet. - M . : Högre skola, 1982. - 256 sid. — 20 000 exemplar.
Kleinrock L. Theory of queuing. Per. från engelska. / Per. I. I. Grushko; ed. V. I. Neiman. - M . : Mashinostroenie, 1979. - 432 sid. — 10 000 exemplar.
Matveev VF, Ushakov VG Kösystem. - M. : MGU, 1984. - 240 sid.
Mathematical Encyclopedic Dictionary / Kap. ed. Yu. V. Prokhorov. - M . : Soviet Encyclopedia, 1988. - 847 sid.
Lifshits A. L., Malts E. A. Statistisk modellering av kösystem / Förord. motsvarande medlem USSR :s vetenskapsakademi N. P. Buslenko . - M . : Sov. Radio, 1978. - 248 sid.
Ventzel E. S. , Ovcharov L. A. Sannolikhetsteori (kapitel 10. Markov-processer. Händelseflöden. Köteori). - M . : "Vetenskap". Main Publishing House of Physical and Mathematical Literature, 1969. - 368 sid. — 100 000 exemplar.
Borovkov AA Probabilistiska processer i teorin om köande. - M . : "Vetenskap". Main Publishing House of Physical and Mathematical Literature, 1972. - 368 sid. - (Sannolikhetsteori och matematisk statistik). - 13 000 exemplar.
Ovcharov L. A. Tillämpade problem med teorin om köande. - M . : Mashinostroenie, 1969. - 323 sid. - 7500 exemplar.
Gnedenko B. V. , Kovalenko I. N. Introduktion till teorin om köande. - M .: Förlaget "Nauka", Huvudupplagan av fysisk och matematisk litteratur, 1966. - 432 sid. - 12000 exemplar.

Ordböcker och uppslagsverk

I bibliografiska kataloger
BNF : 12647707b GND : 4255044-0 J9U : 987007553435905171 LCCN : sh85109832 NDL : 00567524 NKC : ph276803