\documentclass[12pt]{book}
\usepackage{pas-exos}
\usepackage{multirow}
\usepackage{cancel}
\newcommand\dt{\Delta t}
\renewcommand\e[1]{\textrm{e}^{#1}}
\begin{document}
\chapter*{Le phénomène des files d'attente}

\section*{Introduction}

Le phénomène des files d'attente est très fréquent dans notre vie quotidienne. Il suffit d'aller dans une administration, ou dans un commerce fréquenté pour y être confronté.

\medskip

Remarquez qu'il s'agit de \emph{phénomènes stochastiques} ; en effet, les gens arrivent en général de façon aléatoire. De plus, la durée pendant laquelle nous sommes directement confronté à l'agent administratif ou au commerçant n'est en général pas constante.

\medskip

On a coutume de nommer \emph{file d'attente} l'ensemble des personnes qui attendent \emph{après la personne qui est avec le commerçant ou l'agent}. On nomme \emph{système d'attente} l'ensemble des personnes qui sont dans la file d'attente \underline{et} celle qui se fait servir.

\section*{Loi des arrivées}

Prenons le cas trivial d'un service où il n'y a qu'une seule file d'attente.

\medskip

Considérons que le phénomène d'arrivées des clients dans une file d'attente est \emph{stationnaire}. Cela signifie que l'observation que l'on fait de la file d'attente est indépendant de l'origine du temps. On ne tiendra donc, par exemple, pas compte des pics ou creux d'arrivées des clients à certains moments de la journée.

\medskip

Considérons également que les arrivées de chaque client sont indépendantes les unes des autres ; le cas d'arrivées à intervalles réguliers déterminés ou par groupe de clients n'est donc pas ici envisageable.

\medskip

Enfin, la probabilité d'arrivée d'un événement pendant un intervalle de temps $\dt$ est proportionnelle à $\dt$ et égale à $k\cdot\dt$, $k \in\mathbb{R}$.

\medskip

On suppose qu'il y a $n$ événements enregistrés à la date $t+\dt$. Ces $n$ événements ne peuvent provenir que des deux situations suivantes :

\medskip

\begin{center}
\begin{tabular}{|l|c|c|}
\hline
Dates & à $t$ & à $t+\dt$\\
\hline
\multirow{2}{*}{Nombre d'événements} & $n-1$ & $n$\\
\cline{2-3}
 & $n$ & $n$\\
\hline
\end{tabular}
\end{center}

\medskip

Donc la probabilité $p_n\left(t+\dt\right)$ de réalisation de $n$ événements pendant le temps $t+\dt$ est :
\begin{eqnarray}
p_n\left(t+\dt\right) = p_{n-1}(t)\cdot k\cdot \dt+p_n(t)\left(1-k\cdot\dt\right)
\end{eqnarray}

Cette formule est valable pour tout entier naturel $n$ non nul. En effet, lorsque $n=0$, aucun événement n'a été réalisé au temps $t+\dt$ et aucun événement n'avait également été réalisé au temps $t$. On obtient alors :
\[ p_0\left(t+\dt\right)=p_0(t)\left(1-k\cdot\dt\right)\]
Cette dernière formule s'écrit également :
\[ \frac{p_0\left(t+\dt\right)-p_0(t)}{\dt}=-k\cdot p_0(t)\]
Soit :
\[ \lim_{\dt\to 0}\frac{p_0\left(t+\dt\right)-p_0(t)}{\dt}=-k\cdot p_0(t)\]
D'où :
\begin{eqnarray}
p_0^\prime(t)=-k\cdot p_0(t)
\end{eqnarray}

Si on considère maintenant l'équation $(1)$, on peut écrire :
\[ p_n\left(t+\dt\right) -p_n(t)=kp_{n-1}(t)\dt-kp_n(t)\dt\]
D'où :
\[ \frac{p_n\left(t+\dt\right) -p_n(t)}{\dt}=k\left(p_{n-1}(t)-p_n(t)\right)\]
Soit: 
\[ \lim_{\dt\to 0}\frac{p_n\left(t+\dt\right) -p_n(t)}{\dt}=k\left(p_{n-1}(t)-p_n(t)\right)\]
Ainsi :
\begin{eqnarray}
p_n^\prime(t)=k\left(p_{n-1}(t)-p_n(t)\right)
\end{eqnarray}

L'équation différentielle $(2)$ admet pour solutions :
\[ p_0(t)=C\e{-kt},\ C\in\mathbb{R}\]
Or, $p_0(0)=1$ (probabilité pour qu'aucun événement se réalise à l'origine du temps). Ainsi : \[p_0(t)=\e{-kt}\]

Maintenant, regardons de plus près l'équation $(3)$ lorsque $n=1$ :
\[ p_1^\prime(t)=k\left(p_0(t)-p_1(t)\right)\]
Ou encore :
\[ p_1^\prime(t)+kp_1(t)=k\e{-kt}\]
C'est une équation différentielle d'ordre 1 avec second membre. On montre que : \[ p_1(t)=kt\e{-kt}\]

Par récurrence, on montre que pour tout entier nature $n$ :
\[ p_n(t)=\frac{\left(kt\right)^n}{n!}\e{-kt}\]

\textbf{On a ainsi montré que la probabilité $p_n$ suit une loi de Poisson de paramètre $kt$.}

\section*{Loi des services}

La loi des services est la loi qui permet d'estimer le temps qu'occupe un service pour traiter chaque client.

\medskip

Si on considère les intervalles de temps qui s'écoulent entre les événements successifs d'une loi de Poisson de paramètre $m$, on constate qu'ils suivent une loi de la forme :
\[ p(q)=m\e{-mq}\]
où $q$ désigne un intervalle de temps entre deux événements successifs.

\medskip

C'est donc une loi exponentielle. De manière générale, elle s'adapte bien à la durée d'un service. Dans cette loi, $m$ désigne le nombre de clients servis par unité de temps, et $\frac{1}{m}$ désigne le temps moyen que passe chaque client au service.

\section*{Cas d'une file d'attente à un service}

Dans cette section, nous allons considérer le cas d'une unique file d'attente  où les gens arrivent selon une loi de Poisson et sont servis dans un temps suivant une loi exponentielle. 

\medskip

Si $n$ personnes sont dans le système d'attente à $t+\dt$, cela ne peut provenir que de quatre situations :

\medskip

\begin{center}
\begin{tabular}{|*4{c|}}
\hline
\parbox{.2\linewidth}{\centering Nombre de personnes à $t$} & 
\parbox{.2\linewidth}{\centering Entrées pendant $\dt$} & 
\parbox{.2\linewidth}{\centering Sorties pendant $\dt$} & 
\parbox{.2\linewidth}{\centering Nombre de personnes à $t+\dt$}\\
\hline
$n-1$ & 1 & 0 & $n$\\
\hline
$n$ & 0 & 0 & $n$\\
\hline
$n$ & 1 & 1 & $n$\\
\hline
$n+1$ & 0 & 1 & $n$\\
\hline
\end{tabular}
\end{center}

\medskip

D'après les hypothèses, la probabilité qu'une personne entre pendant $\dt$ est $k\dt$ alors que $m\dt$ est la probabilité qu'une personne sorte.

\medskip

On obtient donc la probabilité qu'il y ait $n$ clients au temps $t+\dt$ :
\begin{multline*}
p_n(t+\dt)=p_{n-1}(t)\left[k\dt(1-m\dt)\right] + p_n(t)\left[(1-k\dt)(1-m\dt)\right]\\
+p_n(t)\cdot k\dt\cdot m\dt+p_{n+1}(t)\left[(1-k\dt)\cdot m\dt \right]
\end{multline*}

Si on néglige tous les termes en $\dt^2$, on a :

\[ p_n(t+\dt)=kp_{n-1}(t)\dt + p_n(t)\left[1-(k+m)\dt\right] + mp_{n+1}\dt\]

Soit :

\begin{eqnarray}
\frac{p_n(t+\dt)-p_n(t)}{\dt}=kp_{n-1}(t)-(k+m)p_n(t)+mp_{n+1}(t)
\end{eqnarray}

D'où :

\[ p_n^\prime(t)= kp_{n-1}(t)-(k+m)p_n(t)+mp_{n+1}(t)\]

L'équation $(4)$ possède un cas particulier pour $n=0$, cas représentant la situation où il n'y a aucune personne à l'instant $t+\dt$. Il ne peut pas y avoir une personne qui entre sans que personne ne sorte pendant le temps $\dt$. On a alors :
\[ p_0(t+\dt)=p_0(t)\left[1-k\dt\right] + p_1(t)\left[(1-k\dt)\cdot m\dt\right]\]
Soit :
\[ \frac{p_0(t+\dt)-p_0(t)}{\dt}=-kp_0(t)+mp_1(t)\]
D'où :
\begin{eqnarray}
p_0^\prime(t)=-kp_0(t)+mp_1(t)
\end{eqnarray}

D'après les hypothèses, le phénomène est stationnaire, donc : \[p_0^\prime(t)=p_1^\prime(t)=\cdots=p_n^\prime(t)=\cdots=0\]
Alors, l'équation $(5)$ devient :
\[ p_1(t)=\frac{k}{m}p_0(t)\]
Ainsi, l'équation $(4)$ devient, pour $n=1$ :
\[ 0 = kp_0(t)-(k+m)\frac{k}{m}p_0(t)+mp_2(t)\]
Soit :
\[
p_2(t)=\left(\frac{k}{m}\right)^2p_0(t)
\]

Par récurrence, on montre que pour tout entier naturel $n$ :  \begin{eqnarray}p_n(t)=\left(\frac{k}{m}\right)^np_0(t)\end{eqnarray}

On sait de plus que $\sum\limits_{i=0}^{+\infty}p_i(t)=1$, ce qui donne alors :

\[ \sum_{i=0}^{+\infty}\left(\frac{k}{m}\right)^ip_0(t)=1 \qquad , \qquad m>k\]
Soit :
\[ \frac{1}{1-\frac{k}{m}}p_0(t)=1\]
Finalement, on a :
\[ p_0(t)=1-\frac{k}{m}\]
Ainsi, l'équation $(6)$ devient :
\[ p_n(t)=\left(\frac{k}{m}\right)^n\left(1-\frac{k}{m}\right)\]

\renewcommand{\arraystretch}{2}
\begin{center}
\begin{tabular}{|c|}
\hline
La probabilité qu'il y ait $n$ personne dans le service est :\\
$p_n(t)=\left(\dfrac{k}{m}\right)^n\left(1-\dfrac{k}{m}\right)$\\
\hline
\end{tabular}
\end{center}

\paragraph*{Remarque.} Notez que tout ceci est valable uniquement lorsque $m>k$. Dans le cas contraire, on dit qu'il y a \emph{engorgement}.

\bigskip

Penchons-nous maintenant sur le nombre moyen $h$ de personnes dans la file d'attente.

\medskip

$h$ est l'espérance de la loi de probabilité $p_n$, où :
\[ p_n=\left(\frac{k}{m}\right)^n\left(1-\frac{k}{m}\right)\]
Donc :
\[ h=\sum_{i=0}^{+\infty}i\times p_i\]
\[ h=\sum_{i=0}^{+\infty} i\times\left(\frac{k}{m}\right)^ip_0\]
\[ h=p_0\sum_{i=1}^{+\infty}i\times \left(\frac{k}{m}\right)^i\]
\[ h=\left(1-\frac{k}{m}\right)\left(\frac{k}{m}\right)\sum_{i=0}^{+\infty}(i+1)\times \left(\frac{k}{m}\right)^i\]

En notant $S(x)=\sum\limits_{i=0}^{+\infty} x^i$, on a $S^\prime(x)=\sum\limits_{i=0}^{+\infty}(i+1)x^i$ et donc :
\[ h=\left(1-\frac{k}{m}\right)\left(\frac{k}{m}\right)S^\prime\left(\frac{k}{m}\right)\]

Or, $S(x)=\dfrac{1}{1-x}$ pour $0<x<1$, donc $S^\prime(x)=\dfrac{1}{(1-x)^2}$ d'où :

\[ h=\cancel{\left(1-\frac{k}{m}\right)}\left(\frac{k}{m}\right)\frac{1}{\left(1-\tfrac{k}{m}\right)^{\cancel{2}}}\]
\[ h=\frac{k}{m-k} \]

\begin{center}
\begin{tabular}{|c|}
\hline
Le nombre moyen de personnes dans la file d'attente est :\\
$h=\dfrac{k}{m-k}$\\
\hline
\end{tabular}
\end{center}

\medskip

Il s'en suit alors que la file d'attente de $n$ personnes s'écoulera en un temps égal à $h \times \frac{1}{m}$, où $\frac{1}{m}$ es le temps moyen que passe chaque personne dans la file d'attente.

\medskip

On obtient alors le résultat suivant :

\begin{center}
\begin{tabular}{|c|}
\hline
Le temps moyen qu'attend une personne dans la file d'attente est :\\
$T=\dfrac{k}{m(m-k)}$\\
\hline
\end{tabular}
\end{center}

\section*{Modélisation chez un médecin d'entreprise}

Les ouvriers peuvent se rendre chez le médecin de leur entreprise pendant les heures de travail.\\
On restreint l'étude à la période où le phénomène est stationnaire : durant la première et la dernière demi-heure des horaires d'ouvertures, ainsi qu'à l'heure du repas, l'affluence est très fluctuante et faible. Au contraire, durant les autres périodes de la journée, le phénomène stationnaire est établi.

\medskip

Pendant 100 intervalles de 5 minutes, tous situés dans la période de stationnarité, le nombre de patients arrivant durant chaque période de 5 minutes est décompté :

\begin{center}
\begin{tabular}{|c|c|}
\hline
\parbox{.5\textwidth}{\centering Nombre d'ouvriers arrivant pendant une période de 5 minutes} & \parbox{.33\textwidth}{\centering Fréquences observées $f_i$}\\
\hline
0 & 29\\
\hline
1 & 34\\
\hline
2 & 24\\
\hline
3 & 9\\
\hline
4 & 3\\
\hline
5 & 1\\
\hline
6 & 0\\
\hline
\end{tabular}
\end{center}

\medskip

La moyenne de cette loi de distribution est :

\[ \frac{0\times 29 + 1\times 34+ 2\times 24 + 3\times 9 + 4\times 3 + 5\times 1 + 6\times 0}{100}=1,26\]

L'emploi d'un test statistique va permettre de vérifier si la loi observée se rapproche d'une loi théorique classique (loi de Poisson ici).

\medskip

La formule $p_n(t)=\frac{(kt)^n}{n!}\e{-kt}$, où $kt=1,26$, permet de calculer les fréquences théoriques, qui sont égales à 100 fois les probabilités suivantes :

\[ p_0=0,28\quad ; \quad p_1=0,36\quad ; \quad p_2=0,23\]\[ p_3=0,09\quad
 ; \quad p_4=0,03 \quad ; \quad p_5=0,01\]
 
Utilisons maintenant le test du $\chi^2$ de Pearson, qui s'applique à des classes dans lesquelles le nombre d'événements attendus est de l'ordre de 5 (il nous suffira ici de regrouper les deux dernières classes).

\medskip

Ce test consiste à calculer les carrés des différences entre les fréquences théoriques de la loi à vérifier et les fréquences observées, puis à diviser chacun de ses carrés par la fréquence théorique de la classe à laquelle les fréquences sont relatives.

\begin{center}
\begin{tabular}{*6{|c}|}
\hline
$n$ & \parbox{.2\textwidth}{\centering Fréquences observées $f_{\textrm{obs}}$} & \parbox{.2\textwidth}{\centering Fréquences théoriques $f_{\textrm{th}}$} & $d=\vert f_{\textrm{obs}}-f_{\textrm{th}}\vert$ & $d^2$ & $\dfrac{d^2}{f_{\textrm{th}}}$\\
\hline
0 & 29 & 28 & 1 & 1 & $0,0357$\\
\hline
1 & 34 & 36 & 2 & 4 & $0,1111$\\
\hline
2 & 24 & 23 & 1 & 1 & $0,435$\\
\hline
3 & 9 & 9 & 0 & 0 & 0\\
\hline
$>4$ & 4 & 4 & 0 & 0 & 0\\
\hline
\end{tabular}
\end{center}

\medskip

Le nombre de degrés de liberté du système est égal à : $(5-1)-1=3$ [la formule étant : \og (nombre de classes$-1$)+nombre de paramètres de la loi théorique\fg).

\medskip

En se reportant à une table du $\chi^2$ pour un degré de liberté égal à 3, on obtient $\chi^2(0,95)=0,352$.\\
De plus, $\chi^2_{\textrm{obs}}=0,0357+0,1111+0,435=0,19<\chi^2(0,95)$ donc on peut considérer que le phénomène suit la loi de Poisson de paramètre $1,26$ au seuil de risque de 95\%. 

Dans ce cas, le nombre d'arrivée moyen est de $1,26\div 5=0,25$ par minute.

\bigskip

A 100 reprises, consécutives ou non, mais prises dans la période de stationnarité, on relève la durée du service, c'est-à-dire le temps passé par un ouvrier dans le cabinet du médecin :

\begin{center}
\begin{tabular}{|c|c|}
\hline
\textbf{Durée} & \textbf{Nombre de services observés}\\
\hline
$<1$ min. & 23\\
\hline
de 1 à 2 min. & 20\\
\hline
de 2 à 3 min. & 14\\
\hline
de 3 à 4 min. & 12\\
\hline
de 4 à 5 min. & 9\\
\hline
de 5 à 6 min. & 15\\
\hline
de 6 à 7 min. & 4\\
\hline
de 7 à 8 min. & 5\\
\hline
de 8 à 9 min. & 3\\
\hline
de 9 à 10 min. & 2\\
\hline
de 10 à 11 min. & 2\\
\hline
de 11 à 12 min. & 1\\
\hline
$>12$ min. & 0\\
\hline
\end{tabular}
\end{center}

La moyenne est égale à 3,27 min.\\
Le nombre d'ouvriers \og servis \fg\ par minute est donc $1\div 3,27=0,3$.

\medskip

On fait alors l'hypothèse que la loi des services est une loi exponentielle de paramètre $\mu=0,3$.\\
en réduisant à 9 classes et 7 degrés de liberté, on a $\chi^2_{\textrm{obs}}=0,9609$. De plus, la table nous donne $\chi^2(0,95)=2,167$, donc on peut admettre que la loi observée est bien une loi exponentielle de paramètre $\mu=0,3$ au seuil de risque de 95\%.

\medskip

Les formules données précédemment nous permettent de calculer :

\medskip

\begin{itemize}
\item le nombre moyen d'ouvriers dans la file d'attente : 
\[ n=\frac{\tfrac{0,25}{0,3}}{1-\tfrac{0,25}{0,3}}=5\]
\item le temps moyen d'attente dans la file :
\[ T=\frac{n}{\mu}=\frac{5}{0,3}=16\textrm{ min }40\textrm{ s}\]
\end{itemize}

\medskip

A raison de 8 heures par jour et 0,25 ouvrier par minute, attendant chacun en moyenne 16 min 40 s, cela fait :\[8\times 60 \times 0,25 \times 3,27 = 6\textrm{ h }30\textrm{ min}\]
de non-productivité pour l'entreprise. Aussi faut-il songer à optimiser le nombre de médecins.

\bigskip

L'établissement des formules est assez laborieux. Je vais donc les écrire directement.

\medskip

En posant $S$ le nombre de médecins, $\Psi=\frac{\lambda}{\mu}$, $\lambda$ étant le paramètre de la loi de Poisson et $\mu$ celui de la loi exponentielle, on a :

\medskip

\begin{itemize}
\item Probabilité d'une attente nulle (probabilité de l'absence de tout client dans la file d'attente) :
\[ P_0=\frac{1}{\frac{\Psi^S}{S!\left(1-\tfrac{\Psi}{S}\right)^2}+\sum\limits_{n=0}^{S-1}\frac{\Psi^n}{n!}}\]
\item Temps moyen d'attente dans la file :
\[ T=\frac{\Psi^S \times P_0}{\mu\times S \times (S!)\left(1-\tfrac{\Psi}{S}\right)^2}\]
\item Nombre moyen d'ouvriers dans la file :
\[ N=\Psi\left(\mu\times T+1\right)\]
\end{itemize}

Pour l'exemple que nous avons pris, en posant $\varphi$ le taux moyen d'inactivité des médecins, on a :

\medskip

\begin{itemize}
\item Pour $S=1$, $p_0=1-\Psi=1-0,833=0,167$, $T=$ 16 min 40 s et $\varphi=0,167$.
\item Pour $S=2$, $p_0=0,411$, $T=$ 42 s et $\varphi=1,167$.
\item Pour $S=3$, $p_0=0,432$, $T=$ 5 s et $\varphi=2,167$.
\end{itemize}
\end{document}