UDEM
Département d'informatique et de recherche opérationnelle (IRO)
Hiver 2011

Objectif général

Ce cours vise à étudier les algorithmes et outils mathématiques servant à analyser ou à optimiser des processus de décision séquentiels, pour lesquels il y a interaction entre les décisions, dans un environnement certain ou incertain. On verra comment implanter les algorithmes de calcul et on étudiera leur performance. Dans plusieurs cas on pourra démontrer certaines propriétés caractérisant la forme d'une politique optimale. On examinera aussi des exemples d'applications tirées de différents domaines, incluant la gestion et la finance.

Contenu

  1. Introduction.
    Processus de décision séquentiels. Modèles déterministes et stochastiques. Définition de l'état. équations de récurrence. Horizons finis et infinis, avec et sans actualisation. La malédiction des grandes dimensions. Exemples.
  2. Modèles déterministes en temps discret.
    Prototype: recherche du plus court chemin dans un réseau. Modèle déterministe sur horizon fini. équations de récurrence. Différents algorithmes et comparaisons. Commande optimale en temps continu: aperçu.
  3. Modèles stochastiques sur horizon fini et en temps discret.
    Processus de décision Markoviens sur horizon fini. équations de récurrence et résolution. Modèles à état partiellement observé. Approximations et stratégies sous-optimales. Examples divers.
  4. Horizon infini avec actualisation.
    Modèles en temps discret et en temps continu (renouvellement Markovien). Algorithmes de calcul: itération des valeurs, itérations des politiques, méthodes hybrides, programmation linéaire. Applications contractantes. Conditions de convergence et vitesses de convergence.
  5. Horizon infini avec coût moyen.
    Modèles et hypothèses. Stabilité. Conditions d'optimalité. Algorithmes de calcul.
  6. Autres aspects.
    Méthodes d'aggrégation adaptatives. Algorithmes parallèles. Discrétisations et approximations pour les espaces d'états ou les espaces de décisions continus. Méthodes utilisant la simulation. Jeux dynamiques. Etc. (selon le temps disponible)

Référence de base

Autres références

Evaluation

Examen partiel: 20%, 16 mars 2009 Travail final: 30% Devoirs (4): 50%

Plagiat

Vous êtes priés de lire bien attentivement le règlement sur le plagiat. Il sera appliqué rigoureusement dans ce cours. En particulier, les solutions copiées (ou presque) sur le voisin, ou sur des solutionnaires trouvés sur internet ou ailleurs, ou tirés de livres ou articles sans donner la référence, constituent du plagiat.


Valid XHTML 1.0 Strict