File d’attente, un petit exemple¶

Psychokinèse, les ampoules grillent à distance

Petite histoire¶

Cet énoncé s’inspire du livre Devenez sorciers, devenez savants de Georges Charpak et Henri Broch dont est tiré l’extrait suivant.

Le présentateur se tourne vers la caméra principale, et d’un air très sérieux et enjôleur, regarde le téléspectateur droit dans les yeux en déclarant : Allez-y ! Allumez cinq ou six lampes à côté de vous. Puis il se tourne vers le médium et demande : Vous pensez réellement pouvoir le faire ? Après quelques moments d’hésitation, le mage se prononce : J’espère avoir suffisamment de concentration ce soir, mais je ne suis pas dans les conditions vraiment idéales ; pour produire ce genre de phénomène à distance, d’habitude, je me retire pendant plusieurs jours dans une solitude totale et une profonde obscurité, après un jeûne strict.

Si jamais il échoue, le public le mettra au compte des circonstances et non pas de ces compétences. Et, pourtant, le médium n’échoue pas. Des ampoules grillent chez les téléspectateurs qui regardent cette émission. Ils font part au standard téléphonique de la chaîne qui diffuse en direct cet extraordinaire moment de culture. Le médium a donc bien réussi - comme il le prétendait -, en concentrant sa puissance spirituelle sur la matière, à griller des ampoules électriques à distance.

Supposons que cette émission soit suivie par environ un million de téléspectateurs et qu’elle dure une heure ou plus. Cela signifie qu’environ cinq à six millions d’ampoules ont été allumées pendant une heure ou plus. Supposons que ce nombre soit de deux millions.

La durée de vie moyenne d’une ampoule à incandescence est de mille heures. Ce qui signifie que, pendant la durée de l’émission, il y aura environ deux milles lampes grillées.

Un peu de théorie¶

Ce problème ressemble à un problème de files d’attente. Ce dernier consiste à déterminer un nombre adéquat de guichets en fonction de la vitesse de remplissage d’une file d’attente afin de limiter le temps d’attente. On désigne souvent cette problématique par un sigle du type $M/M/S$ . Le premier $M$ signifie qu’on suppose que la probabilité que $n$ personnes arrivent pendant une durée $t$ suit une loi de Poisson de paramètre $\lambda t$ . Le second $M$ signifie qu’on suppose que le temps de traitement d’une personne par un guichetier suit une loi exponentielle de paramètre $\mu$ . $S$ désigne le nombre de guichets. Pour de tels problèmes, on cherche à déterminer la probabilité que le système (file d’attente + guichets) contienne $n$ personnes. De cette probabilité, on peut déduire par exemple le temps d’attente moyen pour une personne qui entre dans la file d’attente. On suppose que le système est stationnaire, les probabilités ne dépendent pas du temps.

Définition D1 : loi de Poisson et loi exponentielle

Si une variable $X$ suit une loi de Poisson de paramète $\lambda t$ , elle a pour densité :

$\begin{eqnarray} \pr{X = n} &=& \frac{(\lambda t)^n}{n!} \; e^{-\lambda t} \end{eqnarray}$

Si une variable $X$ suit une loi exponentielle de paramètre $\mu$ , elle a pour densité :

$\begin{eqnarray} f(t) &=& \mu \; e^{- \mu t} \text{ et } \pr {X \leqslant t} = \int_0^t \mu \; e^{- \mu x} dx = 1 - e^{-\mu t} \end{eqnarray}$

File d’attente, cas M/M/1¶

On s’intéresse d’abord à un système $M/M/1$ . Il n’y a donc qu’un seul guichet. $\lambda$ est le nombre moyen d’arrivée par unité de temps tandis que $\mu$ est le nombre moyen de clients traités par unité de temps. On suppose également que $\lambda < \mu$ . Dans le cas contraire, la file d’attente devient infinie. On désigne par $p_n(t)$ la probabilité que la file d’attente contiennent $n$ personne. Que vaut cette probabilité à l’instant $t + dt$ ?

