close

Se connecter

Se connecter avec OpenID

6.5 Introduction d`une nouvelle contrainte

IntégréTéléchargement
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
Illustration des principes avec l'exem ple suivant:
T ableau initial
M in
VB
x1
x2
x3
x4
x4
6
5
8
1
x 5 10
20
10
x6
x5
x6
TD
S ujet à
1
6 x1 
x1 , x 2 , x 3  0
8
6
1
0
T ableau optim al
V B x1
x2
1
z
x3

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35
2


1
11


x6
z
x4
7
x6
x1
x2
8
x1
150
1
5 x 2  8 x 3  60
10 x1  20 x 2  10 x 3  150
60
1
 z  5  4.5
z
 5 x1  4.5 x 2  6 x 3
TD
11
1
1
360
7
6.1 Modification des coefficients de
la fonction économique
a)
Le coût cj d’une variable hors base est modifié
cj
c~ j  c j   c j
devient
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 BT B  1 n’est pas modifié, et
les coûts relatifs des autres variables restent donc identiques.
T
Le coût relatif de la variablec xj devient
c  a
l
l
l
c j  ( c j   c j )   a j  (c j   a j )   c j  c j   c j
T
T
La solution demeure optimale si
c j  c j  c j  0
ou
c j  c
j
Si la condition n’est pas vérifiée, alors nous poursuivons
la résolution du problème modifié avec l’algorithme du simplexe
en utilisant xj comme variable d’entrée.
T ableau optim al
V B x1
x2
x2

1
x5
1
3
30
7
35
7
2
1
7
7
14
7
de la variable hors-base x 3
11
2
1
45
c3  c3   c3   6   c3
7
7
14
7
4
11
1
7
14
35
2


1
11
z


x6
z
x4
7
x6
x1
x3
TD
c j  c j  c j
M odifions le coefficient
11
1
1
c3  c3   c3 
360
7
M in
La solution actuelle dem eure optim ale si
c3 
4
7
  c3  0
S i  c3  
4
ou si
 c3  
4
7
S ujet à
4
7
 5 x1  4.5 x 2  6 x 3
6 x1 
5 x 2  8 x 3  60
10 x1  20 x 2  10 x 3  150
.
8
x1
x1 , x 2 , x 3  0
, nous poursuivons la résolution du p roblèm e
7
m odifié avec l'algorithm e du sim plexe en utilisant x 3 com m e
variable d'entrée.
  c3
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
jr
~
cj c
r
 c
jr
jr
Alors le coût relatif de toutes les variables est modifié comme suit.
Le vecteur des multiplicateurs est modifié:
T
T
c B devient c B  [ c j , c j , ..., c j   c j , ..., c j ]
1
A lo rs 
T
 cB B
T
 cB B
T

T
1
2
r
r
1
 [0, 0, ....,  c j , ..., 0] B
r
 [0, 0, ....,  c j , ..., 0] B
r
1
1
m
6.1 Modification des coefficients de
la fonction économique
 
A insi pour j  j r ,
T
 [0, 0, ....,  c j , ..., 0] B
T
1
r
c j  c j   a j
 c j   T a  j  [0, 0, ....,  c j r , ..., 0] B  1 a  j
T
c
 [ 0 , 0 , ....,  c
j
c
j
,..., 0 ] a  j
  c j a rj
r
P our j r
c
jr
1
 ( c j   c j )   a  j  [0, 0, ....,  c j , ..., 0] B a  j
T
jr
r
r
r
r
 ( c j   a  j )   c j  [0, 0, ....,  c j , ..., 0] B
T
r
 (c
r
jr
r
 c j )  c j  0
r
r
r
1
a j
r
r
6.1 Modification des coefficients de
la fonction économique
 
A insi pour j  j r ,
T
 [0, 0, ....,  c j , ..., 0] B
T
1
r
c j  c j   a j
 c j   T a  j  [0, 0, ....,  c j r , ..., 0] B  1 a  j
T
c
 [ 0 , 0 , ....,  c
j
c
j
jr
,..., 0 ] a  j
  c j a rj
r
P our ji , i  r (les autres variables de base)
c
1
 c j   a  j  [0, 0, ....,  c j , ..., 0] B a  j
T
ji
i
 c ji  0  0
i
r
i
1
puisque B a  ji  a  ji est un vecteur
unitaire avec le 1 dans la ligne i , et
donc a rji  0.
En somme, la solution demeure optimale
si
cj
cj
6.1 Modification
des coefficients de
max 
: a rj  0    c j  min 
j 1, 2 ,..., n a rj
j la
1, 2 ,...,
n a rj
fonction
économique



j j
j j
r
r
r
Par conséquent , la solution actuelle demeure
c~
j
c
j
  c j a rj  0
optimale
j  1, 2 ,..., n ; j  j r
r
M ais  j  j r tel que a rj  0
c j  c j   c j a rj  0  c j   c j a rj
r
r
 c j 
r
cj
a rj
De façon similaire ,  j  j r tel que a rj  0
c~
j
c
j
  c j a rj  0    c j a rj   c
r
r
 c j 
r
si
c
j
 a rj

j
c
j
a rj
: a rj

 0 .

6.1 Modification des coefficients de
la fonction économique
En somme, la solution demeure optimale
cj

max 
: a rj  0    c j 
r
j 1, 2 ,..., n a rj


j j
r
si
cj

min 
: a rj  0 .
j 1, 2 ,..., n a rj


j j
r
S i z *  c B b dénote la valeur optim ale du problèm e origi nal,
T
alors la valeur optim ale du problèm e m odifié de vient
c B b  c B b  [0, 0, ....,  c j , ..., 0]b  z *   c j b r
T
T
r
r
Si la condition n’est pas vérifiée, alors nous poursuivons
la résolution du problème modifié avec l’algorithme du simplexe
en utilisant une variable xj avec un coût relatif négatif comme
variable d’entrée.
T ableau optim al
V B x1
x2
1
z
x3

x5
1
3
30
7
35
7
2
1
7
7
14
7
 j  j r tel que a rj  0
11
2
1
45
c j  c j   c j a rj  0  c j   c j a rj
7
7
14
7
4
11
1
7
14
35
2


1
11


x6
z
x4
7
x6
x1
x2
TD
M odifions le coefficient
de la variable de base x1
11
1
1
r
r
 c j 
r
360
cj
a rj
7
L a so lu tio n actu elle d em eu re o p tim ale si
c 3  c 3   c1 a 3 3 
c 4  c 4   c1 a 3 4 
c 5  c 5   c1 a 3 5 
4

11
7
11
7

 c1  0   c1 
2
14
7
1
1
35

 c1  0   c1 
14
4
11
11
4
 c1  0   c1  



2
4

     c1 
5
11

2

5
T ableau optim al
V B x1
x2
1
z
x3

x5
1
3
30
7
35
7
2
1
7
7
14
7
 j  j r tel qque
u e a rjrj  00
11
2
1
45
c j  c j   c jj a rjrj  00 
c jacrjj 
 c 
a rj c j
j 
r
r
7
7
14
7
4
11
1
7
14
35
2


1
11


x6
z
x4
7
x6
x1
x2
TD
M odifions le coefficient
de la variable de base x1
11
1
1
r
r

 cc jjr 
r
360
c cj j
aarjrj

7
L a so lu tio n actu elle d em eu re o p tim ale si
c 3  c 3   c1 a 3 3 
c 4  c 4   c1 a 3 4 
c 5  c 5   c1 a 3 5 
4

11
7
11
7

 c1  0   c1 
2
14
7
1
1
35

 c1  0   c1 
14
4
11
11
4
 c1  0   c1  



2
4

     c1 
5
11

2

5
cj
a rj
T ableau optim al
V B x1
x2
1
z
x3

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
4
11
1
7
14
35
2


1
11


x6
z
x4
7
x6
x1
x2
TD
M odifions le coefficient
de la variable de base x1
11
1
14
1
cj

7
m ax 
: a rj  0    c j 
r
j 1,2 ,..., n a rj


360
j  jr
cj

m in 
: a rj  0 
j 1,2 ,..., n a rj


j j
r
7
L a so lu tio n actu elle d em eu re o p tim ale si
c 3  c 3   c1 a 3 3 
c 4  c 4   c1 a 3 4 
c 5  c 5   c1 a 3 5 
4

11
7
11
7

 c1  0   c1 
2
14
7
1
1
35

 c1  0   c1 
14
4
11
11
4
 c1  0   c1  



2
4

     c1 
5
11

2

5
T ableau optim al
V B x1
x2
x2
1
x3

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35
2

7

x6
x1
1
z
11


x6
z
x4
TD
M odifions le coefficient
de la variable de base x1
11
1
360
1
7
S i z *  c B b dénote la valeur optim ale du problèm e origi nal,
T
alors la valeur optim ale du problèm e m odifié de vient
c B b  c B b  [0, 0, ....,  c j , ..., 0]b  z *   c j b r
T
T
r
La valeur de la fonction économ ique devient
c B b  c B b  [0, 0,  c1 ]b  z *   c1 b 3
T
T

360
7

45
7
 c1
r
6.2 Modifications des termes de droite
Si le terme de droite b r est modifié
pour devenir b r   b r
Illustration des principes avec l'exem ple suivant:
T ableau initial
VB
x1
x2
x3
x4
x4
6
5
8
1
x 5 10
20
10
x6
x5
x6
TD
60
1
150
1
 z  5  4.5
z
1
8
6
1
0
T ableau optim al
V B x1
x2
1
z
x3

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35
2


1
11


x6
z
x4
7
x6
x1
x2
TD
11
1
1
360
7
6.2 Modifications des termes de droite
Si le terme de droite b r est modifié
pour devenir b r   b r
Les term es de droite du tableau optim al devienn ent
  b1   0  
  

b
0
 2  

  

1
1
1
B   
  B b B
  br    br  
  

  

 b   0  

 m 
où   1 r ,  2 r , ...,  rr , ...,  m r 
T
 0   b1    1r 


   

0
b

  2   2r 


   
  br

  
  b r   b r    rr 


   






 0   b m    rm 
 
est la colonne r de B
1
L es term es de droite du tableau optim al devienn ent
  b1   0  
  


b
 2   0 
  

1
1
1
B   
  B b B
  br    br  
  

  
 
 b 
 m  0 
où
  1 r ,  2 r , ...,  rr , ...,  m r 
T
 0   b1    1r 

    
0
b2

    2r 


   
  br

  
  b r   b r    rr 


   


   


 0   b m    rm 
est la colonne r de B
1
A insi la solution de base actuelle dem eure réalisable si
b i   ir  b r  0
 i  1, 2, ..., m
c'est
 dire
P our àtout
i tel que  ir  0 alors
P our tout i tel que  ir  0 alors
bi   ir  br  0 
bi   irbbr  0   ir  br   bi
 bi    ir  br
bi
i
m ax 
:  ir  0   bbr  m in 
:  ir  0  .
bi
i i 1,2 ,..., m
i  1,2 ,..., m




b

  br 
 ir
 ir

r
  ir
 ir
L es term es de droite du tableau optim al devienn ent
  b1   0  
 0   b1    1r 
  
  





b2

0
0
b
2
  


    2r 
  
  





1
1
1
B   
  br
  B b B 
  
 b r    rr 
  br    br  
  bProur
 tout
i tel que  ir  0 alors
P our
que  ir  0 alors


 tout i tel






bi  ir  b r  0   ir  br   bi  bi   ir  br  0  bi    ir  br
 b 

0
0   b    rm 



 m

bi
 bi
 m
  br 
  br 
T
  ir
où   1 r ,  2 r , ...,  rr , ...,  m r 
 ir est la colonne r de B  1
A insi la solution de base actuelle dem eure réalisable si
b i   ir  b r  0
 i  1, 2, ..., m
c'est  à  dire
 bi

m ax 
:  ir  0    b r 
i  1,2 ,..., m
  ir

 bi

m in 
:  ir  0  .
i 1,2 ,..., m
  ir

6.2 Modifications des termes de droite
Ainsi la solution
de base actuelle demeure
b i   ir  b r  0
réalisable
si
 i  1, 2 ,..., m
c' est  à  dire
  b i

max 
:  ir  0    b r 
i  1, 2 ,..., m  

 ir
  b i

min 
:  ir  0  .
i  1 , 2 ,..., m  

 ir
L es term es de droite du tableau optim al devienn ent
  b1   0  
  

b2
0
  

  

1
1
1
B   
  B b B
  br    br  
  

  
 
 b 
 m  0 
où
  1 r ,  2 r , ...,  rr , ...,  m r 
T
 0   b1    1r 

    
0
b2

    2r 


   



  br


 br

  b r    rr 


   








 0   b m    rm 
est la colonne r de B
1
S i z *  c B b dénote la valeur optim ale du problèm e origi nal,
T
alors la valeur optim ale du problèm e m odifié de vient
  1r 


 2r




T
T
cB b  cB 
  br
  rr 




  rm 
6.2 Modifications des termes de droite
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.
T ableau optim al
V B x1
x2
x2
1

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35
2


1
z
11


x6
z
x4
7
x6
x1
x3
TD
11
1
1
360
7
M odifions le term e
de droite b 2 .
Les term es de droite du tableau optim al devienn ent
  b1   0  
  

  b2   0  
  

1
1
1
B   
  B b B
  br    br  
  

  

 b   0  

 m 
où   1 r ,  2 r , ...,  rr , ...,  m r 
L es term es d e d ro ite d u tab leau o p tim al d evien n en t
 30   1
 7   7

 
11     2
7   7

 
45
2

 
 7   7
3
35
1
14

1
14

0

1


0

0   30   3 

  7   35 

 11   1 

 b
  b2   
2




7
1
4



  45   1 
 

0  

  7   1 4 
T
 0   b1    1r 


   

0
b

  2   2r 


   
  br

  
  b r   b r    rr 


   


   
 0   b m    rm 
 
est la colonne r de B
1
T ableau optim al
V B x1
x2
x2
1

x4
x5
1
3
7
35
2
1
7
7
14
11
2
7
7
4
11
1
7
14
35
2

7

x6
x1
x3
1
z
11


1
14
x6
z
TD
30
1
M odifions le term e
de droite b 2 .
7 es d e d ro ite d u tab leau o p tim al d evien n en t
L es term
11
3
 30   1
 0   30   3 

0
 7  7 7
 
  7   35 
35

 45
 
 11   1 
1
1
2
1

  

 b
1    b2   
2
7
7   7
 
14
  7   14 

 360

 
  45   1 
415
2
1

 
 


0  0  
7
  7   1 4 
 7   7
 
14
L a base actuelle dem eure réalisable pour le nouveau problèm e si
30
7

3
35

 b 2  0   b 2   50 

11 1


 b 2  0   b 2   22    22   b 2  90
7 14

45
1


 b 2  0   b 2  90 
7
14

T ableau optim al
V B x1
x2
x2
1


1
z
M odifions le term e
x5
1
3
30
7
35
7
2
1
7
7
14
7
c'est  à  dire
11
2
1
45
7
7
14
7
 bi

m ax 
:  ir  0    b r 
i  1,2 ,..., m
  ir

4
11
1
7
14
35
2

11


x6
z
x4
7
x6
x1
x3
TD
de droite b 2 .
A insi la solution de base actuelle dem eure réalisable si
11
1
1
b i   ir  b r  0
 i  1, 2, ..., m
 bi

m in 
:  ir  0  .
i 1,2 ,..., m
  ir

360
7
L a base actuelle dem eure réalisable pour le nouveau problèm e si
30
7

3
35

 b 2  0   b 2   50 

11 1


 b 2  0   b 2   22    22   b 2  90
7 14

45
1


 b 2  0   b 2  90 
7
14

T ableau optim al
V B x1
x2
x2
1

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35
2


1
z
11


x6
z
x4
7
x6
x1
x3
TD
1
de droite b 2 .
Les term es de droite du tableau optim al devienn ent
11
1
M odifions le term e
360
7
  b1   0  
  

  b2   0  
  

1
1
1
B   
  B b B
  br    br  
  

  

 b   0  

 m 
où   1 r ,  2 r , ...,  rr , ...,  m r 
S i la solution est réalisable, la valeur optim ale devient
  4.5,
0,
  30   3 

7   35 

 

 11   1 
 5 

 b2
  7   14 

 

1
45

 


  7   14 



360  b 2




7
35




T
 0   b1    1r 


   

0
b

  2   2r 


   
  br

  
  b r   b r    rr 


   


   
 0   b m    rm 
 
est la colonne r de B
1
6.3 Modification des contraintes
• Nous limitons notre étude au cas où les coefficients des variables hors base
peuvent être modifiés
Si le coefficien t a ij d' une variable
hors base est modifié
pour devenir a ij   a ij ,
alors le coût relatif de la variable hors base x j de vient
c j  cj 
T

 0 






 a  a    c   T a  
j
j
  j  ij  






0



c'est  à  dire
c j  c j   i  a ij .
T
 0 




a 
ij






0


6.3 Modification des contraintes
L a so lu tio n d em eu re o p tim ale si
c j  c j   i  a ij  0
c'est  à  d ire si
 a ij 
 a ij 
cj
i
cj
i
lo rsq u e  i  0
lo rsq u e  i  0
 a ij q u elco n q u e lo rsq u e  i  0 .
Si la solution n’est plus optimale, nous poursuivons la résolution du
problème modifié avec l’algorithme du simplexe.
T ableau optim al
V B x1
x2
x2
x3

1
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35

7

x6
x1
x5
2
1
z
11


x6
z
x4
TD
M odifions le
coefficient a13 .
11
1
360
1
7
S eul le coût relatif de la variable x 3 est influencé:
c3  c3  
T
 a13   a13 
4 11


T
a 23
 c 3   a  3   1  a13  
 a13


7 14
 a 33

L a solution dem eure optim ale si
c3 
4
7

11
14
 a1 3  0   a1 3  
8
11
.
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 .
T ableau initial
V B x1
x2
x3
x4
6
5
8
1
x 5 10
20
10
x4
x6
1
 z  5  4.5
x5
x6
1
1
6
x7  z
TD
2
60
5
150
0
8
2
1
0
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 éterm inons le coût relatif de x n  1
c n 1  c n 1   a  n 1 .
T
Si
c n  1  c n  1   a  n  1  0,
T
la solution actuelle avec x n  1  0 est optim ale pour le problèm e m odifié .
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 éterm inons le coût relatif de x n  1
c n 1  c n 1   a  n 1 .
T
Si
c n  1  c n  1   a  n  1  0,
T
alors nous poursuivons la résolution du problè m e m odifié avec
l'algorithm e du sim plexe.
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 .
T ableau initial
V B x1
x2
x3
x4
6
5
8
1
x 5 10
20
10
x4
x6
1
 z  5  4.5
x5
x6
1
1
6
x7  z
TD
2
60
5
150
0
8
2
1
0
C onsidérons une nouvelle
T ableau optim al
V B x1
x2
x2
x3

1
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35

7

x6
x1
x5
2
1
11
z


x6
z
x4
TD
11
1
1
variable x 7 avec les coefficients
2
 
dans les contraintes 5
 
 0 
et le coût est c 7   2
360
7
L e co û t relatif c 7 d e la variab le x 7
c7  c7   a 7
T
c7   2 
11
7

1
7
2
1
 11
 
 2  
,
,0 5
35   
 14
 0 

2
7
S i c 7  0 , alo rs la
so lu tio n actu elle avec
x 7  0 est u n e so lu tio n
o p tim ale d u n o u veau
p ro b lèm e.
C onsidérons une nouvelle
T ableau optim al
V B x1
x2
x2
x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
4
11
1
7
14
35
2

7

1
11
z


x6
z
x4

1
x6
x1
x3
TD
11
1
1
variable x 7 avec les coefficients
2
 
dans les contraintes 5
 
 0 
et le coût est c 7   2
360
7
P uis nous poursuivons la
P uisque c 7  0, alors nous calculons a  7 : résolution du problèm e
a7



 




1
3
7
35
2
1
7
14
2
7

1
14
 2   1 
0
   7 
  

3 




1 5  
    14 
  

3

0  0 
    1 4 
m odifié avec l'algorithm e
du sim plexe en ajoutant la
colonne associée à x 7 dans le
dernier tableau du sim plexe
et en utilisant x 7 com m e
variable d'entrée.
C onsidérons une nouvelle
T ableau optim al
VB
x1
x2
x2

1
x4
x5
1
3
1
7
35
7
2
1
7
7
14
14
11
2
1
3
7
7
14
14
4
11
1
7
14
35
2

7

x6
x1
x3
1
z
11


x6
1
x7
z

2
variable x 7 avec les coefficients
30
2
7
 
dans
les
contraintes
5
11
 
7
 0 
3

TD
45
7
1
7
et le coût est c 7   2
360
7
P uis nous poursuivons la
P uisque c 7  0, alors nous calculons a  7 : résolution du problèm e
a7



 




1
3
7
35
2
1
7
14
2
7

1
14
 2   1 
0
   7 
  

3 




1 5  
    14 
  

3

0  0 
    1 4 
m odifié avec l'algorithm e
du sim plexe en ajoutant la
colonne associée à x 7 dans le
dernier tableau du sim plexe
et en utilisant x 7 com m e
variable d'entrée.
6.5 Introduction d’une nouvelle contrainte
a)
C onsidérons l'ajout d'une contrainte du type
n
a
m 1 j
x j  bm 1 .
j 1
S i la solution optim ale actuelle x satisfait le contrainte; i.e.,
n
a
m 1 j
x j  bm 1 ,
j 1
alors x dem eure optim ale m êm e si la nouve lle contrainte est ajoutée.
S inon, introduisons une variable d'écart x n  1 pou r 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.
n
a
j 1
m 1 j
x j  x n 1  bm 1
La variable
x n 1 devient la variable
de base dans la ligne
m  1 du
tableau .
a m 1 j
Pour rendre le coefficien t de x j égale à 0 dans la ligne que
r
nous ajoutons au tableau, il suffit de soustraire
multipliée
par a m 1 j
r
la ligne r
r
a m 1 j
Répétant
la même
opération
pour chaque variable
le coefficien t de x j devient
m
a m 1 j  a m 1 j 
a
m 1 j r
a rj
r 1
et le terme de droite devient
m
b m 1  b m 1 
a
r 1
m 1 j r
br.
de base,
r
Le tableau ainsi modifié devient
m
P uisque
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 actue lle
est négative. N ous poursuivons la résolution d u problèm e
m odifié avec l'algorithm e dual du sim plexe.
A joutons la nouvelle contrainte suivante à notre problèm e :
2 x1  3 x 2  x 3  25.
Introduisons la variable d'écart x 7 :
2 x1  3 x 2  x 3  x 7  2 5 .
C ette contrainte est ajoutée dans l e tableau optim a l.
T ableau optim al
VB
x1
x2
x2
1

x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
2


x1
1
x7
2
3
11


1
x6
x7
z
x4
7
x6
z
x3
11
1
1
4
11
1
7
14
35
TD
25
1
360
7
V B x1
x2
x2
x3
x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
2

1

7

x6
x1
1
x7
2
11
3
x4 : 0  3
x5 : 0  3
2
2
7
2
11
1
7
14
35
11
9
VB
7
x2

7

7
3
1
2
35
30
7

14
2
45
7
les coefficients
des variables de
ligne ajoutée
au tableau.
7
x1
x1
x2
1
x3
x5
1
3
30
7
35
7
2
1
7
7
14
7
11
2
1
45
7
7
14
7
2

5
7
x7
z

7

1
11

9


1


4
7
7
35
4
11
1
7
14
35
x6
x7
z
x4
35

base dans la
2
360
1
x6
4
3
25
1
7
R endons à 0
11
1
4
2
TD
1
7
1
b4  25  3

x7
1
z
x 3 :1  3

x6
z
x4
TD
11
1

1
5
7
1
360
7
6.5 Introduction d’une nouvelle contrainte
b) C onsidérons l'ajout d'une contrainte du type
n
a
m 1 j
x j  bm 1 .
j 1
S i la solution optim ale actuelle x satisfait le contrainte; i.e.,
n
a
m 1 j
x j  bm 1 ,
j 1
alors x dem eure optim ale m êm e si la nouve lle contrainte est ajoutée.
S inon, introduisons une variable d'écart x n  1 pou r 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.
n
a
j 1
m 1 j
x j  x n 1  bm 1
a m 1 j
Pour rendre le coefficien t de x j égale à 0 dans la ligne que
r
nous ajoutons au tableau, il suffit de soustraire
multipliée
par a m  1 j
r
la ligne r
r
a m 1 j
Répétant
la même
opération
pour chaque variable
le coefficien t de x j devient
m
a m 1 j  a m 1 j 
a
m 1 j r
a rj
r 1
et le terme de droite devient
m
b m 1  b m 1 
a
r 1
m 1 j r
br.
de base,
r
Multiplions la dernière ligne du tableau par –1 pour que
xn+1 devienne variable de base dans cette ligne
m
P uisque
 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 actue lle
est négative. N ous poursuivons la résolution d u problèm e
m odifié avec l'algorithm e dual du sim plexe.
6.5 Introduction d’une nouvelle contrainte
c)
C onsidérons l'ajout d'une contrainte du type
n
a
m 1 j
x j  bm 1 .
j 1
S i la solution optim ale actuelle x satisf ait le contrainte; i.e.,
n
a
m 1 j
x j  bm 1 ,
j 1
alors x dem eure optim ale m êm e si la nouve lle contrainte est ajoutée.
S inon, introduisons la contrainte
n
a
j 1
dans le tableau.
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.
n
a
j 1
m 1 j
x j  bm 1
a m 1 j
Pour rendre le coefficien t de x j égale à 0 dans la ligne que
r
nous ajoutons au tableau, il suffit de soustraire
multipliée
par a m  1 j
r
la ligne r
r
a m 1 j
Répétant
la même
opération
pour chaque variable
le coefficien t de x j devient
m
a m 1 j  a m 1 j 
a
m 1 j r
a rj
r 1
et le terme de droite devient
m
b m 1  b m 1 
a
r 1
m 1 j r
br.
de base,
r
Le tableau ainsi modifié devient
S upposons que
b m  1  0.
P our identifier une solution de base du problèm e m odifié,
nous devons trouver une nouvelle variable de base pour la
nouvelle ligne du tableau.
C hoisissons un élém ent négatif dans la dernière lign e
sur lequel nous com plétons un pivot.
Le tableau ainsi modifié devient
S upposons que
b m  1  0.
N otons que si tous les élém ents de la de rnière ligne sont positifs
ou nuls, alors le problèm e n'est pas réa lisable.
Le tableau ainsi modifié devient
Pour préserver
la non
de pivot a m  1 s comme
négativité
des coûts relatifs,
dans l' algorithme
cs
a m 1 s
nous choisisson s l' élément
dual du simplexe
 c j

 max 
: a m 1 j  0 
1 j  n  a m  1 j


:
Le tableau résultant est comme suit
~
bi  0
Si
alors une solution
xj
r
 i  1, 2 ,..., m  1,
optimale
~
 br
du problème
modifié
est
r  1, 2 ,..., m
~
x s  b m 1
Autrement
modifié
nous poursuivon s la résolution
avec l' algorithme
dual du simplexe.
du problème
Le tableau ainsi modifié devient
S upposons que b m  1  0.
N ous procédons de la m êm e façon après avoir m ultiplié


la ligne ( m  1) par  1 pour retrouver un term e de droite  b m  1 négatif .
Le tableau ainsi modifié devient


S upposons que



 b m 1  0.
N otons que si tous les élém ents de la de rnière ligne sont positifs
ou nuls, alors le problèm e n'est pas réa lisable.
Le tableau ainsi modifié devient





P our préserver la non négativité des coûts relatifs, nous choisissons l'élém ent
de pivot  a m  1 s com m e dans l'algorithm e dual du sim ple xe:
cs
 a m 1 s
 cj

 m ax 
:  a m 1 j  0 
1 j  n
 a m 1 j

Le tableau résultant est comme suit
~
bi  0
Si
alors une solution
xj
r
 i  1, 2 ,..., m  1,
optimale
~
 br
du problème
modifié
est
r  1, 2 ,..., m
~
x s  b m 1
Autrement
modifié
nous poursuivon s la résolution
avec l' algorithme
dual du simplexe.
du problème
Auteur
Документ
Catégorie
Без категории
Affichages
4
Taille du fichier
926 Кб
Étiquettes
1/--Pages
signaler