v1.17.9 (1402)

Enseignement ATHENS - TPT06 : Recherche opérationnelle et aide à la décision (Télécom ParisTech)

Domaine > Informatique.

Descriptif

Interdit aux étudiants de Télécom ParisTech ayant suivi ou devant suivre l'U.E. MITRO 205

Objectifs Ce cours propose une introduction à la recherche opérationnelle (RO) et à l’'aide à la décision. On y abordera plusieurs aspects classiques en recherche opérationnelle : des problèmes de référence (problème du voyageur de commerce, problème du sac à dos, un problème de vote), divers types de modélisations (programmation linéaire en variables binaires, graphes), des méthodes générales d’'optimisation combinatoire (méthodes arborescentes par séparation et évaluation, programmation dynamique, relaxation lagrangienne, recuit simulé...) permettant de traiter ces problèmes de façon exacte ou approchée. Plus précisément, on partira d'’un problème de vote : comment élire ou classer des candidats à partir des préférences des votants de sorte que cette élection ou ce classement traduisent « le mieux possible » les opinions des votants ? On modélisera mathématiquement ce problème d'’agrégation à l'’aide de graphes ou sous la forme d’un problème de programmation linéaire en variables binaires. On décrira ensuite des méthodes de résolution issues de l’'optimisation combinatoire et applicables à ce problème de vote aussi bien qu’'aux autres problèmes classiques mentionnés plus haut. Certaines de ces méthodes feront l’'objet d’une programmation en C ou en Java pendant des séances de travaux pratiques.
- Modélisations mathématiques de l'agrégation de préférences ou de relations d'équivalence à l'aide de graphes ou sous forme de problèmes de programmation linéaire en 0/1
- Méthodes exactes ou approchées d'optimisation combinatoire appliquées aux problèmes précédents : heuristiques et métaheuristiques, relaxation lagrangienne, méthodes arborescentes par séparation et évaluation
- Des TP de programmation en C permettront d'illustrer certaines des méthodes précédentes aux problèmes décrits plus haut.

nombre d'heure en présentiel

30

effectifs minimal / maximal

5/40

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'ingénieur

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 3 ECTS
  • Crédit d'UE électives acquis : 3

La note obtenue rentre dans le calcul de votre GPA.

Programme détaillé

- Introduction à la recherche opérationnelle et à l’'aide à la décision
- Théorie du vote et paradoxes en théorie du vote
- Modèles mathématiques pour l’'agrégation des préférences (graphes, programmation mathématique en variables binaires)
- Méthodes d'’optimisation combinatoire exactes ou approchées : heuristiques et métaheuristiques (méthode de descente, recuit simulé), programmation linéaire (algorithme du simplexe), relaxation lagrangienne, méthodes arborescentes par séparation et évaluation (branch and bound), programmation dynamique
- Travaux pratiques (trois fois une heure trente) : méthode par séparation et évaluation appliquée au problème du voyageur de commerce (deux fois une heure trente, en C), métaheuristiques (méthode de descente, recuit simulé) appliquées au problème du voyageur de commerce (une heure trente, en Java), le principe étant dans les deux cas d’'enrichir un programme fourni à l’élève de nouvelles fonctionnalités.

Veuillez patienter