‫ﺑﺳم ﷲ اﻟرﺣﻣن اﻟرﺣﯾم‬

Présenté par :
Dr. Bendiaf M.
Maître de conférences - classe B -
Département d’Informatique.
Université de Bordj Bou Arréridj
[email protected]

2
 CHAPITRE 2 :
Les modèles discrets

3
1. Classification des modèles
2. Rôles des modèles
3. Qualités d’un modèle de simulation
4. Outils de modélisation

4
5
Parfois, il est impossible d’étudier le système directement du fait qu’il soit
inaccessible, ou trop coûteux pour qu’on puisse faire dessus des
expériences directement, du fait qu’il change trop rapidement ou trop
lentement ; dans ces cas, on considère un système de manière globale, par
abstraction de certaines contraintes, nous pouvons associer à un système
complexe une représentation simplifiée de sa structure et de son
fonctionnement, cette représentation plus simple à décrire et à utiliser
s’appelle un modèle.

6
Le modèle conceptuel est une représentation (mathématiques logique,
verbale, etc.) du système réel (ou retenu pour une étude particulière), il
est obtenu dans une phase d'analyse et de modélisation. Le modèle
programmé est la mise en œuvre du modèle conceptuel sur un
calculateur, il est obtenu dans une phase de programmation et de mise en
œuvre. Les enseignements sur le système réel sont obtenus à la suite
d'expérimentations sur le modèle programmé dans une phase
d'expérimentation.

Processus simplifie de modélisation 7

Les caractéristiques fondamentales d’un modèle sont :

 Le caractère abstrait, qui doit notamment permettre de faciliter la

compréhension du système étudié.
 Il réduit la complexité du système étudié.
 Il permet de simuler le système étudié et reproduit ses comportements.
 Modéliser une entité revient donc à définir les concepts qui permettent
de la décrire et les relations fonctionnelles qu’entretiennent ces concepts.

8
 Pour un système donné, il est possible de construire plusieurs types de
modèles selon les objectifs poursuivis ou les contraintes à satisfaire.

 On peut considérer qu’il existe deux grandes catégories de modèles :

les modèles analogiques, encore appelés modèles physiques
(maquettes du système) et les modèles abstraits.

9
Modèle descriptif :
Un modèle décrit un système par son état et par son évolution prévisible. Selon
le poids accordé à l’un ou à l’autre, le modèle est descriptif ou prédictif.
Le modèle descriptif est une sorte de photographie de la réalité.
Celle-ci est décrite dans l’état où elle se présente à une période donnée. On
suppose que les éléments retenus n’évoluent que très lentement. Lorsque la
réalité aura évolué rendant son modèle caduc, on procèdera à la mise à jour du
premier modèle.

Exemple : Les SIG

(Système d'Information
Géographique)

Modèle prédictif:
Un modèle prédictif s’attache à décrire l’évolution d’un phénomène de manière à
pouvoir prédire un état futur à partir d’un état initial connu.
10
 Parmi les modèles analogiques, on peut citer par exemple, une
maquette d’avion permettant d’évaluer l’écoulement de l’air sur les
ailes.

 La réalisation d’un modèle mathématique signifie que tous les

composants du système et toutes les connexions entre les
composants sont exprimées sous la forme de relations
mathématiques.

 Évidemment, la conception d’un modèle, quelle que soit sa nature,

requiert l’acquisition de certaines compétences dans le domaine du
système étudié : productique, physique, biologie, écologie… D’autre
part, le modèle hérite des lacunes des connaissances mises en
œuvre: lois physiques approchées, collecte difficile de données
souvent partielles ou estimées.

11
- Les modèles physiques sont ceux dans lesquels le système réel est
représenté par une réplique ou une maquette, à une échelle différente et
éventuellement à l'aide de matériaux différents. Ils sont utilisés à des
fins d'entraînement : simulateurs de vol, de conduite, maquettes de
véhicules pour des essais aérodynamiques,...

- Les modèles Logico-Mathématiques ou symboliques sont définis par des

relations logiques et quantitatives qui sont manipulées et changées pour
voir comment le modèle du système réel réagit. Ils sont exécutés sur des
ordinateurs.

Une autre distinction concerne la prise en compte d'aléas ou de variations

