Le grand \( M\)
L'idée du grand \( M\) est de faire les deux phases en même temps. Pour ce faire on introduit un constante \( M\) aussi grand que souhaitée.
§ Méthode du grand \( M\)
On met le problème sous forme phasée en introduisant pour les variables artificielle un grand \( M\)
\[
\begin{array}{c|ccccc|c}
&X&E_{I}&E_{II}&\alpha_{II}&\alpha_{III}&\\\hline
E_I&A_I&Id&0&0&0&B_I\\
\alpha_{II}&A_{II}&0&-Id&Id&0&B_{II}\\
\alpha_{III}&A_{III}&0&0&0&Id&B_{III}\\\hline
&C&0&0&-M&-M&0
\end{array}
\]
On actualise la fonction objectif
en faisant apparaitre \( 0\) pour les variables artificielles
(le grand \( M\) apparaitra dans la fonction objectif).
\[
\begin{array}{c|ccccc|c}
&X&E_{I}&E_{II}&\alpha_{II}&\alpha_{III}&\\\hline
E_I&A_I&Id&0&0&0&B_I\\
\alpha_{II}&A_{II}&0&-Id&Id&0&B_{II}\\
\alpha_{III}&A_{III}&0&0&0&Id&B_{III}\\\hline
&*&0&-M&0&0&\vartheta(M)
\end{array}
\]
On applique la méthode du simplexe avec le tableau précédent. L'optimum \( \vartheta(M)\) est une fonction polynomiale en \( M\) .
- Si au moins une variable artificielle est non nul alors le problème n'a pas de solution.
- Si \( \vartheta(M)\) dépend de \( M\) alors le problème n'a pas de solution.
- Sinon la solution trouvée est une solution.
Détaillons un exemple. Considérons le problème \(
\left\{
\begin{array}{rcl}
x+2y&\leqslant&4\\
x+y&\geqslant&1\\
3x+y&=&6\\
Max(2x+y)&&
\end{array}
\right.
\)
Construisons le tableau et introduisons le grand \( M\) :
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
e_1&1&2&1&0&0&0&4\\
\alpha_1&1&1&0&-1&1&0&1\\
\alpha_2&3&1&0&0&0&1&6\\\hline
&2&1&0&0&-M&-M&0
\end{array}
\]
Mettons à jour la fonction objectif :
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
e_1&1&2&1&0&0&0&4\\
\alpha_1&1&1&0&-1&1&0&1\\
\alpha_2&3&1&0&0&0&1&6\\\hline
&2+4M&1+2M&0&-M&0&0&7M
\end{array}
\]
Appliquons la méthode du simplexe en gardant en mémoire que \( M\) est aussi grand que possible :
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
e_1&1&2&1&0&0&0&4\\
\alpha_1&\boxed{1}&1&0&-1&1&0&1\\
\alpha_2&3&1&0&0&0&1&6\\\hline
&2+4M&1+2M&0&-M&0&0&7M
\end{array}
\]
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
e_1&0&1&1&1&-1&0&3\\
x&1&1&0&-1&1&0&1\\
\alpha_2&0&-2&0&\boxed{3}&-3&1&3\\\hline
&0&-1-2M&0&2+3M&-2-4M&0&-2+3M
\end{array}
\]
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
e_1&0&\boxed{\frac{5}{3}}&1&0&0&-\frac{1}{3}&2\\
x&1&\frac{1}{3}&0&0&0&\frac{1}{3}&2\\
e_2&0&-\frac{2}{3}&0&1&-1&\frac{1}{3}&1\\\hline
&0&\frac{1}{3}&0&0&-M&-\frac{2}{3}-M&-4
\end{array}
\]
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
y&0&1&\frac{3}{5}&0&0&-\frac{1}{5}&\frac{6}{5}\\
x&1&0&-\frac{1}{5}&0&0&\frac{2}{5}&\frac{8}{5}\\
e_2&0&0&\frac{2}{5}&1&-1&\frac{1}{5}&\frac{9}{5}\\\hline
&0&0&-\frac{1}{5}&0&-M&-\frac{3}{5}-M&\frac{22}{5}
\end{array}
\]
En conclusion la solution du problème est \( (x;y)=\left(\dfrac{8}{5} ; \dfrac{6}{5}\right)\) pour un optimum de \( \dfrac{22}{5}\) .