Simplexe à deux phases

Cas simple

Pour commencer l'algorithme du simplexe, il faut partir d'une base admissible (valeurs des variables qui vérifient toutes les contraintes, les variables hors base étant égales à 0).
Souvent, on peut utiliser les variables d'écarts comme base initiale. Considérons par exemple le PL ci-dessous:

$\left\{ \begin{array}{ll} \max z = 4x + 5y\\ 2x + y \leq 4 \\ x + 2y \leq 2 \\ x, y \geq 0 \end{array} \right.$

Il peut être mis sous forme standard en ajoutant des variables d'écarts :

$\left\{ \begin{array}{ll} \max z = 4x + 5y\\ 2x + y + e_1 = 4 \\ x + 2y + e_2 = 2 \\ x, y, e_1, e_2 \geq 0 \end{array} \right.$

$(e_1, e_2)$ forme une base admissible car, si $x = y = 0$, on trouve $e_1 = 4$, $e_2 = 2$ qui sont bien positifs (donc vérifient les contraintes $x, y, e_1, e_2 \geq 0$). On peut donc, dans ce cas, appliquer l'algorithme du simplexe avec $(e_1, e_2)$ comme base initiale.

Cas problématique

Cependant, parfois il est plus difficile de trouver une première base admissible. Considérons le programme linéaire suivant, légèrement modifié par rapport au précédent :

$(*) \left\{ \begin{array}{ll} \max z = 4x + 5y\\ -2x + y + e_1 = -4 \\ x - 2y + e_2 = -2 \\ x, y, e_1, e_2 \geq 0 \end{array} \right.$

Trouver une première base admissible

Si $x = y = 0$ alors $e_1 = -4$ et $e_2 = -2$, ce qui n'est pas une base admissible (car négatifs). La méthode du simplexe à 2 phases consiste à modifier le PL en ajoutant des variables artificielles $a_1$, $a_2$ :

$(**)\left\{ \begin{array}{ll} \min y = a_1 + a_2\\ -2x + y + e_1 - a_1 = -4 \\ x - 2y + e_2 - a_2 = -2 \\ x, y, e_1, e_2, a_1, a_2 \geq 0 \end{array} \right.$

On a fait exprès de mettre des signes $-$ devant $a_1$ et $a_2$ pour qu'ils constituent une base admissible de ce nouveau PL $(**)$. En effet, si $x = y = e_1 = e_2 = 0$ alors $a_1 = 4$ et $a_2 = 2$, qui sont bien positifs. L'idée est ensuite d'utiliser l'algorithme du simplexe sur ce nouveau PL pour sortir $a_1$ et $a_2$ de la base. On obtiendra alors une base constituée uniquement d'éléments parmi $x, y, e_1, e_2$, qui sera aussi une base du PL initial $(*)$.

Ecrivons le PL $(**)$ sous forme de tableau :

On met des coefficients positifs sur le second membre :

Faisons rentrer $x$, en utilisant la première ligne comme pivot (on regarde la valeur min de $B_p/p$ comme d'habitude) :

$\Longleftrightarrow$

Faisons rentrer $y$, en utilisant la deuxième ligne comme pivot (on regarde la valeur min de $B_p/p$ comme d'habitude) :

$\Longleftrightarrow$

On obtient alors une base admissible $x = \frac{10}{3}$ et $y = \frac{8}{3}$ que l'on peut utiliser comme point de départ d'une seconde application de l'algorithme du simplexe, cette fois sur $(*)$.