Master Informatique et Modélisation des Systèmes
Complexes ( IMSC )
Département d’ Informatique et Mathématique
Rapport intitule:
SIMULATION D’UNE FILE D’ATTENTE
Sujet: Mod. Eval. Perf. Syst
Réalisé par:
AIT AICHA Othman
MOUSTAGE Imane
ZBIR Oumaima
Responssable:
Prof. BENTAHER
Année universitaire : 2020/2021
Sommaire
I. Introduction
II. Processus d’arrivées
III. Simulation du Nombre d’Achats et Temps de Simulation
IV. Organisation de paiement guichet unique
V. Cas d’un Nombre Fini de Guichets
VI. Problème d’optimisation
VII. Conclusion
I. Introduction:
Le candidat a pour objectif de décrire quelques méthodes de génération de lois
usuelles utilisées en probabilités, et de les appliquer au cadre qui lui est proposé. Il
veillera à équilibrer au cours de son exposé les explications relevant de la
modélisation, les simulations informatiques et les raisonnements mathématiques.
II. Processus d’arrivées:
Pour deux entiers p, n non nuls arbitrairement fixés, l’algorithme suivant permet de
simuler une réalisation du vecteur N (1/n), N (2/n), ..., N (p/n).
Algorithme:
j =1
T (1) = − ln (runif )/λ
Tant que (T (j) < p/n) faire
T (j + 1) = T (j) − ln (runif )/λ
j = j +1
Fin de boucle
Pour 0 ≤ j ≤ p, N (j) = Nombre de T (i) entre 0 et j/n
Renvoyer le vecteur N
Code en Python:
def simuler_realisation_vect_N(n,p,landa):
j=0
T=[]
N=[]
T.append(-np.log(random.uniform(0,1))/landa)
while T[j]<p/n:
T.append(T[j]-np.log(random.random())/landa)
j=j+1
j=0
for j in range(p):
c=0
for i in T:
if i>=0 and i<=j/n:
c=c+1
N.append(c)
return N
#landa=0.01
landa=0.1
#landa=1
#N=simuler_realisation_vect_N(3,1000,landa)
#N=simuler_realisation_vect_N(1,1000,landa)
N=simuler_realisation_vect_N(9,1000,landa)
plt.plot(N)
Affichage:
landa=0.1 landa=0.01
landa=1
la variable aléatoire T(1)= (− ln (1 − U )/λ) suit la loi exponentielle de paramètre λ.
Comme U et 1 − U ont même loi, alors la variable aléatoire − ln (U )/λ suit la loi exponentielle
de paramètre λ.
III. Simulation du Nombre d’Achats et Temps de Simulation:
Lemme 3.1
Soit X une variable aléatoire réelle de fonction de répartition F . Soit
−1
F (x) = inf {t ∈ R|F (t) ≥ x} ∀x ∈]0, 1]
−1
F est une variable aléatoire réelle. Si U est une variable aléatoire de loi uniforme sur [0, 1],
−1
alors F (U) est une variable aléatoire de même loi que X.
Nous cherchons à simuler informatiquement la loi ν(c). D’après le lemme 3.1, on peut
calculer les valeurs de la fonction répartition de cette loi par l’algorithme suivant :
Algorithme:
U = (exp(c) − 1) ∗ runif
j =1
p=c
Tant que (U > p), faire
j = j +1
p = p + c j /j!
Fin de boucle
Simulation = j
Code en Python:
## on peut calculer les valeurs de la fonction de répartition de cette loi par l’algorithme suivant
import nump as np
import math
def val_repartition(c):
U=(np.exp(c)-1)*random.uniform(0,1)
j=1
p=c
while(U>p):
j=j+1
p=p+(pow(c,j))/math.factorial(j)
return j
val_repartition(2)
Lemme 3.2.
Pour toute suite (σ n ) n≥1 de variables aléatoires indépendantes et de même loi exponentielle de pa-
ramètre c la variable aléatoire
S = inf[n ≥ 1; (σ 1 + ... + σ n ) > 1] − 1
suit la loi de Poisson de paramétre c.
En se basant sur ce dernier lemme, on a l’algorithme suivant qui permet de
modéliser une variable aléatoire de loi de poisson de paramètre c.
Algorithme:
V = runif
j=0
Tant que (V > exp (−c)), faire
j = j +1
V = V ∗ runif
Fin de boucle
Simulation = j
Code en Python:
def loi_poisson(c):
V=random.uniform(0,1)
j=0
while V>math.exp(-c):
j=j+1
V=V*random.uniform(0,1)
Sumilation=j
return Sumilation
c=2*3
loi_poisson(c)
IV. Organisation de paiement guichet unique:
Nous visons maintenant à étudier la taille de la file d’attente à un temps donné. En
particulier, nous prenons désormais en compte les sorties survenues après la
réalisation des services. Dans ce modèle, nous supposons que le serveur ne compte
qu’un guichet, que la file peut contenir un nombre illimité de clients et que les clients
sont servis dans l’ordre d’arrivée.
Algorithme:
T (1) = − ln (runif )/λ
U (1) = T (1)
n =1
Tant que (T (n) < p) faire
T (n + 1) = T (n) − ln (runif )/λ
U (n + 1) = max(U (n) + a ∗ randach(c) + D, T (n + 1))
n=n+1
Fin de boucle
Pour 0 ≤ j ≤ p, N(j) = Nombre de T(i) entre 0 et j
Pour 0 ≤ j ≤ s ≤ p, S(j) = Nombre de U (i) entre 0 et j.
Pour 0 ≤ s ≤ j ≤ p, F (j) = N (j) − S(j).
code en python:
def simuler_vect_F(p,landa,a,D,c):
T=[];U=[];S=[];F=[];N=[]
T.append(-np.log(random.uniform(0,1))/landa)
U.append(T[0])
l=0
while(T[l]<p):
T.append(T[l]-np.log(random.uniform(0,1))/landa)
U.append(max(U[l]+a*randach(c)+D,T[l+1]))
l=l+1
for j in range(p):
t=0
for i in T:
if i>=0 and i<=j:
t=t+1
N.append(t)
for x in range(p):
u=0
for i in U:
if i>=0 and i<=x:
u=u+1
S.append(u)
for i in range(0,p):
F.append(N[i]-S[i])
return F
#landa=0.15
landa=0.1
#landa=0.01
#landa=0.9
p=1000
a=0.8
#a=0.1
#a=0.01
D=1
c=3
plt.plot(simuler_vect_F(p,landa,a,D,c))
Affichage:
landa=0.1 landa=0.1
landa=1
Ces trois graphiques font apparaitre les phénomènes suivants :
- Si l'espérance des temps d'inter-arrivées est strictement plus grande que l'espérance
du temps de paiement, la file d'attente passe fréquemment par 0. Ceci peut encore
s'exprimer de la façon suivante : le temps d'attente s'annule avec une fréquence assez
élevée.
- Si l'espérance des temps d'inter-arrivées est égale à l'espérance du temps de
paiement, la file d'attente passe par 0, mais la fréquence de libération du guichet
semble beaucoup plus faible. En particulier, il existe de longues périodes au cours
desquelles la file compte toujours au moins un client.
- Si l'espérance des temps d'inter-arrivées est strictement inférieure à l'espérance du
temps de paiement, la taille de la d'attente explose avec le temps. Le serveur est
manifestement saturé.
V. Cas d’un Nombre Fini de Guichets:
On suppose désormais que l’organe de service dispose de k guichets,
pour un entier k ≥ 1 fixé. En revanche, nous conservons les hypothèses suivantes :
(1) Les clients arrivent selon un processus de Poisson de paramètre λ > 0.
(2) Les clients en attente forment une unique file d’attente et sont servis dans l’ordre
d’arrivée.
(3) Les temps de paiement sont régis par une relation affine avec le nombre d’achats.
Ajoutons que les guichets sont numérotés de 1 à k : si deux guichets sont libres, le client choisi
celui de plus petit numéro.
Pour un entier p non nul arbitrairement fixé, l’algorithme suivant permet de simuler
une réalisation du vecteur (F (1), F (2), ..., F (p)):
Algorithme:
T(1) = -ln (runif )/λ
U(1) = T(1)
n=1
Tant que (T (n) < p et n < k) faire
T (n + 1) = T (n) − ln (runif )/λ
U (n + 1) = T (n + 1)
n = n +1
Fin de boucle
V=tri par ordre croissant de (U (1) + a ∗ randach(c) + D, ..., U (k) + a ∗ randach(c) + D)
Tant que (T (n) < p) faire
T (n + 1) = T (n) − ln (runif )/λ
U (n + 1) = max(V (1), T (n + 1))
V=tri par ordre croissant de (U (n + 1) + a ∗ randach(c) + D, V (2), ..., V (k))
n = n +1
Fin de boucle
Pour 0 ≤ j ≤ p, N (j) = Nombre de T (i) entre 0 et j
Pour 0 j ≤ p, S(j) = Nombre de U (i) entre 0 et j.
Pour 0 ≤ j ≤ p, F (j) = N (j) − S(j).
Code en python:
def simuler_vect_F_nbG(p,landa,a,D,c,k):
T=[];U=[];V=[];F=[];S=[];N=[]
T.append(-np.log(random.uniform(0,1))/landa)
U.append(T[0])
n=0
while(T[n]<p and n<k):
T.append(T[n]-np.log(random.uniform(0,1))/landa)
U.append(T[n+1])
n=n+1
for i in range(0,k):
V.append(U[k]+a*randach(c)+D)
V.sort()
while(T[n]<p):
T.append(T[n]-np.log(random.uniform(0,1))/landa)
U.append(max(V[0],T[n+1]))
V[0]=U[n+1]+a*randach(c)+D
V.sort()
n=n+1
for j in range(p):
t=0
for i in T:
if i>=0 and i<=j:
t=t+1
N.append(t)
for x in range(p):
u=0
for i in U:
if i>=0 and i<=x:
u=u+1
S.append(u)
for i in range(0,p):
F.append(N[i]-S[i])
return F
landa=0.7
p=100
a=0.8
D=1
c=5
k=4
plt.plot(simuler_vect_F_nbG(p,landa,a,D,c,k))
Affichage:
(Un )n≥1 désignant maintenant la suite des instants d’arrivée des clients aux différentes caisses.
l’algorithme que nous proposons est pour simuler la taille de la file d’attente jusqu’à un
instant donné.
VI. Problème d’optimisation:
Dans ce paragraphe, nous visons à calibrer le nombre de caisses du magasin de facon à ce que
la taille de la file d’attente demeure raisonnable au cours d’une journée d’ouverture.
Dans cette perspective, nous cherchons à estimer, pour un réel t > 0 fixé, la probabilité que la
taille de la file d’attente franchisse entre les instants 0 et t un seuil critique S donné, S étant un
entier non nul. Plus exactement, nous cherchons à déterminer la valeur de :
l’algorithme suivant permet de simuler une réalisation de la variable max[0,t] F:
code en python:
def simuler_variable_optimisation(p,landa,a,D,c,k,tto):
T=[];U=[];V=[];F=[];S=[];N=[]
T.append(-np.log(random.uniform(0,1))/landa)
U.append(T[0])
n=0
while(T[n]<p and n<k):
T.append(T[n]-np.log(random.uniform(0,1))/landa)
U.append(T[n+1])
n=n+1
for i in range(0,k):
V.append(U[k]+a*randach(c)+D)
V.sort()
while(T[n]<p):
T.append(T[n]-np.log(random.uniform(0,1))/landa)
U.append(max(V[0],T[n+1]))
V[0]=U[n+1]+a*randach(c)+D
V.sort()
n=n+1
for j in range(p):
t=0
for i in T:
if i>=0 and i<=j:
t=t+1
N.append(t)
for x in range(p):
u=0
for i in U:
if i>=0 and i<=x:
u=u+1
S.append(u)
for i in range(0,p):
F.append(N[i]-S[i])
return F
M=[]
for i in range(0,tto):
m=0
for j in range(0,i):
if(U[j]>T[i]):
m=m+1
M.append(m)
return max(M)
landa=0.99
p=100
a=0.9
D=1
c=5
k=4
tto=2
plt.plot(simuler_variable_optimisation(p,landa,a,D,c,k,tto))
Affichage:
VII. Conclusion:
Selon les données prises en compte et à l'aide de la simulation, nous sommes
maintenant en mesure d'aider le preneur de décision à améliorer son commerce tout
en se préservant des pertes occasionnées par une éventuelle extension. Les
programmes que l'on a implémentés sous Matlab nous ont permis de proposer au
gestionnaire la meilleure stratégie (k=3 guichets) qui lui évite des dommages tout en
optimisant le revenu total de l'entreprise.
