Intitulé de la matière : Programmation
linéaire
Intitulé de l’UE : UEM11
Crédits : 3
Coefficients : 2
Objectifs de l’enseignement:Ce module a pour but de présenter la programmation linéaire et ses applications en optimisation.et de sensibiliser l'étudiant à l'importance pratique des problèmes d'optimisation linéaires, de maîtriser l’ensemble théorique sous-jacent, et de pouvoir utiliser ces techniques dans des problèmes pratiques.
Connaissances préalables recommandées :
Optimisation du niveau Licence.
Contenu de la matière :
1. Généralités
- Définitions et modélisation des problèmes de programmation linéaire
- Géométrie de la programmation linéaire: Espaces vectoriels, systèmes d’équations linéaires, rang de matrice, ensemble convexe, hyperplan, polyèdre,points extrêmes.
- Solutions de base réalisables.
2. Méthode primale de résolution d’un programme linéaire
- Position du problème
- Caractérisation des points extrêmes
- Existence et optimalité des points extrêmes
- Algorithme du simplexe : amélioration de la fonction objectif en passant d’un pont extrême à un autre, algorithme du simplexe sous forme matricielle
- Condition suffisante de solutions réalisables dans le problème primal
- Algorithme dual du simplexe
3. Applicationspratiques de la PL
- Problème de production
- Problèmes de transport2
Mode d’évaluation :Contrôle continu-Examen
Références
- M. Minoux, Programmation mathématique, Théorie et Algorithmes, Dunod, 1983.1
- A. Kauffman, Méthodes et modèles de R.O., Ed. Dunod, 1976.
- V. Chvatal, Linear programming.W.H. Freeman and Company, 1983
- R. J. Vanderbei, Linear Programming: Foundations and Extensions », Kluwer Academic Publishers, 1998.