6.

Analyse postoptimale
 Analyse postoptimale

• Mesurer l’influence sur la solution optimale de modifier

certains coefficients du problème
• Indiquer à l’utilisateur où mettre son énergie pour estimer avec
plus de précision les coefficients les plus critiques

• 6.1 Modification des coefficients de la fonction économique

• 6.2 Modification des termes de droite
• 6.3 Modification des contraintes
• 6.4 Introduction d’une nouvelle variable
• 6.5 Introduction d’une nouvelle contrainte
 6.1 Modification des coefficients de
la fonction économique
a) Le coût cj d’une variable hors base est modifié
cj devient c~j  c j  c j
Seul le coût relatif de la variable xj est influencé dans le tableau optimal
du simplexe.
En effet B et cB n’étant pas modifiés,  T
 c T
B B 1
n’est pas modifié, et
les coûts relatifs des autres variables restent donc identiques.
Le coût relatif de la variable xj devient
c~ j  (c j  c j )   T a  j  (c j   T a  j )  c j  c j  c j

La solution demeure optimale si

c~ j  c j  c j  0 ou c j  c j
 6.1 Modification des coefficients de
la fonction économique

b) Le coût c jr de la variable de base dans la ligne r est modifié

c devient c~  c  c
jr jr jr jr

Alors le coût relatif de toutes les variables est modifié comme suit.

Le vecteur des multiplicateurs est modifié:

c TB devient c~BT  [c j1 , c j2 , ..., c jr  c jr , ..., c jm ]
Alors ~ T  c~BT B 1

 c TB B 1  [0, 0, ...., c jr ,..., 0]B 1

  T  [0, 0, ...., c jr ,..., 0]B 1

 6.1 Modification des coefficients de
la fonction économique
~ T   T  [0, 0, ...., c jr ,..., 0]B 1
Ainsi pour j  j r ,
c~ j  c j  ~ T a  j
 c j   T a  j  [0, 0, ...., c jr ,..., 0]B 1 a  j
 c j  [0, 0, ...., c jr ,..., 0]a  j
 c j  c jr a rj

Pour j r
c~ jr  (c jr  c jr )   T a  jr  [0, 0, ...., c jr ,..., 0]B 1 a  jr
 (c jr   T a  jr )  c jr  [0, 0, ...., c jr ,..., 0]B 1 a  jr

 ( c j r  c j r )  c j r  0
 6.1 Modification des coefficients de
la fonction
En somme, la solution économique
demeure optimale si
Par conséquent  c j , la solution
 actuelle demeure  c j optimale si
max  : a rj  0  c jr  min  : a rj  0.
~
j 1, 2,..., n a rj c  c  c a  j0 1, 2,..., n aj rj
 1,2,..., n ;j  j r
j  jr  j j  j r
rj j  jr 

Mais j  j r tel que a rj  0

c~ j  c j  c jr a rj  0  c j  c jr a rj
cj
 c jr 
a rj

De façon similaire, j  j r tel que a rj  0

c~ j  c j  c jr a rj  0   c jr a rj  c j
cj cj
 c jr  
 a rj a rj
 6.1 Modification des coefficients de
la fonction économique
En somme, la solution demeure optimale si
cj  cj 
max  : a rj  0  c jr  min  : a rj  0.
j 1, 2,..., n a rj j 1, 2,..., n a rj
j  jr   j  jr  

Si z*  c TB b dénote la valeur optimale du problème original,

alors la valeur optimale du problème modifié devient
c~ T b  c T b  [0, 0, ...., c ,..., 0]b  z *  c b
B B jr jr r
 6.1 Modification des coefficients de
la fonction économique

Si la condition
 c j   c j 
max  : a rj  0  c jr  min  : a rj  0
j 1, 2,...,n  a rj  j 1, 2,...,n  a rj 
j  jr  j  jr 

n' est pas vérifiée, alors nous poursuivons la résolution

du problème modifié avec l' algorithme du simplexe.
 6.2 Modifications des termes de droite

Si le terme de droite br est modifié pour devenir br  br

Les termes de droite du tableau optimal deviennent

 b1   0    0  b1   1r 
          
 b2   0    0  b 2  
 2r 
      
