Description
Cet ECUE introduit les notions de bases de la programmation linéaire. A la fin de cet enseignement les étudiants ont acquis des éléments nécessaires pour appréhender la modélisation en programmation mathématique. Ils connaissent l’algorithme du simplexe, et savent utiliser un logiciel d’aide à la décision qui implémente cet algorithme. Ils sont capables d’interpréter les solutions obtenues par ce logiciel pour fournir une aide au décideur. Seront également abordées les notions fondamentales de complexité théorique des algorithmes. Ils sont ainsi capables d’évaluer la performance d’un algorithme donné
Contenu :
- Modélisation d’un problème sous la forme d’un programme linéaire
- Résolution graphique d’un programme linéaire et caractérisation des solutions
- Algorithme du simplexe
- Dualité et analyse de sensibilité
- Notions temps CPU et mémoire, mesure de performance, notations mathématiques
- Algorithme « diviser pour régner » et quelques méthodes pour calculer la complexité
- NP complétude
- Complexité amortie