Informations du cours

La programmation linéaire est l’une des plus importantes techniques d’optimisation utilisées en recherche opérationnelle. Ceci est dû à la facilité de la modélisation, à l’efficacité des algorithmes développés et à l’existence sur le marché de nombreux logiciels. La généralisation de micro-informatique a mis la programmation linéaire à la portée de tous.

Ce cours est destine aux étudiants de 3 ème année  Licence option Informatique .

 L'objectif de la  programmation linéaire est de déterminer l’affectation optimale de ressources rares entre des activités ou produits concurrents. Les situations économiques demandent souvent qu’on optimise une fonction sous plusieurs contraintes prenant la forme d’inégalités.

L’objectif de ce cours est double. Il s’agit, d’une part, de donner une introduction à la formulation en modèles d’optimisation. Il s’agit, d’autre part, de présenter les techniques de résolution de ces problèmes.

On parle de problème d’optimisation lorsqu’il faut maximiser ou minimiser  une fonction sous contraintes. Par exemple, maximiser le bénéfice d’une entreprise sous les contraintes de satisfaire la demande et de respecter la capacité de production.

Le cours est divisé  en cinq  parties. Dans la première partie du cours, nous nous abordons la formulation  des problèmes linéaires, c’est-`a-dire les problèmes o`u la fonction objectif et les contraintes sont purement linéaires.  Ensuite la méthode de résolution graphique lorsqu’il n’y a que deux variables de décision, d"un problème linéaire.

Lorsqu’il y a un plus grand nombre de variables, un algorithme  mis en oeuvre sous la forme d’un programme informatique qui s’avère nécessaire. Il s’agit de l’algorithme du Simplexe que nous verrons au chapitre 3 sous forme  de tableaux. Au chapitre 4, nous examinerons une question très importante : à  savoir la dualité et la sensibilité de la solution `a des modifications de données. On parle d’analyse post-optimale.

Lorsque les variables doivent prendre des valeurs entières, on parle de problèmes en nombres entiers. C’est l’objet de la dernière partie du cours. On devrait `a proprement parler de problèmes linéaires en nombres entiers.Dans cette partie nous verrons  une technique de résolution de ces problèmes : il s’agit de la méthode e branch and bound.