Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
Travaux dirigés avec corrigés
Exercice 1 :
Un jardinier souhaite composer un compost équilibré en mélangeant deux types de
composts, le Type 1 et le Type 2, afin de respecter des exigences spécifiques en termes
d’unités de carbone et d’azote, comme indiqué dans le tableau suivant :
Compte tenu de ces informations, on vous demande de traiter les questions suivantes :
1- Exprimez à l’aide d’un programme linéaire la combinaison des deux types de composts
qui remplira les conditions exigées au moindre coût.
2- Trouvez, en utilisant la méthode graphique, la quantité de compost de type 1 et de type 2
que le jardinier doit acheter afin de minimiser le coût total.
Exercice 2 :
Un atelier fabrique des tables et des bureaux. Chaque table nécessite 2, 5 h pour l’assemblage,
3 h pour le polissage et 1 h pour la mise en caisse. Chaque bureau exige 1 h pour l’assemblage, 3
h pour le polissage et 2 h pour la mise en caisse. L’entreprise ne peut disposer, chaque semaine,
de plus de 10 h pour l’assemblage, de 15 h pour le polissage et de 8 h pour la mise en caisse. Sa
marge de profit est de 30 Dh par table et de 40 Dh par bureau.
Table Bureau Capacité
Assemblage 2.5 1 10
Polissage 3 3 15
Mise en caisse 1 2 8
Profit 30 40
1. Écrire le programme linéaire qui maximise le profit.
2. Trouver la solution optimale à l’aide de la méthode graphique.
Exercice 3 :
Soit le programme linéaire suivant :
𝒎𝒂𝒙 𝑧 = 5 𝑥! + 6 𝑥" + 3 𝑥#
s.c.
4 𝑥! + 3 𝑥" + 𝑥# ≤ 2
𝑥! + 2𝑥" + 2 𝑥# ≤ 3
𝑥! , 𝑥" , 𝑥# ≥ 0
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
1- Résoudre le programme linéaire en utilisant la méthode de simplexe.
Exercice 4 :
Soit le programme linéaire suivant :
1- Résoudre le programme linéaire avec la méthode à deux phases.
Exercice 5 :
On considère le programme linéaire suivant :
1- Trouver le dual du P.L.
2- Résoudre le programme linéaire dual.
3- A l’aide des écarts complémentaires, trouver la solution optimale de primal.
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
Corrigé
Exercice 1 :
1- P.L.
x1 : Quantité du compost Type I min Z = 160 x1 + 150 x2
s.c.
x2 : Quantité du compost Type II 6 x1 + 9 x2 ≥ 18
6 x1 + 3 x2 ≥ 12
2- Solution graphique : x1, x2 ≥ 0
18
𝑥! = 0 → 𝑥" = = 2; 𝑝𝑜𝑖𝑛𝑡1: (0, 2)
𝐶𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒 1 ; 9
18
𝑥" = 0 → 𝑥! = = 3; 𝑝𝑜𝑖𝑛𝑡2 ∶ (3,0)
6
12
𝑥! = 0 → 𝑥" = = 4; 𝑝𝑜𝑖𝑛𝑡1: (0, 4)
𝐶𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒 2 ; 3
12
𝑥" = 0 → 𝑥! = = 2; 𝑝𝑜𝑖𝑛𝑡2 ∶ (2,0)
6
Il y a 3 points extrêmes (sommets)
La droite en rouge de la fonction objectif est facultative.
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
Exercice 2 :
1-
2-
5 points extremes (sommets): A(0,0), B(0,8), C(4,6), D(6.7 , 3.2), E(8, 0)
Le point optimal est le point : (𝑥! , 𝑥" ) = (4, 6) et la valeur optimale est :
z∗ = 20×4+40×6 = 320
Exercice 3 :
𝒎𝒂𝒙 𝑧 = 5 𝑥! + 6 𝑥" + 3 𝑥#
La forme standard
s.c.
1- 4 𝑥! + 3 𝑥" + 𝑥# + 𝑒! = 2
𝑥! + 2𝑥" + 2 𝑥# + 𝑒" = 3
𝑥! , 𝑥" , 𝑥# , 𝑒! , 𝑒" ≥ 0
B b x1 x2 x3 e1 e2 Rapport
e1 2 4 3p 1 1 0 2/3
e2 3 1 2 2 0 1 3/2
Z 0 5 6 3 0 0
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
B b x1 x2 x3 e1 e2 Rapport
𝑥" 2/3 4/3 1 1/3 1/3 0 2
e2 5/3 -5/3 0 4/3p -2/3 1 5/4
Z -4 -3 0 1 -2 0
B b x1 x2 x3 e1 e2 Rapport
𝑥" 1/4 1 0 1/2 -1/4
x3 5/4 -5/4 0 1 -1/2 3/4
Z -21/4 -6 0 0 -3/2 -3/4
"! ! (
La solution optimale est 𝑍$%& = '
avec 𝑥! = 0, 𝑥" = ' 𝑒𝑡 𝑥# = '
Exercice 4 :
1- Programme linéaire standard (PLS)
max 𝑍 = 55 𝑥! + 30 𝑥"
4 𝑥! + 3 𝑥" + 𝑒! = 6
!
𝑥! + 2 𝑥" − 𝑒" = 2
𝑥! , 𝑥" , 𝑒! , 𝑒" ≥ 0
2- P.L.A. (P.L.F)
min 𝑤 = 𝑟 ⟺ max −𝑤 = −𝑟
4 𝑥! + 3 𝑥" + 𝑒! = 6
!
𝑥! + 2 𝑥" − 𝑒" + 𝒓 = 2
𝑥! , 𝑥" , 𝑒! , 𝑒" , 𝑟 ≥ 0
Nous réécrivons la fonction objectif en utilisant la deuxième contrainte :
𝑟 = 2 − 𝑥! − 2 𝑥" + 𝑒"
min 𝑤 = 𝑟 ⟺ max −𝑤 = −𝑟 = −2 + 𝑥! + 2 𝑥" − 𝑒"
4 𝑥! + 3 𝑥" + 𝑒! = 6
!
𝑥! + 2 𝑥" − 𝑒" + 𝒓 = 2
𝑥! , 𝑥" , 𝑒! , 𝑒" , 𝑟 ≥ 0
Nous obtenons le PL suivant :
max 𝑊 = −2 + 𝑥! + 2 𝑥" − 𝑒"
4 𝑥! + 3 𝑥" + 𝑒! = 6
!
𝑥! + 2 𝑥" − 𝑒" + 𝒓 = 2
𝑥! , 𝑥" , 𝑒! , 𝑒" , 𝑟 ≥ 0
La solution réalisable est : solr = (𝑥! , 𝑥" , 𝑒! , 𝑒" , 𝑟) = (0,0,6,0,2) avec la valeur de la fonction
objectif est W(solr) = -2
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
Phase I :
B b x1 x2 e1 e2 r Rapport
e1 6 4 3 1 0 0 2
r 2 1 2p 0 -1 1 1
-w 2 1 2 0 -1 0 --
Diviser toute la ligne pivot par le pivot, annuler la colonne pivot en gardant 1 sur la case
pivot. Pour les autres cases, utiliser la méthode du rectangle. Par exemple, pour recalculer la
valeur de e₁ :
2∗3
𝑒! = 6 − =3
2
B b x1 x2 e1 e2 r Rapport
e1 3 5/2 0 1 3/2 -3/2 2
x2 1 1/2 1 0 -1/2 1/2 1
-w 0 0 0 0 0 -1 --
Conclusion : w=0 ⇔ a=0 alors le programme linéaire peut admettre une solution, on passe à la
phase II.
Phase II
3- Programme linéaire Équivalent :
max 𝑧 = 55 𝑥! + 30 𝑥"
⎧5 3
⎪ 𝑥! + 𝑒! + 𝑒" = 3
2 2
⎨ 𝑥 + 𝑥 − 1𝑒 = 1
1
⎪ 2 ! "
2 "
⎩ 𝑥1 , 𝑥2 , 𝑒1 , 𝑒2 ≥ 0
La fonction objectif ne doit contenir que des variables hors base. Or, 𝑥" est une variable de
base. Nous réécrivons donc la fonction objectif en fonction des variables hors base en
utilisant la deuxième contrainte :
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
1 1
𝑥" = 1 + 𝑒" − 𝑥!
2 2
1 1
𝑧 = 55 𝑥! + 30 𝑥" = 55 𝑥! + 30 P1 + 𝑒" − 𝑥! Q = 55 𝑥! + 30 + 15 𝑒" − 15 𝑥!
2 2
= 40 𝑥! + 15 𝑒" + 30
Nous obtenons le PL suivant :
max 𝑧 = 40 𝑥! + 15 𝑒! + 30
⎧ 5 3
⎪ 𝑥! + 𝑒! + 𝑒" = 3
2 2
⎨ 1 1
𝑥! + 𝑥" − 𝑒" = 1
⎪ 2 2
⎩ 𝑥1 , 𝑥2 , 𝑒1 , 𝑒2 ≥ 0
La solution réalisable est : solr= (0,1,3,0) avec Z(solr) = 30
4-
B b x1 x2 e1 e2 Rapport
e1 3 5/2 p 0 1 3/2 6/5
x2 1 1/2 1 0 -1/2 2
Z -30 40 0 0 15 --
B b x1 x2 e1 e2 Rapport
x1 6/5 1 0 2/5 3/5
x2 2/5 0 1 -1/5 -4/5
Z -78 0 0 -16 -9
La solution optimale est : Zmax = 78
V.B. : V.H.B. :
𝑥! = 6/5 𝑒! = 0
𝑥" = 2/5 𝑒" = 0
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
Exercice 5 :
Le primal :
2 1 0
𝐴 = = ?
1 2 1
1- Le dual :
2 1
𝐴′ = A1 2B
0 1
m𝑎𝑥 4𝑦! + 5𝑦"
⎧ 2𝑦 + 𝑦 ≤ 8
⎪ ! "
𝑑𝑢𝑎𝑙 ∶ 𝑦! + 2 𝑦" ≤ 7
⎨ 𝑦" ≤ 3
⎪
⎩ 𝑦! , 𝑦" ≥ 0
2- Résoudre le dual en utilisant la méthode des tableaux :
B b y1 y2 e1 e2 e3 Rapport
e1 8 2 1 1 0 0 8/1
e2 7 1 2 0 1 0 7/2
e3 3 0 1p 0 0 1 3/1
Z 0 4 5 0 0 0
B b y1 y2 e1 e2 e3 Rapport
e1 5 2 0 1 0 -1 5/2
e2 1 1p 0 0 1 -2 1
y2 3 0 1 0 0 1 -
Z -15 4 0 0 0 -5
Année Scolaire : 2023/2024
Élément : Programmation linéaire
3ème Année-IIR
B b y1 y2 e1 e2 e3 Rapport
e1 3 0 0 1 -2 3p 3/3
y1 1 1 0 0 1 -2 -
y2 3 0 1 0 0 1 3/3
Z -19 0 0 0 -4 3
Remarque : Le rapport est égal à 1 pour les deux lignes, donc vous pouvez choisir soit 𝑒! , soit 𝑦"
comme ligne pivot.
B b y1 y2 e1 e2 e3 Rapport
e3 1 0 0 1/3 -2/3 1
y1 3 1 0 2/3 -1/3 0
y2 2 0 1 -1/3 2/3 0
Z -22 0 0 -1 -2 0
La solution optimale est : 𝑍$%& = 22 avec 𝑦! = 3, 𝑦" = 2.
3- Déduire la solution optimale du primal en utilisant celle du dual :
On considère les contraintes du dual
Puisqu'on a trouvé la solution 𝑦! = 3 𝑒𝑡 𝑦" = 2 par le simplexe, on les remplace dans les
contraintes du dual :
• Contrainte 1 : 2𝑦! + 𝑦" = 2 ∗ 3 + 2 = 8 contrainte saturée ⇒ 𝑥! variable de base
• Contrainte 2 : 𝑦! + 2𝑦" = 3 + 2 ∗ 2 = 7 contrainte saturée ⇒ 𝑥" variable de base.
• Contrainte 3 : 𝑦" = 2 contrainte non-saturée ⇒ D'après le théorème des écarts
complémentaires, on a 𝑥# = 0.
On résout le système en se ramenant aux contraintes saturées du primal :
2𝑥 + 𝑥" = 4
W !
𝑥! + 2𝑥" = 5
2(5 − 2𝑥" ) + 𝑥" = 4
W
𝑥! = 5 − 2𝑥"
𝑥" = 2
W
𝑥! = 5 − 2 ∗ 2 = 1
⇒ 𝑥! = 1, 𝑥" = 2 solution du primal
