Embed Size (px)
DESCRIPTION
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 - PowerPoint PPT Presentation
Citation preview
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'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
6.1 Modification des coefficients de la fonction économique
a) Le coût cj d’une variable hors base est modifié
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, n’est pas modifié, et les coûts relatifs des autres variables restent donc identiques.
Le coût relatif de la variable xj devient
La solution demeure optimale si
ou
jjjj cccc ~devient
T T 1Bc B
T T( ) ( )j jj j j j j j jc c c a c a c c c
0j j jc c c jj cc
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.
Tl l lc c a
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
j j jc c c
3 3 3
3
3
La solution actuelle demeure optimale si
4 40 ou si .
7 7
4Si , nous poursuivons la résolution du problème
7modifié avec l'algorithme du simplexe en utilisant comme
variable d'entrée.
c c c
c
x
3
3 3 3 3
3 3 3 3
Modifions le coefficient
de la variable hors-base
6
4
7
x
c c c c
c c c c
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
Illustration des principes avec l'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
6.1 Modification des coefficients de la fonction économique
a) Le coût cj d’une variable hors base est modifié
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, n’est pas modifié, et les coûts relatifs des autres variables restent donc identiques.
Le coût relatif de la variable xj devient
La solution demeure optimale si
ou
jjjj cccc ~devient
T T 1Bc B
T T( ) ( )j jj j j j j j jc c c a c a c c c
0j j jc c c jj cc
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.
Tl l lc c a
jjc c
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
j j jc c c
3 3 3
3
3
La solution actuelle demeure optimale si
4 40 ou si .
7 7
4Si , nous poursuivons la résolution du problème
7modifié avec l'algorithme du simplexe en utilisant comme
variable d'entrée.
c c c
c
x
3
3 3 3 3
3 3 3 3
Modifions le coefficient
de la variable hors-base
6
4
7
x
c c c c
c c c c
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
6.1 Modification des coefficients de la fonction économique
b) Le coût de la variable de base dans la ligne r est modifié
Alors le coût relatif de plusieurs variables est modifié comme suit.
Le vecteur des multiplicateurs est modifié:
rjc
1 2
T T
T
devient [ , ,..., ,..., ]
[0,0,..., ,...,0]
r r m
r
B B j j j j j
B j
c c c c c c c
c c
T 1 1[0,0,...., ,...,0]rB jc B c B
T 1[0,0,...., ,...,0]rj
c B
T T 1Alors Bc B
rrrr jjjj cccc ~devient
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
j j jc c c
3 3 3
3
3
La solution actuelle demeure optimale si
4 40 ou si .
7 7
4Si , nous poursuivons la résolution du problème
7modifié avec l'algorithme du simplexe en utilisant comme
variable d'entrée.
c c c
c
x
3
3 3 3 3
3 3 3 3
Modifions le coefficient
de la variable hors-base
6
4
7
x
c c c c
c c c c
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
Illustration des principes avec l'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
6.1 Modification des coefficients de la fonction économique
b) Le coût de la variable de base dans la ligne r est modifié
Alors le coût relatif de plusieurs variables est modifié comme suit.
Le vecteur des multiplicateurs est modifié:
rjc
1 2
T T
T
devient [ , ,..., ,..., ]
[0,0,..., ,...,0]
r r m
r
B B j j j j j
B j
c c c c c c c
c c
T 1 1[0,0,...., ,...,0]rB jc B c B
T 1[0,0,...., ,...,0]rj
c B
T T 1Alors Bc B
rrrr jjjj cccc ~devient
6.1 Modification des coefficients de la fonction économique
T T 1[0,0,...., ,...,0]
rjc B
T
Ainsi pour ,r
j j j
j j
c c a
T 1[0,0,...., ,...,0]
rj j j jc a c B a
jjj accr
]0,...,....,,0,0[
T 1
Pour
( ) [0,0,...., ,...,0]r r r r r r
r
j j j j j j
j
c c c a c B a
T 1( ) [0,0,...., ,...,0]r r r r rj j j j jc a c c B a
0r r rj j jc c c
rjjj accr
T( ) [0,0,...., ,...,0]r r r r rj j j j jc a c c a
0
1
0
rja
element r
6.1 Modification des coefficients de la fonction économique
T T 1[0,0,...., ,...,0]
rjc B
T
Ainsi pour ,r
j j j
j j
c c a
T 1[0,0,...., ,...,0]
rj j j jc a c B a
jjj accr
]0,...,....,,0,0[
T 1
Pour , (les autres variables de base)
[0,0,...., ,...,0]i i i r i
i
j j j j j
j i r
c c a c B a
10 0 puisque est un vecteur
unitaire avec le 1 dans la ligne , et
donc 0.
i i i
i
j j j
rj
c B a a
i
a
rjjj accr
0
1
0
rja
element i
T [0,0,...., ,...,0]i i irj j j jc a c a
6.1 Modification des coefficients de la fonction économique
Par conséquent, la base actuelle demeure optimale si
0 hors baser
j j rjjc c c a j
Mais hors base, tel que 0
0r r
r
rj
j j rj j rjj j
j
jrj
j a
c c c a c c a
cc
a
De façon similaire, hors base, tel que 0
0r r
r
rj
j j rj rj jj j
j j
jrj rj
j a
c c c a c a c
c cc
a a
1,2,...,1,2,..., hors base hors base
En somme, la base demeure optimale si
max : 0 min : 0 .r
j jrj rjj
j nj n rj rjjj
c ca c a
a a
6.1 Modification des coefficients de la fonction économique
T
T T
Si * dénote la valeur optimale du problème original,
alors la valeur optimale du problème modifié devient
[0,0,...., ,...,0] *r r
B
rB B j j
z c b
c b c b c b z c b
1,2,...,1,2,..., hors base hors base
En somme, la base demeure optimale si
max : 0 min : 0 .r
j jrj rjj
j nj n rj rjjj
c ca c a
a a
6.1 Modification des coefficients de la fonction économique
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.
1,2,...,1,2,..., hors base hors base
En somme, la base demeure optimale si
max : 0 min : 0 .r
j jrj rjj
j nj n rj rjjj
c ca c a
a a
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1
Modifions le coefficient
de la variable de base x
hors base, tel que 0
0r r
r
rj
j j rj j rjj j
jj
rj
j a
c c c a c c a
cc
a
3 3 1 33 1 1
4 4 1 34 1 1 1
5 5 1 35 1 1
La solution actuelle demeure optimale si
4 11 40
7 7 1111 2 11 2 4
014 7 4 5 111 1 2
035 14 5
c c c a c c
c c c a c c c
c c c a c c
hors base, tel que 0
0r r
r
rj
j j rj rj jj j
j jj
rj rj
j a
c c c a c a c
c cc
a a
1,2,...,1,2,...,hors basehors base
max : 0 min : 0r
j jrj rjj
j nj n rj rj
c ca c a
a a
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1
Modifions le coefficient
de la variable de base x
T
T T
Si * dénote la valeur optimale du problème original,
alors la valeur optimale du problème modifié devient
[0,0,...., ,...,0] *r r
B
rB B j j
z c b
c b c b c b z c b
31 1
1
La valeur de la fonction économique devient
[0,0, ] *
360 45
7 7
T TB Bc b c b c b z c b
c
6.2 Modifications des termes de droite
rrr bbb devenirpourmodifiéestdroitedetermeleSi
Illustration des principes avec l'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
6.2 Modifications des termes de droite
rrr bbb devenirpourmodifiéestdroitedetermeleSi
11 1
22 2
1 1 1
Les termes de droite du tableau optimal deviennent
0 0
0 0
0 0
r
r
r rr r
m m
bb
b b
B B b Bb bb b
b b
T 11 2où , ,..., ,..., est la colonne de
rrr
rm
r r rr mr
b
r B
11 1
22 2
1 1 1
Les termes de droite du tableau optimal deviennent
0 0
0 0
0 0
r
r
r rr rrr
m m
bb
b b
B B b Bb bb b
b b
T 11 2où , ,..., , ..., est la colonne de
r
rm
r r rr mr
b
r B
1,2,...,1,2,...,
Ainsi la solution de base actuelle demeure réalisable si
0 1,2,...,
c'est à dire
max : 0 min : 0 .
i ir r
i iir r ir
i mi m ir ir
b b i m
b bb
Pour tout tel que 0 alors0
ir
i ir r ir r i
ir
ir
ib b b b
bb
Pour tout tel que 0 alors0
ir
i ir r i ir r
ir
ir
ib b b b
bb
11 1
22 2
1 1 1
Les termes de droite du tableau optimal deviennent
0 0
0 0
0 0
r
r
r rr rrr
m m
bb
b b
B B b Bb bb b
b b
T 11 2où , ,..., , ..., est la colonne de
r
rm
r r rr mr
b
r B
1,2,...,1,2,...,
Ainsi la solution de base actuelle demeure réalisable si
0 1,2,...,
c'est à dire
max : 0 min : 0 .
i ir r
i iir r ir
i mi m ir ir
b b i m
b bb
Pour tout tel que 0 alors0
ir
i ir r ir r i
ir
ir
ib b b b
bb
Pour tout tel que 0 alors0
ir
i ir r i ir r
ir
ir
ib b b b
bb
11 1
22 2
1 1 1
Les termes de droite du tableau optimal deviennent
0 0
0 0
0 0
r
r
r rr rrr
m m
bb
b b
B B b Bb bb b
b b
T 11 2où , ,..., , ..., est la colonne de
r
rm
r r rr mr
b
r B
T
1 1 1
2 2 2
T T T
Si * dénote la valeur optimale du problème original,
alors la valeur optimale du problème modifié devientB
r r
r
B r B Brrr
rmm
z c b
b
b
c b c b cb
b
r
rrr
rm
b
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 optimale pour le problème modifié avec l’algorithme dual du simplexe.
Illustration des principes avec l'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
2
Modifions le terme
de droite .b
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
2
Modifions le terme
de droite .b
11 1
22 2
1 1 1
Les termes de droite du tableau optimal deviennent
0 0
0 0
0 0
r
r
r rr r
m m
bb
b b
B B b Bb bb b
b b
T 11 2où , ,..., ,..., est la colonne de
rrr
rm
r r rr mr
b
r B
2 2
Les termes de droite du tableau optimal deviennent
30 1 3 30 3007 7 35 7 35
11 2 1 11 11
7 7 14 7 14145 2 1 45
0 0 147 7 14 7
b b
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
2
Modifions le terme
de droite .b
2 2
Les termes de droite du tableau optimal deviennent
30 1 3 30 3007 7 35 7 35
11 2 1 11 11
7 7 14 7 14145 2 1 45
0 0 147 7 14 7
b b
2 2
2 2 2
2 2
La base actuelle demeure réalisable pour le nouveau problème si
30 30 50
7 3511 1
0 22 22 907 1445 1
0 907 14
b b
b b b
b b
1,2,...,1,2,...,
Ainsi la solution de base actuelle demeure réalisable si
0 1,2,...,
c'est à dire
max : 0 min : 0 .
i ir r
i iir r ir
i mi m ir ir
b b i m
b bb
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
2
Modifions le terme
de droite .b
22
Si la solution est réalisable, la valeur optimale devient
30 3
7 3511 1 360
4.5, 0, 57 14 7 35
145
147
bb
T
1 1 1
2 2 2
T T T
Si * dénote la valeur optimale du problème original,
alors la valeur optimale du problème modifié devientB
r r
r
B r B Brrr
rmm
z c b
b
b
c b c b cb
b
r
rrr
rm
b
6.3 Modification des contraintes
• Nous limitons notre étude au cas où les coefficients des variables hors base peuvent être modifiés
,devenirpour
modifiéestbasehorsvariableuned'tcoefficienleSi
ijij
ij
aa
a
Illustration des principes avec l'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
13
Modifions le
coefficient .a
6.3 Modification des contraintes
• Nous limitons notre étude au cas où les coefficients des variables hors base peuvent être modifiés
,devenirpour
modifiéestbasehorsvariableuned'tcoefficienleSi
ijij
ij
aa
a
T T T
alors le coût relatif de la variable hors base devient
0 0
0 0
c'est à dire
.
j
j j j ij j j ij
j j i ij
x
c c a a c a a
c c a
6.3 Modification des contraintes
Si la solution n’est plus optimale, nous poursuivons la résolution du problème modifié avec l’algorithme du simplexe.
La solution demeure optimale si
0
c'est à dire si
lorsque 0
lorsque 0
quelconque lorsque 0.
j j i ij
jij i
i
jij i
i
ij i
c c a
ca
ca
a
Illustration des principes avec l'exemple suivant:
1 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5 6 1 0
x x x x x x z
x
x
x
z
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
1 2 3
1 2 3
1 2 3
1
1 2 3
Min 5 4.5 6
Sujet à 6 5 8 60
10 20 10 150
8
, , 0
x x x
x x x
x x x
x
x x x
13
Modifions le
coefficient .a
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
3
13 13T T
3 3 23 3 3 1 13 3 1 13 13
33
Seul le coût relatif de la variable est influencé:
4 11
7 14
x
a a
c c a c a a c a a
a
3 13 13
La solution demeure optimale si
4 11 80 .
7 14 11c a a
13
Modifions le
coefficient .a
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 . 1na
71 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5
2
5
0
26 1 0
x x x x x x z
x
x
x
z
x
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 . 1na
1
T1 1 1
Déterminons le coût relatif de
.
n
n n n
x
c c a
T1 1 1
1
Si 0,
la solution actuelle avec 0 est optimale pour le problème modifié.
n n n
n
c c a
x
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 . 1na
1
T1 1 1
Déterminons le coût relatif de
.
n
n n n
x
c c a
T1 1 1
1
11 1
Si 0,
alors nous poursuivons la résolution du problème modifié avec
l'algorithme du simplexe.
La variable devient variable d'entrée, et pour exécuter
le critère de sortie, nous devons calculer
n n n
n
n n
c c a
x
a B a
.
71 2 3 4 5 6
4
5
6
Tableau initial
VB TD
6 5 8 1 60
10 20 10 1 150
1 1 8
5 4.5
2
5
0
26 1 0
x x x x x x z
x
x
x
z
x
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
7
7
Considérons une nouvelle
variable avec les coefficients
2
dans les contraintes 5
0
et le coût est 2
x
c
7 7
T7 7 7
7
Le coût relatif de la variable
211 1
2 , ,0 514 35
0
11 1 22
7 7 7
c x
c c a
c
7
7
Si 0, alors la
solution actuelle avec
0 est une solution
optimale du nouveau
problème.
c
x
1 2 3 4 5 6
2
6
1
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 74 11 1 360
17 14 35 7
x x x x x x z
x
x
x
z
7
7
Considérons une nouvelle
variable avec les coefficients
2
dans les contraintes 5
0
et le coût est 2
x
c
7 7
7
Puisque 0, alors nous calculons :
1 3 1207 35 72 1 3
1 57 14 14
32 10 0 147 14
c a
a
7
7
Puis nous poursuivons la
résolution du problème
modifié avec l'algorithme
du simplexe en ajoutant la
colonne associée à dans le
dernier tableau du simplexe
et en utilisant comme
variable d'entrée.
x
x
1 2 3 4 5 6
6
1
7
2
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7
1
73
143
142
7
7 14 74 11 1 360
17 14 35 7
xx x x x x x z
x
x
x
z
7
7
Considérons une nouvelle
variable avec les coefficients
2
dans les contraintes 5
0
et le coût est 2
x
c
7 7
7
Puisque 0, alors nous calculons :
1 3 1207 35 72 1 3
1 57 14 14
32 10 0 147 14
c a
a
7
7
Puis nous poursuivons la
résolution du problème
modifié avec l'algorithme
du simplexe en ajoutant la
colonne associée à dans le
dernier tableau du simplexe
et en utilisant comme
variable d'entrée.
x
x
6.5 Introduction d’une nouvelle contrainte
a)
1 11
1 11
Considérons l'ajout d'une contrainte du type
.
Si la solution optimale actuelle satisfait le contrainte; i.e.,
,
alors demeure optimale même si la nouvelle contrainte est
n
m j j mj
n
m j j mj
a x b
x
a x b
x
1
1 1 11
ajoutée.
Sinon, introduisons une variable d'écart pour rendre la contrainte
standard
.
n
n
m j j n mj
x
a x x b
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.
1 1 11
n
m j j n mj
a x x b
.tableaudu1ligneladansbasedevariableladevientvariableLa 1 mxn
r
r
jm
j
a
r
x
1parmultipliée
lignelasoustrairedesuffitiltableau,auajoutonsnous
queligneladans0àégaledetcoefficienlerendrePour
rjma 1
rjma 1
m
r
rjmmm
m
r
rjjmjmjm
j
babb
aaaa
x
r
r
1111
1111
.
devientdroitedetermeleet
devientdetcoefficienle
base,devariablechaquepouropérationmêmelaRépétant
Le tableau ainsi modifié devient
1 1 11
1
Puisque 0,
alors la variable de base dans la solution actuelle
est négative. Nous poursuivons la résolution du problème
modifié avec l'algorithme dual du simplexe.
r
m
m rm m jr
m
b b a b
x
2
2 3
1
7
7
1
3
Ajoutons la nouvelle contrainte suivante à notre problème :
2 3 25.
Introduisons la variable d'écart :
.
Cette contrainte est ajoutée dans l
2 3 2
e tableau optima .
5
l
x x x
x x x x
x
1 2 3 4 5 6
2
6
1
7
7
Tableau optimal
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 7
4 11 1 3601
7 14
2 3 1 1 2
35 7
5
x x x x x x z
x
x
z
x
x
x
1 2 3 4 5 6
2
6
7
7
1
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 7
4 11 1 3601
7 14 35 7
2 3 1 1 25
x
x
x x x x x x z
x
x
x
z
71 2 3 4 5 6
7
2
6
1
VB TD
2 1 3 301
7 7 35 711 2 1 11
17 7 14 7
11 2 1 451
7 7 14 79 1 4 5
174 11 1 360
17 14 35
35 7
7
7
x x x x x x x
x
z
x
x
x
z
Rendons à 0
les coefficients
des variables de
base dans la
ligne ajoutée
au tableau.
32 11 9
:1 3 27 7 7
x
41 2 1
:0 3 27 7 7
x
53 1 4
:0 3 235 14 35
x
430 45 5
25 3 27 7 7
b
3
2
6.5 Introduction d’une nouvelle contrainte
b)
1 11
1 11
Considérons l'ajout d'une contrainte du type
.
Si la solution optimale actuelle satisfait le contrainte; i.e.,
,
alors demeure optimale même si la nouvelle contrainte est
n
m j j mj
n
m j j mj
a x b
x
a x b
x
1
1 1 11
ajoutée.
Sinon, introduisons une variable d'écart pour rendre la contrainte
standard
.
n
n
m j j n mj
x
a x x b
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.
1 1 11
n
m j j n mj
a x x b
r
r
jm
j
a
r
x
1parmultipliée
lignelasoustrairedesuffitiltableau,auajoutonsnous
queligneladans0àégaledetcoefficienlerendrePour
rjma 1
rjma 1
m
r
rjmmm
m
r
rjjmjmjm
j
babb
aaaa
x
r
r
1111
1111
.
devientdroitedetermeleet
devientdetcoefficienle
base,devariablechaquepouropérationmêmelaRépétant
Multiplions la dernière ligne du tableau par –1 pour que xn+1 devienne variable de base dans cette ligne
1 1 11
1
Puisque 0,
alors la variable de base dans la solution actuelle
est négative. Nous poursuivons la résolution du problème
modifié avec l'algorithme dual du simplexe.
r
m
m rm m jr
m
b b a b
x
6.5 Introduction d’une nouvelle contrainte
c)
1 11
Considérons l'ajout d'une contrainte du type
.n
m j j mj
a x b
6.5 Introduction d’une nouvelle contrainte
c)
1 11
1 11
Considérons l'ajout d'une contrainte du type
.
Si la solution optimale actuelle satisfait le contrainte; i.e.,
,
alors demeure optimale même si la nouvelle contrainte est
n
m j j mj
n
m j j mj
a x b
x
a x b
x
1 11
ajoutée.
Sinon, introduisons la contrainte
dans le tableau.
n
m j j mj
a x b
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.
1 11
n
m j j mj
a x b
r
r
jm
j
a
r
x
1parmultipliée
lignelasoustrairedesuffitiltableau,auajoutonsnous
queligneladans0àégaledetcoefficienlerendrePour
rjma 1
rjma 1
m
r
rjmmm
m
r
rjjmjmjm
j
babb
aaaa
x
r
r
1111
1111
.
devientdroitedetermeleet
devientdetcoefficienle
base,devariablechaquepouropérationmêmelaRépétant
Le tableau ainsi modifié devient
1Supposons que 0.
Alors si tous les éléments de la dernière ligne sont positifs
ou nuls, alors le problème n'est pas réalisable.
mb
Le tableau ainsi modifié devient
1Supposons que 0.
Autrement, pour identifier une solution de base du problème modifié,
nous devons trouver une nouvelle variable de base pour la
nouvelle ligne du tableau.
Choisissons un élément négatif dans la d
mb
ernière ligne
sur lequel nous complétons un pivot.
Le tableau ainsi modifié devient
1
1
1
1 1 1 1 1
Pour préserver la non négativité des coûts relatifs, nous choisissons l'élément
de pivot comme dans l'algorithme dual du simplexe:
tel que 0
0 0
m s
m j
m j j s j sj s
m s m j m s m j m
a
j a
a c c c cc c
a a a a a
111 1
max : 0
s
s jm j
j nm s m j
c ca
a a
Le tableau résultant est comme suit
1~
,...,2,1~
estmodifiéproblèmeduoptimalesolutionunealors
,1,...,2,10~
Si
ms
rj
i
bx
mrbx
mib
r
simplexe.dudualalgorithmel'avecmodifié
problèmedurésolutionlaspoursuivonnousAutrement
Le tableau ainsi modifié devient
1
1
Supposons que 0.
Nous procédons de la même façon après avoir multiplié
la ligne ( 1) par 1 pour retrouver un terme de droite négatif .
m
m
b
m b
Le tableau ainsi modifié devient
1Supposons que 0.
Alors si tous les éléments de la dernière ligne sont positifs
ou nuls, alors le problème n'est pas réalisable.
mb
Le tableau ainsi modifié devient
1
11 11
Pour préserver la non négativité des coûts relatifs, nous choisissons l'élément
de pivot comme dans l'algorithme dual du simplexe:
max : 0
m s
s j
m jj n m jm s
a
c ca
a a
Le tableau résultant est comme suit
1~
,...,2,1~
estmodifiéproblèmeduoptimalesolutionunealors
,1,...,2,10~
Si
ms
rj
i
bx
mrbx
mib
r
simplexe.dudualalgorithmel'avecmodifié
problèmedurésolutionlaspoursuivonnousAutrement
