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.
Modalités : 9 blocs, 36 heures, 4 ECTS Stéphane Gaubert
Langue du cours : Français
Diplôme(s) concerné(s)
- Programmes d'échange internationaux
- M1 Mathématiques Jacques Hadamard
- MSc X-HEC Entrepreneurs
- M1 Innovation, Entreprise et Société
- M1 Fondements de l'Informatique MPRI
- Titre d’Ingénieur diplômé de l’École polytechnique
Parcours de rattachement
- PA-Panaché P1
- MSc X-HEC Entrepreneurs - Master
- PA - Innovation Technologique
- M1MPRI - Electifs hors maquette
Objectifs de développement durable
ODD 9 Industrie, Innovation et Infrastructure.Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme M1 Innovation, Entreprise et Société
Pour les étudiants du diplôme Programmes d'échange internationaux
Vos modalités d'acquisition :
- 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 Jacques Hadamard
Pour les étudiants du diplôme MSc X-HEC Entrepreneurs
Pour les étudiants du diplôme M1 Fondements de l'Informatique MPRI
Programme détaillé
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.