Chapitre 4
Pr. Mohamed DHIB 1
ENSIT
1. Introduction
2. Modification des coefficients de la fct objectif ci
3. Variation des coefficients du membre de droite bi
4. Introduction d’une nouvelle contrainte
2
3
Est-ce que la solution optimale est sensible
aux paramètres du programme linéaire?
Une analyse post-optimale (ou analyse de
sensibilité) se résume à la recherche des intervalles
de variation possibles des paramètres du
programme linéaire (coefficient de la fonction
objectif ou du membre du droite) sans que la
solution optimale ne soit modifiée.
3
4
Une solution de base optimale est dite stable si elle ne
change pas lorsque les valeurs de paramètres de PL
sont modifiées.
On appelle post-optimisation l’ensemble des
techniques permettant d’obtenir l’optimum du
problème de PL lorsque certaines données ont subi
des modifications.
4
Nous allons envisager deux cas:
La variation des coefficients de la fonction objectif ci
La variation des coefficients du membre du droite bi
Max Z = c1x1 + c2x2 + …. + cnxn
a11x1 + a12x2 + …. + a1nxn b1
a21x1 + a22x2 + …. + a2nxn b2
an1x1 + an2x2 + …. + annxn bn
5
La question qui se pose est la suivante:
6
La question qui se pose est la suivante:
Si on augmente le prix de vente unitaire ou si l’on
diminue le coût unitaire de production, quel est
l’impact sur la valeur de l’objectif?
6
La question qui se pose est la suivante:
Si on augmente le prix de vente unitaire ou si l’on
diminue le coût unitaire de production, quel est
l’impact sur la valeur de l’objectif?
Déterminer un intervalle dans lequel peut varier
le coefficient ci d’une variable de décision sans
que la solution optimale change: intervalle
6
d’optimalité
Exemple d’application
On considère une usine de meubles pour la fabrication de
bureaux et de tables.
Bureau Table Temps libre
Menuiserie 1h 2h 20 h
Assemblage 2h 1h 22 h
Vernissage 1h 1h 12 h
Profit 300 € 200 €
Soit x1 le nombre de bureaux construits, et x2 le
nombre de tables construits. On souhaite maximiser
le profit, mais en respectant les contraintes de
7
temps libres.
8
MaxZ = 300 x1 + 200 x2
8
MaxZ = 300 x1 + 200 x2
x1 + 2 x2 20 (Menuiserie)
2x1 + x2 22 (Assemblage)
x1 + x2 12 (vernissage)
8
MaxZ = 300 x1 + 200 x2
x1 + 2 x2 20 (Menuiserie)
2x1 + x2 22 (Assemblage)
x1 + x2 12 (vernissage)
D’après le dernier tableau du simplexe, la base optimale est:
(x1, x2) = (10, 2) et la valeur de Z est 3400 €
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 0 -100 -100 -3400
8
Modification de variable C1
Etudions la variation du coefficient C1 relatif au profit à retirer
de la vente du bureau (C1= 300 €)
Considérons une variation du coefficient c1 de : C’1= C1+
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100 -100 -3400
Le tableau n’est plus optimal (on calcul les éléments de la dernière ligne)
9
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100- -100+ -3400-10*
10
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100- -100+ -3400-10*
La solution donnée par le tableau reste optimale si :
-100 - 0 -100
-100 + 0 100
10
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100- -100+ -3400-10*
La solution donnée par le tableau reste optimale si :
-100 - 0 -100
-100 100
-100 + 0 100
10
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100- -100+ -3400-10*
La solution donnée par le tableau reste optimale si :
-100 - 0 -100
-100 100
-100 + 0 100
c’1 = c1+ = 300 + 200 c’1 400
L’intervalle d’optimalité: c1[200, 400]
10
La valeur du profit change: Z[2400, 4400]
Modification de variable C2
Etudions la variation du coefficient C2 relatif au profit à retirer
de la vente d’une table (C2= 200 €)
Considérons une variation du coefficient c2 de : C’2= C2+
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100 -100 -3400
Le tableau n’est plus optimal (on calcul les éléments de la dernière ligne)
11
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100+ -100-2* -3400-2*
12
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100+ -100-2* -3400-2*
La solution donnée par le tableau reste optimale si :
-100 + 0 100
-100 – 2* 0 -50
12
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6
x1 1 0 0 1 -1 10
x2 0 1 0 -1 2 2
Z 0 0 -100+ -100-2* -3400-2*
La solution donnée par le tableau reste optimale si :
-100 + 0 100
-50 100
-100 – 2* 0 -50
c’2 = c2+ = 200 + 150 c’2 300
L’intervalle d’optimalité: c2[150, 300]
12
La valeur du profit change: Z[3300, 3600]
Conclusion
La solution optimale reste stable (ne change pas) et prend
la même valeur (x1, x2)=(10, 2) tant que:
c1[200, 400]
c2 [150, 300]
13
La question qui se pose est la suivante:
14
La question qui se pose est la suivante:
Si on augmente ou on diminue la capacité
disponible d’une ressource (nombre d’heures
disponible dans chaque atelier) , quel est l’impact
sur la solution et la valeur de l’objectif ?
14
La question qui se pose est la suivante:
Si on augmente ou on diminue la capacité
disponible d’une ressource (nombre d’heures
disponible dans chaque atelier) , quel est l’impact
sur la solution et la valeur de l’objectif ?
Déterminer un intervalle dans lequel peut varier
le second membre bi d’une contrainte sans que
14
la solution optimale change.
Variation de b2
Dans le tableau optimal, la colonne correspondant à e2 nous donne les
coefficients de dans la colonne des termes de droite (b2).
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6 + 1*
x1 1 0 0 1 -1 10 + 1*
x2 0 1 0 -1 2 2 - 1*
Z 0 0 0 -100 -100 -3400 -100*
Les termes de droite sont toujours positifs (e1,x1,x2)
La base reste optimale tant que :
15
Variation de b2
Dans le tableau optimal, la colonne correspondant à e2 nous donne les
coefficients de dans la colonne des termes de droite (b2).
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6 + 1*
x1 1 0 0 1 -1 10 + 1*
x2 0 1 0 -1 2 2 - 1*
Z 0 0 0 -100 -100 -3400 -100*
Les termes de droite sont toujours positifs (e1,x1,x2)
La base reste optimale tant que :
6+ 0 -6
10+ 0 -10
2- 0 2
15
Variation de b2
Dans le tableau optimal, la colonne correspondant à e2 nous donne les
coefficients de dans la colonne des termes de droite (b2).
VB x1 x2 e1 e2 e3 bi
e1 0 0 1 1 -3 6 + 1*
x1 1 0 0 1 -1 10 + 1*
x2 0 1 0 -1 2 2 - 1*
Z 0 0 0 -100 -100 -3400 -100*
Les termes de droite sont toujours positifs (e1,x1,x2)
La base reste optimale tant que :
6+ 0 -6
-6 2
10+ 0 -10
2- 0 2
b’2 = b2 + = 22 + 16 b’2 24
15
La solution reste optimale tant que: b2[16, 22]
Tout changement au terme de droite (bi) d’une
contrainte saturée entrainera une modification de
la valeur de la fonction objectif
La valeur de Z change: Z[2800, 3200]
16
De même, on montre que la solution reste optimale
pour:
17
De même, on montre que la solution reste optimale
pour:
b1[14, +[, en effet au dessous de b1 = 14 la solution
optimale va changer.
17
De même, on montre que la solution reste optimale
pour:
b1[14, +[, en effet au dessous de b1 = 14 la solution
optimale va changer.
La 1ère contrainte n’est pas saturée (e1=6 0) donc la
valeur de Z ne change pas (Z=3400)
17
De même, on montre que la solution reste optimale
pour:
b1[14, +[, en effet au dessous de b1 = 14 la solution
optimale va changer.
La 1ère contrainte n’est pas saturée (e1=6 0) donc la
valeur de Z ne change pas (Z=3400)
b3[11, 14].
17
De même, on montre que la solution reste optimale
pour:
b1[14, +[, en effet au dessous de b1 = 14 la solution
optimale va changer.
La 1ère contrainte n’est pas saturée (e1=6 0) donc la
valeur de Z ne change pas (Z=3400)
b3[11, 14].
Comme la 3ème contrainte est saturée (e 3 = 0) donc la
valeur de Z change: Z[3300, 3600]
17
Si la solution optimale satisfait la nouvelle contrainte, le
problème admettra la même solution. Sinon
l’introduction de cette contrainte va engendrer une
nouvelle solution optimale.
18
Je vous remercie pour
votre attention
19
