Descriptif
La recherche opérationnelle est un ensemble de techniques permettant de formaliser et de résoudre les problèmes d'organisation et de décision qui se posent dans le monde de l'entreprise. On peut citer les problèmes de transport, de localisation d’entrepôt, de tournées de véhicule, d'emploi du temps, de gestion de stock ou de réserve énergétique (hydraulique, gaz, combustible nucléaire), mais aussi des applications particulières, telles que la conception de circuits ou de câblages, l'allocation de fréquence, etc..., qui conduisent à étudier des problèmes d'optimisation fondamentaux, souvent de nature combinatoire.
Le cours présente quelques grandes familles de méthodes mathématiques utiles en recherche opérationnelle, afin de donner la capacité de modélisation, et de permettre de reconnaître les problèmes pour lesquels des algorithmes rapides de résolution existent. On met l'accent sur les techniques issues de la programmation linéaire ou convexe, qui sont souvent à l'origine de tels algorithmes.
Il n'y a pas de pré-requis, hormis une familiarité avec les mathématiques appliquées, qui a pu être acquise en suivant l'un des cours de ce domaine en seconde année. Signalons que la recherche opérationnelle est aussi abordée en programme d'approfondissement d'informatique de second semestre, dans les cours traitant d'analyse d'algorithmes et de programmation par contraintes, qui apportent un éclairage complémentaire sur la discipline. Le présent cours peut être suivi de manière indépendante, ou bien en association avec ceux-ci.
Principaux concepts développés dans le cours :
- Modélisation de problèmes combinatoires, points entiers de polyèdres, matrices totalement unimodulaires.
- Problèmes de flots. Rappels de dualité. Algorithmes.
- Multiflots : communications, transport. Flots potentiels,
- Génération de colonnes et algorithme de Dantzig-Wolfe
- Algorithmes polynômiaux en optimisation convexe. Points intérieurs.
- Le problème du voyageur de commerce. Séparation et évaluation. Principe
des relaxations et coupes.
- Coupes de Chvátal et Gomory
- Relaxation lagrangienne. Optimisation non différentiable : plans sécants.
Décomposition de Benders.
- Coloriage et coupes de graphes : l’approche par programmation semidéfinie.
- Programmation dynamique déterministe et stochastique
Modalités : 9 blocs, 36 heures, 4 ECTS Stéphane Gaubert
Langue du cours : Français
Credits ECTS : 4
Diplôme(s) concerné(s)
- M1 MPRI - Foudations of Computer Science
- Echanges PEI
- M1 Mathématiques et Applications - Voie Jacques Hadamard - École Polytechnique
- MSc X-HEC Entrepreneurs
- M1 Mathematiques Jacques Hadamard
- Titre d’Ingénieur diplômé de l’École polytechnique
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme M1 MPRI - Foudations of Computer Science
Pour les étudiants du diplôme M1 Mathematiques Jacques Hadamard
Pour les étudiants du diplôme MSc X-HEC Entrepreneurs
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Le rattrapage est autorisé (Max entre les deux notes)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme M1 Mathématiques et Applications - Voie Jacques Hadamard - École Polytechnique
Le rattrapage est autorisé (Max entre les deux notes)Pour les étudiants du diplôme Echanges PEI
Le rattrapage est autorisé (Max entre les deux notes)- Crédits ECTS acquis : 5 ECTS