Make your own free website on Tripod.com

INDEX

b. Amélioration de la solution

Pour améliorer la solution il faut générer une autre solution de base (point extrême) qui augmente la valeur de la fonction objectif. C’est à dire, qu’on doit sélectionner une variable hors base et une variable de base et les permuter de telle façon que la nouvelle solution donne une plus grande valeur de la fonction objectif.

Pour savoir si on peut améliorer notre solution réalisable de base initiale nous allons introduire deux nouvelles lignes au-dessus du tableau de simplexe.

La première ligne, notée zj, représente la variation de la valeur de la fonction objectif qui résulte du fait qu’une unité de la variable correspondante à la jème colonne de la matrice A est amenée dans la base. Par exemple z1 représente la diminution du profit qui résulte de l’ajout d’une unité à la valeur de x1.

En effet, si on produit un hectare supplémentaire de x1, la valeur de quelques variables de base vont changer vu qu’on a :

x1 + S1 = 150

4x1 + S2 = 440

x1 + S3 = 480

x1 + S4 = 90

Donc, une augmentation de x1 de 0 vers 1 va être accompagnée d'une diminution des variables de base S1, S2, S3, S4 respectivement de 1, 4, 1 et 1.

L’effet de cette diminution sur la fonction objectif est nul car les coefficients des variables d’écarts dans cette fonction sont nulles

z1 = 0 ´ S1 + 0 ´ S2 + 0 ´ S3 + 0 ´ S4 =0 ´ 1 + 0 ´ 4 + 0 ´ 1 + 0 ´ 1 = 0

La valeur z1 est calculée en multipliant les coefficients de la première colonne de la matrice A relatifs à la variable x1 par les coefficients ci de la première colonne. Généralement, on a :

zj =

La deuxième ligne, notée cj - zj, représente l’effet net de l’augmentation d’une unité de la jème variable.

Dans notre exemple, l’effet net sur la fonction objectif engendré par l’augmentation d’une unité dans la valeur de x1 est

c1 - z1 = 100 - 0 = 100

Si on reprend la même opération pour le reste des variables, on trouve le tableau suivant :

 

 

 

100

200

0

0

0

0

 

 

 

x1

x2

S1

S2

S3

S4

0

S1

150

1

1

1

0

0

0

0

S2

440

4

2

0

1

0

0

0

S3

480

1

2

0

0

1

0

0

S4

90

1

0

0

0

0

1

 

 

zj

0

0

0

0

0

0

 

 

cj - zj

100

200

0

0

0

0

En analysant la ligne relative à l’évaluation nette cj - zj, on remarque qu’une augmentation d’une unité de la valeur de x1 engendre un profit de 100 dinars, et qu’une augmentation d’une unité de la valeur de x2 engendre un profit supplémentaire de 200 dinars. Donc, si on a à choisir, on va opter pour une augmentation de la valeur de x2. On dit que x2 est la variable entrante.

Le problème est maintenant, jusqu’où peut-on augmenter x2 ?

Cette augmentation ne peut pas se faire infiniment, sous l’hypothèse que x1 reste nulle. On a

x1 + S1 = 150

2x2 + S2 = 440

4x2 + S3 = 480

x4 + S2 = 90

On peut voir que x2 peut prendre comme valeur maximale la valeur de 100 (il ne faut pas oublier que les Si, i=1, 2, 3, 4 sont des variables positives). Cette valeur est obtenue en choisissant la plus petite valeur positive des divisions de 100/1, 440/2, 480/4 et 90/0 (on suppose que 90/0 est égale à l’infini ¥ ).

En général, la valeur maximale de la variable entrante xj est le minimum des valeurs positives des rapports de Qi par les coefficients de la colonne de la matrice A relatif à la jème variable. Ces rapports feront l’objet d’une autre colonne à droite de la matrice A.

Dans notre exemple, on aura :

 

 

 

100

200

0

0

0

0

 

 

 

 

X1

x2

S1

S2

S3

S4

 

0

S1

100

1

1

1

0

0

0

150

0

S2

440

4

2

0

1

0

0

220


0

S3

480

1

4

0

0

1

0

120

0

S4

90

1

0

0

0

0

1

¥

 

 

 

0

0

0

0

0

0

 

 

 

 

100

200

0

0

0

0

 

Le fait d’augmenter x2 jusqu’à la valeur 100 va engendrer l’annulation de la valeur du variable d’écart S3, ce qui élimine S3 de la base. On appelle S3 variable sortante.

L’élément 4, à l’intersection de la ligne relative à la variable sortante S1 (dite ligne pivot) et de la colonne relative à la variable entrante x2 (dite colonne pivot) est l’élément pivot. (C’est l’élément cerclé dans le tableau).

 

Cliquer ici pour enregistrer le chapitre 3 en format Word sur votre disque dur (151 Ko)


Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com