c. Calcul des tableaux suivants

Dans le nouveau tableau de simplexe on va remplacer S₃ par x₂ et l’ensemble des variables de base deviendra S₁, S₂, x₂, S₄. On exige que x₂ prenne la même place dans la colonne des variables de base que celle de la variable sortante S₃.

Jusqu’à maintenant on ne peut pas remplir le tableau relatif à cette nouvelle solution de base :

Ce qui reste à déterminer sont les coefficients a_ij de la nouvelle matrice A et les valeurs Q_i des variables de base. Ceci est réalisé en utilisant la règle de pivot :

En appliquant cette règle sur notre exemple, on trouve le tableau suivant :

1. On vérifie toujours que les colonnes de la matrice relative à chacune des variables de base sont formées par des zéros sauf 1 dans l’intersection avec la ligne relative aux mêmes variables de base.
2. On peut vérifier aussi que l’ensemble des solutions réalisables, induit par les contraintes décrites dans le dernier tableau de simplexe, est le même que celui représenté par les contraintes initiales. La règle de pivot est une combinaison linéaire des contraintes du programme linéaire donc elle ne change pas l’ensemble des solutions réalisables.
3. La nouvelle solution réalisable de base est

x₁ = 0

x₂ = 120

S₁ = 30

S₂ = 200

S₃ = 0

S₄ = 90

Cette nouvelle solution correspond au point A(voir graphique). On vérifie bien que la valeur de la fonction objectif est passer de 0 à 120 x 200. La valeur de la fonction objectif peut être facilement calculer en multipliant membre à membre les c_i de la première colonne par les valeurs des variables de base Q_i dans la 3^ème colonne.

4. La solution de départ correspond au point O. La première itération nous a amené dans le sens de l'amélioration du profit (fonction objectif), c’est à dire le long de l’axe des ordonnées.

Ayant retrouvé une nouvelle solution, on veut savoir s’il est possible de retrouver une solution réalisable de base meilleure. Pour arriver à cette fin, on doit ajouter les deux lignes relatives au choix de la variable entrante, et la colonne relative au choix de la variable sortante.

La variable entrante est x₁ ; elle présente la plus grande valeur c_j- z_j. Si on calcule les quotients Q_i/c_i1, on retrouve que la variable sortante est S₁  à qui on associe la plus petite valeur du ratio Q₁/c₁₁=40. L’élément pivot dans ce tableau est 3/4. La nouvelle base est composée de x₁, S₂, x₂, S₄.

Le tableau de simplexe suivant issu de l’application de la règle de pivot est :

Cette nouvelle solution

x₁ = 40

correspond au point B qui est, d’après les résultats retrouvée par la méthode graphique, la solution optimale du problème. Ainsi, il faut s’attendre à ce que la méthode de simplexe reconnaisse cette solution comme étant la solution optimale.

Ajoutons la ligne relative au calcul de l'effet net d’une augmentation unitaire d’une des variables du problème, on a :

L’effet net associé aux variables hors base S₁ et S₂ est négatif. Ceci nous oblige à dire que faire entrer une de ces deux variables dans la base va engendrer une diminution dans la valeur de la fonction objectif. Donc il n’y a pas une autre solution réalisable de base qui peut engendrer un profit meilleur. Par suite cette dernière solution est la solution optimale. Ce dernier tableau de simplexe est donc dit tableau optimal.

On peut généraliser ce résultat en disant que la solution optimale d’un programme linéaire est atteinte s’il n’y a aucune valeur positive dans la ligne c_j-z_j du tableau du simplexe.