École Supérieure Privée d’Ingénierie et de Technologies

Correction série 3 : Méthode de simplexe, dual et analyse de sensibilité

Niveau : 4ème année Année universitaire : 2020-2021

Exercice 1
Une aciérie produit trois types A, B, et C d’acier. Les compositions en matières et les prix de
vente par tonne de produit sont les suivants :

L’entreprise dispose quotidiennement de 30 tonnes de fer et de 60 tonnes de houille.

1°) Ecrire le problème de maximisation de la recette journalière obtenue par la production des
produits A, B et C.
2°) Résoudre par la méthode du Simplexe le problème posé, et donner la solution de production
optimale.
3°) L’entreprise doit limiter sa consommation d’énergie à 20000 unités par jour. L’énergie
nécessaire pour produire une tonne d’acier (de type A, B, ou C) est de 1000 unités.
Déterminer un nouveau plan de production.

Correction exercice 1
1. Les variables de décision :
x1 : La quantité produite d’acier A.
x2 : La quantité produite d’acier B.
x3 : La quantité produite d’acier C.
x1 , x2 , x3 ≥ 0.

Le programme linéaire qui modélise ce problème est donc le suivant :

Trouver
 max Z = 30x1 + 40x2 + 20x3
 2x1 + x2 + 2x3 ≤ 30
(S.C) x1 + 3x2 + 2x3 ≤ 60
x1 , x2 , x3 ≥ 0


2. Forme standard
max Z= 30x1 + 40x2 + 20x3
 2x1 + x2 + 2x3 + e1 = 30
(S.C) x1 + 3x2 + 2x3 + e2 = 60
x1 , x2 , x3 , e1 , e2 ≥ 0

Tableau initial :
 x1 x2 x3 e1 e2 2éme membre ratio
e1 2 1 2 1 0 30 30/1
e2 1 3 2 0 1 60 60/3
-Z 30 40 20 0 0 0
La variable entrante : x2 .
La variable sortante : e2 .
Tableau 2 :
x1 x2 x3 e1 e2 2éme membre ratio
e1 5/3 0 4/3 1 -1/3 10 30/5
x2 1/3 1 2/3 0 1/3 20 60
-Z 50/3 0 -20/3 0 -40/3 -800
La variable entrante : x1 .
La variable sortante : e1 . Tableau 3 :
x1 x2 x3 e1 e2 2éme membre
x1 1 0 4/5 3/5 -1/5 6
x2 0 1 2/5 -1/5 2/5 18
-Z 0 0 -20 -10 -10 -900
La solution optimale est atteint en x1 = 6, x2 = 18 et x3 = 0. Donc Z = 900.
3. On va ajouter la contrainte associée à la consommation de l’énergie suivante :
100x1 + 100x2 + 100x3 ≤ 2000

Exercice 2
On considère le programme linéaire suivant :

max 40x1 + 50x2

s.c 5x1 + 4x2 ≤ 80
x1 + 2x2 ≤ 24
3x1 + 2x2 ≤ 36
x1 ≥ 0, x2 ≥ 0

1. Donner le dual PL* de ce primal PL

2. Résoudre le primal PL par le simplexe
3. Déduire la solution du dual PL*
Correction exercice 2
1. Le dual PL* de ce primal PL est
min w 
= 80y1 + 24y2 + 36y3
 5y1 + y2 + 3y3 ≥ 40
(S.C) 4y1 + 2y2 + 2y3 ≥ 50
y1 , y2 , y3 ≥ 0


2
2. Résolution du PL par le simplexe
Forme standard
max Z= 40x1 + 50x2

 5x1 + 4x2 + e1 = 80
x1 + 2x2 + e2 = 24

(S.C)

 3x1 + 2x2 + e3 = 36
x1 , x2 , e1 , e2 , e3 ≥ 0

Tableau initial :
x1 x2 e1 e2 e3 2éme membre ratio
e1 5 4 1 0 0 80 80/4
e2 1 2 0 1 0 24 24/2
e3 3 2 0 0 1 36 36/2
-Z 40 50 0 0 0 0
La variable entrante : x2 .
La variable sortante : e2 .
Tableau 2 :
x1 x2 e1 e2 e3 2éme membre ratio
e1 3 0 1 -2 0 32 32/3
x2 1/2 1 0 1/2 0 12 12×2
e3 2 0 0 -1 1 12 12/2
-Z 15 0 0 -25 0 -600
La variable entrante : x1 .
La variable sortante : e3 .
Tableau 3 :
x1 x2 e1 e2 e3 2éme membre ratio
e1 0 0 1 -1/2 -3/2 14
x2 0 1 0 3/4 -1/4 9
x1 1 0 0 -1/2 1/2 6
-Z 0 0 0 -35/2 -15/2 -690
La solution optimale est : Z=690
3. A l’optimum, le primal et le dual sont liés par les règles suivantes :
- les fonctions objectifs z et w ont la même valeur optimale z=cx* = y*b=w
- la valeur marginale d’une variable dans un programme est égale à l’opposé de la valeur
optimale de la variable associée dans l’autre programme et réciproquement
- les variables du primal (x1, x2), étant toutes différentes de 0, alors les contraintes associées
du dual sont saturées, d’où pour le dual à résoudre :
5y1 + y2 + 3y3 = 40
4y1 + 2y2 + 2y3 = 50
- la première variable d’écart e1 est non nulle donc la première valeur y1 = 0, d’où le dual à
résoudre est :
y2 + 3y3 = 40

