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.

Modalités : 9 blocs, 36 heures, 4 ECTS Stéphane Gaubert


Langue du cours : Français

Credits ECTS : 4