aléatoires dans le modèle.
- Si le système est indépendant de l'influence de variables aléatoires ou
imprévisibles, on utilise un modèle déterministe.
- Si les aléas jouent un rôle significatif dans le comportement du système
(exemple typique : les pannes), on utilise un modèle stochastique.
12
 Un modèle déterministe produit une seule sortie pour un intrant
donné.
 Un modèle stochastique produit plusieurs sorties possibles pour un
intrant donné.
13
Une troisième classification distingue :
- les modèles statiques, pour lesquels le temps n'intervient pas.
Exemple : modèle comptable permettant de calculer le bénéfice en fin
d'année à l'aide d'un tableur.
- les modèles dynamiques, pour lesquels le comportement est une fonction
du temps. Exemple : système de manutention dans une usine.

Enfin, à l'intérieur des modèles dynamiques, on distingue :

- les modèles à événements discrets (ou discontinus) dans lesquels les
changements d'état ne surviennent que lors d'événements tels le début
ou la fin d'une opération, la mise en attente d'une pièce dans un stock, la
libération d'une ressource, ... Dans une simulation à événements
discrets, les flux essentiels que l'on examine sont composés d 'éléments
isolables que l'on peut dénombrer et identifier individuellement. Ces
éléments sont couramment appelés "Entités" ou "Articles" ,

14
- les modèles continus, plus adaptés aux flux continus, qui utilisent des
équations mathématiques pour prendre en compte les changements
d'état qui s'effectuent de façon continue au cours du temps. Les valeurs
des variables d'état sont recalculées régulièrement selon un pas d'horloge
d'après ces équations. Exemple : un réacteur chimique.

- les modèles combinés (ou mixtes), qui intègrent les deux aspects.
Exemple : industrie métallurgique ou agro-alimentaire.

15
La méthodologie présentée par [QUERE 97] décompose le processus de
modélisation en quatre phases consécutives et éventuellement itératives :

(dans un formalisme
mathématique ou de
programmation)

 L’analyse peut utiliser les diagrammes entité / association , UML …

 la spécification peut utiliser SADT, SA-RT, les réseaux de Pétri, DEVS
(Discrete Event System Specification)
 La construction du modèle de connaissance doit être réalisée en
collaboration avec les experts du domaine. Elle consiste en la récolte et
la formalisation de la connaissance sur le système étudié. Une méthode
de décomposition peut être employée pour faciliter la formalisation de
la connaissance lorsque le système étudié est complexe. 16
Construction d’un modèle de connaissance

17
(Exemple)

18
Modèle d’action (exemples)

Exemple de représentation du modèle

Witness

Exemple du modèle SIMULA

19
20
Les modèles permettent de mieux comprendre le système que l’on développe, ils
permettent ainsi d’atteindre plusieurs objectifs parmi lesquels on cite:

 Les modèles nous aident à visualiser un système tel qu’il est ou tel
que nous voudrions qu’il soit.

 Les modèles permettent de préciser la structure ou le

comportement d’un système.

 Les modèles fournissent un canevas qui guide la construction d’un

système.
 Les modèles permettent de documenter les décisions prises.

21
Un modèle doit être :
– Le plus simple et le plus clair possible
– Valide (et validable !)
– Le plus fidèle possible par rapport au besoin de la simulation
– Le plus efficace par rapport au but poursuivi

Le meilleur modèle est celui qui reflète le mieux les aspects

du système réel que l’on veut étudier, compte tenu du besoin
et des contraintes de moyens et de délais de développement.

22
 1- Les Réseaux de Petri (Définition)

Un réseau de Pétri est un moyen de:

 modélisation du comportement des systèmes dynamiques à
événements discrets.
 description des relations existantes entre des conditions et des
évènements.
2- Places, transitions et arcs

Une place est Un arc relie soit

représentée par Une transition soit une transition
une place à une
un cercle par un trait: à une place.
transition

23
 3- Marquage
Chaque place contient un nombre entier positif ou nul de marques ou
jetons. Le marquage M définit l'état du système décrit par le réseau à un
instant donné. C'est un vecteur colonne de dimension le nombre de places
dans le réseau. Le iéme élément du vecteur correspond au nombre de
jetons contenus dans la place Pi .

Exemple 1 :marquage Exemple 2 :marquage Exemple 3 :marquage