3
 2y2 + 2y3 = 50
⇒ y1 = 35/2 et y2 = −15/2.
Remarque :
il n’existe que quatre situations possibles pour une paire de problèmes liés par la dualité :
1. Les deux problèmes possèdent des solutions optimales finies ( liées par les relations ci-
dessus ).
2. Le problème primal est non borné et le problème dual est impossible.
3. Le problème primal est impossible et le problème dual est non borné.
4. Les deux problèmes sont impossibles.

Exercice 3
Un fabricant produit 2 variétés de biscuit, l’une à la noix de coco et l’autre au chocolat, selon
le schéma suivant :

1. Formuler le problème comme un PL et trouver un plan de fabrication qui maximise le profit.

2. Pour quelle variation du prix de vente du biscuit au chocolat, ce plan de fabrication reste
optimal ?
3. On annonce une pénurie de chocolat ; déterminer la quantité minimale de chocolat nécessaire
en stock, pour que ce plan de fabrication ne soit pas compromis.
4. On étudie la production d’un nouveau biscuit à la noix de coco et au chocolat à raison de
1/3 de noix de coco et 2/3 de chocolat. Ce nouveau produit sera vendu à 8 dinars. Quel est
le schéma de production optimal ?
5. Déterminer le dual PL* de ce primal PL.
6. En déduire la solution du dual PL*.
Correction exercice 3
1. max Z= 6x1 + 5x2
 x1 + x2 ≤
 8
5x2 ≤ 22

(S.C)

 3x1 ≤ 12
x1 , x2 ≥ 0

Résolution :
Forme standard

4
 max Z= 6x1 + 5x2

 x1 + x2 + e 1 = 8
5x2 + e2 = 22

(S.C)

 3x1 + e3 = 12
x1 , x2 , e1 , e2 , e3 ≥ 0

Tableau initial :
x1 x2 e1 e2 e3 2éme membre ratio
e1 1 1 1 0 0 8 8/1
e2 0 5 0 1 0 22 22/0
e3 3 0 0 0 1 12 12/3
-Z 6 5 -1 0 0 0
La variable entrante : x1 .
La variable sortante : e3 .
Tableau 2 :
x1 x2 e1 e2 e3 2éme membre ratio
e1 0 1 1 0 -1/3 4 4/1
e2 0 5 0 1 0 22 22/5
x1 1 0 0 0 1/3 4 4/0
-Z 0 5 -1 0 0 -24
La variable entrante : x2 .
La variable sortante : e1 .
Tableau 3 :
x1 x2 e1 e2 e3 2éme membre
x2 0 1 1 0 -1/3 4
e2 0 0 5 -1 -5/3 -2
x1 1 0 0 0 1/3 4
-Z 0 0 -5 0 -1/3 -44
La solution optimale est : Z=44.
2. soit t la variation du prix de vente du biscuit au chocolat alors la fonction objectif devient
Max Z = 6x1 + tx2 . on cherche maintenant c pour que la solution obtenue dans la première
question reste optimale.
D’après le dernier tableau, on a
x2 + e1 − 1/3e3 = 4 et x1 + 1/3e3 = 4.
Ceci donne
Z = 6(4 − 1/3e3 ) + t(4 − e1 + 1/3e3 )
Par suite
Z = −e1 t − e3 (1/3t − 2).
On conclut que t ≥ 0 et t ≤ 6 ⇒ 0 ≤ t ≤ 6.
3. d’après les coût marginaux, il nous reste en stock 2 quantité de chocolat, donc la quantité
minimale pour que plan de fabrication optimal ne soit pas compromis, il faut avoir en réserve
22-2 =20 quantité de chocolat.

5
4. Le dual PL* de ce primal PL est :

min w 
= 8y1 + 22y2 + 12y3
 y1 + 5y2 + 3y3 ≥ 6
(S.C) y1 ≥ 22
y1 , y2 , y3 ≥ 0


5. la solution du dual PL* est Z = cx* = y*b = w=44