Cette UE est destinée à introduire les graphes et la programmation linéaire comme outils de modélisation et de résolution de problèmes d'optimisation ou de décision. Elle a pour objet l'étude de modèles et l'analyse d'algorithmes fondamentaux de l'optimisation combinatoire. Elle constitue une base nécessaire à tout étudiant en informatique souhaitant acquérir une bonne maîtrise des modèles et algorithmes pour la résolution de problèmes d'optimisation, qu'il s'agisse de problèmes réels rencontrés dans un contexte industriel, ou de problèmes de recherche académique. Les étudiants auront aussi l'occasion de mettre en pratique les modèles étudiés en utilisant un solveur de programmes linéaires. Dans la partie concernant les graphes, on s'intéressera à la modélisation et la résolution de problèmes de chemins optimaux, d'arbres couvrants, de flots, d'affectation, de transports, à des méthodes générales de résolution de problèmes d'optimisation telles que la programmation dynamique et le branch and bound. Dans la partie concernant la programmation linaire, on apprend à formaliser des problèmes d'optimisation comme des programmes linéaires, puis à les résoudre par l'algorithme du Simplexe et quelques variantes. On aborde ensuite la dualité en programmation linéaire et l'analyse post-optimale et l'optimisation linéaire en nombre entiers. Les travaux dirigés sont l'occasion de s'exercer à la modélisation de problèmes standard par les graphes et la programmation linéaire pour en permettre une résolution efficace par la machine. Un projet vient compléter la formation en donnant aux étudiants l'occasion de mettre en pratique ces notions sur des problèmes types en utilisant un solveur de programme linéaire ou en développant des algorithmes de graphes.
Documents
- "Graphes et Algorithmes", Michel Gondran, Michel Minoux, Lavoisier, 2009.
- "Programmation mathématique : Théorie et algorithmes", Michel Minoux, Lavoisier, 2008.
- "Linear Programming", Vasek Chvatal, second edition, John Wiley and Sons, New-York, 1990.
- "Recherche Opérationnelle, méthodes d'optimisation", Jacques Teghem, Ellipses, 2012.
- "Exercices résolus de recherche opérationnelle", Tome 1 Graphes, leurs usages, leurs algorithmes, Dunod, 2005.
- "Exercice résolus de Recherche opérationnelle, Tome 3 - Programmation linéaire et extensions, problèmes classiques", Dunod, 2005.
- "Aide à la décision, une approche par les cas, Gestion, mathématiques, informatique", Philippe Vallin, Daniel Vanderpooten, 2002.