Postoptimisation et analyse de sensibilité

• Ajout de contraintes

• Sensibilité du membre de droite

• Sensibilité de la fonction objectif

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 152

 Postoptimisation et analyse de sensibilité

La postoptimisation est l’ensemble des techniques permettant d’étudier le

comportement de la solution optimale d’un programme lors de la
modification de ses données (variations des coefficients, ajout/suppression
de variables/contraintes).

L’analyse de sensibilité se concentre sur l’étude du comportement de la

solution optimale d’un programme lors de la variation de ses données
(A, b, c). Plus précisément, elle cherche à déterminer dans quel intervalle
peut varier un coefficient sans que la base optimale ne change.

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 153

 Ajout de contraintes
Considérons le PL canonique de tableau optimal
Max z = 2x1 + x2 x1 x2 x3 x4 z
s.c. x1 + x2 ≤ 2 0 1 1/2 −1/2 0 1/2
T =
∗
x1 − x2 ≤ 1 1 0 1/2 1/2 0 3/2
x1 , x2 ≥ 0 0 0 3/2 1/2 1 7/2

Que devient la solution optimale si on ajoute la contrainte x1 ≤ 1 ?

• Sous forme standard, cette contrainte s’écrit

x1 + x5 = 1 avec x5 ≥ 0.
• Du tableau optimal, on tire x1 = 3/2 − 1/2x3 − 1/2x4, ainsi dans la base
B = {1, 2, 5} la contrainte s’écrit
−1/2x3 − 1/2x4 + x5 = −1/2.
J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 154
En introduisant l’équation précédente dans T ∗ on obtient
x1 x2 x3 x4 x5 z
0 1 1/2 −1/2 0 0 1/2
T1 = 1 0 1/2 1/2 0 0 3/2
0 0 −1/2 −1/2 −1/ 2 1 0 −1/2
0 0 3/2 1/2 0 1 7/2
Ce tableau n’est plus optimal mais il est dual-admissible. On peut donc
utiliser l’algorithme dual pour déterminer la nouvelle solution optimale.
Pivotant sur α34 = −1/2, il vient
x1 x2 x3 x4 x5 z
0 1 1 0 −1 0 1
T2 = 1 0 0 0 1 0 1
0 0 1 1 −2 0 1
0 0 1 0 1 1 3

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 155

 Sensibilité du membre de droite b

Rappelons que le tableau optimal a la forme

xD xE z

TB = B −1A B −1 0 B −1b

cB B −1A − cD cB B −1 1 cB B −1b

Si une composante de b est modifiée, seule la dernière colonne du tableau

change et ce dernier reste optimal tant que la solution basique primale reste
admissible.

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 156

Plus précisément, si la ie composante de b est modifiée, on a b# = b + δei
(où ei est la ie colonne de la matrice identité) et la base actuelle reste
optimale tant que

B −1b# = B −1 (b + δei) ≥ 0

autrement dit, tant que

δB −1
i ≥ −B −1
b = −β.

Dans l’expression précédente, B −1

i dénote la i e
colonne de l’inverse de la
matrice de base optimale B. Cette colonne se lit donc dans le tableau
optimal, en dessous de la ie variable d’écart !

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 157

 Exemple
Reprenons le problème canonique

Max z = 2x1 + x2
s.c. x1 + x2 ≤ 2
x1 − x2 ≤ 1
x1 ≤ 1
x1 , x2 ≥ 0
de tableau optimal

x1 x2 x3 x4 x5 z
0 1 1 0 −1 0 1
T∗ = 1 0 0 0 1 0 1
0 0 1 1 −2 0 1
0 0 1 0 1 1 3

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 158

Si b3 varie, la base actuelle reste optimale tant que

δB −1e3 ≥ −B −1b ⇐⇒ δB −1
3 ≥ −β

   
−1 1
   
⇐⇒ δ 1  ≥ − 1 
−2 1

 δ ≤ 1

⇐⇒ δ ≥ −1 ⇐⇒ −1 ≤ δ ≤ 1/2.

 δ ≤ 1/2

Actuellement b3 est égal à 1, la base {2, 1, 4} reste donc optimale tant que

b#3 ∈ [0, 3/2].

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 159
Si on cherche maintenant à calculer la sensibilité de b2, la base actuelle
reste optimale tant que

B −1 (b + δe2) ≥ 0 ⇐⇒ δB −1
2 ≥ −β
    
0 1 
 0 ≥ −1
   
⇐⇒ δ  0  ≥ −  1  ⇐⇒ 0 ≥ −1 ⇐⇒ δ ≥ −1.


1 1 δ ≥ −1

La valeur actuelle de b2 étant égale à 1, l’intervalle dans lequel peut varier

b2 sans changement de la base optimale est [0, ∞).

Remarque. Si la ie variable d’écart xn+i est basique à l’optimum et a la

valeur βj (c.-à.d. σ(j) = n + i), la base reste optimale tant que

b#i ∈ [bi − βj , ∞).

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 160
 Interprétation géométrique
b3 = 0 b3 = 1 b3 = 3/2
x2 x2 x2

z=2 z=3 z = 7/2

x1 x1 x1

x2 x2 x2

z=3 z=3 z=3

x1 x1 x1

b2 = 0 b2 = 1 b2 >> 1

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 161

 Interprétation des variables duales
En faisant varier b3 dans l’intervalle [0, 3/2] la base B = {2, 1, 4} reste
optimale mais la solution basique associée et, en particulier, les valeurs des
variables de décision, changent. Il en est de même de la valeur de la
solution optimale qui devient

