Matière : Programmation linéaire
Unité d’enseignement méthodologique : UEM
Crédits :4
Coefficient : 2
Objectifs de l’enseignement :
Ce module a pour objectifs 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 : Mathématiques et informatique générales
Contenu de la matière :
Chapitre1 : Introduction générale
1.1 Historique de la programmation linéaire
1.2 Exemples de modélisation de problèmes pratiques sous forme de programme linéaire.
Chapitre2 : Géométrie de la programmation linéaire
2.1 Espaces vectoriels, rang de matrice, systèmes d’équations linéaires
2.2 Ensemble convexe, hyperplan, polyèdre, simplexe, point extrême
Chapitre3 : Méthode primale de résolution d’un programme linéaire
3.1 Position du problème
3.2 Caractérisation des points extrêmes
3.3 Optimalité en un point extrême
3.4 Critères d’optimalité : formule d’accroissement de la fonction objectif, critère d’optimalité,
3.5 condition suffisante d’existence de solution non bornée
3.6 Algorithme du simplexe : amélioration de la fonction objectif en passant d’un pont extrême à un autre, algorithme du simplexe sous forme matricielle, finitude de l’algorithme du simplexe, algorithme et tableau du simplexe
3.7 Initiation de l’algorithme du simplexe : cas du programme linéaire sous forme normale, M-méthode, méthode de deux phases,
Chapitre4 : Méthodes duales en programmation linéaire
4.1 Définitions
4.2 Formule d’accroissement de la fonction duale et critère d’optimalité
4.3 Condition suffisante de solutions réalisables dans le problème primale
4.4 Algorithme dual du simplexe
Initialisation de l’algorithme duale du simplexe
Mode d’évaluation :Examen (60%) , contrôle continu (40%)
Références:
- M. Sakarovicth, Graphes et programmation linéaire, Ed. Hermann. 1984.
- H. Mauran, Programmation linéaire appliquée, Ed. Technip, 1967.
- A. Kauffman, Méthodes et modèles de R.O., Ed. Dunod, 1976.
- V. Chvatal, Linear programming. W.H. Freeman and Company, 1983.