24
4- Franchissement d'une transition
Une transition est franchissable lorsque toutes les places qui lui sont
en amont (ou toutes les places d'entrée de la transition) contiennent
au moins un jeton.

Exemple 4 : Franchissement d'une transition

T1 ne peut pas être

franchie car P2 ne
contient aucun jeton.

Le franchissement consiste à retirer un jeton de chacune des

places d'entrée et à rajouter un jeton à chacune des places de
sortie de la même transition.
25
 Exemple 5 : Franchissement d'une transition
Avant franchissement : Après franchissement :

Le franchissement de T1 consiste
à enlever un jeton de P1 et un
jeton de P2 et à rajouter un jeton
dans P3 et un jeton dans P4.

Exemple 6 : Franchissement d'une transition

Avant franchissement : Après franchissement :

Le franchissement de T1 consiste à
enlever un jeton de P1 et à ajouter
un jeton à chacune des places P2,
P3 et P4.

26
Une transition franchissable n'est pas forcément immédiatement franchie.
Une transition sans place d'entrée est toujours franchissable : c'est une
transition source.
Exemple 7: transition source

Le franchissement d'une transition source consiste à rajouter un jeton à

chacune de ces places de sortie.
Une transition sans place de sortie est une transition puits.

Exemple 8: transition puits

Le franchissement d'une transition puits consiste à retirer un jeton de

chacune de ses places d'entrée. 27
 5- Séquence de franchissement
Une séquence de franchissement S est une suite de transitions Ti Tj…Tk qui
peuvent être franchies successivement à partir d'un marquage donné. Une seule
transition peut être franchie à la fois.

On note: ou : à partir du marquage Mi , le

franchissement de la séquence S aboutit au marquage Mj.

Exemple 9: séquence de franchissement

T1T2 et T1T3 sont deux séquences de

franchissement:

et 3 avec et

28
6- Marquages accessibles
L'ensemble des marquages accessibles est l'ensemble des marquages Mi qui
peuvent être atteint par le franchissement d'une séquence S à partir du
marquage initial M0.
On le note *M0.

Exemple 10 : ensemble des marquages accessibles

avec ; ;

et

29
7- Graphe de marquages
On utilise le graphe de marquages quand le nombre de marquages accessibles
est fini.

Exemple 11 : graphe de marquages

Le graphe de marquage correspondant:

8- RdP autonome et non autonome

Un RdP autonome décrit le fonctionnement d'un système dont les instants de

franchissement ne sont pas connus ou indiqués.
Exemple 13 : RdP autonome

Le moment de passage de l'été à l'automne est inconnu.

Un RdP non autonome décrit le fonctionnement d'un système dont

l'évolution est conditionnée par des événements externes ou par le
temps. Un RdP non autonome est synchronisé et/ou temporisé.
1- Graphe d'état
Un réseau de Pétri non marqué est un graphe d'état si et seulement si toute
transition a exactement une seule place d'entrée et une seule place de sortie.

Exemple 14 : graphe d'état

Chacune des transitions T1, T2, T3, T4 et T5 possède une seule place
d'entrée et une seule place de sortie.
2- Graphe d'événement
Un RdP est un graphe d'événement si et seulement si chaque place possède
exactement une seule transition d'entrée et une seule transition de sortie.

Exemple 15 : graphe d'événement

3- RdP sans conflit
 Un Rdp sans conflit est un réseau dans lequel chaque place a au plus une
transition de sortie.
 Un RdP avec conflit est un réseau qui possède donc une place avec au
moins deux transitions de sorties.
 Un conflit est noté: [Pi , {T1,T2,…,Tn}] ; avec T1,T2,…,Tn étant les transitions de
sorties de la place Pi .

Exemple 16 :

[P1 , {T1,T2}]
4- RdP à choix libre
Un RdP est à choix libre est un réseau dans lequel pour tout conflit [Pi ,
{T1,T2,…,Tn}] aucune des transitions T1,T2,…,Tn ne possède aucune autre
place d’entrée que Pi .

Exemple 17 :
5- RdP simple

Un Réseau de Pétri simple est un RdP dans lequel chaque transition ne peut
être concernée que par un conflit au plus.

Exemple 18 :
 6- RdP pur
Un RdP pur est un réseau dans lequel il n’existe pas de transition ayant une
place d’entrée qui soit à la fois place de sortie de cette transition.

Exemple 19 :

Ces différentes propriétés de RdP sont selon un point de vue

structurel, indépendamment des marquages.
7- RdP généralisés
 Un RdP généralisé est un RdP dans lequel des poids (nombres entiers
strictement positifs) sont associés aux arcs.
 Si un arc ( Pi,Tj ) a un poids k : la transition Tj n'est franchie que si la
place Pi possède au moins k jetons. Le franchissement consiste à retirer
k jetons de la place Pi.
 Si un arc ( Tj,Pi ) a un poids k : le franchissement de la transition rajoute
k jetons à la place Pi. Lorsque le poids n’est pas signalé, il est égal à un
par défaut.

Exemple 20 :RdP généralisé

Avant franchissement : Après franchissement :

 8- RdP à capacités
Un RdP à capacités est un RdP dans lequel des capacités (nombres entiers
strictement positifs) sont associées aux places. Le franchissement d’une
transition d’entrée d’une place Pi dont la capacité est cap(Pi) n’est possible que
si le franchissement ne conduit pas à un nombre de jetons dans Pi qui est plus
grand que Cap(Pi).

Exemple 21 :

Le franchissement de T1 conduit à 3 jetons dans P2 d'où T1 ne peut plus être franchie.

9- RdP à priorités
Dans un tel réseau si on atteint un marquage tel que plusieurs transitions
sont franchissables, on doit franchir la transition qui a la plus grande
priorité.

Exemple 22 : RdP à priorité

Avant franchissement : Après franchissement :

 a- Matrice Post-incidence
n le nombre de places , m le nombre de transitions
Chaque élément de cette matrice Post (Pi, Tj) correspond
au nombre de jetons à rajouter dans Pi en franchissant Tj.
b- Matrice Pré -incidence
Chaque élément de cette matrice Pré (Pi, Tj) correspond au nombre
de jetons à enlever dans Pi en franchissant Tj.
c- Matrice d'incidence
Chaque élément de cette matrice C(Pi, Tj) correspond au nombre de
jetons à rajouter moins celui à enlever dans Pi en franchissant Tj.

-1 1

1 -1
Pré (Pi, Tj) = Post (Pi, Tj)= C=Post-Pré =
1 -1
1 -1

1 -1
les propriétés dépendantes, c'est à dire les propriétés qui sont dépendantes du
marquage initial Mo.
conflit effectif
Un conflit effectif pour un marquage Mo sur une place Pi est un conflit structurel
tel que le nombre de jetons dans Pi est inférieur strictement au nombre de
transitions franchissables en aval de Pi.
On note ce conflit effectif: <Pi, {Tj, Tk...}, Mo>.
Place bornée
Soit un réseau R et un marquage Mo. Une place Pj du réseau marqué (R,Mo) est
k-bornée si pour tout marquage Mi accessible depuis Mo , Mi (Pj) <= k.

RdP borné
Un RdP marqué est borné si toutes ses places sont bornées.
Dans le cas contraire la place Pj est dite non bornée. Il s’en suit que le RdP est
qualifié de non borné.
Exemple : Soit une machine dont l'état est soit en marche soit en arrêt (son état
initial). Proposez un RdP qui compte le nombre de passage de cet état dans la
valeur marche. Est-il borné ?
Réponse : La place P3 n'est pas bornée.
Exemple :
Le premier réseau est 3-borné puisque toutes ses places sont 3-bornées. De plus, la
séquence t1t1t2t1 est répétitive et nous ramène toujours sur le marquage initial.

