Ensimag Rubrique Formation 2022

Recherche opérationnelle - 3MM1RO

  • Volumes horaires

    • CM 18.0
    • Projet -
    • TD 18.0
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 3.0

Objectif(s)

Apprendre comment modéliser certains problèmes susceptibles d'être résolus par des méthodes d’Optimisation Combinatoire et de proposer une introduction aux concepts de base de la Recherche Opérationnelle.

Responsable(s)

Moritz MUHLENTHALER, Zoltan SZIGETI

Contenu(s)

1. Graphe - un remarquable outil de modélisation : de nombreux exercices illustrent les notions de base: connexité, stabilité, coloration, couplages, arbres et arborescences, structurations des données.
2. La programmation linéaire : concepts fondamentaux, l'aspect algorithmique (la méthode du simplexe) et l'aspect théorique.
3. Les aspects algébriques et algorithmiques des graphes (co-)cycles, (co-)arbres.
4. Quelques algorithmes sélectionnés comme :

  • arbres de recouvrement de poids optimal ;
  • chemins optimaux et leurs applications dans des ordonnancements de projets.
    5. La notion de complexité des problèmes est introduite. On explique les motivations de l'introduction des algorithmes heuristiques et approximatifs.
    • Ce cours est donné en Période(s) Académique(s) 1 et 2 **

Prérequis

Aucun, mais a priori, élève doit pouvoir suivre le raisonnement formel avec un certain niveau d’abstraction (=bon niveau en maths).

Contrôle des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) : -

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : écrit
Salle spécifique :
Durée : 2 heures
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : notes de cours
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : calculatrices
    Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : oral
Salle spécifique :
Durée : 1/2 heure
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : calculatrices
    Commentaires

  • MCC en présentiel et distantiel
    N1=(E1+E2)/2
    N2=E3

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Alternance - Alternance 1ere annee
cf. l'emploi du temps 2023/2024

Informations complémentaires

Code de l'enseignement : 3MM1RO
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

W. BIENIA : "Introduction à la recherche opérationnelle et optimisation combinatoire", polycopié 2009
V. CHVATAL : "Linear programming", W.H. Freeman Company, 1983
G. FINKE at al “Recherche Opérationnelle et réseaux” traité IGAT, HERMES, 2002