Support de cours ROP Mme BOUKERRAM
PROGRAMMATION LINEAIRE
CHAPITRE 1 : MODELISATION
1.1 Qu'est-ce que la programmation linéaire ?
La programmation linéaire peut se définir comme une technique mathématique
permettant de résoudre des problèmes de gestion et particulièrement ceux où le
gestionnaire doit déterminer, face à différentes possibilités, l’utilisation optimale des
ressources de l’entreprise pour atteindre un objectif spécifique comme la maximisation
des bénéfices ou la minimisation des coûts.
A l'origine, le terme programme a le sens de planification opérationnelle mais il est
aujourd'hui employé comme synonyme de problème d'optimisation.
La terminologie est due à G. B. Dantzig, inventeur de l'algorithme du simplexe (1947).
L’approche pour résoudre ce type de problèmes sera divisée en deux étapes principales :
a) La modélisation du problème sous forme d’équations ou d’inéquations linéaires qui
permettra ainsi de bien identifier et structurer les contraintes que doivent respecter les
variables du modèle; de plus, on doit définir l’apport de chaque variable à l’atteinte de
l’objectif poursuivi par l’entreprise, ce qui se traduira par une fonction à optimiser.
b) La détermination de l’optimum mathématique à l’aide de certaines techniques propres
à la programmation linéaire
1.2 PROBLEMATIQUE ET MODELISATION
Exemple1 : problème du restaurateur
Un restaurateur à constater que sa clientèle préfère les assortiments de fruits et il peut
offrir indifférement :
des assiettes à 80 DA contenant 5 Fraises, 2 Poires et 1 Banane
des assiettes à 60 DA contenant 3 Fraises, 2 Poires et 3 Bananes
Sachant que le restaurateur ne dispose que de 30 Fraises, 24 Poires et 18 Bananes
Comment doit – il disposer ses assièttes pour réaliser une recette maximale ??
Résolution
Modélisation sous forme d’un programme linéaire (PL)
Objectif : Maximiser le bénéfice tout en respectant la disponibilité des ressources (fruits)
en stock.
Assiette de type I Assiette de type I Disponibilité des
ressources
Fraises 5 3 30
Poires 2 2 24
Bananes 1 3 18
Profit/assiette 80 Da 60 DA
Comment calculer le profit du restaurateur ??
Profit = [Link] d’assiettes de type I + [Link] d’assiettes de type II
Donc il faut déterminer le nombre d’assiettes de type I et celles de type II à proposer
pour max le bénéfice.
Les variables sont donc :
X1 : Nbre d’assiettes de type 80 et X2 Nbre d’assiettes de type 60
1
Support de cours ROP Mme BOUKERRAM
l’objectif s’écrit :
Max(Z) = 80.X1 + 60.X2
Le restaurateur ne peut pas fabriquer une infinité d’assiettes il a des contraintes de
diponibilité des fruits.
Les contraintes sur les quantités s’écrivent :
5.X1 + 3.X2 <= 30 (Qt de fraises utilisés ne doit pass dépasser la qt disponible)
2.X1 + 3.X2 <= 24 (Qt de Poires utilisés ne doit pass dépasser la qt disponible)
1.X1 + 3.X2 <= 18 (Qt de Banane utilisés ne doit pass dépasser la qt disponible)
X1, X2 >= 0 (les qt sont positives)
Le PL (P) s’écrit :
Max(Z) = 80.X1 + 60.X2
5.X1 + 3.X2 <= 30
2.X1 + 3.X2 <= 24
1.X1 + 3.X2 <= 18
X1, X2 >= 0
- On peut constater que toutes les équations et inéquations sont linéaires.
- La résolution d’un tel Problème consiste à déterminer X1 et X2 de façon
à respecter les 4 contraîntes et à rendre Z Maximale .
Exemple 2 : Fabrication de produits
Une usine fabrique 2 produits (A) et (B) à partir de 3 types de matières premières (I), (II)
et (III). Le fonctionnement de l’usine s’effectue comme indique le tableau suivant :
(A) (B)
(I) 2 1 Pour fabriuer une unité de (A) il faut 2 unité
(II) 1 2 de matière (I) et 1 unité de (II)
(III) 0 1
L’entreprise dispose de matières premières en quantité limités respectivement 8, 7 et 3
pour (I), (II) et (III).
Le profit dû à la fabrication d’une (1) unité de (A) est de l’ordre de 4DA et celui de (B)
est de l’ordre de 5 DA.
Comment l’usine doit elle produire les articles (A) et (B) pour réaliser le meilleur
bénéfice ?
Résolution
Modélisation sous forme d’un programme linéaire (PL)
Objectif : Maximiser le bénéfice tout en respectant la disponibilité des ressources
(matières premières) en stock.
Produit (A) Produit (B) Disponibilité des
ressources
I 5 3 8
II 2 2 7
III 1 3 3
Profit/assiette 4 Da 5 DA
Comment calculer le profit ??
Profit = 4 *qt produit (A) + 5**qt produit (A)
2
Support de cours ROP Mme BOUKERRAM
Les variables sont donc :
X1 : qt de produit (A) à fabriquer et
X2 :qt de produit (B)
Objectif :
Max(Z) = 4. X1 + 5. X2
Les contraintes
2.X1+X2 <= 8 (qt de matière (I) utilisée ne doit pas dépasser la qt disponible)
1.X1+ 2.X2 <= 7 (qt de matière (II) utilisée ne doit pas dépasser la qt disponible)
1.X2 <= 3 (qt de matière (III) utilisée ne doit pas dépasser la qt disponible)
X1 , X2 >= O (qt sont positif)
Le PL (P) s’écrit :
Max(Z) = 4.X1 + 5.X2
2.X1 + X2 <= 8
1.X1 + 2.X2 <= 7
1.X2 <= 3
X1, X2 >= 0
Exemple3 : Problème du transport
Une entreprise de construction de véhicules possède 3 unités situées à Tiaret, Rouiba et
Constantine
Un certain type de métal nécéssaire à la construction des véhicules est disponible à Béni-
Saf et Djelfa.
Les qt de ce métal nécessaire aux usines sont 400, 300 et 200 tonnes/Semaines
respectivement pour Rouiba, Constantine et Tiaret.
Tandisque les qt disponibles à Bénisaf et Djelfa sont respectivement de 550 T et 350T.
Les coûts de transport supposés proportionnelle aux qt transportées. Les coûts unitaires
sont donnés par le tableau suivant :
Rouiba Constantine Tiaret Ségnifie que pour transporter une tonne de
Béni-saf 5 6 3 métal Béni-saf à Rouiba le coût est de 5 DA
Djelfa 3 5 4
Déterminer un plan de transport Optimal ?
Résolution
Soit Xij : la qt de métal transporté de i vers l’usine j/ (i=b,d) et (i=r, c et t)
Objectif : Minimiser le coût de transport
Min(Z) = 5Xbr + 6Xbc + 3Xbt + 3Xdr +5Xdc +4Xdt
Les contraîntes
Sur la disponibilité
Xbr + Xbc +Xbt <= 530 (qt transporté de Beni-saf aux usines doit être <= à la qt
disponible)
Xdr + Xdc +Xdt <= 350 (qt transporté de djelfa aux usines doit être <= à la qt
disponible)
Sur la demande
Xbr + Xdr >= 400 (qt acheminé à Rouiba ne doit pas être inférieur au besoin de
l’usine)
Xbc + Xdc >= 300 (qt acheminé à Constantine ne doit pas être inférieur au besoin
de l’usine)
Xbt + Xdt >= 200 (qt acheminé à Tiaret ne doit pas être inférieur au besoin de
l’usine)
Avec Xij >= 0 (i=b,d) et (i=r, c et t)
3
Support de cours ROP Mme BOUKERRAM
Définition :
On appelle fonction économique (ou objectif) la fonction qui doit être maximisée ou
minimisée.
On appelle programme de base : l’identification des variables, la donnée de la fonction
économique ainsi que du système d’inéquations correspondant aux contraintes.
1.3. Forme générale d'un programme linéaire
Max(Min)Z j 1c j x j
n
Sous les contraintes
a x b pour i I 1,..m
n
j 1 ij j i
a x b pour k K 1,..m
n
j 1 kj j k
a x b pour r R 1,..m
n
j 1 rj j r
l x u pour j 1.. n
j j j
Les ensembles I, K, et R sont disjoints, I K R = {1…. M} et lj = - et uj = + sont
des valeurs possibles.
1.4 Terminologie
Les variables x1…. xn sont appelées variables de décision du problème.
La fonction linéaire à optimiser est appelée fonction objectif (ou parfois fonction
économique).
Les contraintes prennent la forme d'équations et d'inéquations linéaires.
Les contraintes de bornes se résument souvent à des contraintes de non-négativité xi 0.