Introduction
Une première tentative, nous mène à définir la recherche opérationnelle comme
ensemble de méthodes (algorithmiques et mathématiques, après passage par la
modélisation) afin de prendre des décisions optimales ou proches de l’optimum pour des
problèmes complexes, qui traitent de la maximisation d’un profit ou la minimisation d’un
coût, à titre d’exemples :
- Comment ordonnancer les tâches d’un projet, tout en minimisant sa durée ?
- Comment investir ses millions de dinars de sorte à maximiser le profit obtenu après
deux ans ?
- Trouver un (plus court) chemin entre deux villes ... .
La programmation linéaire est un domaine de la recherche opérationnelle qui a été
développée la fin des années 1940, pour résoudre un certain nombre de problèmes
d’allocation de ressources pour le gouvernement fédéral des États Unis d’Amérique et dont
le développement peut se situer aux environs des années cinquantes, particulièrement à partir
de 1951, l’année où G. Dantzig (1914- 2005) découvrit l’algorithme du Simplexe, principal
outil de résolution des programmes linéaires.
On peut citer les domaines d’application de la programmation linéaire qui sont : les
transports, les banques, les industries lourdes et légères, l’agriculture, les chaînes
commerciales, la sidérurgie, et même le domaine des applications militaires.
I. Notions fondamentales de la programmation linéaire
Modélisation.
Choix des variables de décisions. Posons
x1 : Quantité du produit (A) à confectionner.
x2 : Quantité du produit (B) à confectionner.
Formulation des contraintes.
On constate (après simplifications) que
x1 ≥ 0, x2 ≥ 0 les contraintes de non négativité
Les contraintes sur les disponibilités
6𝑥1 + 5𝑥2 ≤ 5
10𝑥1 + 20𝑥2 ≤ 15
𝑥1 ≤ 0.8
Détermination des objectifs à atteindre
Posons z le profit net. On a
max 𝑧 = 50𝑥1 + 45𝑥2
Donc on est amené à résoudre le problème (programme) suivant :
max 𝑧 = 50𝑥1 + 45𝑥2
6𝑥1 + 5𝑥2 ≤ 5
10𝑥1 + 20𝑥2 ≤ 15
𝑠. 𝑐 {
𝑥1 ≤ 0.8
𝑥1 , 𝑥2 ≥ 0