Le second réseau n’est pas borné puisque la place P2 ne l’est pas. Par contre sa
place P1 est 1-bornée.

 Il est facile de réaliser que la construction du graphes des marquages accessibles

permet de vérifier cette propriété de chacun des réseaux.
RdP sauf (ou binaire)
un RdP est sauf (ou binaire) pour un marquage initial Mo, si pour marquage
accessible, chaque place contient au plus un jeton.
Propriété : Un réseau sauf est borné.
Démonstration
Evidente : si un réseau est sauf, alors M(Pi) ∈{0,1}, donc αi =1 est une borne
supérieure pour tout Pi, donc k =1 est une borne pour le RdP.

Transition vivante
Une transition Tj est vivante pour un marquage initial Mo, si pour tout marquage
accessible, il existe une séquence de franchissement qui contienne Tj à partir de
ce marquage accessible.

Cela signifie que quelle que soit l'évolution, il subsistera toujours une
possibilité de franchir Tj.
 Transition quasi-vivante
Une transition Tj est quasi-vivante pour un marquage initial Mo si il
existe une séquence de franchissement qui contienne Tj à partir de Mo :

Exemple : Dans le réseau suivant, indiquer la vivacité de T1 et T2.

Réponse :
La transition T1 est quasi-vivante, non vivante et
T2 est vivante, et donc quasi-vivante.

