6. Analyse postoptimale

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