Simulation

Simulation: technique qui utilise l'ordinateur pour imiter (simuler) le

comportement d'un processus

Souvent utilisée pour étudier les processus stochastiques

Exemple: Analyse de files d'attente quand le temps entre les arrivées

et le temps de service ne sont pas exponentiel (hypothèse markovienne
n'est pas satisfaite)
Difficile d'évaluer mathématiquement l'évolution "exacte" du système, et
alors nous avons recours à la simulation pour obtenir des résultats "qui ne
sont pas exacts mathématiquement" mais qui permettent d'avoir une très
bonne information sur ceux-ci.

Pour imiter (simuler) l'évolution du système:

faire appel à une ou des distributions de probabilité pour générer
l'occurence des événements qui vont spécifier l'évolution d'un système
Éléments nécessaires pour spécifier un modèle de simulation:

1. L'état du système que nous voulons analyser (le nombre de clients dans un
système de file d'attente)

2. L'ensemble des états possibles que le système peut prendre.

3. L'ensemble des événements possibles qui peuvent modifier l'état du système

(les arrivées et les fins de service dans un système de file d'attente).

4. Disponibilité d'une horloge de simulation pour enregistrer les moments où

les événements se produisent.

5. Une méthode pour générer aléatoirement les événements.

6. Procédure pour identifier les tranformations de l'état du système suite aux

divers événements.
Exemple: Lancement d'une pièce de monnaie:
Règles du jeu:
1. Chaque partie consiste a lancer plusieurs fois une pièce de monnaie
jusqu'à ce que la différence entre le nombre de fois où la pièce tombe
sur Face et celui où la pièce tombe sur Pile est égal à 3.
2. À chaque lancement de la pièce de monnaie, vous déboursez $1. Vous
ne pouvez cesser de jouer au cours d'une partie.
3. Vous recevez $8 à la fin de la partie.

Exemples de résultats de partie:

PPP 3 lancés gain: $5
PFPPP 5 lancés gain: $3
PFFPFPFPPPP 11 lancés perte:$3
Exemple: Lancement d'une pièce de monnaie:
Règles du jeu:
1. Chaque partie consiste a lancer plusieurs fois une pièce de monnaie
jusqu'à ce que la différence entre le nombre de fois où la pièce tombe
sur Face et celui où la pièce tombe sur Pile est égal à 3.
2. À chaque lancement de la pièce de monnaie, vous déboursez $1. Vous
ne pouvez cesser de jouer au cours d'une partie.
3. Vous recevez $8 à la fin de la partie.

Expérience de simulation pour générer une suite d'observations aléatoires

en utilisant un générateur de nombres aléatoires dans l'intervalle [0,1].

Probabilités du resultat de lancer la pièce de monnaie:

1 1
P ( Face ) = P ( Pile ) =
2 2
Exemple: Lancement d'une pièce de monnaie:
Règles du jeu:
1. Chaque partie consiste a lancer plusieurs fois une pièce de monnaie
jusqu'à ce que la différence entre le nombre de fois où la pièce tombe
sur Face et celui où la pièce tombe sur Pile est égal à 3.
2. À chaque lancement de la pièce de monnaie, vous déboursez $1. Vous
ne pouvez cesser de jouer au cours d'une partie.
3. Vous recevez $8 à la fin de la partie.
Les probabilités du résultat de lancer la pièce de monnaie:
1 1
P ( Face ) = P ( Pile ) =
2 2
Ainsi, pour simuler le lancement de la pièce, l'ordinateur peut justement
indiquer que la moitié des lancements sont des Faces et l'autre moitié sont
des Piles, ou plus spécifiquement, la correspondance utilisée est la suivante:
0.0000 à 0.4999 → Face
0.5000 à 0.9999 → Pile
Exemple: Lancement d'une pièce de monnaie:
Règles du jeu:
1. Chaque partie consiste a lancer plusieurs fois une pièce de monnaie
jusqu'à ce que la différence entre le nombre de fois où la pièce tombe
sur Face et celui où la pièce tombe sur Pile est égal à 3.
2. À chaque lancement de la pièce de monnaie, vous déboursez $1. Vous
ne pouvez cesser de jouer au cours d'une partie.
3. Vous recevez $8 à la fin de la partie.

Expérimentations:
Nombre de Nombre moyen Résultats
parties de lancés

14 7.14 gain: $0.86

1000 8.97 perte : $0.97

Éléments nécessaires pour spécifier un modèle de simulation de la pièce:

1. L'état du système que nous voulons analyser

N ( t ) = nombre de Faces moins le nombre de Piles après t lancés
2. L'ensemble des états possibles que le système peut prendre.
N ( t ) ∈ {−3, −2, −1, 0,1, 2,3}
3. L'ensemble des événements possibles qui peuvent modifier l'état du système

Événements changeant l'état du système: lancé est une Face, lancé est une Pile
4. Disponibilité d'une horloge de simulation pour enregistrer les moments où
les événements se produisent.
L'horloge enregistre le nombre de lancements.
5. Une méthode pour générer aléatoirement les événements.
0.0000 à 0.4999 → Face
Un générateur de nombres aléatoires dans l'intervalle [0,1]. 0.5000 à 0.9999 → Pile
6. Procédure pour identifier les tranformations de l'état du système suite aux
divers événements.
1. L'état du système que nous voulons analyser
N ( t ) = nombre de Faces moins le nombre de Piles après t lancés

2. L'ensemble des états possibles que le système peut prendre.

3. L'ensemble des événements possibles qui peuvent modifier l'état du système

Événements changeant l'état du système: lancé est une Face, lancé est une Pile

4. Disponibilité d'une horloge de simulation pour enregistrer les moments où

les événements se produisent.
L'horloge enregistre le nombre de lancements.
5. Une méthode pour générer aléatoirement les événements.
0.0000 à 0.4999 → Face
Un générateur de nombres aléatoires dans l'intervalle [0,1]. 0.5000 à 0.9999 → Pile
6. Procédure pour identifier les tranformations de l'état du système suite aux
divers événements. N ( 0 ) := 0
 N ( t − 1) + 1 si lancé est Face
N ( t ) := 
 N ( t − 1) − 1 si lancé est Pile
Fin de la partie si N ( t ) = ±3
 Exemple: Système de file d'attente M / M /1:
Arrivée: temps entre arrivée est exponentiel
Service: service exponentiel
1 serveur
λ = taux d'arrivée = 3 à l'heure
µ = taux de service = 5 à l'heure
1. L'état du système que nous voulons analyser

N ( t ) = nombre de clients dans le système de file d'attente

3. L'ensemble des événements possibles qui peuvent modifier l'état du système:

l'arrivée d'un nouveau client ou une fin de service
Exemple: Système de file d'attente M / M /1:
Arrivée: Poisson, (temps entre arrivée est exponentiel)
Service: exponentiel
1 serveur
λ = taux d'arrivée = 3 à l'heure
µ = taux de service = 5 à l'heure

1. L'état du système que nous voulons analyser

N ( t ) = nombre de clients dans le système de file d'attente

6. Procédure pour identifier les tranformations de l'état du système suite aux

divers événements.
N ( 0 ) := 0
 N ( t − 1) + 1 si une arrivée se produit à t
N ( t ) := 
 N ( t − 1) − 1 si une fin de service se produit à t
Méthode d'augmentation du temps par période fixe
Augmentation du temps par des périodes de longueur fixe
Au cours de chaque période fixe d'augmentation du temps, déterminons
quels événements se produisent et que devient l'état du système.

Deux événements: arrivée et fin de service

Hypothèse sur la durée de la période de temps lors d'une augmentation:
assez petite pour supposer qu'il ne peut se produire plus d'une arrivée
ou plus d'une fin de service.
Supposons que la longueur de la periode fixe d'augmentation est de 0.1 heure
(6 minutes).

λ = taux d'arrivée = 3 à l'heure

µ = taux de service = 5 à l'heure

PA = probabilité d'une arrivée dans une période de 0.1 heure

= P ( temps d'une arrivée ≤ 0.1) = 1 − e3×0.1 = 0.259

PD = probabilité d'une fin de service dans une période de 0.1 heure

= P ( temps d'une fin de service ≤ 0.1) = 1 − e5×0.1 = 0.393

Pour générer aléatoirement l'une ou l'autre de ces événements selon ces lois
de probabilité, l'ordinateur utilise un générateur de nombres aléatoires sur
l'intervalle [0,1].
PA = probabilité d'une arrivée dans une période de 0.1 heure
= P ( temps d'une arrivée ≤ 0.1) = 1 − e3×0.1 = 0.259
PD = probabilité d'une fin de service dans une période de 0.1 heure
= P ( temps d'une fin de service ≤ 0.1) = 1 − e5×0.1 = 0.393
Pour générer aléatoirement l'une ou l'autre de ces événements selon ces lois
de probabilité, l'ordinateur utilise un générateur de nombres aléatoires sur
l'intervalle [0,1].

En générant un premier nombre aléatoire rA ∈ [0,1]

rA < 0.259 ⇒ une arrivée se produit
rA ≥ 0.259 ⇒ une arrivée ne se produit pas

De façon similaire, en générant un deuxième nombre aléatoire rD ∈ [0,1]

rD < 0.393 ⇒ une fin de service se produit
rD ≥ 0.393 ⇒ une fin de service ne se produit pas
En générant un premier nombre aléatoire rA ∈ [0,1]
rA < 0.259 ⇒ une arrivée se produit
rA ≥ 0.259 ⇒ une arrivée ne se produit pas

De façon similaire, en générant un deuxième nombre aléatoire rD ∈ [0,1]

rD < 0.393 ⇒ une fin de service se produit
rD ≥ 0.393 ⇒ une fin de service ne se produit pas

Table des résultats pour 10 itérations

Génération de nombres (pseudo) aléatoires

Pour mettre au point un modèle de simulation, il faut générer des nombres

aléatoires pour obtenir des observations aléatoires répondant à une
distribution de probabilité.

Plusieurs tables de nombres aléatoires ont déjà été générées par des mécanismes
physiques comme la roulette, mais maintenant nous pouvons utiliser l'ordinateur
pour les réaliser.

Plusieurs "software packages" permettent de générer des nombres aléatoires.

Exemple d'une table de nombres aléatoires
Un générateur de nombres aléatoires est un algorithme qui produit des
suites de nombres qui ont l'apparence d'être aléatoires.

La dénotation nombre aléatoire indique qu'il s'agit d'une observation

d'une variable aléatoire ayant une sorte de distribution uniforme permettant
à chaque nombre généré d'être aussi probable que les autres.
Deux catégories de nombres aléatoires:

Un nombre entier aléatoire est une observation d'une variable ayant une
distribution uniforme entière définie sur l'ensemble n, n + 1,… , n .
Les probabilités définissant cette distribution sont les suivantes:
1
P ( n ) = P ( n + 1) = … = P ( n ) = .
n − n +1
Souvent n = 0 ou 1, et si ce n'est pas le cas, il suffit de faire une
translation appropriée des éléments de l'ensemble pour retouver
cette propriété.
Deux catégories de nombres aléatoires:
Un nombre entier aléatoire est une observation d'une variable ayant une
distribution uniforme entière définie sur l'ensemble n, n + 1,… , n .
Les probabilités définissant cette distribution sont les suivantes:
1
P ( n ) = P ( n + 1) = … = P ( n ) = .
n − n +1
Souvent n = 0 ou 1, et si ce n'est pas le cas, il suffit de faire une
translation appropriée des éléments de l'ensemble pour retouver
cette propriété.

Un nombre uniforme aléatoire est une observation d'une variable ayant une
distribution uniforme continue définie sur un intervalle [ a, b ] . La fonction de
densité de cette distribution est la suivante
 1
 si a ≤ x ≤ b
f ( x) = b − a
0 sinon.
Très souvent a = 0 et b = 1.
Très souvent les nombres aléatoires générés par ordinateur sont des nombres
entiers aléatoires qui peuvent être transformés en nombres uniformes aléatoires
comme suit:
Étant donné un nombre entier aléatoire dans l'ensemble 0 à n , il suffit de le
diviser par n pour obtenir (approximativement) un nombre uniforme aléatoire.
Lorsque la valeur de n est petite, nous pouvons obtenir un nombre uniforme
aléatoire comme suit:
1
en ajoutant d'abord la valeur au nombre entier aléatoire avant de diviser
2
ce résultat par ( n + 1) .

En fait, les nombres aléatoires générés par ordinateur sont plutôt des nombres
pseudo-aléatoires parce qu'ils sont prévisibles et qu'ils peuvent être reproduits
de nouveau.

Plusieurs procédures statistiques sophistiquées permettent d'évaluer si les

suites de nombres générés ont l'apparence d'être aléatoires.
Méthode de congruents mixte pour générer des nombres aléatoires

La méthode de congruents mixte génère une suite de nombres entiers aléatoires

sur l'ensemble 0 à (m − 1).
Méthode itérative générant le prochain nombre aléatoire xn +1 à partir du nième
nombre aléatoire xn :
- Il faut donc choisir un premier point x0 dénoté le germe (seed).
- Spécifier des nombres entiers a, c et m tels que a < m et c < m.
- Déterminer
xn +1 := ( axn + c ) ( modulo m ) .
xn +1 est le reste de la division de ( axn + c ) par m.
 Tableau illustrant la méthode avec x0 = 4, a = 5, c = 7 et m = 8
xn +1 := ( axn + c ) ( modulo m ) .

Le nombre de nombres générés consécutifs de la suite avant qu'elle commence

à se répéter dénote la longueur de cycle ( 8 dans l'exemple précédent ) .
Conversion des nombres entiers aléatoires en des nombres uniformes aléatoires
avec la formule
1
nombre entier aléatoire +
nombre uniforme aléatoire = 2
m
est illustrée dans le tableau suivant
 Méthode de congruents multiplicative pour générer des nombres aléatoires

La méthode de congruents multiplicative génère une suite de nombres entiers aléatoires

sur l'ensemble 0 à (m − 1).
Méthode itérative générant le prochain nombre aléatoir xn +1 à partir du nième
nombre aléatoir xn :
- Il faut donc choisir un premier point x0 dénoté le germe (seed).
- Spécifier des nombres entiers a et m tels que a < m .
- Déterminer
xn +1 := ( axn ) ( modulo m ) .
xn +1 est le reste de la division de ( axn ) par m.

Méthode de congruents multiplicative ≡ Méthode de congruents mixte

o ù c = 0.
Méthode de congruents additive pour générer des nombres aléatoires

La méthode de congruents additive génère une suite de nombres entiers aléatoires

sur l'ensemble 0 à (m − 1).
Méthode itérative générant le prochain nombre aléatoir xn +1 à partir du nième
nombre aléatoir xn :
- Il faut donc choisir un premier point x0 dénoté le germe (seed).
- Spécifier le nombre entier m.
- Déterminer
xn +1 := ( xn + xn −1 ) ( modulo m ) .
xn +1 est le reste de la division de ( xn + xn −1 ) par m.

Méthode de congruents additive ≡ Méthode de congruents mixte

où a = 1 et c = xn −1.
Génération d'observations aléatoires pour diverses distribution de probabilités

Étant donné une suite de nombres aléatoires, nous pouvons associer

à ces nombres, des observations aléatoires d'une variable ayant
une distribution spécifiée de probabilités.