1    
 1 1
  
    
B    B bB     br
 br  br   
br  b r    rr 
      
    
   
    
   
 b   0    
 0  b m    rm 
 m    
où  1r ,  2 r ,...,  rr ,...,  mr  T est la colonne r de B 1
Les termes de droite du tableau optimal deviennent
 b1   0    0  b1    1r 
          
 b2   0    0  b 2  
 2r 
      
1    
 1 1
  
    
B    B bB     br
 br  br   
br  b r    rr 
      
    
   
    
   
 b   0    
 m    0  b m    rm 

où  1r ,  2 r ,...,  rr ,...,  mr  T est la colonne r de B 1

Ainsi la solution de base actuelle demeure réalisable si

b i   ir br  0 i  1,2,..., m
c' est  à  dire
  b i    b i 
max  :  ir  0  br  min  :  ir  0.
i 1, 2,...,m   ir  i 1, 2 ,..., m   ir 

 6.2 Modifications des termes de droite

Ainsi la solution de base actuelle demeure réalisable si

b i   ir br  0 i  1,2,..., m
c' est  à  dire
  b i    b i 
max  :  ir  0  br  min  :  ir  0.
i 1, 2,...,m   ir  i 1, 2,...,m   ir 
 

Si la solution n’est plus réalisable sous l’effet du changement, nous

déterminons une nouvelle solution réalisable pour le problème modifié
avec l’algorithme dual du simplexe.
 6.3 Modification des contraintes

• Nous limitons notre étude au cas où les coefficients des variables hors base
peuvent être modifiés
Si le coefficient aij d' une variable hors base est modifié
pour devenir a ij  aij ,

alors le coût relatif de la variable hors base x j devient

  0   0 
     
       
~ T 
c j  c j    a  j  a ij    c j   a  j   a ij 
T T
   
       
    
 0 0
    
c' est  à  dire
c~  c   a .
j j i ij
 6.3 Modification des contraintes

La solution demeure optimale si

c~ j  c j   i aij  0
c' est  à  dire si
cj
aij  lorsque  i  0
i
cj
aij  lorsque  i  0
i
aij quelconque lorsque  i  0.

Si la solution n’est plus optimale, nous poursuivons la résolution du

problème modifié avec l’algorithme du simplexe.
 6.4 Introduction d’une nouvelle variable

Considérons le cas où nous voulons introduire une nouvelle variable xn+1

dont le coût unitaire est cn+1 et dont la colonne des coefficients est a n 1 .
Déterminons le coût relatif de x n 1
c n 1  c n 1   T a n 1 .

Si c n 1  c n 1   T an 1  0,
la solution actuelle avec x n 1  0 est optimale pour le problème modifié.
 6.4 Introduction d’une nouvelle variable

Considérons le cas où nous voulons introduire une nouvelle variable xn+1

dont le coût unitaire est cn+1 et dont la colonne des coefficients est a n 1 .
Déterminons le coût relatif de x n 1
c n 1  c n 1   T a n 1 .

Si c n 1  c n 1   T a n 1  0,
alors nous poursuivons la résolution du problème modifié avec
l' algorithme du simplexe.
La variable x n 1 devient variable d' entrée, et pour exécuter
le critère de sortie, nous devons calculer
a n 1  B 1 a n 1 .
 6.5 Introduction d’une nouvelle contrainte

a) Considéron s l' ajout d' une contrainte du type

n

a
j 1
m 1 j x j  bm1 .

Introduiso ns une variable d' écart x n 1 pour rendre la contrainte standard

n

a
j 1
m 1 j x j  x n 1  bm1 .
 6.5 Introduction d’une nouvelle contrainte

Le tableau associé à la solution optimale avant l’ajout de la nouvelle contraint

est modifié en introduisant la nouvelle contrainte dans

la ligne (m+1) du tableau.
La variable x n1 devient la variable de base dans la ligne  m  1 du tableau.
 a m1 jr

Pour rendre le coefficient de x jr égale à 0 dans la ligne que

nous ajoutons au tableau, il suffit de soustraire la ligne r
multipliée par a m 1 jr
 a m1 jr

Répétant la même opération pour chaque variable de base,

