Objectifs (en termes de savoir-faire) :
L’étudiant.e sera initié.e à la recherche opérationnelle à travers deux classes de problèmes majeures : la théorie des graphes et la programmation linéaire. Il/Elle apprendra les concepts de base, les formulations mathématiques de certains problèmes majeurs, ainsi que les méthodes de résolution couramment utilisées.
Programme succinct :
Le cours comporte une introduction générale et trois classes de problèmes, méthodes et outils de RO : théorie des graphes, programmation linéaire et optimisation combinatoire. En introduction, l'accent est mis sur le caractère appliqué de la RO même si elle est à la frontière des maths et de l'informatique. Pour illustrer la richesse et la variété de ses domaines d'application, le cours s'appuie sur trois exemples d'applications ayant fait l'objet de contrats industriels ou projets ANR : design de réseaux cellulaires, docking moléculaire et ordonnancement de type Flow-Shop. L'introduction comporte également quelques notions de complexité nécessaires pour comprendre la complexité des algorithmes présentés dans la suite du cours.
Dans les trois parties suivantes du cours, la démarche consiste à présenter la/les formulation(s) du problème, une ou plusieurs approche(s) de résolution et un exemple illustratif. En complément du cours déjà bien illustré avec des exemples pratiques, des séries d'exercices corrigées permettent à l'étudiant(e) d'assimiler une démarche méthodologique lui permettant d'appréhender, modéliser et résoudre des problèmes dans différents domaines d'application. En complément des exercices corrigés, d’autres exercices non corrigés en classe sont proposés pour ceux/celles désirant aller plus loin.
Plan du cours
- Introduction générale à la Recherche Opérationnelle
- Définition et historique de la RO
- Domaines et exemples d'applications de la RO
- La RO en recherche et en industrie
- Eléments de complexité
- Graphes et leurs applications
- Eléments de la théorie des graphes
- Recherche des plus courts chemins dans un graphe
- Gestion de projets et ordonnancement de tâches
- Flots dans les réseaux
- Programmation linéaire
- Modélisation de problèmes en programmes linéaires
- Résolution graphique de programmes linéaires
- Résolution par la méthode du Simplexe
Compétences acquises (directes/indirectes) :
A l’issue de ce module, l'étudiant.e doit acquérir les compétences nécessaires pour utiliser les outils de la recherche opérationnelle pour modéliser certaines classes de problèmes souvent rencontrés en industrie (recherche de plus courts chemins, flots dans les réseaux, ordonnancement, etc.) pour ensuite les résoudre par des approches issues notamment de la théorie des graphes, de la programmation linéaire et de l’optimisation combinatoire.- Docente: Nouredine Melab