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 z_j, 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 z₁ représente la diminution du profit qui résulte de l’ajout d’une unité à la valeur de x₁.

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

x₁ + S₁ = 150

Donc, une augmentation de x₁ de 0 vers 1 va être accompagnée d'une diminution des variables de base S₁, S₂, S₃, S₄ 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

La deuxième ligne, notée c_j - z_j, 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 x₁ est

c₁ - z₁ = 100 - 0 = 100

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

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

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

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

x₁ + S₁ = 150

En général, la valeur maximale de la variable entrante x_j est le minimum des valeurs positives des rapports de Q_i 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 :

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

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