Letztes Mal Betrachten Sie M / M / N / N wie zuvor angekündigt. Diesmal [Warteschlangentheorie (geschrieben von Shinichi Oishi)](https://www.amazon.co.jp/%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97% E7% 90% 86% E8% AB% 96-% E5% A4% A7% E7% 9F% B3-% E9% 80% B2% E4% B8% 80 / dp / 4339060739) wird bezeichnet.

Was ist ein M / M / N / N-Modell?

Das M / M / N / N-Modell ist ein Ein-Server-Modell, bei dem der Client gemäß der Poisson-Verteilung ankommt und die Servicezeit der Exponentialverteilung folgt. Die maximale Länge der Matrix beträgt 0. Dies bedeutet, dass Sie nicht anstehen können. Servicedisziplin wird weggelassen, aber es ist FCFS. Dieses System ist auch als Alans Anrufverlustraten-System bekannt. Dieses Modell ist eine Grundidee für Modelle, die nicht so in die Warteschlange gestellt werden können. Daher ist es gut zu verstehen. Beachten Sie auch, dass in diesem Modell die Verwendung per Definition $ \ rho = \ frac {\ lambda} {N \ mu} $ ist.

Wahrscheinlichkeit von n Personen im System

Angenommen, der Client kommt gemäß dem Poisson-Prozess. Nehmen wir also an, dass höchstens ein Client in einem ausreichend kurzen Zeitintervall $ \ Delta t $ kommt. Wenn zu diesem Zeitpunkt die durchschnittliche Ankunftsrate $ \ lambda $ beträgt, kann die Wahrscheinlichkeit, dass ein Kunde kommt, als $ \ lambda \ Delta t $ ausgedrückt werden. Hier sei $ P_k (t) $ die Wahrscheinlichkeit, dass sich zum Zeitpunkt t k Clients im System befinden. Wir werden die Änderung dieser Wahrscheinlichkeit nach $ \ Delta t $ beschreiben. Ebenso beträgt die Wahrscheinlichkeit, dass ein Client einen Server mit einer durchschnittlichen Servicerate von $ \ mu $ verlässt, $ \ mu \ Delta t $. Bis zu diesem Punkt ist es das gleiche wie die vorherige Annahme. Nehmen wir diesmal an, dass die durchschnittliche Servicerate, wenn der Zustand k $ 1 \ leq k \ leq n $ ist, $ k \ mu $ ist. Dies bedeutet, dass k Server mit einer durchschnittlichen Servicerate von $ \ mu $ ausgeführt werden. Im Folgenden betrachten wir eine Gleichung (Zustandsgleichung), die die Änderung der Anzahl der Clients im System ausdrückt. Berücksichtigen Sie jedoch wie im vorherigen die Grenze, indem Sie auf die Grenze $ k = 0, N $ achten. Wenn Sie davon ausgehen, dass es nach einer ausreichenden Zeit einen stabilen Zustand erreicht hat P_k=\frac{\frac{a^k}{k!}}{\sum_{i=0}^{N}\frac{a^i}{i!}} $ (I = 0, ..., N), a = \ frac {\ lambda} {\ mu} $. Jetzt kennen wir die Wahrscheinlichkeit, dass sich k Clients im System befinden. Danach werde ich versuchen, eine Formel zu finden, die in den frühen Geschichten der Warteschlange häufig vorkommt.

Durchschnittliche Anzahl der Kunden im System L.

Da L der Durchschnittswert ist, dh der erwartete Wert, kann er aus $ L = \ sum_ {k = 0} ^ {N} kP_k $ berechnet werden. Daher ist $ L = \ sum_ {k = 0} ^ {N} kP_k $ =a\frac{\sum_{k=0}^{N}\frac{a^k}{k!}-\frac{a^N}{N!}}{\sum_{k=0}^{N}\frac{a^k}{k!}} =a(1-P_N)

Durchschnittliche Wartezeit im System W.

Aus der Formel von Little $ W = \ frac {L} {\ lambda} = \ frac {1-P_N} {\ mu} $

Durchschnittliche Anzahl der Kunden in der Warteschlange L_q

Es wird 0 sein, da keine Warteschlange vorhanden ist.

Durchschnittliche Wartezeit in der Warteschlange W_q

Es wird 0 sein, weil es nicht in der Warteschlange steht.

Anrufverlustrate

Die Anrufverlustrate ist der Prozentsatz der Personen, die nicht in die Warteschlange gestellt werden können und evakuiert werden. Es wird normalerweise als $ P_b $ oder $ E_N (a) $ geschrieben, aber hier wird es als $ E_N (a) $ geschrieben. Die Anrufverlustrate entspricht der Wahrscheinlichkeit, dass der Server voll ist, also $ E_N (a) = P_N $. Es heißt Alan B-Typ, weil Herr Ala dies gefunden hat. Abgesehen davon scheint es sogar eine C-Formel zu geben. Interessanter als eine schrittweise Formel E_0(a)=1 E_N=\frac{a E_{N-1}(a)}{s+a E_{N-1}(a)} Wird eingerichtet und wenn Sie $ F_N (a) = \ frac {1} {E_N (a)} $ setzen F_0(a)=1 F_N(a)=1+\frac{N}{a}F_{N-1}(a) Ist festgelegt. In beiden Fällen ist N eine ganze Zahl größer oder gleich 1.

Betrag Y übergeben und Betrag a_l verloren

Der übergebene Betrag ist die durchschnittliche Anzahl der Kunden im System. Das heißt, $ Y = a (1-P_N) = a (1-E_N (a)) $. Davon zu subtrahieren ist der übergebene Betrag vom Gesamtdurchschnitt a, um den verlorenen Betrag zu berechnen, $ a_l = a-Y = a E_N (a) $.

Beziehung zwischen a und N.

Sei B $ E_N (a) = B $ mit einem konstanten Wert von 0 oder mehr und 1 oder weniger. Zu diesem Zeitpunkt ist die partielle Differentialgleichung für a von $ E_N (a) $ \frac{\partial E_N(a)}{\partial a}=(\frac{N}{a}-1+E_N(a))E_N(a) Kann für a und N erhalten werden, indem unter der Bedingung $ E_N (a) = B $ gelöst wird. Darüber hinaus scheint die Nutzungsrate $ \ rho_N (B) = \ frac {a (1-B)} {N} $ von N, a und B zu gelten. Dieses Mal werde ich eine Grafik dieser beiden in Python zeichnen. Dies ist das Programm.

`Python:M_M_N_N.py![N_a.png](https://qiita-image-store.s3.amazonaws.com/0/167385/d4735a76-af5c-4604-d1a4-c555f4b480ef.png)`



# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt

#Verschwenderisches Programm

def E_B(N, a):
    #Berechnen Sie die Alan B-Gleichung.
    #N ist die Anzahl der Server
    #a ist die Verkehrsdichte
    p=1
    i=1
    while i < N+1:
       b = a * p
       p = b / (i + b)
       i += 1
    return p



def make_list(n, b):
    #n ist die maximale Anzahl von Servern
    #b ist die Zielfunktion E zum Lösen nach der Newton-Methode_B(N, a)-Repräsentiert B von B und repräsentiert die Anrufverlustrate.
    p = [0 for i in range(n+1)]  # n+Der erste ist E._B(N, a)Wird
    p[0] = 0  # a=s=Weil 0 eindeutig gilt
    c = 1  # a_Bestimmen Sie den Anfangswert c als 0.
    for i in range(1, len(p)):
        a = c
        # E(N,a)=Finden Sie den Wert, der zu B wird, indem Sie ihn etwa 20 Mal wiederholen.
        for j in range(20):
            t = E_B(i, a)
            a = a - (t-b) / ((i/a-1+t)*t)
        p[i] = a
        c=a #Aktualisieren Sie das nächste Mal auf einen angemessenen Anfangswert

    return p


#Von hier aus zeichnen und ausführen
n=50
b=0.01
p = make_list(n, b)

plt.figure()
plt.plot(range(n+1), p)
plt.xlabel("N")
plt.ylabel("a")
plt.title("E_N(a)=%.3f" % b)

plt.figure()
rho = [0]

for n, a in enumerate(p):
    if n == 0:
        continue
    rho.append(a*(1-b)/n)

plt.plot(range(n+1), rho)
plt.xlabel("N")
plt.ylabel("rho_N(B)")
plt.title("E_N(a)=%.3f" % b)

plt.show()

Gemäß diesem Programm ist die Beziehung zwischen der Verkehrsdichte a und der Anzahl der Server N Und die Nutzungsrate $ \ rho_N (B) $, wenn B die Anrufverlustrate ist

Zusammenfassung

Bis jetzt war diese Serie Qiita, aber es gab keine Programmierung, also habe ich sie hinzugefügt. Bitte beachten Sie, dass die Berechnung durchgeführt wird, wenn $ 0 <\ rho <1 $ ist. Wenn Sie also mit einem anderen Wert rechnen, ist dies ein seltsamer Wert. Und ich lerne immer noch mit dem Einführungsbuch, also könnte es falsch sein. Was soll ich das nächste Mal tun?

[PYTHON] Warteschlangentheorie Teil 3