Analyse de sensibilité

1. Analyse de sensibilité sur les quantités

On va travailler sur le même exemple vu au début du chapitre (entreprise qui fabrique des
chaises, des tables et des armoires et qui dispose de 60m3 de bois, 40 H d’assemblage et 80H
de finition)
Max Z = 2x1 + 4x2 + 3x3
⎧3x + 4x + 2x ≤ 60
⎪ 1 2 3

⎪2x1 + x2 + 2x3 ≤ 40
S /C⎨
⎪ x1+ 3x2 + 2x3 ≤ 80
⎪x , x , x ≥ 0
⎩ 1 2 3

Le tableau optimal est le suivant :

7 8 8 0 0 0
VB
x1 x2 x3 s1 s2 S3 Q
4 x2 1/3 1 0 1/3 -1/3 0 20/3
3 x3 5/6 0 1 -1/6 2/3 0 50/3
0 S3 -5/3 0 0 -2/3 -1/3 1 80/3
zj 23/6 4 3 5/6 2/3 0
280/3
dzj=Cj-Zj -11/6 0 0 --5/6 -2/3 0

Maintenant au lieu d’avoir 60 pour la quantité de la première contrainte b1=60 on veut connaître
dans quel intervalle b1 doit varier pour que la BASE optimale reste inchangée.

Est-ce qu’il y a dans le tableau optimal de simplexe la valeur de b1=60 ? NON

Est-ce que le changement de b1 intervient dans les Cj-Zj ? NON

Alors où pourrait intervenir le b1 ? et dans quelle matrice ?

1/3 −1/3 0 𝑏1
En fait b1 va intervenir dans le vecteur quantité AB-1.b = !−1/6 2/3 0) !40) =
−2/3 −1/3 1 80
!" $%
#
− #
⎛ &%⎞
⎜−𝑏1/6 + # ⎟
'!" '%%
− +
⎝ # # ⎠
Comment j’ai trouvé le AB-1 ? c’est simple : selon la forme standard As = Id = matrice Identité donc la
matrice des variables (S1 S2 S3) dans le tableau de simplexe est AB-1.AS = AB-1.Id = AB-1=
1/3 −1/3 0
!−1/6 2/3 0).
−2/3 −1/3 1

𝑏1 60
C’est quoi le vecteur !40) ? En fait, c’est le vecteur b=!40) mais comme on est en train de faire
80 80
l’analyse de sensibilité sur b1, j’ai remplacé le 60 par b1.

!" $%
#
− #
⎛ &%⎞
Maintenant, j’ai trouvé la matrice ⎜−𝑏1/6 + # ⎟. Quelle est la condition sur cette matrice pour que
'!" '%%
− +
⎝ # # ⎠
la base reste optimale ?

En effet, il faut que les quantités soient positives pour que la base reste optimale.

On résout donc un système issu de la matrice des quantités pour trouver l’intervalle de b1 :
!" $%
⎧ # − # ≥0
⎪ 𝑏1 ≥ 40
&%
−𝑏1/6 + # ≥ 0 et on obtient ;𝑏1 ≤ 160 ce qui donne 40 ≤ 𝑏1 ≤ 100
⎨ '!" '%% 𝑏1 ≤ 100
⎪− + ≥ 0
⎩ # #

__________40_________100____________160__________

Interprétation : tant que b1 appartient à l’intervalle [40,100], l’entreprise suit la même politique de
production : la base reste optimale (même variables de base : X1*=0 : ne pas produire des chaises et
produire des tables et des armoires)

2. Ajout d’une nouvelle variable de décision

L’addition d’une nouvelle activité implique le rajout d’une nouvelle variable de décision qui possède
un coefficient économique (profit dans la fonction objectif) et des coefficients technologiques (dans
les contraintes). La question est de déterminer si l’addition de cette nouvelle activité (variable) va
améliorer la valeur optimale de la fonction objectif ou pas. En cas d’amélioration de la valeur
optimale de la fonction objectif, la solution du dernier tableau du simplexe ne sera plus optimale et
pourra être augmentée dans le cas d’une maximisation ou diminuée dans le cas d’une minimisation.
Dans le cas contraire, cette nouvelle activité n’aura aucun impact sur la solution optimale.

2.1. Comment savoir si la nouvelle activité va améliorer la fonction objectif ?

L’introduction d’une nouvelle variable de décision induit le rajout d’une nouvelle contrainte
duale. Dans le cas où cette nouvelle variable de décision améliore la valeur optimale de la
fonction objectif, cette dernière sera revue à la hausse pour une maximisation (Z’ > Z) ou à
la baisse pour une minimisation (C’< C).
 En pratique, il convient d’écrire la nouvelle contrainte duale associée à la nouvelle variable