le coefficient de x j devient
m
a m 1 j  a m 1 j  a
r 1
m 1 jr a rj

et le terme de droite devient

m
b m 1  bm 1  a
r 1
m 1 jr br .
Le tableau ainsi modifié devient

m
Si b m 1  bm 1  a
r 1
m 1 jr br  0

alors la solution actuelle avec x m 1  b m 1

est une solution optimale du probleme modifié.
Le tableau ainsi modifié devient

m
Si b m 1  bm 1  a
r 1
m 1 jr b r  0,

alors la variable de base xm 1 dans la solution actuelle

est négative. Nous poursuivons la résolution du problème
modifié avec l' algorithme dual du simplexe.
 6.5 Introduction d’une nouvelle contrainte

b) Considéron s l' ajout d' une contrainte du type

n

a
j 1
m 1 j x j  bm1 .

Introduiso ns une variable d' écart x n 1 pour rendre la contrainte standard

n

a
j 1
m 1 j x j  x n 1  bm 1 .
 6.5 Introduction d’une nouvelle contrainte

Le tableau associé à la solution optimale avant l’ajout de la nouvelle contraint

est modifié en introduisant la nouvelle contrainte dans

la ligne (m+1) du tableau.
 a m 1 jr

Pour rendre le coefficient de x jr égale à 0 dans la ligne que

nous ajoutons au tableau, il suffit de soustraire la ligne r
multipliée par a m1 jr
 a m 1 jr

Répétant la même opération pour chaque variable de base,

le coefficient de x j devient
m
a m 1 j  a m1 j  a
r 1
m 1 jr a rj

et le terme de droite devient

m
b m1  bm 1  a
r 1
m 1 jr br .
Multiplions la dernière ligne du tableau par –1 pour que
xn+1 devienne variable de base dans cette ligne

m
Si  b m 1  bm 1  a
r 1
m 1 jr br  0

alors la solution actuelle avec x m 1  b m 1

est une solution optimale du probleme modifié.
Multiplions la dernière ligne du tableau par –1 pour que
xn+1 devienne variable de base dans cette ligne

m
Si  b m1  bm1  a
r 1
m 1 jr b r  0,

alors la variable de base x m 1 dans la solution actuelle

est négative. Nous poursuivons la résolution du problème
modifié avec l' algorithme dual du simplexe.
 6.5 Introduction d’une nouvelle contrainte

c) Considérons l' ajout d' une contrainte du type

n

a
j 1
m 1 j x j  bm 1 .
 6.5 Introduction d’une nouvelle contrainte

Le tableau associé à la solution optimale avant l’ajout de la nouvelle contraint

est modifié en introduisant la nouvelle contrainte dans

la ligne (m+1) du tableau.
 a m 1 jr

Pour rendre le coefficient de x jr égale à 0 dans la ligne que

nous ajoutons au tableau, il suffit de soustraire la ligne r
multipliée par a m1 jr
 a m 1 jr

Répétant la même opération pour chaque variable de base,

le coefficient de x j devient
m
a m 1 j  a m1 j  a
r 1
m 1 jr a rj

et le terme de droite devient

m
b m 1  bm1  a
r 1
m 1 jr br .
Le tableau ainsi modifié devient

Supposons que b m 1  0.
Pour identifier une solution de base du problème modifié,
choisissons un élément négatif dans la dernière ligne
sur lequel nous complétons un pivot.
 Le tableau ainsi modifié devient

Pour préserver la non négativité des coûts relatifs, nous choisissons l' élément
de pivot a m 1s comme dans l' algorithme dual du simplexe :
cs  c j 
 max  : a m 1 j  0
a m 1s 1 j  n  a m 1 j 

 Le tableau ainsi modifié devient

Si b m1  0, nousprocédons de la même façon après avoir multiplié

 
la ligne (m  1) par  1 pour retrouver un terme de droite  b m 1 négatif .
Le tableau résultant est comme suit

~
Si bi  0 i  1,2,..., m  1,
alors une solution optimale du problème modifié est
~
x j r  br r  1,2,..., m
~
x s  bm 1

Autrement nous poursuivons la résolution du problème

modifié avec l' algorithme dual du simplexe.