Dès que le jeton arrive en P2, il lui est

impossible de remonter en P1.

RdP vivant
un RdP est vivant pour un marquage initial Mo si toutes ses
transitions sont vivantes pour Mo.

RdP quasi-vivant
un RdP est quasi-vivant pour un marquage initial Mo si toutes ses
transitions sont quasi-vivantes pour Mo.

Propriété : un RdP vivant est quasi-vivant.

 Blocage (ou état puits)
Un blocage (ou état puits) est un marquage M où aucune transition est
franchissable.

RdP sans blocage

un RdP est sans blocage pour un marquage initial Mo si
aucun marquage accessible Mi ∈*Mo n'est un blocage.

Le franchissement de T1 suivi de celui de T3 conduit

à une situation de blocage. Cet RdP est donc avec
blocage.

Etat d'accueil
un RdP dispose d'un état d'accueil Ma pour un marquage initial Mo si :

L'ensemble des états d'accueil est appelé espace d'accueil Ea.

RdP réinitialisable (propre)

Un RdP est réinitialisable pour un marquage initial Mo si Mo est un état
d'accueil.
 Exemple : Identifier les propriétés structurelles et dépendantes des deux RdP
suivants

RdP #1 RdP #2
48
1- Exemples

et :
- Serveurs informatiques
-Télécommunications
(téléphonie, call-centers)
- Trafic aérien
- …..

St Pancras Station, Londres, dec. 2010. 49

2- Objectif : dimensionnement, organisation
par l’estimation de mesures de performance comme :
 temps moyen d’attente
 nombre moyen de clients dans la file
 nombre de serveurs occupés
 probabilité que la file soit vide / pleine
 ...
3- Caractéristiques d’un système d’attente