de décision. Si cette nouvelle contrainte est vérifiée, Z (ou C) reste la valeur optimale de la
fonction objectif. Dans le cas contraire, c'est-à-dire la contrainte duale n’est pas vérifiée, Z’
(ou C’) devient la valeur optimale de la fonction objectif.

NB : La forme canonique (Max sous <= OU Min sous >=) doit être respectée pour le passage
primal / Dual.

2.2. Comment déterminer les coefficients technologiques de la nouvelle variable de décision

pour le tableau optimal du simplexe ?
Rajouter une nouvelle variable de base implique qu’il faut rajouter une colonne au tableau
du simplexe dans laquelle sont notés les coefficients technologiques de cette variable. Les
coefficients technologiques fournis pour la nouvelle variable de décision sont celles du 1er
tableau du simplexe. Pour une nouvelle base, ces coefficients doivent être multipliés par la
matrice AB-1 qui a permis le changement de base.

2.3. Exemple

Soit le Programme linéaire suivant et son tableau optimal

Max Z = 7 x1 + 8 x2 + 8 x3
ì3x1 + 2 x2 + 4 x3 £ 10
ï
S / C í3x1 + 3x2 + x3 £ 16
ïx , x , x ³ 0
î 1 2 3

7 8 8 5 0 0
VB
x1 x2 x3 X4 s1 s2 Q
8 x2 3/2 1 2 ? 1/2 0 5
0 s2 -3/2 0 -5 ? -3/2 1 1
zj 12 8 16 4 0
40
dzj -5 0 -8 -4 0

Est-il profitable d’introduire une nouvelle variable x4 ayant les

caractéristiques suivantes :
æ1ö
c4 = 5; a4 = ç ÷
è5ø
La contrainte duale associée à cette nouvelle variable est : y1 + 5 y2 ³ 5
Dans la ligne dzj du tableau optimal, on lit directement que y1 = 4 et y2 =0. Par
conséquent, y1 + 5 y2 = 4 <5. La contrainte duale n’est donc pas vérifiée. On en conclut
qu’il est profitable d’introduire cette nouvelle variable de décision.

Pour introduire cette nouvelle variable, il est nécessaire de déterminer ses coefficients
dans le tableau optimal. Les variables de base du 1er tableau du simplexe sont {s1, s2}. La
matrice AB-1 qui a permis le changement de base se lit directement dans les colonnes s1
et s2 du tableau optimal.

æ 1 ö
ç 0÷
AB -1 = ç 2 ÷
ç- 3 1 ÷÷
ç
è 2 ø

Les coefficients technologiques de x4 dans le tableau optimal sont :

æ a '14 ö æ 1 ö
ç ÷=ç ÷
è a '24 ø è 5 ø
æ 1 ö æ1ö
ç 0÷
æ a ö æ1ö ç 2 ÷
AB -1 * ç 14 ÷ = ç 2 ÷ç ÷ = ç ÷
è a24 ø ç - 3 5 7
1 ÷÷ è ø çç ÷÷
ç
è 2 ø è2ø

On obtient le tableau suivant dans lequel le dzj de x4 >0 :

7 8 8 5 0 0
VB
x1 x2 x3 x4 s1 s2 Q RT
8 x2 3/2 1 2 1/2 1/2 0 5 10
0 s2 -3/2 0 -5 7/2 -3/2 1 1 2/7
zj 12 8 16 4 4 0
40
dzj -5 0 -8 1 -4 0

x4 entre dans la base en remplacement de s2

La valeur de la fonction objectif peut être améliorée par l’introduction de la variable de

décision x4 à la place de s2. La nouvelle solution devient :

7 8 8 5 0 0
VB
x1 x2 x3 x4 s1 s2 Q
8 x2 12/7 1 19/7 0 5/7 -1/7 34/7
5 x4 -3/7 0 -10/7 1 -3/7 2/7 2/7
zj 81/7 8 101/7 5 25/7 2/7
282/7
dzj -32/7 0 -45/7 0 -25/7 -2/7
3. Ajout d’une nouvelle contrainte

L’addition d’une nouvelle contrainte à un programme linéaire implique deux possibilités :

- La nouvelle contrainte n’a aucun effet sur la solution optimale qui reste la même.
- La solution optimale devient non réalisable.

3.1. Comment savoir si la nouvelle contrainte va impacter la solution optimale ?

