Recherche Opérationnelle (théorie)
Objectifs
La recherche opérationnelle s'intéresse à l'application de méthodes analytiques à différents problèmes d'optimisation.
Pour cela, des techniques telles que la modélisation mathématique et l'optimisation sont utilisées pour déterminer le profit maximal ou le coût minimal pour un objectif du monde réel.
Plan du cours
Dans ce cours, nous discutons de plusieurs problèmes d'optimisation comme la recherche
- des chemins les plus courts
- des arbres couvrants minimaux
- des couplages maximales
- des ensembles stables maximaux
- des colorations minimales
- des circuits les plus courts à travers tous les arêtes ou nœuds d'un graphe
Pour tous les problèmes, nous discutons du contexte théorique, de certains algorithmes combinatoires et de la qualité des algorithmes présentés (en particulier dans quelles conditions ils produisent des solutions optimales).
Pour trouver les circuits les plus courts à travers tous les nœuds d'un graphe, un algorithme d'approximation est basé sur des arbres couvrants, des correspondances et des circuits à travers tous les arêtes comme sous-problèmes.
Description des TP
voir cours "RO - pratique"
Connaissances requises
Comment modéliser certains problèmes d'optimisation classiques dans des graphes et comment les résoudre par des algorithmes combinatoires