Programmation linéaire

Objectifs: 

Les problèmes d'optimisation avec une fonction objectif et des contraintes linéaires (appelés classiquement "programmes linéaires") constituent une classe importante de problèmes pour lesquels il existe des méthodes de résolution efficaces, en particulier la méthode du simplexe. De plus, la programmation

linéaire constitue l'outil fondamental de résolution des problèmes d'optimisation en recherche opérationnelle, qui ont une grande importance pratique : problèmes d’affectation, transport, production, planification, etc. Elle est aussi étroitement reliée à la résolution des systèmes d'inégalités et aux polyèdres convexes. Le cours se limite aux problèmes avec variables continues. Le cas des variables 0-1 ou entières, très courant en pratique, est traité dans le cours “Optimisation Combinatoire” pour lequel ce cours est un pré-requis.

Contenu du cours:

1. Présentation de quelques problèmes pratiques courant en recherche opérationnelle, et modélisation sous forme de programme linéaire.
2. Forme standard d'un programme linéaire, interprétation et résolution géométrique.
3. La méthode du simplexe, notion de dictionnaire, de solution de base.
4. Initialisation du simplexe, méthode à 2 phases, bouclage, temps de calcul.
5. Notion de dualité, écarts complémentaires, interprétation économique du dual.
6. La méthode révisée du simplexe.
7. Solvabilité d'un système d’inégalités linéaires, lemmes de Farkas, élimination de Fourier-Motzkin.
8. Analyse de sensibilité.
9. Les autres méthodes de résolution (ellipsoïde, méthode du point intérieur)
10. Polyèdres et polytopes convexes, sommets et rayons extrêmes

Références:

• Chvatal. Linear programming. W.H. Freeman and Company, 1983.
• Matousek, B. Gärtner. Understanding and using linear programming. Springer Universitext, 2007.
• Gondran, M. Minoux. Programmation mathématique, Théorie et Algorithmes. Dunod, 1983.