École Nationale Supérieur de Statistique et d’Économie Appliquée
(E.N.S.S.E.A)
Pôle universitaire de Kolea, tipaza.
Programmation Linéaire
Chapitre -6-
Analyse de sensibilité
Enseignant : F. DERMECHI
A l’attention des étudiants en 1ère année Master (Section 1)
2024 − 2025
Enseignant : F. DERMECHI Analyse de sensibilité
Introduction
L’optimisation d’un modèle de programmation linéaire à l’aide de l’algorithme du
simplexe et la détermination des valeurs marginales des ressources sont deux aspects
importants de cet outil puissant qu’est la programmation linéaire pour le
gestionnaire.
Toutefois le modèle et par conséquent l’optimum dépendent des paramètres aij, bi et
cj. Est-ce que les données associées à ces paramètres sont exactes ? Qu’advient il à la
solution optimale si par exemple un coefficient cj d’une variable de décision s’avère
inexact ou encore que la marge bénéficiaire est réduite cause d’une augmentation de
coûts ? De quelle façon la solution optimale est modifiée dans ce cas ?
La préoccupation du gestionnaire se résume à une question importante : dans quelle
mesure la solution optimale obtenue à l’aide des techniques de la programmation
linéaire est sensible à des modifications qui peuvent être apportées aux principaux
paramètres du modèle ?
Il existe des outils qui permettent d’évaluer la sensibilité de la solution optimale et
c’est ce qu’on appelle l’analyse de sensibilité qui consiste à déterminer les domaines
dans lesquels les données aij bi et cj peuvent varier tout en préservant l’optimalité de
la solution primaire.
1. Modification des coefficients de la fonction-objectif
A partir d’une solution de base optimale, supposons que le coefficient cj d’une
variable de décision xj est modifié. Supposons qu’il passe de la valeur cj à cj’.
𝑐𝑗′ = 𝑐𝑗 + ∆𝑐𝑗
Avec : ∆𝑐𝑗 est la variation du coefficient 𝑐𝑗 .
Est-ce que la solution demeure toujours optimale ?
Il faut distinguer deux cas selon que la variable 𝑥𝑗 est une variable hors base ou de
base.
1.1. Modification d’un coefficient pour une variable hors base
Dans ce cas, 𝑐𝐵 n’est pas affecté. Le seul terme du tableau qui sera modifié est 𝑐𝑗 − 𝑧𝑗
qui devient 𝑐𝑗′ − 𝑧𝑗 .
Cas de maximisation : la solution de base demeure optimale en autant que 𝑐𝑗′ − 𝑧𝑗 ≤
0, soit 𝑐𝑗′ ≤ 𝑧𝑗 . Ou encore la variation ∆𝑐𝑗 permise pour le coefficient 𝑐𝑗 est :
𝑐𝑗 + ∆𝑐𝑗 ≤ 𝑧𝑗
2
Enseignant : F. DERMECHI Analyse de sensibilité
∆𝑐𝑗 ≤ −(𝑐𝑗 − 𝑧𝑗 )
Si la valeur du coefficient objectif de la variable 𝑥𝑗 > 𝑧𝑗 , l’optimalité est détruite.
Cas de minimisation : la solution de base demeure optimale autant que 𝑐𝑗′ − 𝑧𝑗 ≥ 0
soit, 𝑐𝑗′ ≥ 𝑧𝑗 . Ou encore si ∆𝑐𝑗 ≥ −(𝑐𝑗 − 𝑧𝑗 ).
𝑀𝑎𝑥 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 … + 𝑐𝑛 𝑥𝑛
Soumises aux contraintes
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
.
.
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
𝑥1 , 𝑥2 … 𝑥𝑛 ≥ 0
A partir de la forme canonique du primal, on lui associe la forme canonique du Dual
dont, l’optimisation en est une minimisation avec des contraintes du type (≥) et des
variables toutes non négatives.
Exemple 1.1
Considérons le Programme Linéaire ci-dessous :
𝑀𝑎𝑥 𝑍 = 12𝑥1 + 20𝑥2
S/C
6𝑥1 + 10𝑥2 ≥ 60
8𝑥1 + 25𝑥2 ≥ 200
2𝑥1 + 8𝑥2 ≤ 80
𝑥1 , 𝑥2 ≥ 0
L’algorithme du Simplexe nous conduit au tableau optimal suivant :
Solution
CB VB 𝑥1 𝑥2 𝑆1 𝑆2 𝑒1
de base
12 𝑥1 1 4 0 0 ½ 40
0 𝑆1 0 14 1 0 3 180
0 𝑆2 0 7 0 1 4 120
Cj 12 20 0 0 0
Zj 12 48 0 0 6 Z=480
Cj − Z j 0 -28 0 0 -6
3
Enseignant : F. DERMECHI Analyse de sensibilité
Déterminons la plage de variation pour 𝑐2 . Du tableau optimal, on sait que :
𝑧2 = 48 et 𝑐2 − 𝑧2 = −28
On obtient donc :
−∞ < 𝑐2 < 𝑧2
−∞ < 𝑐2 < 48
Ou encore :
−∞ < ∆𝑐2 < −(𝑐2 − 𝑧2 )
−∞ < ∆𝑐2 < 28
La solution demeure optimale aussi longtemps que 𝑐2 varie entre −∞ et 48.
Exemple 1.2
Considérons le Programme Linéaire ci-dessous :
𝑀𝑎𝑥 𝑍 = 12𝑥1 + 20𝑥2
S/C
6𝑥1 + 10𝑥2 ≥ 60
8𝑥1 + 25𝑥2 ≥ 200
2𝑥1 + 8𝑥2 ≤ 80
𝑥1 , 𝑥2 ≥ 0
L’algorithme du Simplexe nous conduit au tableau optimal suivant :
Solution
CB VB 𝑥1 𝑥2 𝑆1 𝑆2 𝑒1
de base
12 𝑥1 1 4 0 0 ½ 40
0 𝑆1 0 14 1 0 3 180
0 𝑆2 0 7 0 1 4 120
Cj 12 20 0 0 0
Zj 12 48 0 0 6 Z=480
Cj − Z j 0 -28 0 0 -6
Déterminons la plage de variation pour 𝑐2 . Du tableau optimal, on sait que :
𝑧2 = 48 et 𝑐2 − 𝑧2 = −28
On obtient donc :
−∞ < 𝑐2 < 𝑧2
4
Enseignant : F. DERMECHI Analyse de sensibilité
−∞ < 𝑐2 < 48
Ou encore :
−∞ < ∆𝑐2 < −(𝑐2 − 𝑧2 )
−∞ < ∆𝑐2 < 28
La solution demeure optimale aussi longtemps que 𝑐2 varie entre −∞ et 48.
Exemple 1.3
Considérons le Programme Linéaire ci-dessous :
𝑀𝑖𝑛 𝑍 = 8𝑥1 + 10𝑥2 + 20𝑥3
S/C
5𝑥1 + 10𝑥2 + 20𝑥3 = 16 000
𝑥1 ≤ 400
𝑥2 ≤ 600
𝑥3 ≤ 600
𝑥1 + 𝑥2 + 𝑥3 ≤ 1 000
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
L’algorithme du Simplexe nous conduit au tableau optimal suivant :
CB VB 𝑥1 𝑥2 𝑥3 𝑒1 𝑒2 𝑒3 𝑒4 Solution de base
10 𝑥2 3/2 1 0 0 0 0 2 400
0 𝑒1 1 0 0 1 0 0 0 400
0 𝑒2 -3/2 0 0 0 1 0 -2 200
0 𝑒3 ½ 0 0 0 0 1 1 0
20 𝑥3 -1/2 0 1 0 0 0 -1 600
Cj 8 10 20 0 0 0 0
Zj 5 10 20 0 0 0 0 Z= 16 00
Cj − Z j 3 0 0 0 0 0 0
Déterminons les bornes de variation pour 𝑐1 qui permettent de maintenir une base
optimale. Du tableau optimal, on sait que :
𝑧1 = 5 et 𝑐1 − 𝑧1 = 3
On obtient donc :
𝑧1 < 𝑐1 < ∞
5 < 𝑐1 < ∞
Ou encore :
5
Enseignant : F. DERMECHI Analyse de sensibilité
−3 < ∆𝑐1 < ∞
Si la valeur de 𝑐1 est inférieure à 5, l’optimalité sera détruite, il faudra alors
introduire 𝑥1 dans la base.
1.2. Modification d’un coefficient pour une variable de base
Le changement d’un coefficient 𝑐𝑗 pour une variable 𝑥𝑗 dans la base optimale aura
cette fois une influence beaucoup plus importante puisque 𝑐𝐵 change et tous les
𝑧𝑗 = 𝑐𝐵 𝑢𝑗 sont modifiés pour les variables qui ne sont pas dans la base optimale (à
moins que 𝑢𝑖𝑗 = 0).
Par conséquent tous les termes 𝑐𝑗 − 𝑧𝑗 = 𝑐𝑗 − 𝑐𝐵 𝐵 −1 𝑎𝑗 du tableau peuvent être
modifiés. La solution demeure optimale si tous les 𝑐𝑗 − 𝑧𝑗 ≤≥ 0 .
La solution de base 𝑋𝐵 demeure optimale autant que le coefficient 𝑐𝐾 d’une variable
de décision 𝑥𝑘 dans la base n’excède pas les bornes de variation suivantes :
Cas de maximisation
𝑐𝑗 − 𝑧𝑗 𝑐𝑗 − 𝑧𝑗
𝑀𝑎𝑥 𝑐𝑘 + ≤ 𝑐𝑘 ≤ 𝑀𝑖𝑛 𝑐𝑘 +
𝑢ℓ𝑗 𝑢ℓ𝑗
𝑢ℓ𝑗 > 0, 𝑗 hors base 𝑢ℓ𝑗 < 0, 𝑗 hors base
𝑐𝑗 − 𝑧𝑗 𝑐𝑗 − 𝑧𝑗
𝑀𝑎𝑥 ≤ ∆𝑐𝑘 ≤ 𝑀𝑖𝑛
𝑢ℓ𝑗 𝑢ℓ𝑗
𝑢ℓ𝑗 > 0 𝑢ℓ𝑗 < 0
Cas de minimisation
𝑐𝑗 − 𝑧𝑗 𝑐𝑗 − 𝑧𝑗
𝑀𝑎𝑥 𝑐𝑘 + ≤ 𝑐𝑘 ≤ 𝑀𝑖𝑛 𝑐𝑘 +
𝑢ℓ𝑗 𝑢ℓ𝑗
𝑢ℓ𝑗 < 0, 𝑗 hors base 𝑢ℓ𝑗 > 0, 𝑗 hors base
𝑐𝑗 − 𝑧𝑗 𝑐𝑗 − 𝑧𝑗
𝑀𝑎𝑥 ≤ ∆𝑐𝑘 ≤ 𝑀𝑖𝑛
𝑢ℓ𝑗 𝑢ℓ𝑗
𝑢ℓ𝑗 < 0 𝑢ℓ𝑗 > 0
Exemple 1.4
6
Enseignant : F. DERMECHI Analyse de sensibilité
Considérons le Programme Linéaire ci-dessous :
𝑀𝑎𝑥 𝑍 = 66𝑥1 + 84𝑥2
S/C
3𝑥1 + 4𝑥2 ≤ 4200
𝑥1 + 3𝑥2 ≤ 2250
2𝑥1 + 2𝑥2 ≤ 2600
𝑥1 ≤ 1 100
𝑥1 , 𝑥2 ≥ 0
L’algorithme du Simplexe nous conduit au tableau optimal suivant :
CB VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑒4 Solution de base
66 𝑥1 1 0 -1 0 2 0 1000
84 𝑥2 0 1 1 0 -3/2 0 300
0 𝑒2 0 0 -2 1 5/2 0 350
0 𝑒4 0 0 1 0 -2 1 100
Cj 66 84 0 0 0 0
Zj 66 84 18 0 6 0 Z= 91 200
Cj − Z j 0 0 -18 0 -6 0
La base optimale est B = 𝑎1 , 𝑎2 , 𝑎4 , 𝑎6
a) Déterminer les limites de variation permises pour le coefficient objectif du
modèle.
On veut déterminer la plage de variation pour 𝑐1 . La variable de décision
correspondante (𝑥1 ) apparait dans la première ligne (ℓ = 1) du tableau.
- Détermination de la borne inférieure de 𝑐1
Il n’y a dans la première ligne, qu’un seul 𝑢1𝑗 > 0, pour les variables hors base, soit,
𝑢15 = 2 .
𝑐5 −𝑧5
𝑐1 = Borne inférieure de 𝑐1 = 𝑐1 +
𝑢 15
(−6)
= 66 + = 63
2
𝑐5 −𝑧5
Ou encore ∆𝑐1 =
𝑢15
= -3
- Détermination de la borne supérieure de 𝑐1
7
Enseignant : F. DERMECHI Analyse de sensibilité
Il en est de même pour la borne supérieure ; seulement l’élément 𝑢13 < 0
𝑐3 −𝑧3
𝑐1 = Borne supérieure de 𝑐1 = 𝑐1 +
𝑢 13
(−18)
= 66 + = 84
−1
𝑐3 −𝑧3
Ou encore ∆𝑐1 =
𝑢13
= −18
−1
= 18
La base actuelle demeure optimale tant et aussi longtemps que 𝑐1 est à l’intérieure de
l’intervalle suivant :
63 ≤ 𝑐1 ≤ 84
C’est dire :
−3 ≤ ∆𝑐1 ≤ 18
Autre manière de calculer ∆𝑐1
De la première ligne du tableau, on a 𝑐𝑗 ′ = 66 + ∆𝑐1 .
On sait que 𝑐𝑗 − 𝑧𝑗 = 𝑐𝑗 − 𝑐𝐵 𝑢𝑗 . Calculons les 𝑐𝑗 − 𝑧𝑗 pour les variables hors base. On
obtient pour 𝑥3 :
−1
1
𝑐3 − 𝑧3 = 𝑐3 − 𝑐𝐵 𝑢3 = 0 − (66 + ∆𝑐1 , 84, 0, 0) = − −66 − ∆𝑐1 + 84
−2
1
= −18 + ∆𝑐1
Dans le cas de la variable hors base 𝑥5 , on a :
2
−3/2
𝑐5 − 𝑧5 = 0 − 𝑐𝐵 𝑢5 = 0 − (66 + ∆𝑐1 , 84, 0, 0) = − 132 + 2∆𝑐1 − 126
5/2
−2
= −6 − 2∆𝑐1
La solution actuelle demeure optimale en autant que
(Variable 𝑥3 ) −18 + ∆𝑐1 ≤ 0 ⇒ ∆𝑐1 ≤ 18
(Variable 𝑥5 ) −6 − 2∆𝑐1 ≤ 0 ⇒ ∆𝑐1 ≥ −3
Par conséquent, −3 ≤ ∆𝑐1 ≤ 18
8
Enseignant : F. DERMECHI Analyse de sensibilité
b) Quelle sera la variable entrante dans la base si ∆𝑐1 > 18, disons ∆𝑐1 = 19 (𝑐1
passe de 66 à 85) ?
La variable 𝑥3 puisque 𝑐3 − 𝑧3 = −18 + ∆𝑐1 = −18 + 19 = 1 > 0 ; on détruit
l’optimalité.
c) Quelle sera la variable entrante dans la base si ∆𝑐1 < −3, disons ∆𝑐1 = −4 (𝑐1
passe de 66 à 62) ?
Dans ce cas c’est la variable 𝑥5 puisque 𝑐5 − 𝑧5 = −6 − 2∆𝑐1 = −6 − 2(−4) = 2 > 0 ;
on détruit l’optimalité.
d) Déterminer la plage de variation pour 𝑐2
La variable de décision correspondante est 𝑥2 apparait dans la 2 éme ligne du
tableau optimal (ℓ = 2).
On a 𝑢23 > 0 et 𝑢25 < 0
La borne inférieure pour ∆𝑐2 est obtenue de
𝑐3 −𝑧3 −18
(Variable 𝑥3 ) ∆𝑐2 = = = -18 ; (18 − ∆𝑐2 ≤ 0)
𝑢 23 1
La borne supérieure pour ∆𝑐2 est obtenue de
𝑐5 −𝑧5 −6 3
(Variable 𝑥5 ) ∆𝑐2 = = =4 ; (−6 + ∆𝑐2 ≤ 0)
𝑢 25 −3/2 2
Ce qui nous donne :
−18 ≤ ∆𝑐2 ≤ 4
Avec 𝑐2 = 84 :
66 ≤ 𝑐2 ≤ 88
Limites de validité de l’optimum pour 𝑐1 et 𝑐2
Valeur Limite Limite Variable Variable
𝑐𝑗
actuelle inférieure suépérieure entrante sortante
𝑐1 66 63 84 𝑥5 𝑥3
𝑐2 84 66 88 𝑥3 𝑥5
2. Modification du second membre des contraintes
Soit le programme linéaire suivant :
9
Enseignant : F. DERMECHI Analyse de sensibilité
Max (Z) = cX
S/C
AX = b
X≥0
Considérons que l’optimisation du modèle à une solution optimal XB= B-1b et Z= cB XB.
On voit qu’une variation du second membre b affectera la solution XB (ainsi que Z).
La ligne cj-zj ne sera pas affectée puisque B est toujours la base de la solution actuelle.
Nous devons nous préoccuper de la faisabilité de la solution actuelle (XB ≥ 0) et non
pas du critère d’optimalité.
Détermination des limites de variation pour le second membre b
On sait que XB= B-1b= 𝑏. Notons par Bij , les éléments de B-1. L’expression algébrique
de XB est alors :
Supposons qu’on apporte ne modification à 𝑏𝑘 de ∆𝑏𝑘 :𝑏𝑘′ = 𝑏𝑘 + ∆𝑏𝑘 . Alors le second
membre b est remplacé par b’ et la nouvelle solution sera : 𝑋𝐵′ = 𝐵 −1 𝑏 ′ et 𝑏 ′ = 𝑏 +
∆𝑏. La solution devient alors : 𝑋𝐵′ = 𝐵 −1 𝑏 + 𝐵 −1 ∆𝑏.
Si la nouvelle solution 𝑋𝐵′ = 𝐵 −1 𝑏 ′ ≥ 0 alors la base actuelle demeure optimale et les
nouvelles valeurs de la solution de base sont données par 𝑋𝐵′ et 𝑍 = 𝑐𝐵 𝑋𝐵′ .
Si la nouvelle solution 𝑋𝐵′ = 𝐵 −1 𝑏 ′ < 0, alors la solution n’est pas réalisable.
𝑋𝐵′ 𝑖 = 𝑋𝐵𝑖 + 𝐵𝑖𝑘 ∆𝑏𝑘 , 𝑖 = 1 … 𝑚
Nouvelle solution= Ancienne solution + 𝐵𝑖𝑘 ∆𝑏𝑘
Pour que cette solution soit réalisable, il faut que : 𝑋𝐵𝑖 + 𝐵𝑖𝑘 ∆𝑏𝑘 ≥ 0 et puisque
𝑋𝐵𝑖 ≥ 0 donc, 𝐵𝑖𝑘 ∆𝑏𝑘 ≥ 0.
Limites de variation du second membre bk
Limite inférieure Limite supérieure
𝑋𝐵 𝑖 𝑋𝐵 𝑖
Max 𝑏𝑘 − ≤ bk ≤ Min 𝑏𝑘 −
𝐵𝑖𝑘 𝐵𝑖𝑘
𝐵𝑖𝑘 > 0 𝐵𝑖𝑘 < 0
10
Enseignant : F. DERMECHI Analyse de sensibilité
𝑋𝐵 𝑖 𝑋𝐵 𝑖
Max − ≤ ∆bk ≤ Min −
𝐵𝑖𝑘 𝐵𝑖𝑘
Exemple 2.1
Considérons le Programme Linéaire de l’exemple (1.2.1). Depuis le tableau optimal
on a :
−1 0 2 0
1 0 −3/2 0
𝐵 −1 =
−2 1 5/2 0
1 0 −2 1
↑ ↑ ↑ ↑
𝑢3 𝑢4 𝑢5 𝑢6
Dans le cas de la variation sur b1 , on s’intéresse aux éléments de 𝑢3 de 𝐵 −1 , c'est-à-
dire aux éléments de la première colonne de 𝐵 −1 .
𝑋𝐵 𝑖
La borne inférieure de b1 = max 𝑏1 − , 𝐵𝑖1 > 0
𝐵𝑖1
Les éléments positifs de la première colonne de 𝐵 −1 sont : 𝐵21 = 1 et 𝐵41 = 1.
𝑋𝐵 2 𝑋𝐵 4
La borne inférieure de b1 = max 𝑏1 − , 𝑏1 −
𝐵21 𝐵41
300 100
= max 4200 − , 4200 − = 4100
1 1
Ou encore ∆𝑏1 = −100
𝑋𝐵 𝑖
La borne supérieure de b1 = min 𝑏1 − , 𝐵𝑖1 < 0
𝐵𝑖1
Les éléments négatifs de la première colonne de 𝐵 −1 sont : 𝐵11 = −1 et 𝐵31 = −2
𝑋𝐵 1 𝑋𝐵 3
La borne supérieure de b1 = min 𝑏1 − , 𝑏1 −
𝐵11 𝐵31
1000 350
= min 4200 − , 4200 − = 4375
−1 −2
Ou encore ∆𝑏1 = +175
Les limites de variation permises pour le b1 est :
4100 ≤ 𝑏1 ≤ 4375
−100 ≤ ∆𝑏1 ≤ 175
On peut également préciser la variable qui devient nulle pour chaque limite de b1.
11
Enseignant : F. DERMECHI Analyse de sensibilité
A la limite inférieure, on a ∆𝑏1 = −100 et :
𝑋𝐵2 = 𝑥2 = 300 + 1 −100 = 200
𝑋𝐵4 = 𝑒4 = 100 − 100 = 0
Si ∆𝑏1 < −100 , la variable 𝑒4 devient négative, on dit qu’à la limite inférieure, la
variable sortante est 𝑒4 .
Pour la limite supérieure, on a ∆𝑏1 = +175
𝑋𝐵1 = 𝑥1 = 1000 − 1 −175 = 825
𝑋𝐵3 = 𝑒2 = 350 − 2 (175) = 0
La variable sortante à cette limite est 𝑒2 .
3. Ajout d’une nouvelle variable de décision
Considérons maintenant le cas ou l’on veut ajouter une variable de décision, c’est
dire ajouter une activité dans le modèle de programmation linéaire. Notons par xn+1,
la variable de décision correspondante avec un coefficient économique cn+1. Les
éléments des contraintes fonctionnelles associées à cette activité xn+1 sont identifiés
par an+1.
Puisque nous avons déjà obtenu une solution optimale au modèle sans cette nouvelle
activité comment peut-on déterminer si la variable de décision xn+1 permettrait
d’améliorer la valeur de la fonction-objectif, sans ré-optimiser le modèle à nouveau.
Pour déterminer si la base actuelle est optimale, il faut évaluer cn+1 - zn+1. On sait
que :
𝑧𝑛+1 = 𝑐𝐵 𝑢𝑛+1
𝑢𝑛 +1 = 𝐵 −1 𝑎𝑛+1
𝑐𝑛+1 − 𝑧𝑛+1 = 𝑐𝑛+1 − 𝑐𝐵 𝐵 −1 𝑎𝑛+1
Pour le cas de maximisation : la base actuelle demeure optimale si 𝑐𝑛+1 − 𝑧𝑛+1 ≤ 0.
La variable xn+1 demeure alors une variable hors base (xn+1=0). D’autre part si
𝑐𝑛+1 − 𝑧𝑛+1 > 0, l’optimalité est détruite. On doit introduire la variable xn+1 dans la
base et l’algorithme du simplexe pour déterminer une nouvelle solution optimale.
Pour le cas de minimisation : la base actuelle demeure optimale si 𝑐𝑛+1 − 𝑧𝑛+1 ≥ 0.
Dans ce cas, la variable xn+1 demeure une variable hors base. Si 𝑐𝑛+1 − 𝑧𝑛+1 < 0, la
12
Enseignant : F. DERMECHI Analyse de sensibilité
variable xn+1 est introduite dans la base et l’algorithme du simplexe est appliquée
pour déterminer la nouvelle solution optimale.
Exemple 3.1
Considérons le Programme Linéaire de l’exemple (1.2.1). IL s’agit d’une entreprise
souhaitons introduire un modèle intermédiaire sur le marché et dont le bénéficie est
de 68Um l’unité. Le marché est en état d’absorber toute la production. La fabrication
de ce modèle exige 2.4 heures pour l’assemblage lors de la phase 1 et 2 heures pour la
vérification et l’empaquetage lors de la phase 2. Est-ce qu’il serait rentable pour
l’entreprise d’assembler ce nouveau modèle ?
Nous reprenons le tableau optimal sans le nouveau modèle :
CB VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑒4 Solution de base
66 𝑥1 1 0 -1 0 2 0 1000
84 𝑥2 0 1 1 0 -3/2 0 300
0 𝑒2 0 0 -2 1 5/2 0 350
0 𝑒4 0 0 1 0 -2 1 100
Cj 66 84 0 0 0 0
Zj 66 84 18 0 6 0 Z= 91 200
Cj − Z j 0 0 -18 0 -6 0
Identifions par xno , la variable de décision associée ce nouveau modèle. On sait que
cno = 68 et ano = [2.4, 1.8, 2, 0]T
Du tableau optimal on a :
−1 0 2 0
1 0 −3/2 0
𝐵−1 =
−2 1 5/2 0
1 0 −2 1
Déterminons uno=𝐵−1 ano
−1 0 2 0 2.4 8/5
1 0 −3/2 0 1.8 −3/5
𝑢𝑛𝑜 = =
−2 1 5/2 0 2 2
1 0 −2 1 0 −8/5
8/5
−3/5
𝑧𝑛𝑜 = 𝑐𝐵 𝑢𝑛𝑜 = 66 84 0 0 = 55.2
2
−8/5
𝑐𝑛𝑜 −𝑧𝑛𝑜 = 68 − 55.2 = 12.8 > 0
13
Enseignant : F. DERMECHI Analyse de sensibilité
La base actuelle n’est plus optimale, il faut introduire 𝑥𝑛𝑜 dans la base.
Ajoutons d’abord la colonne (uno) dans le tableau du Simplexe :
CB VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑒4 xno Solution de base
66 𝑥1 1 0 -1 0 2 0 8/5 1000
84 𝑥2 0 1 1 0 -3/2 0 -3/5 300
0 𝑒2 0 0 -2 1 5/2 0 2 350
0 𝑒4 0 0 1 0 -2 1 -8/5 100
Cj 66 84 0 0 0 0 340/5
Zj 66 84 18 0 6 0 276/5 Z= 91 200
Cj − Z j 0 0 -18 0 -6 0 64/5
64
Le tableau n’est pas optimal puisque 𝑐𝑛𝑜 −𝑧𝑛𝑜 = 5
>0
Appliquons l’algorithme du Simplexe :
Variable entrante xno et la variable sortante est e2 . Le pivot P : u3, no=2
CB VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑒4 xno Solution de base
66 𝑥1 1 0 3/5 -4/5 0 0 0 720
84 𝑥2 0 1 2/5 3/10 -3/4 0 0 405
68 𝑥𝑛𝑜 0 0 -1 ½ 5/4 0 1 175
0 𝑒4 0 0 -3/5 4/5 0 1 0 380
Cj 66 84 0 0 0 0 68
Zj 66 84 26/5 32/5 22 0 68 Z = 93 440
Cj − Z j 0 0 -26/5 -32/5 -22 0 0
Le tableau est optimal, tous les 𝑐𝑗 −𝑧𝑗 ≤ 0.
4. Ajout d’une nouvelle contrainte
Examinons la situation ou l’on doit ajouter une contrainte au modèle. Considérons
que B est la base optimale avec XB = B-1b = 𝑏 , avant que la contrainte :
𝑎𝑚 +1 𝑥1 + 𝑎𝑚 +1 𝑥2 + ⋯ + 𝑎𝑚 +1 𝑥𝑛 ≤ 𝑏𝑚 +1 ,
a été ajoutée dans le modèle
L’ajout de la variable d’écart 𝑥𝑛+1 donne :
𝑎𝑚 +1 𝑥1 + 𝑎𝑚 +1 𝑥2 + ⋯ + 𝑎𝑚 +1 𝑥𝑛 + 𝑥𝑛+1 = 𝑏𝑚 +1
Et : 𝑥𝑛+1 = 𝑏𝑚 +1 − 𝑎𝑚 +1 𝑥1 + 𝑎𝑚 +1 𝑥2 + ⋯ + 𝑎𝑚 +1 𝑥𝑛
On peut vérifier si la solution actuelle XB est toujours optimale par substitution :
14