50
Une file d'attente est caractérisée par :
µ
• Un flot d'arrivées λ
• Un mécanisme de service "Salle" d'attente
• Une salle d'attente
• Une discipline de service mécanisme de
service
– Flot d'arrivée
• suite stochastique
• Tn: est le temps du neme client
• sn: la charge apportée par le neme client, service nécessaire.
• Les clients arrivent successivement, un à la fois, il n'y a pas
d'accumulation: 0<T1<T2<T3<......<Tn<Tn+1<...
– Mécanisme de service
• nombre de serveurs et leur vitesse, σn unités de temps par
service.
51
– Capacité de la file d'attente:
• nombre de places possibles : limité ou illimité.
• Si capacité limitée: les clients supplémentaires sont perdus ou rejoignent une
autre file d'attente.
• Le nombre de clients dans le système est différent du nombre de clients dans
la file d'attente
– Discipline de service: règle d'ordonnancement des clients au service.
• FIFO: first in first out (exemple file d’attente à la cantine, 1er arrivé 1er servie)
• LIFO : Last in first out (ex : l’ascenseur : dernier rentré, premier sortie)
• PS : processor sharing, un serveur donne à chaque client en attente une
'tranche' de service.
• ALEA un serveur libre choisit un client au hasard dans la file
• Priorité: on ajoute une suite {Un}, n appartient à N+, au flot des arrivées où
Un est une variable aléatoire prenant ses valeurs dans l'ensemble des classes
de priorités P. Un=i, signifie que le neme client, arrivant au temps Tn est de la
classe i.
• Priorité préemptive: le programme préemptif passe en premier devant tous
les autres et est servi en premier (ex: système préemptif peut en permanence
décider d'interrompre un processus, principalement si celui-ci échoue et
provoque l'instabilité du système.)
52
 Loi de Poisson

Cette loi est souvent utilisée dans la modélisation des files d'attente : nombre de
clients en attente a une caisse de supermarché, nombre de conducteurs passes a
un péage pendant une période de temps. . .
Exemple
A un guichet d'une banque, on sait que le nombre moyen de clients par heure est de 12. On
suppose que le nombre de clients par heure est distribue selon une loi de Poisson.
Quelle est la probabilité pour qu'en une heure, le guichetier s'occupe de plus de 15 clients ?

k!

53
Les notations de Kendall (1953)
File (système) d’attente décrite par :
A/B/m/N/S
où :
 A est la distribution des arrivées : stochastique ou déterministe ;
{M = markovien ; D=déterministe (temps d’inter-arrivées ou de
service constant) ; G=générale (quelconque)}
 B est la distribution des temps de service : idem ;
 m est le nombre de serveurs ;
 N est le nombre maximum de clients dans le système ;
 S est la discipline de service (FIFO, LIFO, RAND. . .)
Exemple:
M/M/1  Modèle le plus classique
M/M/5/20
M/M/5/infini/LIFO

54
 Exemple: Application aux réseaux de communications et aux systèmes
informatiques:
• clients = tâches, programmes, paquets, …
• temps de service = durée de tâche
• serveur = processeur
• salle d'attente = tampon

4- Loi de little
• HYPOTHESES
 Lorsqu'un client, ayant terminé son service, quitte le système, il laisse,
en moyenne, derrière lui, un nombre de clients égal à E(k).
Ce client a trouvé en arrivant E(k) clients déjà présents et a passé dans
le système un temps, E(T).
 Nous supposons que:
• Le nombre moyen des arrivées est égal au nombre moyen des
départs du système.
• La longueur moyenne de la file lors des arrivées est égale à la
longueur moyenne de la file lors des départs
55
 la loi de Little dit
que le nombre moyen de clients dans un système stable est égal à leur
fréquence moyenne d'arrivée multipliée par leur temps moyen passé
dans le système :
Ls = nombre espéré de clients dans le système (à un instant quelconque dans le long terme)
Lq = nombre espéré de clients dans la file d'attente (à un instant quelconque dans le long terme)
Ws = temps espéré passé par chaque client dans le système (dans le long terme)
Wq = temps espéré passé par chaque client dans la file d'attente (dans le long terme).

La loi de Little est valide sous des hypothèses très générales et sous une
interprétation très large du mot « système ». En particulier, elle reste valide lorsque
la file d'attente elle-même est interprétée comme un système:

56
• VALIDITE
 Régime permanent
 Les formules de Little sont valides pour les files
G/G/S. Elles ont un caractère très général. En
effet, il n' y a aucune restriction quant à :
la loi d'arrivée, la loi des services, le nombre de
serveurs.
 Elles peuvent prendre en compte le cas où il
existe plusieurs classes de clients mais la
discipline de service doit être définie, nous avons
considéré la discipline FIFO.

57
Exemple
Le gestionnaire d'un petit atelier enregistre en moyenne 5 commandes par
jour. Les 6 ouvriers employés dans l’atelier sont très polyvalents, si bien que
chaque commande peut être réalisée par n’importe lequel d’entre eux.
Néanmoins, le gestionnaire est inquiet car il constate que les ouvriers sont
occupés en permanence et que son carnet de commandes contient, en
moyenne, une vingtaine de commandes en cours (enregistrées, mais non
satisfaites).
Pour mieux comprendre la situation, le gestionnaire aimerait estimer le temps
moyen consacré par les ouvriers à chaque commande. Il voudrait également
pouvoir annoncer à ses clients, au moment de la passation de commande, un
délai de livraison attendu.

58
On a: leff = 1000 et Lq = 8. Donc, par la loi de Little, Wq=8/1000 sec

On a: Ws-Wq=(Ls-Lq)/ leff =(13-8)/1000= 5/

1000 sec (serveur est occupé
à 100%) 59
5- File M/M/1
M/M/1 = statistique du processus d’arrivée : markovien / statistique des
lois de service : markovien / 1 serveur

Les formules à retenir :

État : nombre de clients, k, dans le système

: probabilité d’avoir 0 clients dans la file d’attente

Taux de trafic, p (charge, activité du serveur) :

: taux de traffic
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
60
 Condition de stabilité :
 activité du serveur <1


 Débit d’entrée < débit du serveur
 Temps moyen inter-arrivée > temps de service moyen

 Si serveur saturé ( —>1) :

 La distribution des intervalles de temps séparant deux départ
consécutifs de la file saturée tend vers la distribution des temps de
service

61
 Nombre moyen de clients dans le système, Ls

: taux de traffic
Ls: Nombre de client dans le système
Nombre moyen de clients dans la file, Lq

: Taux de traffic
Lq: Nombre moyen de client dans la file
Temps moyen, Ws, passé par un client dans le système

: taux de traffic
Ws: temps passé par un client dans le système
62
: taux moyen de traitement, débit du serveur, taux de service
Temps moyen, Wq, passé par un client dans la file d'attente

donc

63
6- File M/M/S
M/M/S = statistique du processus d’arrivée : markovien / statistique des
lois de service : markovien / S serveurs

Les formules à retenir :

Taux de trafic, p (charge, activité du serveur) :
µ

(Condition de stabilité) λ

µ
: taux de traffic
S serveurs
: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
S : Nombre de serveurs

64
 Nombre moyen de guichets, g, occupés :

: Nombre de guichets occupés

: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
• g= /
– résultat très simple, principe de conservation:
• flux d'arrivées des clients est l, personne ne disparaît dans le
système, le flux de sortie doit être l, hors saturation.
• Ce nombre est égal au nombre moyen de guichets actifs g par le
taux individuel de chacun .
µ
λ
  g

µ
65
{g guichets occupés}
Nombre moyen de clients, (Lq) , dans la file :
* Il existe un file d'attente si k>S
k>s, k : nombre de clients, s nombre de serveurs

Lq

Lq : nombre moyen de clients dans la file

: taux moyen d’arrivée des clients
: taux moyen de traitement, débit du serveur, taux de service du serveur
: probabilité qu’il y ait 0 client dans le système
M : nombre de serveurs

66
67
Un peu d'humour sur la théorie des files d'attentes

68
3-1 Introduction
La simulation discrète représente, dans plusieurs situations, une
expérimentation statistique contrôlée. Les modèles de simulation incluent
généralement des éléments stochastiques de nature. Par exemple, des
expériences sont conduites par des séquences d’entrée aléatoires, comme
le temps des arrivées à un système, et produisent des séquences de sortie
aléatoires, comme le temps de service.

3-2 Les générateurs de nombres aléatoires

Un générateur de nombres aléatoires est ‘’un algorithme qui génère une
séquence de nombres présentant certaines propriétés du hasard. Cependant,
les sorties d'un tel générateur ne sont pas entièrement aléatoires.’’
(Selon l’encyclopédie libre WIKIPEDIA [www.fr.wikipedia.org])

Elles s'approchent seulement des propriétés idéales des sources

complètement aléatoires.

69
La raison pour laquelle on se contente d’un rendu pseudo-aléatoire est :
 il est difficile d’obtenir de « vrais » nombres aléatoires et que, dans
certaines situations, il est possible d’utiliser des nombres pseudo-
aléatoires, en lieu et place de vrais nombres aléatoires ;
 ce sont des générateurs particulièrement adaptés à une implémentation
informatique, donc plus facilement et plus efficacement utilisables.

Générer des nombres aléatoires sur ordinateur revient à créer une suite d'entiers:
Sn+1 = f(Sn)

Où f est une fonction qui doit être choisie judicieusement pour que la
répartition des nombres Sn ne puisse pas être distinguée de ce que
donnerait le hasard. On parle alors de nombres pseudo aléatoires.

70
 La suite peut fournir M nombres aléatoires dans l'intervalle [0, M-1].
M dépend du type des entiers :
entiers 16 bits : M = 216 = 65 536
entiers 32 bits : M = 232 = 4 294 967 296 (soit plus de 4 milliards de
nombres aléatoires)

 La valeur de départ S0, appelée graine (seed), doit être fournie par
l'utilisateur.

 La même graine donnera toujours la même suite de nombres.

 la suite se reproduit au bout d'un nombre de valeurs appelé période.

Cette période doit être la plus grande possible.
 Si la fonction f a été correctement choisie, chaque nombre a la même
probabilité d'apparaître. On dit que les nombres aléatoires suivent
une loi uniforme (ils sont équirépartis sur [0,1]) .

71
 Nous décrivons ici une des méthodes permettant de générer des
nombres aléatoires qui est celles des générateurs congruentiels,
c'est à dire définis par le choix de la valeur entière initiale S0 (le
"random seed") et par la récurrence on aura :

