Programmation linéaire

Course ID

Campus

Département Informatique

Level

Licence

Semester

Semestre 5

Credit

Method

Cours, TD

Objectifs de l’enseignement :

Acquisition d’un panorama de techniques de modélisation utilisées en programmation linéaire avec développement d’applications économiques et industrielles en optimisation.

Connaissances préalables recommandées :

Avoir des connaissances sur l’algèbre, l’algorithmique et la théorie des graphes, acquises en 1ère et 2ème années.

Contenu de la matière :

Rappels Mathématiques (Algèbre linéaire)
- Espace vectoriel
- Dimension, base
- Matrice, déterminant d’une matrice, inverse d’une matrice

II. Introduction et propriétés de la programmation linéaire

Forme générale d’un programme linéaire, forme canonique, standard et
Résolution graphique, notion de polyèdre.
Résolution analytique.

III. Méthode du simplexe

Introduction de la méthode, algorithme du simplexe, tableau du simplexe
Méthodes particulières : méthode des pénalités, méthode des deux phases
Forme révisée du simplexe

IV. Dualité

Introduction, règles de passage du primal au dual
Algorithme dual du simplexe

V. Problème du transport

Introduction du problème, graphe associé au tableau du transport
Algorithme du transport
Algorithme dual du

Mode d’évaluation : Examen (50%), contrôle continu (50%)

Références bibliographiques:

Fleury, Ph. Lacomme, Programmation linéaire avancée, Ellipses, 2010
-C. Moisdon, M. Nakhla, Recherche opérationnelle : Presses des Mines – Transvalor, 2010.
J. Vanderbei – Linear Programming, Foundations and Extensions, Springer-Verlag, 2008.
Borne, A. El Kamel, Kh. Melloul, Programmation linéaire et applications, Technip, 2004.
Faure, J-P. Boss, A. Le Garff , La Recherche opérationnelle, Edit. P.U.F., 2001
Baillargeon, Programmation linéaire appliquée, Edit. S.M.G. 2000
Guéret, C. Prins et M. Sevaux, Programmation linéaire: 65 problèmes d’optimisation modélisés et résolus avec Visual Xpress, Eyrolles, 2000.

Polycopiés et sites internet à consulter :