Les fondements théoriques et la procédure de résolution de la programmation linéaire

Le terme «recherche opérationnelle», d'origine militaire, n'est pas très suggestif, c'est le moins qu'on puisse dire. La recherche opérationnelle constitue autant une façon de traiter des problèmes à l'aide d'outils mathématiques et informatiques. La programmation linéaire en occupe une place important, L'importance de l'optimisation est la nécessité d'un outil simple pour modéliser des problèmes de décision que ce soit économique, militaire ou autres, ont fait de la programmation linéaire un des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers travaux (1947) sont celle de George B. Dantzig et ses associés du département des forces de l'air des Etats Unis d'Amérique (De nombreux mathématiciens, parmi eux le Russe L. V. Kantorovich 1938, se sont penchés sur le problème de programmation linéaire avant 1947).

Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de divers domaines sont représentés ou approximés par des modèles de PL. L'utilisation de ces techniques de modélisation s'est renforcée encore après avoir construit des algorithmes et des logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision que de contraintes.
Après la publication de la méthode de simplexe, la théorie de la programmation linéaire a été développé d'une façon remarquable, la naissance et l'évolution des méthodes de la programmation en nombre entier. Le développement des méthodes de décompositions des grands systèmes linaires, la fusion de la programmation mathématique avec la théorie des graphes.

La programmation linéaire permet d'optimiser une fonction linéaire appelé fonction-objectif sur un domaine définie par des inéquations appelées contraintes. La détermination des variables de base constitue une première étape, puis le suivie du processus de résolution.
Dans le présent exposé nous allons présenter dans un premier chapitre, les fondements théoriques de la programmation linéaire. Puis, nous allons traiter l'aspect concernant la procédure de résolution d'un programme.