Sj+1 = modp (Sj x a + b, p) c'est-à-dire Sj+1 = Le reste de [(Sj x a + b)/

p)
 On peut en effet calculer aisément la période d'un tel générateur.

 Examinons les cas réellement utiles : p = 2m et p premier. L'intérêt

du premier cas est évident car l'arithmétique modulaire se
simplifie considérablement lorsque 2m est égal à la taille du "mot
machine" ou est une puissance de celui-ci.

72
 Prenant comme exemple (simpliste) p=2m= 8 et a= 5, b= 1 on obtient :

 Prenant comme exemple (simpliste) p = 7 a= 5, b= 0 on obtient :

 Si pour un intérêt plus particulier avec plus détail sur les générateurs
de nombres aléatoires, nous suggérons le site web
[www.random.org].
73
3-3 Quelques générateurs pseudo-aléatoires
La méthode de Von Neumann
En 1946, John von Neumann propose un générateur pseudo-aléatoire
connu sous le nom de la méthode middle-square (carré médian). Très
simple, elle consiste à prendre un nombre, à l’élever au carré et à prendre
les chiffres au milieu comme sortie. Celle-ci est utilisée comme graine pour
l’itération suivante.
Exemple: prenons le nombre 1111. Les étapes de l’algorithme sont:
1. 11112= 1234321
2. on récupère les chiffres du milieu: 3432. C’est la sortie du générateur.
3. 34322= 11778624
4. on récupère les chiffres du milieu: 7786, et ainsi de suite.

