Intitulé de la matière : Programmation linéaire
Intitulé de l’UE : UEM1.1.2
Crédits : 4
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
3. Méthodes duales en programmation linéaire
- Définitions
- Formule d’accroissement de la fonction duale et critère d’optimalité
- Condition suffisante de solutions réalisables dans le problème primale
- Algorithme dual du simplexe
4. Applicationspratiques de la PL
- Problème de production
- Problèmes de transport 2-4
Mode d’évaluation : Examen (60%), continue (40%)
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.