Modélisation des réseaux
Devan SOHIER
Files M/M : corrigé de l’exercice 1
Exercice 1 : Standard téléphonique
Deux lignes téléphoniques sont mises à la disposition des clients qui passent des commandes. Lorsque les deux
lignes sont occupées les appels restent en file et dès qu’une ligne est libérée le premier entre en contact. On suppose
que des appels arrivent suivant le processus de Poisson de taux de 20 à l’heure et l’on retient l’hypothèse que la
durée de la commande est une variable aléatoire exponentielle de durée moyenne 4 mn.
Dessiner le diagramme de transition. Le système est-il ergodique (stable) ? Si oui trouver la distribution station-
naire.
Trouver le nombre moyen d’appels branchés, le nombre moyen d’appels en attente, la durée moyenne de temps
passé par usager et la durée d’attente pour avoir une conversation en régime stationnaire
Quelle est la portion de temps où les deux lignes sont occupées ?
Corrigé
Deux lignes téléphoniques sont mises à la disposition des clients qui passent des commandes. Lorsque les
deux lignes sont occupées les appels restent en file et dès qu’une ligne est libérée le premier entre en contact.
On suppose que des appels arrivent suivant le processus de Poisson de taux de 20 à l’heure et l’on retient
l’hypothèse que la durée de la commande est une variable aléatoire exponentielle de durée moyenne 4 mn. Le
système décrit est une file M /M /2 de paramètres λ = 20 et µ = 15 appels par heure.
Attention à bien tout exprimer dans les mêmes unités. Ici, l’énoncé parle de 20 à l’heure pour la cadence à laquelle
arrive les appels, et de 4 minutes pour le temps de traitement : 4 minutes pour un traitement signifie que l’on peut
4 = 15 appels en une heure. λ et µ s’expriment toujours en nombres par minute.
traiter 60
Dessiner le diagramme de transition. Le graphe d’états de ce système est :
20 20 20 20 20 20 20 20
0 1 2 3 ... n−1 n n+1 ...
15 30 30 30 30 30 30 30
Le système est-il ergodique (stable) ? Ce système est stable car 30 > 20, et à partir de l’état 2, il a une capacité de
traitement supérieure à l’intensité à laquelle les appels parviennent au standard.
Dans l’état 1, puisqu’un seul standardiste travaille, on tend à recevoir plus vite un nouvel appel qu’il ne traite
l’appel en cours ; ce n’est pas grave, car son collègue peut alors l’aider, et, à eux deux, ils ont une cadence supérieure
à celle de l’arrivée des appels.
Si oui trouver la distribution stationnaire. Les équations vérifiées par la distribution stationnaire sont :
20π0 = 15π1 (0)
35π1 = 20π0 + 30π2 (1)
50π2 = 20π1 + 30π3 (2)
50π3 = 20π2 + 30π4 (3)
..
.
50πn = 20πn−1 + 30πn+1 (n)
..
.
1
On peut avantageusement diviser chaque terme de chacune de ces équations par 5 (ou même 10, ce qui laisserait
des demies pour seulement deux de ces équations), ce qui simplifie un peu les calculs par la suite. Ce n’est pas
nécessaire, et je poursuis ce corrigé sans cette simplification.
De l’équation 0, on tire
20 4
π1 = π0 = π0
15 3
L’équation 1 donne :
35π1 = 20π0 + 30π2
⇔ 30π2 = 35π1 − 20π0
4
⇔ 30π2 = 35 × π0 − 20π0 D’après la formule trouvée plus haut.
3
80
⇔ 30π2 = π0
3
8
⇔ π2 = π0
9
L’équation 2 donne alors π3 .
50π2 = 20π1 + 30π3
⇔ 30π3 = 50π2 − 20π1
8 4
⇔ 30π3 = 50 × π0 − 20 × π0 D’après les formules trouvées plus haut.
9 3
160
⇔ 30π3 = π0
9
16
⇔ π3 = π0
27
A ce stade, on remarque que pour passer de π1 à π2 , on multiplie par 32 , et que pour passer de π2 à π3 , on multiplie
4
par 32 également. Ce n’est pas vrai pour le passage de π0 à π1 , puisque l’on multiplie par 3 , mais c’est dû au fait
que l’état 1 est différent des autres : un seul serveur travaille et non deux. On va donc avoir une formule un peu
différente pour l’état 0, mais, à partir de l’état 1, la probabilité stationnaire de l’état suivant s’obtient toujours en
4
multipliant par 32 (c’est du moins ce que l’on va démontrer par récurrence juste après). Donc, partant de π = 3 π0 ,
on multiplie par 32 une fois pour obtenir π2 , deux fois pour π3 , et plus généralement, n − 1 fois pour obtenir πn .
n−1 n−1
4
Autrement dit, on s’attend à ce que πn = 23 π1 , et donc πn = 23 3 π0
De l’équation 3, on tire de même que
32
π4 = π0
81
k−1
4 4
On pose donc pout tout n > 0 l’hypothèse de récurrence (Hn ) : « ∀1 ≤ k ≤ n, πk = 32 3 π0 ». π1 = 3 π0 =
0 1
4 4
3
2
3 π0 et π2 = 89 π0 = 3 23 π0 , donc (H2 ) est vraie. Soit n de N , supposons (Hn ). Démontrons maintenant (Hn+1 ).
Lorsque l’on écrit un raisonnement par récurrence, il est essentiel de bien écrire l’hypothèse de récurrence. C’est elle
qui permettra de vérifier que, à chaque étape, on ne déforme pas ce que l’on est en train de démontrer. L’initialisation,
ici, doit être faite au rang 2 : en effet, le rang 0 ne dit rien (∀1 ≤ k ≤ 0 : il n’y a aucun k entre 1 et 0 !), et le
rang 1 ne nous suffira pas, puisque l’on a exprimé πn+1 en fonction des deux rangs précédents : on a besoin d’une
formule pour πn et πn−1 pour pouvoir travailler sur l’équation n : 50πn = 20πn−1 + 30πn+1 .
Soit n de N, supposons (Hn ). Démontrons maintenant (Hn+1 ).
2
D’après l’équation n :
50πn = 20πn−1 + 30πn+1
⇔ 30πn+1 = 50πn − 20πn−1
n−1 n−2
2 4 2 4
⇔ 30πn+1 = 50 × π0 − 20 π0 D’après l’hypothèse de récurrence.
3 3 3 3
n−2
2 2 4
⇔ 30πn+1 = 50 × − 20 π0
3 3 3
n−2
40 2 4
⇔ 30πn+1 = π0
3 3 3
n−2
4 2 4
⇔ πn+1 = π0
9 3 3
2 n−2 n
2 2 4 2 4
⇔ πn+1 = π0 = π0
3 3 3 3 3
Le passage de récurrence fait obligatoirement intervenir l’hypothèse de récurrence : si ce n’est pas le cas, c’est qu’il
était inutile d’adopter une approcha par récurrence.
n−1
4
(Hn+1 ) est donc vraie, et par le principe de récurrence, pour tout n > 0, πn = 23 3 π0 .
P+∞
Calculons π0 . Comme π est une distribution de probabilité, on a n=0 πn = 1. Donc
+∞
πn = 1
X
n=0
+∞ n−1
2 4
π0 + π0 =1
X
⇔
n=1 3 3
+∞ n−1
4X 2
⇔ 1+ π0 =1
3 n=1 3
+∞ m
4X 2
⇔ 1+ π0 =1 En posant m = n − 1.
3 m=0 3
4 1
⇔ 1+ π0 =1
3 1 − 2/3
⇔ 5π0 = 1
n−1
4
Donc π0 = 15 , et ∀n > 0, πn = 15
2
3 .
Trouver le nombre moyen d’appels branchés,
+∞ +∞
N = nπn = 0π0 +
X X
nπn
n=0 n=1
+∞ n−1 +∞ n−1
4 2 4 X 2
= =
X
n n
n=1 15 3 15 n=1 3
4 1 12
= =
15 (1 − 2/3)2 5
le nombre moyen d’appels en attente,
Dans l’état n, pour n > 1, n − 2 appels sont en attente. Dans les états 0 et 1, aucun appel n’est en attente, pas -1
et -2 !
3
+∞ +∞ +∞
Nf = (n − 2)πn = πn
X X X
nπn − 2
n=2 n=2 n=2
+∞ +∞
= nπn − π1 − 2 πn − π0 − π1 = N + π1 + 2π0 − 2
X X
n=0 n=0
12 4 2 16 16
= + + −2= =
5 15 5 15 15
la durée moyenne de temps passé par usager et la durée d’attente pour avoir une conversation en régime
stationnaire. D’après la loi de Little,
N 3
T = =
λ 25
et
Nf 4
T f = =
λ 75
Quelle est la portion de temps où les deux lignes sont occupées ? Les deux lignes sont occupées dans tous les
états n > 2. Donc, la proportion du temps où les deux lignes sont occupées est
+∞ +∞
πn = π n − π0 − π1
X X
n=2 n=0
1 4 8
=1− − =
5 15 15
n−1
On peut aussi calculer +∞
4
n=2 πn en remplaçant πn par l’expression que l’on a calculée πn =
2
, et l’on
P
15 3
obtiendra le même résultat. . . après plus de calculs !