LoginAccueil


Recherche avancée
Libres Savoirs >> Informatique >> Cursus Paris
Responsable :

Olivier HUDRY
  

Equipe Pédagogique :
Irène CHARON
Olivier HUDRY

Niveau : Graduate

Langue du cours : Français

Nombre d'heures : 20

Crédits ECTS : 3
INF392 Recherche opérationnelle et aide à la décision (TPT06)
Ressources Pédagogiques :
Interdit aux étudiants de Télécom ParisTech ayant suivi ou devant suivre l’U.E. INF226 ou

l’U.E. INFMDI 340.

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.

Interdit aux étudiants de Télécom ParisTech ayant suivi ou devant suivre l’U.E. INFMDI 340 ou l'UE INF226
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.

ATTENTION : il est interdit aux élèves ayant suivi INF226 ou INFMDI340 de s'inscrire à INF392.

Modalités d'évaluation : contrôle écrit.

Dernière mise à jour : Thursday 27 August 2015

© Télécom ParisTech 2017 - Réalisé par Winch Communication