Il y a deux manières de résoudre un problème de minimisation en utilisant la méthode de simplexe.

La première méthode nécessite le changement de la règle de choix de la variable entrante. Dans un problème de maximisation la règle est de choisir comme variable entrante celle qui a le plus grand effet net positif non nul. Ceci parce que notre objectif est de choisir la variable qui en entrant dans la base va engendrer un profit supplémentaire et ainsi accroître la valeur de la fonction objectif. Pour un problème de minimisation, on va utiliser la règle inverse. C’est-à-dire la variable entrante est celle à laquelle on associe la plus petite valeur négative non nulle de l’effet net c_j - z_j.

Ceci va nous amener aussi à changer notre règle d’arrêt de la procédure de simplexe et de définir le tableau optimal, comme celui où tous les effets nets
c_j - z_j sont positifs ou nuls.

Essayons d’appliquer la méthode de simplexe sur le problème de médecine :

Avec les problèmes de maximisation on attribue à ces variables un coefficient
-M dans la fonction objectif pour les contraindre à quitter la base rapidement. Dans le cas de problèmes de minimisation, on a intérêt à changer le coefficient de ces variables en M (M très grand) afin d’arriver au même résultat et de les faire sortir de la base.

Avant de construire le tableau de simplexe initial, on réécrit le programme linéaire relatif au problème de médecine avec les variables artificielles.

Min x₁ + x₂ + MA₁ + MA₂+ MA₃

Après 4 itérations, on trouve le tableau de simplexe optimal suivant :

On retrouve la même solution obtenue par la méthode graphique :

x₁ = 8

Après avoir vérifier que le second membre des contraintes est positif, le tableau suivant résume les transformations à faire subir à notre programme linéaire avant de le résoudre par la méthode de simplexe :

Le tableau suivant résume les étapes de la méthodes de simplexe relatif aux problèmes de maximisation et minimisation :

La deuxième méthode pour résoudre un problème de se base sur le résultat suivant " Résoudre un problème min c^tx sujet à un ensemble de contraintes est équivalent à résoudre un problème max -c^tx sujet au même ensemble de contraintes ". Ces deux problèmes sont équivalents dans la mesure où ils donnent le même vecteur des solutions optimales. La seule différence est que la valeur de la solution max -c^tx est l’opposé de la solution de min c^tx; (i.e. min c^tx = - max -c^tx).

Donc pour résoudre le programme linéaire relatif au problème de médecine, on peut résoudre le problème de maximisation suivant:

Max - x₁ - x₂