CHPS0805 - Optimisation et recherche opérationnelle

Retour au parcours Retour à la liste des EC
  • Équipe pédagogique

    • Responsables

    • DELISLE Pierre (Responsable)
      Département : Informatique (UFR SEN)
  • Volume horaire

  • Nature CMTDTP Total
    Durée 20h10h10h40h
  • Modalités de contrôle des connaissances (MCC)

  • Epreuves Nature ProjetDSTEOT Total
    Durée 2h0h30
    Cas général 1ère session 4060 100%
    2nd session 4060 100%
    Dispense contrôle continu 1ère session 4060 100%
    2nd session 4060 100%
  • Modalités de contrôle des connaissances (MCC)

  • Cas général

  • Nature Durée 1ère session 2ème session
    Projet 40% 40%
    DST 2h 60% 0%
    EOT 0h30 0% 60%
  • Dispense contrôle continu

  • Nature Durée 1ère session 2ème session
    Projet 40% 40%
    DST 2h 60% 0%
    EOT 0h30 0% 60%
  • Objectifs

    • Acquérir les connaissances de base permettant d’appréhender la résolution d’un problème d’optimisation
    • Se familiariser avec les différentes méthodes d’optimisation et leurs implémentations logicielles
    • Développer une application permettant de résoudre un problème d’optimisation donné
  • Compétences spécifiques visées

    • Programmation linéaire
    • Programmation dynamique
    • Résolution exacte ou approchée de problèmes d’optimisation
    • Implémentation logicielle de méthodes d’optimisation, utilisation d’outils libres et commerciaux
  • Compétences générales visées

    • Domaines d’application de l’optimisation et de la recherche opérationnelle
    • Modélisation de problèmes d’optimisation dans un paradigme donné
    • Méthodes d’optimisation exactes, heuristiques et méta-heuristiques
  • Connaissances requises

  • Algorithmique et structures de données élémentaires (tas, piles, files, listes, arbres, graphes). Programmation C/C++.

  • Programme

    • Programmation linéaire : méthode du simplexe, dualité
    • Programmation dynamique : modélisation sous forme de problèmes de plus courts chemins
    • Problèmes d’optimisation : voyageur de commerce, sac à dos, ordonnancement, flot
    • Programmation linéaire en nombres entiers : méthodes branch and bound
    • Notion de voisinage, méthodes de recherche locale, heuristiques
    • Méta-heuristiques : algorithmes génétiques, optimisation par colonie de fourmis, recherche taboue