La méthode a surtout une importance historique. Elle est faible et la qualité

des sorties dépend de la graine. Par exemple l’état 0000 produit toujours la
même séquence et constitue un état absorbant de l’algorithme.
74
Générateur congruentiel linéaire

 Le générateur congruentiel linéaire (en anglais linear congruential

generator (LCG)) a été proposée en 1951 par Lehmer pour générer des
nombres pseudo-aléatoires selon une distribution uniforme U(0, 1).
 Un générateur LCG génère une séquence zi de nombres entiers non
négatifs grâce à la formule de récurrence (aussi connue comme
l’algorithme de Lehmer)

où a, c, sont des entiers, m est un nombre premier très grand

et mod dénote le reste de la division entière (par exemple 15 mod 4 = 3).

75
 La valeur initiale z0 est appelée la graine (ou seed) de la séquence.
 suite ui = zi /m ∈[0, 1] est la suite de nombres pseudo-aléatoires qui sont
renvoyé par le générateur LCG.
 Si c = 0 le générateur est appelé générateur multiplicatif.
 La séquence de nombres entiers zi prenne valeur entre 0 et m - 1; il s’ensuit
que si nous exécutons l’itération pour m étapes, au moins deux valeurs zi (et
donc deux valeurs ui ) seront identiques.
 La séquence est donc périodique pour N > m avec une période m0 ≤ m. Si la
période est m0=m alors on dit que le générateur est à période maximale.
 Une séquence périodique ne peut évidemment pas être une séquence
aléatoire. Toutefois, pour des applications où le nombre de ui, la périodicité
n’a aucun effet.
 Il est possible montrer que seulement quelque ensemble de paramètres
permet la génération d’une séquence avec des bonnes propriétés statistiques.
 Des choix communs pour les paramètre du LCG sont: a = 75 (=16807), c = 0 et
m = 231 -1 (=2147483647)  Générateur LGM (Lewis, Goodman, Miller, 1969)

76
 on présente quelques pseudo-aléatoires générateurs
congruentiels utilisés sur des gammes d’ordinateurs ou
par des logiciels connus.

 Le générateur congruentiel linéaire (linear congruentiel

generator) est initialement proposé par Lehmer.
Le pseudo générateur est de la forme :

Yn+1 = (ayn + b) mod m et un seed y0 et on l’exprime par

LCG(m,a,b, y0)

77
 ANSIC : est le générateur utilisé par le ANSIC rand()
fonction, version BSD .et proposé par [Park et al. 1988]
LCG(231,1103515245,12345,12345)
 MINSTD: Ce générateur a été suggéré par [Lewis et al. 1969]
LCG(231- 1, 16807, 0, 1)
 SIMSCRIPT: Ce générateur [Fishman et al 1982], [Fishman et
al 1986, Fishman 1996]] est implémenté dans le langage de
simulation SIMSCRIPT II.
LCG(231 - 1, 630360016, 0, 1)
 BCSLIB: Ce générateur provient de [Knuth 67] et il a été
utilisé par BCSLIB (Boeing Computer Services).
LCG(235 , 515 , 7261067085,0)
 APPLE : Ce générateur est implémenté sur les machines
Apple en se basant sur les travaux de [Jennergren 1983].
LCG(235 , 513 = 1220703125, 0,1)
78