[PYTHON] Théorie de la file d'attente partie 3

Dernière fois Considérez M / M / N / N comme annoncé précédemment. Cette fois, [Théorie de la file d'attente (écrite par Shinichi Oishi)](https://www.amazon.co.jp/%E5%BE%85%E3%81%A1%E8%A1%8C%E5%88%97% Il est fait référence à E7% 90% 86% E8% AB% 96-% E5% A4% A7% E7% 9F% B3-% E9% 80% B2% E4% B8% 80 / dp / 4339060739).

Qu'est-ce que le modèle M / M / N / N?

Le modèle M / M / N / N est un modèle à serveur unique dans lequel le temps nécessaire à un client pour arriver et servir selon une distribution de Poisson suit une distribution exponentielle. La longueur maximale de la matrice est de 0. Cela signifie que vous ne pouvez pas faire la queue. La discipline de service est omise, mais c'est FCFS. Ce système est également connu sous le nom de système de taux de perte d'appels d'Alan. Ce modèle est une idée de base pour les modèles qui ne peuvent pas être mis en file d'attente comme ça, il est donc bon à comprendre. Notez également que dans ce modèle, l'utilisation est $ \ rho = \ frac {\ lambda} {N \ mu} $ par définition.

Probabilité de n personnes dans le système

Tout d'abord, supposons que le client soit conforme au processus de Poisson. Supposons donc qu'au plus un client arrive à un intervalle de temps assez court $ \ Delta t $. À ce stade, si le taux d'arrivée moyen est $ \ lambda $, la probabilité qu'un client vienne peut être exprimée par $ \ lambda \ Delta t $. Ici, soit $ P_k (t) $ la probabilité qu'il y ait k clients dans le système au temps t. Nous décrirons le changement de cette probabilité après $ \ Delta t $. De même, la probabilité qu'un client quitte un serveur avec un taux de service moyen de $ \ mu $ est $ \ mu \ Delta t $. Jusqu'à présent, c'est la même chose que l'hypothèse précédente. Cette fois, supposons que le taux de service moyen lorsque l'état k est $ 1 \ leq k \ leq n $ est $ k \ mu $. Cela signifie qu'il y a k serveurs fonctionnant avec un taux de service moyen de $ \ mu $. Dans ce qui suit, nous considérerons une équation (équation d'état) qui représente le changement du nombre de clients dans le système. Cependant, comme dans le précédent, considérez la frontière en faisant attention à la frontière $ k = 0, N $. Si vous calculez en supposant qu'il a atteint un état stable après un laps de temps suffisant P_k=\frac{\frac{a^k}{k!}}{\sum_{i=0}^{N}\frac{a^i}{i!}} Cependant, $ (i = 0, ..., N), a = \ frac {\ lambda} {\ mu} $. Nous connaissons maintenant la probabilité qu'il y ait k clients dans le système. Après cela, je vais essayer de trouver une formule qui se produit fréquemment dans les premières histoires de la file d'attente.

Nombre moyen de clients dans le système L

Puisque L est la valeur moyenne, c'est-à-dire la valeur attendue, elle peut être calculée à partir de $ L = \ sum_ {k = 0} ^ {N} kP_k $. Donc $ 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)

Temps d'attente moyen dans le système W

De la formule de Little $ W = \ frac {L} {\ lambda} = \ frac {1-P_N} {\ mu} $

Nombre moyen de clients dans la file d'attente L_q

Ce sera 0 car il n'y a pas de file d'attente.

Temps d'attente moyen dans la file d'attente W_q

Ce sera 0 car il ne sera pas dans la file d'attente.

Taux de perte d'appels

Le taux de perte d'appels est le pourcentage de personnes qui ne peuvent pas être mises en file d'attente et qui sont évacuées. Il s'écrit généralement $ P_b $ ou $ E_N (a) $, mais ici il s'écrit $ E_N (a) $. Le taux de perte d'appels est égal à la probabilité que le serveur soit plein, donc $ E_N (a) = P_N $. Il s'appelle le type Alan B parce que M. Ala l'a trouvé. En passant, il semble qu'il existe même une formule C. Plus intéressant en tant que formule progressive E_0(a)=1 E_N=\frac{a E_{N-1}(a)}{s+a E_{N-1}(a)} Est établi, et si vous mettez $ F_N (a) = \ frac {1} {E_N (a)} $ F_0(a)=1 F_N(a)=1+\frac{N}{a}F_{N-1}(a) Est établi. Dans les deux cas, N est un entier supérieur ou égal à 1.

Montant Y passé et montant a_l perdu

Le montant passé est le nombre moyen de clients dans le système. Autrement dit, $ Y = a (1-P_N) = a (1-E_N (a)) $. De là, en soustrayant le montant passé de la moyenne totale a pour calculer le montant perdu, on obtient $ a_l = a-Y = a E_N (a) $.

Relation entre a et N

Soit B $ E_N (a) = B $ avec une valeur constante de 0 ou plus et 1 ou moins. À ce moment, l'équation différentielle partielle pour a de $ E_N (a) $ \frac{\partial E_N(a)}{\partial a}=(\frac{N}{a}-1+E_N(a))E_N(a) Peut être obtenu pour a et N en résolvant sous la condition $ E_N (a) = B $. De plus, il semble que le taux d'utilisation $ \ rho_N (B) = \ frac {a (1-B)} {N} $ soit valable pour N, a et B. Cette fois, je vais dessiner un graphique de ces deux en Python. Voici le programme.

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

#Programme de gaspillage

def E_B(N, a):
    #Calculez l'équation d'Alan B.
    #N est le nombre de serveurs
    #a est la densité du trafic
    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 est le nombre maximum de serveurs
    #b est la fonction objectif E pour résoudre par la méthode de Newton_B(N, a)-Représente B de B et représente le taux de perte d'appels.
    p = [0 for i in range(n+1)]  # n+Le premier est E_B(N, a)Devient
    p[0] = 0  # a=s=Parce que 0 tient clairement
    c = 1  # a_Déterminez la valeur initiale c comme 0.
    for i in range(1, len(p)):
        a = c
        # E(N,a)=Trouvez la valeur qui devient B en répétant environ 20 fois.
        for j in range(20):
            t = E_B(i, a)
            a = a - (t-b) / ((i/a-1+t)*t)
        p[i] = a
        c=a #Mettre à jour à une valeur initiale raisonnable pour la prochaine fois

    return p


#Dessinez et exécutez à partir d'ici
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()

Selon ce programme, la relation entre la densité de trafic a et le nombre de serveurs N est Et le taux d'utilisation $ \ rho_N (B) $ lorsque B est le taux de perte d'appel

Résumé

Jusqu'à présent, cette série était qiita, mais il n'y avait pas de programmation, alors je l'ai ajoutée. Veuillez noter que le calcul est fait lorsque $ 0 <\ rho <1 $, donc si vous calculez avec une autre valeur, ce sera une valeur étrange. Et j'étudie toujours avec le livre d'introduction, donc ça pourrait être faux. Que dois-je faire la prochaine fois?