Linear Programming
Résumé de section
-
University: Djilali Bounaama Khemis Miliana
Faculty: Material and Computer Sciences
Department: Informatique
Level: L3 (SI)
Module: Programmation linéaire
Semester: 05
Crédits : 04
Coefficient : 02
Lecturer: Dr. BOUKEDROUN. Mohammed
Specialty: Mathematics
Diploma: Doctor in optimization and operational research
Grade: MCA
Contact: You can contact me on m.boukedroun@univ-dbkm.dz from.
-
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. -
Chapitre 1 : 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
Chapitre 2 : 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
Chapitre 3 : 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é
-
Condition suffisante d’existence de solution non bornée
3.6 Algorithme du simplexe :
-
Amélioration de la fonction objectif en passant d’un point 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éthode M
-
Méthode des deux phases
Chapitre 4 : 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 primal
4.4 Algorithme dual du simplexe
4.5 Initialisation de l’algorithme dual du simplexe
Mode d’évaluation
-
Examen : 60 %
-
Contrôle continu : 40 %
-
-
Références:
1. M. Sakarovicth, Graphes et programmation linéaire, Ed. Hermann. 1984.
2. H. Mauran, Programmation linéaire appliquée, Ed. Technip, 1967.
3. A. Kauffman, Méthodes et modèles de R.O., Ed. Dunod, 1976.
4. V. Chvatal, Linear programming. W.H. Freeman and Company, 1983.