L’objectif est de fournir les bases de la programmation linéaire nécessaires à la formalisation et à la résolution algorithmique de problèmes d’optimisation combinatoire en lien avec des problématiques d’aide à la décision.
Programmation Linéaire
- Modélisation et formulation d’un programme linéaire en variables réelles (PL) et en variables binaires ou entières (PLNE)
- Théorèmes fondamentaux de la programmation linéaire et dualité
- Algorithmes (primal et dual) du simplexe
- Analyse post-optimale
Techniques de l’optimisation combinatoire
- Programmation Linéaire continue versus Programmation Linéaire discrète
- Résolution approchée d’un PLNE
- Résolution exacte d’un PLNE : énumération implicite
Prérequis
Bases de l’algorithmique et de l’algèbre linéaire.
Acquis d’apprentissage
- Le paradigme de la programmation linéaire continue et discrète : concevoir un modèle PL/PLNE pour un problème de décision.
- L’algorithme du simplexe et ses variantes pour la programmation linéaire continue : conception, mise en œuvre informatique et application.
- Les algorithmes d’énumération implicite pour la programmation linéaire discrète : conception, mise en œuvre informatique et application.
- L’analyse post-optimale en programmation linéaire : interprétation économique des solutions calculées.
- Connaître les solveurs de référence d’optimisation pour la modélisation et résolution de PL/PLNE.
Compétences visées
- Maîtriser les outils mathématiques et informatiques de base de modélisation, d’analyse et de résolution de problématiques en lien avec les sciences de la décision.
- Connaître les logiciels de référence d’optimisation et concevoir des solutions logicielles adaptées à des problématiques de décisions.
- Concevoir des algorithmes et évaluer leur complexité.
- Modéliser des problèmes complexes.
- Proposer des solutions informatiques à des problèmes complexes.