Recherche opérationnelle
Cours de base (30 h de cours, 30h de TD)
Cours : Paul Feautrier (Paul.Feautrier)
TD : ? (?)
Présentation
La recherche opérationnelle est cette partie de la Mathématique Appliquée
qui cherche à représenter une situation réelle par un modèle mathématique,
puis à identifier les meilleures décisions dans le modèle en espérant
qu'elles seront aussi les meilleures dans la réalité. La situation
est modélisée par des contraintes, dont le but est de séparer le possible
de l'impossible. Usuellement, les décisions sont évaluées à l'aide de
fonctions objectifs ou économiques. On se ramène donc à trouver le minimum
(ou le maximum) d'une fonction objectif parmi les solutions qui respectent
les contraintes. Il existe de nombreuses méthodes qui dépendent fortement
de la fonction objectif, de la nature des contraintes et du type des
variables de décision. On présentera les plus utiles d'enntre ces méthodes.
Plan
-
Présentation, modélisation, classification des problèms.
- Algorithmes simples
-
Optimisation à une dimension sans contraintes.
- Ordonnancement.
- Problèmes de flots.
- Programmation dynamique.
- Programamtion linéaire.
- Optimisation Combinatoire
-
Définitions, exemples.
- Programmation linéaire en nombres entiers.
- La méthode banch and bound.
- Heuristiques et méta-heuristiques
-
Recuit Simulé.
- Tabou.
- Algorithmes <<génétiques>>
- Utilisation des méthodes de la RO en Informatique.
Bibliographie
-
Michel Minoux, Programamtion mathématique tomes I et II. Dunod, 1983.
- Alexander Schrijver, Theory of Linear and Integer Programming,
Wiley, 1986.
- J. Carlier, Ph. Chretienne, Problèmes d'ordonnancement. Masson, 1988.