UDEM
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

Travaux Pratiques

Evaluation

Contenu

  1. 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.
  2. 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).
  3. 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.
  4. 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.
  5. 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).
  6. 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. 1/10. Introduction (Chapitre 1)
  2. 5/10. Principes de base de la simulation à événements discrets (Chapitre 3).
  3. 12/10. Générateurs congruentiels linéaires (Chapitre 4) Découverte d'ORATIO.
  4. 15/10. Générateurs aléatoires récursifs multiples.
  5. 19/10. Générateurs aléatoires: structure de réseau.
    Combinaison de générateurs.
  6. 22/10. Générateurs sur F2.
  7. 26/10. Validation de générateurs aléatoires.
  8. 29/10. Génération de variables non-uniformes: inversion de la fonction de répartition.
  9. 29/10. Génération de variables non-uniformes: inversion de la fonction de répartition.
  10. 02/11. Génération de variables non-uniformes: méthodes d'acceptation-rejet; cas particuliers.
  11. 05/11. Intervalles de confiances: introduction.
  12. 12/11: Révision.
  13. 19/11. Intervalles de confiances: mise à jour séquentielle.
  14. 23/11: Introduction au bootstrap.
  15. 26/11: Méthode Delta.
  16. 03/12: Intervalle de confiance sur une seule simulation
  17. 07/12: Intervalle de confiance sur une seule simulation
  18. 10/12: Introduction aux méthodes de réduction de variance
  19. 14/12: Variables aléatoires communes
  20. 17/12: Variables de contrôle
  21. 20/12: Variables antithétiques

Démonstrations

  1. 1/10: Rappels
  2. 15/10: introductin à l'utilisation d'Oratio. Fichiers d'exemple: synthetic.c, exemple_mm1.c.
  3. 22/10: Simulation à événements discrets avec Oratio. Sources: Randu, queue_event.cpp.
  4. 29/10: Demo 4. standardminimal_testu01.c
  5. 05/11: Demo 5.
  6. 12/11: Demo 6.
  7. 19/11: Demo 7. queueevent_ci.cpp
  8. 26/11: Demo 8. queue_event_revisited.cpp, bootstrap_maxunif.c.
  9. 03/12: Illustration de la méde Delta et du boostrap pour un calcul de rapport d'espérances: fichier ratio.c
  10. 10/12: Demo 10
  11. 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.

Livres de référence de base

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