On considère que pendant la durée $t + dt$ , au plus une personne peut s’ajouter à la file d’attente et au plus une personne peut être traitée par un guichetier. Les autres cas sont négligeables. On désigne par $B(x,t,dt)$ le fait qu’une personne quitte un guichet pendant les instants $t$ et $t+dt$ sachant qu’elle est arrivée au guichet à l’instant $x$ . On cherche à déterminer la probabilité $\pr{B(x,t,dt)}$ . On peut dire aussi que $\pr{B(x,t,dt}$ est la probabilité que le temps de traitement d’une personne est inférieur à $t+dt-x$ sachant qu’il est supérieur à $t-x$ . Si $D$ est une variable de durée suivant une loi exponentielle, alors :

(1)¶ $\begin{eqnarray*} \pr{B(x,t,dt)} &=& \pr{ D \leqslant t+dt-x \sac D > t-x } \\ &=& \frac{ \pr{ t+dt-x \supegal D > t-x } } { \pr{ D > t-x }} \\ &=& \frac{ \int_{t-x}^{t+dt-x} \mu e^{-\mu u} du } { \int_{t-x}^{\infty} \mu e^{-\mu u} du } = \frac{ e^{- \mu (t-x) } - e^{- \mu (t-x+dt) } } { e^{-\mu (t-x) }} \\ &=& 1 - e^{- \mu dt} \\ \pr{B(x,t,dt)} &=& - \mu dt + o(dt) \end{eqnarray*}$

Cette probabilité ne dépend ni de $x$ , ni de $t$ . En ce qui concerne les arrivées, la probabilité qu’une personne arrive pendant les instants $t$ et $t+dt$ ne dépend pas du passé et suit une loi de Poisson de paramètre $\lambda$ . Cette constation et l’équation (1) nous permettent d’écrire que :

(2)¶ $\begin{eqnarray} \pr{ \text{une personne arrive pendant } dt } &=& \lambda dt \; e^{-\lambda dt} \sim \lambda dt + o(dt) \\ \pr{ \text{une personne part pendant } dt } &=& 1 - e^{-\mu dt} \sim \mu dt + o (dt) \end{eqnarray}$

De plus, pendant la durée $dt$ , quatre cas sont possibles :

Une personne peut arriver sans qu’aucune ne parte d’un guichet.
Une personne peut partir d’un guichet sans qu’aucune autre n’arrive.
Une personne peut arriver et une autre partir d’un guichet.
Aucune personne n’arrive et aucune ne part d’un guichet.

Ces quatre cas permettent d’écrire la relation suivante :

(3)¶ $\begin{eqnarray*} p_n(t+dt) &=& p_{n-1}(t) \; \lambda dt + p_{n+1}(t) \; \mu dt + \\ && p_n(t) \pa{ \mu dt \lambda dt} + p_n(t) \pa { 1 - \mu dt} \pa{ 1 - \lambda dt} \end{eqnarray*}$

On néglige les termes du second degré en $(dt)^2$ :

$\begin{eqnarray*} p_n(t+dt) &=& p_{n-1}(t) \; \lambda dt + p_{n+1}(t) \; \mu dt + p_n(t) \pa { 1 - \mu dt - \lambda dt } \\ \Longleftrightarrow \frac{ p_n(t+dt) - p_n (t)} {dt} &=& \lambda p_{n-1}(t) + \mu p_{n+1}(t) - \pa { \mu + \lambda } p_n(t) \end{eqnarray*}$

Cette relation n’est vraie que lorsque $n > 0$ , lorsque $n = 0$ , aucune personne déjà présente ne peut être traitée par un guichetier, on a donc :

$\frac{ p_0(t+dt) - p_0 (t)} {dt} = \mu p_{1}(t) - \lambda p_0(t)$

Comme le système est stationnaire, toutes les dérivées sont nulles. Les probabilités ne dépendent pas du temps. Ceci donne les relations suivantes :

(4)¶ $\begin{eqnarray*} && \left \{ \begin{array}{lll} \lambda p_{n-1} + \mu p_{n+1} - \pa { \mu + \lambda } p_n &=& 0 \\ \mu p_1 - \lambda p_0 &=& 0 \end{array}\right. \\ \Longleftrightarrow && \left \{ \begin{array}{lll} \mu p_{n+1} &=& \pa { \mu + \lambda } p_n - \lambda \; p_{n-1} \\ \mu p_1 &=& \lambda p_0 \end{array}\right. \end{eqnarray*}$

On vérifie par récurrence que :

$p_n = \pa{\frac{\lambda}{\mu}}^n p_0$

Il reste à déterminer $p_0$ . Or, comme $\sum_0^{\infty} p_n = 1 = p_0 \; \sum_0^{\infty} \pa{\frac{\lambda}{\mu}}^n$ , on obtient que frac{p_0}{ 1 - frac{lambda}{mu}} = 1 Longleftrightarrow p_0 = 1 - frac{lambda}{mu}.

Exemple :

On suppose qu’un médecin traite en moyenne quatre patients par heure tandis qu’il accepte trois rendez-vous par heure. Donc $\lambda = 3$ et $\mu = 4$ . Le nombre moyen $\overline{n}$ de patients dans sa salle d’attente est donné par :

$\begin{eqnarray*} \overline{n} &=& \sum_0^{\infty} n p_n = \pa{1 - \frac{\lambda}{\mu} } \sum_0^{\infty} n \pa{\frac{\lambda}{\mu}}^n = \frac{ \frac{\lambda}{\mu} } { 1 - \frac{\lambda}{\mu} }= \frac{\lambda}{\mu - \lambda } \end{eqnarray*}$

Il y a donc en moyenne trois personnes dans la salle d’attente de ce médecin. Comme le temps moyen de traitement de chacun est $\frac{1}{\mu}$ , le temps moyen d’attente d’un patient arrivant dans la salle d’attente est $\frac{\lambda \mu}{\mu - \lambda }$ . Ce temps est égal à trois quarts d’heure pour cet exemple.

File d’attente, cas M/M/S¶

Le système contient dorénavant $S$ guichets, on suppose que la vitesse $\mu$ de traitement des clients est commune à tous les guichets. On cherche tout d’abord la probabilité qu’une personne s’en aille parmi les $k$ qui occupent un guichet. On désigne par $\vecteur{D_1}{D_k}$ $k$ variables indépendantes suivant une loi exponentielle de paramètre $\mu$ , pendant un temps $dt$ , la probabilité qu’une personne parmi $k$ quitte un guichet est :

$\begin{eqnarray*} \pr{ \min \ensemble{D_1}{D_k} \leqslant dt } &=& 1 - \pr {\min \ensemble{D_1}{D_k} > dt} \\ &=& 1 - \cro{\prod_{n=1}^{k} \pr {D_n > dt}} \\ &=& 1 - \cro{\prod_{n=1}^{k} 1 - \pr {D_n \leqslant dt}} \\ &=& 1 - \cro{\prod_{n=1}^{k} e^{-\mu dt}} \\ &=& 1 - e^{- k\mu dt} \sim k \mu dt + o(dt) \end{eqnarray*}$

Pour déterminer les probabilités $\pa{p_n}_n$ , on applique le même raisonnement que pour un système $M/M/1$ en distinguant les cas $n \leqslant S$ et $n > S$ . On adapte la récurrence donnée par le système d’équations (4) au cas $M/M/S$ :

(5)¶ $\begin{eqnarray*} && \left \{ \begin{array}{lll} \mu p_1 - \lambda p_0 &=& 0 \\ \lambda p_{n-1} + \pa{n+1} \mu p_{n+1} - \pa {n \mu + \lambda } p_n &=& 0 \text{ si } 1 \leqslant n < S \\ \lambda p_{n-1} + S \mu p_{n+1} - \pa { S \mu + \lambda } p_n &=& 0 \text{ si } n \supegal S \end{array}\right. \end{eqnarray*}$

On suppose que $\frac{\lambda}{S \mu} < 1$ afin que la file d’attente ne devienne infinie. Comme pour un système $M/M/1$ , ces formules de récurrences et le fait que $\sum_0^{\infty} p_n = 1$ permet de déduire que :

$\begin{eqnarray*} \left\{ \begin{array}{lll} p_0 &=& \dfrac{1}{ \frac{ \pa{\frac{\lambda}{\mu}}^S } { S! \pa { 1 - \frac{\lambda}{S \mu}} } + \sum_{k=1}^{S-1} \frac{ \pa{ \frac{\lambda}{\mu}}^n }{ n!} } \\ \\ p_n &=& \dfrac{1}{n!} \; \pa{\dfrac{\lambda}{\mu}}^n p_0 \quad \text{ si } n < S \\ \\ p_n &=& \dfrac{1}{S^{n-S} S!} \; \pa{\dfrac{\lambda}{\mu}}^n p_0 \quad \text{ si } n \supegal S \end{array} \right. \end{eqnarray*}$

Ces calculs sont utilisés pour optimiser le nombre de guichets. Chaque guichetier a un coût qui doit être comparé avec le coût associé au temps d’attente des clients. Ces résultats sont extraits du livre [Faure2000].

La théorie des files d’attente remonte aux premiers travaux de K. Erlang (1917), sur le calcul du nombre d’organes de chaque type à installer dans un central téléphonique automatique. Développée aussi par Engset (1918), cette théorie s’est amplifiée sous l’impulsion de nombreux chercheurs (E. Borel, D. Kendall, A. Kolmogorov, Khintchine, LC. Palm, F. Pollaczek, L. Feller, …). Les informaticiens l’utilisent notamment pour l’évaluation de performances, à titre prévisionnel, des systèmes ou des réseaux informatiques.

Retour aux ampoules¶

La durée de traitement d’un client fait penser à la durée de vie d’une ampoule. Les lampes font office de guichets tandis que le rôle des clients est joué par des lumières. Toutefois, ce n’est pas le temps d’attente moyen ni la longueur moyenne de la file d’attente qui nous intéresse mais, en quelque sorte, le nombre de clients qui sont traités pendant une durée $T$ . En fait, plus exactement, c’est le nombre de guichets qui auront traités au moins un client pendant une durée $T$ qui nous intéresse. Il correspond exactement au nombre d’ampoules qui vont griller pendant cette même période $T$ . Il reste à définir ce qu’est une file d’attente d’ampoules et surtout son paramètre $\lambda$ .

Lorsqu’une ampoule grille, elle est a priori changée dans les plus brefs délais, comme si la file d’attente des ampoules était infinie. Ceci signifie que $\lambda >> \mu$ , configuration qui sort du champ d’application des files d’attente $M/M/S$ . Le paramètre $\lambda$ n’a a priori aucun rôle à jouer. On peut néanmoins s’inspirer de la méthode développée dans les paragraphes précédants pour aborder le problème des ampoules.

On suppose que la durée de vie d’une ampoule suit toujours une loi exponentielle de paramètre $\mu$ et qu’il y en a exactement $S$ qui brillent en même temps. On note $p_n(t)$ la probabilité que $n$ ampoules aient grillées à l’instant $t$ . Si $N(t)$ est le nombre d’ampoules grillées à l’instant $t$ : $p_n(t) = \pr{ N(t) = n}$ . Cette fonction n’est plus stationnaire et décroît avec le temps à partir d’un certain moment. Plus on avance dans le temps, plus le nombre d’ampoules grillées augmente. Par conséquent, la probabilité qu’il y ait $n$ ampoules grillées augmente tout d’abord puis, à partir d’un moment $t$ , elle diminue.}. On utilise un raisonnement similaire à celui qui a permis d’écrire les équations (2), (3) pour obtenir :

(6)¶ $\begin{eqnarray*} p_n(t +dt) &=& \pa{1 - S \mu dt} p_n(t) + S \mu p_{n-1}(t) dt \\ \Longleftrightarrow \frac{p_n(t +dt) - p_{n-1}(t)}{dt} &=& - S \mu p_n(t) + S \mu p_{n-1}(t) \\ \Longleftrightarrow p_n'(t) &=& - S \mu p_n(t) + S \mu p_{n-1}(t) \end{eqnarray*}$

On connaît la fonction $p_0(t)$ puisqu’elle correspond à la probabilité qu’aucune des $S$ ampoules n’ait grillé depuis l’instant~0 jusqu’à l’instant $t$ , par conséquent :

$\begin{eqnarray*} p_0(t) &=& \pr{ \text{ durée de vie des } S \text{ ampoules soient toutes supérieures à } t } \\ \Longrightarrow p_0(t) &=& \cro{ \int_t^{\infty} \mu e^{- \mu u} du } ^S \\ \Longrightarrow p_0(t) &=& e^{-S\mu t} \end{eqnarray*}$

L’équation (6) permet de définir une suite d’équations différentielles du premier degré :

(7)¶ $\begin{eqnarray*} p_0(t) &=& e^{-S\mu t} \\ p_1'(t) &=& - S \mu p_1(t) + S \mu e^{-S\mu t} \\ p_2'(t) &=& - S \mu p_2(t) + p_1(t) \\ ... && \\ p_n'(t) &=& - S \mu p_n(t) + S \mu p_{n-1}(t) \end{eqnarray*}$

On peut donc calculer par récurrence la suite de fonction $\pa{p_n(t)}_n$ . La solution de l’équation différentielle homogène est $e^{-S\mu t}$ . On utilise la méthode de la variation de la constante en posant $p_n(t) = C_n(t) e^{-S \mu t}$ . On aboutit à l’équation :

$\begin{eqnarray*} p_n'(t) &=& - S \mu p_n(t) + S \mu p_{n-1}(t) = - S \mu p_n(t) + C_n'(t) e^{- S \mu t} \\ \Longrightarrow C_n'(t) e^{- S \mu t} &=& S \mu p_{n-1}(t) \\ \Longrightarrow C_n'(t) &=& S \mu p_{n-1}(t) e^{ S \mu t} \end{eqnarray*}$

Pour $n = 1$ , on obtient $C_1'(t) = S \mu \Longrightarrow C_1'(t) = S \mu t + A_1$ . Par conséquent, $p_1(t) = \pa{S \mu t + A_1} e^{- S \mu t}$ . On sait que $\forall t, \; \sum_0^{\infty} p_n(t) = 1$ mais cela ne permet pas de déterminer la constante $A_1$ . Néanmoins, en faisant tendre $t \longrightarrow 0$ , nécessairement $p_1(t) \longrightarrow 0$ . Par conséquent : $A_1 = 0$ et $p_1(t) = S \mu t \; e^{- S \mu t}$ . On pose maintenant $p_2(t) = C_2(t) e^{- S \mu t}$ . La résolution de l’équation différentielle (7) pour $n=2$ aboutit à :

$\begin{eqnarray*} C_2'(t) &=& S \mu p_{1}(t) e^{ S \mu t} = \pa{S \mu t}^2 \\ \Longrightarrow C_2(t) &=& \frac{1}{2} S^2 \mu^2 t^2 + A_2 \\ \Longrightarrow p_2(t) &=& \pa{ \frac{1}{2} S^2 \mu^2 t^2 + A_2} e^{- S \mu t} \end{eqnarray*}$

De même, en faisant tendre $t \longrightarrow 0$ , on démontre que $A_2 = 0$ . En poursuivant ce raisonnement, par récurrence, on démontre que :

(8)¶ $p_n(t) = \frac{\pa{S \mu t}^n }{n!} \; e^{- S \mu t}$

$p_n(t) = \pr{ N(t) = n}$ et d’après l’équation (8), la variable aléatoire $N(t)$ suit une loi de Poisson de paramètre $S \mu t$ . $N$ est aussi appelé processus de Poisson. L’espérance de $N$ est égale à $\esp{N(t)} = S \mu t$ . Pendant une durée $T$ , le nombre moyen d’ampoules grillées est :

$\esp{N (t) - N (t-T)} = \esp{N (T)} - \esp{N (t-T)} = S \mu T$

Ce nombre est indépendant du temps $t$ .

Application numérique¶

Pour des ampoules d’une durée de 1000 heures, le paramètre $\mu = \frac{1}{1000}$ , $T = 1$ . S’il y a deux millions d’ampoules, le nombre moyen d’ampoules grillées par heure est $S \mu T = 2000$ . On retrouve le résultat énoncé.

Programme informatique¶

La durée de vie de chaque ampoule suit une loi exponentielle de paramètre $\mu$ . Il faut donc simuler une telle variable dont la fonction de répartition est $F_{\mu}(x) = 1 - e^{ \mu x}$ . On utilise pour cela une propriété qui découle de la fonction de répartition. On note $F_{\mu}^{-1}(x) = - \; \frac{\ln(1-x)}{\mu}$ . Cette fonction vérifie $F_{\mu}^{-1}\pa{F_{\mu}(x)} = 1$ . Or si $U$ est une variable aléatoire uniforme sur $\cro{0,1}$ , alors la variable $V = F_{\mu}^{-1}(U)$ suit la loi exponentielle avec $\mu$ pour paramètre. Effectivement, $\pr{ V \leqslant t} = \pr{ F_{\mu}^{-1}(U) \leqslant t} = \pr{U \leqslant F_{\mu}(t)} = F_{\mu}(x)$ . La fonction de répartition de la variable $V$ est $F_{\mu}$ , $V$ est donc une loi exponentielle de paramètre $\mu$ . La première fonction simule une variable exponentielle de paramètre $\mu$ :

<<<

import math
import random


def generate_expo(mu):
    x = 0
    while x == 0:
        x = random.random()
    y = -math.log(1 - x) / mu
    return y


print(generate_expo(2))

>>>

    0.12228554499118525

Le module random propose aussi une fonction qui simule automatiquement une variable exponentielle.

<<<

import random

def generate_expo(mu):
    return random.expovariate(mu)

print(generate_expo(2))

>>>

    0.3063274548076286

Pour réaliser cette simulation, on suppose qu’on a un tableau de $S$ ampoules. Chaque case de ce tableau contient la durée de vie restante d’une ampoule, simulée selon une loi exponentielle. Au départ, toutes les durées de vie sont nulles. On considère qu’à chaque itération, une heure passe. Lors de chaque itération, pour chaque ampoule, on vérifie sa durée de vie restante. Si celle-ci est nulle, on la remplace par une autre dont on choisit aléatoirement la durée de vie (arrondie à l’entier le plus proche). Si la durée de vie n’est pas nulle, on la diminue d’une heure. A chaque itération, on compte le nombre d’ampoules grillées pour en faire la moyenne au bout de $n$ itérations. Pour effectuer cette simulation, les valeurs choisies sont :

$S = 10000, \mu = \frac{1}{100}, n = 500$

Le programme suivant réalise cette simulation. On calcule la moyenne du nombre d’ampoules grillées par heure sur les 500 itérations excepté la première pour laquelle toutes les ampoules sont grillées - configuration aberrante ou tout du moins très peu probable -. La valeur obtenue est proche de $S \mu = 100$ .

File d’attente, un exemple simple

Bibliographie¶

[Faure2000]

Précis de recherche opérationnelle, 5ième édition, Robert Faure, Bernard Lemaire, Christophe Picouleau, Dunod