Jusqu'à maintenant, nous avons considéré des problèmes pour lesquels il existait une solution de base admissible évidente (toutes les variables de décisions étaient égales à 0). Cependant dans de nombreux cas de figure cela n'est pas vrai. Il convient alors de trouver une telle solution pour obtenir le tableau initial du simplexe.
Illustrons ce cas avec le problème suivant :
Ce qui donne en mettant les contraintes sous forme standard :
ce qui correspond à une solution non admissible puisque la variable y2 prend une valeur strictement négative.
Supposons que nous connaissions une solution admissible de ce problème consistant à fixer la variable x2 à 1 (et par conséquence la variable d'écart y1 à 4). Nous pouvons alors reformuler les contraintes du problèmes selon cette solution de base :
De même, en remplaçant la variable x2 dans la fonction objectif, on obtient :
Cette reformulation du problème permet ainsi d'obtenir le tableau simplexe initial.
Lorsque l'on ne connaît pas de solution admissible, une autre possibilité consiste à transformer le problème de recherche d'une solution admissible initiale en un problème d'optimisation grâce à l'introduction de variables artificielles (pénalisées dans la fonction objectif avec un coefficient M choisi suffisamment grand pour que les variables artificielles soient nulles dans la solution optimale, on par le technique du big M) :
Le tableau simplexe initial de ce nouveau problème s'écrit alors :
et après une itération (en choisissant la variable x2 comme variable entrante) :
Ce tableau correspond ainsi à une solution de base admissible du problème initial. Notons que le coût réduit de la variable artificielle ya fait qu'elle n'entrera plus en base lors des itérations suivantes et la colonne correspondante peut donc être supprimée du tableau simplexe. On retrouve dans ce cas le tableau simplexe correspondant à la solution admissible considérée ci-dessus.