Département d'informatique et de recherche opérationnelle (IRO)
Automne 2010
Objectif général
Ce cours vise à faire connaître les principales techniques utilisant l'ordinateur pour imiter (simuler) le comportement de systèmes réels complexes, dans le but d'en améliorer la conception et la gestion. On mettra l'accent sur les systèmes dynamiques stochastiques à événements discrets (i.e., qui évoluent dans le temps et qui impliquent des éléments d'incertitude).
Parmi les nombreux exemples de tels systèmes, on peut penser à un
réseau de communication, un centre d'appels téléphoniques, un réseau
de transport, etc.
Les principaux aspects abordés seront: la modélisation des systèmes,
la programmation de ces modèles, la génération de valeurs
pseudo-aléatoires, l'analyse des résultats de simulation et plusieurs
techniques pour améliorer l'efficacité des estimateurs.
Pour la programmation, on utilisera des librairies Java.
Horaire
Théorie
-
Lundi, 9h30-10h30, local 1207, pavillon A. Aisenstadt.
-
Vendredi, 12h30-14h30, local 1207, pavillon A. Aisenstadt.
Travaux Pratiques
-
Lundi, 10:30-12:30, local 1207, pavillon A. Aisenstadt.
Evaluation
- Devoirs: 50%
- Intra: 20%
- Final: 30%
Contenu
- Principes de base des modèles de simulation.
Pourquoi simuler. Types de modèles. Simulation versus modèles
analytiques. Exemples de modèles et de programmes. Organisation d'un simulateur à événements discrets. Simulation continue. Notions de variance, bias
et efficacité. Coup d'oeil sur la génération de valeurs aléatoires.
- Simulation en utilisant la librairie SSJ.
Langages généraux versus langages spécialisés et environnements
graphiques pour la simulation (e.g., Arena). Avantages,
inconvénients, comparaisons. Simulation dans un langage tout usage
en utilisant des librairies. Vision par événements et par processus.
Gestion de l'horloge et des listes. Travaux pratiques en utilisant SSJ (en Java).
- Principes et techniques de modélisation. Exemples. Choix
des lois de probabilité. Quelques lois discrètes et continues
usuelles. Processus stochastiques. Processus de Poisson homogènes et
non homogènes. Niveaux de détail. Modularité. Vérification et validation.
- Génération de valeurs pseudo-aléatoires.
Propriétés théoriques recherchées. Différents types de générateurs. Congruences linéaires simples et multiples. Combinaisons de générateurs.
Tests statistiques. Exemples de très mauvais générateurs dans les
logiciels populaires. Génération de valeurs suivant une loi
spécifiée, à partir de valeurs uniformes entre 0 et
1. Inversion. Méthode d'acceptation/rejet.
- Analyse des résultats.
Estimation et intervalles de confiance. Différentes mesures de performance d'un système. Horizons finis et infinis. Comparaisons de deux ou plusieurs
systèmes. Simulation et optimisation (bref aperçu).
- Amélioration de l'effficacité.
Notion d'efficacité. Techniques de réduction de la variance. Valeurs
aléatoires communes. Variables antithétiques. Variables de
contrôle. Stratification. Espérance conditionnelle. Problème des
événements rares et esquisses de solutions. Applications.
Théorie
-
1/10. Introduction (Chapitre 1)
-
5/10. Principes de base de la simulation à événements discrets (Chapitre 3).
-
12/10. Générateurs congruentiels linéaires (Chapitre 4)
Découverte d'ORATIO.
-
15/10. Générateurs aléatoires récursifs multiples.
-
19/10. Générateurs aléatoires: structure de réseau.
Combinaison de générateurs.
-
22/10. Générateurs sur F2.
-
26/10. Validation de générateurs aléatoires.
-
29/10. Génération de variables non-uniformes: inversion de la fonction de répartition.
-
29/10. Génération de variables non-uniformes: inversion de la fonction de répartition.
-
02/11. Génération de variables non-uniformes: méthodes d'acceptation-rejet; cas particuliers.
- 05/11. Intervalles de confiances: introduction.
- 12/11: Révision.
- 19/11. Intervalles de confiances: mise à jour séquentielle.
- 23/11: Introduction au bootstrap.
- 26/11: Méthode Delta.
- 03/12: Intervalle de confiance sur une seule simulation
- 07/12: Intervalle de confiance sur une seule simulation
- 10/12: Introduction aux méthodes de réduction de variance
- 14/12: Variables aléatoires communes
- 17/12: Variables de contrôle
- 20/12: Variables antithétiques
Démonstrations
- 1/10: Rappels
- 15/10: introductin à l'utilisation d'Oratio. Fichiers d'exemple: synthetic.c, exemple_mm1.c.
- 22/10: Simulation à événements discrets avec Oratio. Sources: Randu, queue_event.cpp.
-
29/10: Demo 4. standardminimal_testu01.c
-
05/11: Demo 5.
-
12/11: Demo 6.
-
19/11: Demo 7. queueevent_ci.cpp
-
26/11: Demo 8. queue_event_revisited.cpp, bootstrap_maxunif.c.
-
03/12: Illustration de la méde Delta et du boostrap pour un calcul de rapport d'espérances: fichier ratio.c
-
10/12: Demo 10
- 17/12: Demo 11
Support de cours
Notes de cours
Les notes suivantes serviront de support principal au cours, bien qu'il soit vivement recommandé de consulter les livre de référence.
En outre, il est à noter que le
document est susceptible d'évoluer en cours de trimestre, et que toute suggestion à son égard est bienvenue.
- notes (version du 5 novembre 2012).
Livres de référence de base
-
A. M. Law, Simulation Modeling and Analysis, quatrième édition, McGraw-Hill, USA, 2007.
-
Yosef Sheffi, Urban Transportation Networks, Prentice-Hall, USA, 1985.
Logiciels
Devoirs
Examens
Avis important: les examens sont à court ouverts Toute documentation jugée pertinente est autorisée, mais aucun support électronique n'est autorisé, y compris les calculatrices.
Corrigé de l'examen intra 2009