La méthode de simplexe commence par l'identification d'une solution réalisable de base et ensuite, elle essaye de trouver d'autres solutions réalisables de base jusqu’à atteindre à la solution optimale. Ainsi, on doit, tout d’abord, retrouver cette solution réalisable de base. 

Généralement si le programme linéaire satisfait ces deux propriétés :

P1/ Parmi les variables du problème standard, il y a m variables qui apparaissent avec un coefficient non nul dans chaques contraintes (dans notre exemple : S₁, S₂, S₃ et S₄).

P2/ Les valeurs du second membre des contraintes (les composants du vecteur b) sont positives.

Alors une solution réalisable de base est obtenue en annulant les (n-m) variables de décision et la valeur des variables d'écart est directement donnée par le second membre. La deuxième propriété assure la satisfaction des contraintes de nonnégativité des variables d'écart.

Dans notre exemple, la forme standard du programme linéaire vérifie ces deux propriétés.

a. Tableau de simplexe initial

Après avoir mis le programme linéaire sous une forme qui vérifie les deux propriétés P1 et P2, l’étape suivante est de tracer le tableau de simplexe initial.

Le modèle général des tableaux de simplexe est :

Pour notre exemple le tableau de simplexe initial est le suivant :

On remarque qu’on a placé en première ligne les contributions unitaires de toutes les variables de décision x₁,..., S₄ dans la fonction objectif. Dans la troisième ligne, on retrouve la première contrainte x₁ + x₂ + S₁ = 150. La valeur 150 représente ici la valeur de S₁ relative à la solution réalisable de base initiale. Dans la première colonne on trouve les contributions nulles des variables d'écart qui forment la solution de base initiale.

Question : Quelles sont les contraintes et la fonction objectif du programme linéaire décrit par le tableau de simplexe suivant :

Réponse : Les contraintes du programme sont :

et la fonction objectif est : 6x₁ + 7x₂ + 0S₁ + 0S₂

Remarque : Les variables qui figurent dans la deuxième colonne sont dites variables de base. A chacune de ces variables, on associe la valeur 1 à l’intersection de la ligne et de la colonne relative à cette variable et dans le reste de la colonne on trouve des zéros.

Jusqu’à ici on a vu comment retrouver une solution réalisable de base et comment présenter le tableau de simplexe initial. Dans la section suivante, on examinera la procédure liée à la méthode de simplexe qui permet de passer de cette solution réalisable de base initiale à une autre solution réalisable de base qui donne une meilleure valeur de la fonction objectif.