z # = cB B −1 (b + δe3) = y (b + δe3)
= yb + δye3 = z ∗ + δy3 = 3 + δ.
On retrouve, évidemment, l’interprétation en termes de prix marginaux des
variables duales. À l’optimum, y3 = 1 et ce prix s’applique tant que la
modification δ de b3 reste dans l’intervalle [−1, 1/2].
Si b2 varie dans l’intervalle [0, ∞), seule la valeur de x4 est modifiée. En
particulier ni les valeurs optimales des variables de décision, ni la valeur
optimale du programme ne changent.
J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 162
 Sensibilité de la fonction objectif c

Considérons un tableau optimal dont les colonnes ont été réordonnées afin
d’isoler la base optimale

xN xB z

P
TB = B −1N I 0 B −1b

cB B −1N − cN 0 1 cB B −1b

Si une composante de c est modifiée, seule la dernière ligne du tableau

change et ce dernier reste optimal tant que la solution basique duale reste
admissible.
J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 163
Plus précisément, si la j e composante de c est modifiée, on a c# = c + δej
et la base actuelle reste optimale tant que

−γ #N = c#B B −1N − c#N ≥ 0.

Remarque. Ici, c désigne la fonction objectif du problème standard. On a

donc c = (cD cE ) = (cD 0).

Cas particulier. Si la variable xj est hors base, la situation est

particulièrement simple. La base et la solution basique actuelles restent
optimales tant que

δ ≤ −γj ⇐⇒ c#j ∈ (−∞, cj − γj ].

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 164

 Exemple
Rappelons que le PL initial qui nous intéresse est

Max z = 2x1 + x2
s.c. x1 + x2 ≤ 2
x1 − x2 ≤ 1
x1 ≤ 1
x1 , x2 ≥ 0
son tableau optimal étant

x1 x2 x3 x4 x5 z
0 1 1 0 −1 0 1
T∗ = 1 0 0 0 1 0 1
0 0 1 1 −2 0 1
0 0 1 0 1 1 3

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 165

La base optimale est B = {2, 1, 4}.
+ , + ,
On a donc N = {3, 5}, cB = 1 2 0 et cN = 0 0 .

Si on modifie le coefficient c1, actuellement égal à 2, cette base reste

optimale tant que

c#B B −1N − c#N ≥ 0

 
+ ,  1 −1  + , + ,
⇐⇒ 1 c1 0  0 1 − 0 0 ≥ 0 0
1 −2

+ , + ,
⇐⇒ 0 −1 + c1 ≥ 0 0 ⇐⇒ c1 ≥ 1
J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 166
Ainsi, tant que c1 ≥ 1, la base actuelle et sa solution basique associée
restent optimales. La valeur optimale du programme varie, elle, avec c1 et
est égale à
z ∗ = c1x1 + c2x2 = c1 + 1.

c1 = 1 c1 = 2 c1 → ∞
x2 x2 x2

z=3
z→∞
z=2

x1 x1 x1

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 167

 Sensibilité et dégénérescence

Considérons le PL canonique de représentation graphique

x2

Max z = 2x1 − x2
s.c. x1 + x2 ≤ 2
x1 − x2 ≤ 1
x1 ≤ 1 x1
x1 , x2 ≥ 0
z=2
La solution optimale x1 = 1, x2 = 0 de valeur z = 2 est associée aux trois
bases dégénérées :

B = {1, 2, 3} B # = {1, 3, 4} B ## = {1, 3, 5}

Cependant, seuls les tableaux associés à B et B # sont optimaux !

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 168
Dans la base B, le tableau est

x1 x2 x3 x4 x5 z
0 0 1 1 −2 0 1
TB = 1 0 0 0 1 0 1
0 1 0 −1 1 0 0
0 0 0 1 1 1 2

Le prix marginal de b3 est égal à 1 et est valable tant que

   
−2 1
   
δB −1e3 ≥ −β ⇐⇒ δ  1  ≥ −  1  ⇐⇒ 0 ≤ δ ≤ 1/2.
1 0

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 169

Dans la base B #, le tableau est

x1 x2 x3 x4 x5 z
0 1 1 0 −1 0 1
T B! = 1 0 0 0 1 0 1
0 −1 0 1 −1 0 0
0 1 0 0 2 1 2

Le prix marginal de b3 est égal à 2 et est valable tant que

   
−1 1
   
δ(B #)−1e3 ≥ −β ⇐⇒ δ  1  ≥ −  1  ⇐⇒ −1 ≤ δ ≤ 0.
−1 0

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 170

Dans la base B ##, le tableau est

x1 x2 x3 x4 x5 z
0 2 1 −1 0 0 1
T B !! = 1 −1 0 1 0 0 1
0 1 0 −1 1 0 0
0 −1 0 2 0 1 2

Dans ce tableau x5 est basique et la troisième contrainte n’est pas reconnue

comme active. Ainsi le prix marginal de b3 est nul et devrait le rester tant
que
δ(B ##)−1e3 ≥ −β ⇐⇒ δ ≥ 0.

Ceci n’est pas correct car pour δ ∈ [0, 1/2], le prix marginal de b3 est 1 et
non 0 !

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 171

 Objectifs

• Partant d’un tableau optimal, être capable d’ajouter de nouvelles

contraintes et de déterminer, si besoin est, le nouvel optimum.
• Pouvoir effectuer une analyse de sensibilité d’un coefficient du second
membre et de la fonction objectif dans les cas non dégénérés.

J.-F. Hêche, ROSO-EPFL Recherche opérationnelle SC & PH 172