Il suffit de remplacer les variables de décision par leurs valeurs optimales dans la nouvelle
contrainte. Si la contrainte est vérifiée, elle n’aura aucun impact sur la solution optimale.
Dans le cas contraire, la solution optimale deviendra non réalisable après l’introduction de
cette nouvelle contrainte

3.2. Comment retrouver la nouvelle solution optimale si la nouvelle contrainte n’est pas
vérifiée ?

Rajouter une nouvelle contrainte implique rajouter une nouvelle variable de base (qui est la
variable d’écart dans le tableau optimal , c'est-à-dire qu’il faut rajouter une nouvelle ligne au
tableau du simplexe avec cette variable d’écart comme VB. Mais cette variable d’écart n’a
aucun effet sur les Cj-Zj. En regardant attentivement le tableau optimal on remarque que
tout est en ordre sauf certaines variables de base n’ont pas le vecteur identité. Donc Il
faudra effectuer des combinaisons linéaires avec la variable de base en question pour
retrouver la matrice identité pour les variables de base.
Généralement, on obtiendra un tableau non réalisable avec des quantités négatives pour la
nouvelle variable de base. Pour retrouver la nouvelle solution on a recours à l’algorithme du
dual-simplexe.
3.3. Exemple

Soit le Programme linéaire suivant et son tableau optimal

Max Z = 15 x1 + 40 x2 + 12 x3
ì6 x1 + 10 x2 + 2 x3 £ 60
ï
S / C í2 x1 + 10 x2 + 6 x3 £ 140
ïx , x , x ³ 0
î 1 2 3

15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 S3 Q
40 x2 8/10 1 0 3/20 -1/20 0 2
12 x3 -1 0 1 -1/4 1/4 0 20
0 S3 3 10 4 0 0 1 95
zj 20 40 12 3 1 0
320
dzj -5 0 0 -3 -1 0
Soit la contrainte suivante : 3x1 + 10x2 +4x3 ≤ 95.
Sachant que x1 = 0 ; x2 = 2 et x3 =20, 3x1 + 10x2 +4x3 = 100 > 95.
La contrainte n’est pas vérifiée et son introduction dans le programme linéaire entrainera
un changement de la solution optimale.

Nouveau tableau du simplexe :

15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 s3 Q
40 x2 8/10 1 0 3/20 -1/20 0 2
12 x3 -1 0 1 -1/4 1/4 0 20
0 s3 3 10 4 0 0 1 95
zj 20 40 12 3 1 0
320
dzj -5 0 0 -3 -1 0

On remarque que les coefficients technologiques des variables de base ne forment pas une
matrice identité (les cases en gris doivent être égales à 0):

15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 s3 Q
40 x2 8/10 1 0 3/20 -1/20 0 2
12 x3 -1 0 1 -1/4 1/4 0 20
0 s3 3 10 4 0 0 1 95
zj 20 40 12 3 1 0
320
dzj -5 0 0 -3 -1 0
Traitement de la colonne x2 : Ligne 3 -10 * ligne 1

15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 s3 Q
40 x2 8/10 1 0 3/20 -1/20 0 2
12 x3 -1 0 1 -1/4 1/4 0 20
0 s3 -5 0 4 -3/2 1/2 1 75
zj 20 40 12 3 1 0
320
dzj -5 0 0 -3 -1 0

Traitement de la colonne x3 : Ligne 3 -4 * ligne 2

 15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 s3 Q
40 x2 8/10 1 0 3/20 -1/20 0 2
12 x3 -1 0 1 -1/4 1/4 0 20
0 s3 -1 0 0 -1/2 -1/2 1 -5
zj 20 40 12 3 1 0
320
dzj -5 0 0 -3 -1 0

la solution n’est pas réalisable puisqu’une quantité est négative. On applique l’algorithme
du dual-simplexe.

15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 s3 Q
40 x2 8/10 1 0 3/20 -1/20 0 2
12 x3 -1 0 1 -1/4 1/4 0 20
0 s3 -1 0 0 -1/2 -1/2 1 -5
zj 20 40 12 3 1 0
320
Cj-Zj=dzj -5 0 0 -3 -1 0
RT=
Cj-Zj / 5 - - 6 2 0
Colpivot

s2 remplace s3. Après changement de base, on obtient le tableau optimal suivant :

15 40 12 0 0 0
VB
x1 x2 x3 s1 s2 s3 Q
40 x2 9/10 1 0 1/5 0 -1/10 5/2
12 x3 -3/2 0 1 -1/2 0 1/2 35/2
0 s2 2 0 0 1 1 -2 10
zj 18 40 12 2 0 2
310
dzj -3 0 0 -2 0 -2