Les deux phases
Nous avons vu que la méthode du simplexe permet de résoudre des problèmes linéaires. Mais nous avons signalé que cette méthode a quelques limites. L'une de ces limites est que le point de départ de l'algorithme est l'origine du repère. Lorsque ce point n'est pas sur la frontière du simplexe, l'algorithme n'est pas initialisé et ne peut donc pas démarrer.
Ce genre de problème arrive très régulièrement lorsque le problème initial fait apparaitre des équations ou inéquations excluant l'origine.
La méthode des deux phases permet de résoudre ce problème. La première phase va permettre de déterminer un "coin" du simplexe pour permettre d'initialiser l'algorithme la seconde phase va permettre d'arriver à la solution.
Définition
Soient \( p\) , \( n_I\) , \( n_{II}\) et \( n_{III}\) des entiers positifs et \( A_{I}\in \M_{(n_{I},p)}(\R)\) , \( A_{II}\in \M_{(n_{II},p)}(\R)\) , \( A_{III}\in \M_{(n_{III},p)}(\R)\) , \( B_{I}\in \M_{(n_{I}, 1)}(\R^+)\) , \( B_{II}\in \M_{(n_{II}, 1)}(\R^+)\) , \( B_{III}\in \M_{(n_{III}, 1)}(\R^+)\) , \( C\in \M_{(1, p)}(\R)\) et \( X={}^t(X_{i})_{i\in[\![1;p]\!]}\) le vecteur colonne des indéterminés.
Un problème de la forme \( \dpl{
\left\{
\begin{array}{rcl}
A_IX&\leqslant&B_I\\
A_{II}X&\geqslant&B_{II}\\
A_{III}X&=&B_{III}\\
X&\geqslant&0\\
Max(C.X)&&
\end{array}
\right.
}\)
est un problème linéaire sous forme préphasée.
Proposition
Tout problème linéaire est équivalent à un problème linaire sous forme préphasée.
Démonstration
Il suffit de multiplier les lignes avec des coefficients constants négatifs par \( -1\) .
Définition
Reprenons les notations précédentes et considérons le problème préphasée \( \dpl{
\left\{
\begin{array}{rcl}
A_IX&\leqslant&B_I\\
A_{II}X&\geqslant&B_{II}\\
A_{III}X&=&B_{III}\\
X&\geqslant&0\\
Max(C.X)&&
\end{array}
\right.
}\)
On introduit des variables d'écarts \( e^I=(e^I_i)_{i\in [\![1; n_I]\!]}\) et \( e^{II}=(e^{II}_i)_{i\in [\![1; n_{II}]\!]}\) mais également des variables artificielles \( \alpha^{II}=(\alpha^{II}_i)_{i\in [\![1; n_{II}]\!]}\) , \( \alpha^{III}=(\alpha^{III}_i)_{i\in [\![1; n_{III}]\!]}\) toutes positives.
On appel forme phasée du problème la forme
\[
\left\{
\begin{array}{rcl}
A_IX+e^I&=&B_I\\
A_{II}X-e^{II}+\alpha^{II}&=&B_{II}\\
A_{III}X+\alpha^{III}&=&B_{III}\\
X&\geqslant&0\\
Max(C.X)&&
\end{array}
\right.
\]
§ Méthode des deux phases
- Première phase.
- On met le problème sous forme phasée en modifiant 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&0&0&-1&-1&0
\end{array}
\]
- \( \bullet\)
- On actualise la fonction objectif
en faisant apparaitre \( 0\) pour les variables artificielles
(en sommant les blocs de ligne des variables artificielles
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&-1&0&0&\vartheta
\end{array}
\]
- \( \bullet\)
- On applique la méthode du simplexe avec le tableau précédent.
- Si \( \vartheta\neq 0\) après l'application de l'algorithme du simplexe
ou si au moins une variable artificielle est non nul
alors le problème initial n'admet pas de solution.
- Sinon on élimine les variables artificielles et on passe à la phase 2.
- Seconde phase.
- On récupère un tableau sans variable artificielle. On modifie la fonction objectif :
\[
\begin{array}{c|ccc|c}
&X&E_{I}&E_{II}&\\\hline
*&*&*&*&*\\
*&*&*&*&*\\
*&*&*&*&*\\\hline
&C&0&0&0
\end{array}
\]
- \( \bullet\)
- On actualise la fonction objectif : on soustrait de la fonction objectif les lignes apparaissant dans le tableau.
- \( \bullet\)
- On applique la méthode du simplexe.
Détaillons un exemple en suivant l'algorithme précédent.
Considérons le problème
\[
\left\{
\begin{array}{rcl}
x+2y&\leqslant&4\\
-x-y&\leqslant&-1\\
3x+y&=&6\\
Max(2x+y)&&
\end{array}
\right.
\]
On met le problème sous forme préphasée :
\(
\left\{
\begin{array}{rcl}
x+2y&\leqslant&4\\
x+y&\geqslant&1\\
3x+y&=&6\\
Max(2x+y)&&
\end{array}
\right.
\)
- Première phase.
-
On construit le tableau correspondant à la forme phasée :
\[
\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
&0&0&0&0&-1&-1&0
\end{array}
\]
On actualise la fonction objectif en faisant apparaitre des zéros aux variables artificielles :
\[
\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
&4&2&0&-1&0&0&7
\end{array}
\]
On applique la méthode du simplexe.
\[
\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
&4&2&0&-1&0&0&7
\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&-2&0&3&-4&0&3
\end{array}
\]
\[
\begin{array}{c|cccccc|c}
&x&y&e_1&e_2&\alpha_1&\alpha_2&\\\hline
e_1&0&\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&0&0&0&-1&-1&0
\end{array}
\]
Le coefficient en bas à droite étant nul, il existe au moins une solution. On peut passer à la seconde phase.
- Seconde phase.
-
On supprimes les variables artificielles et on modifie la fonction objectif :
\[
\begin{array}{c|cccc|c}
&x&y&e_1&e_2&\\\hline
e_1&0&\frac{5}{3}&1&0&2\\
x&1&\frac{1}{3}&0&0&2\\
e_2&0&-\frac{2}{3}&0&1&1\\\hline
&2&1&0&0&0
\end{array}
\]
On actualise la fonction objectif en soustrayant deux fois la ligne du \( x\) dans la fonction objectif (\( 2\) fois car le coefficient du \( x\) est \( 2\) , s'il y avait eu une ligne \( y\) on aurait soustrait une fois la ligne \( y\) et s'il y avait eu les deux lignes on aurait soustrait deux fois la ligne \( x\) et une fois la ligne \( y\) ).
\[
\begin{array}{c|cccc|c}
&x&y&e_1&e_2&\\\hline
e_1&0&\frac{5}{3}&1&0&2\\
x&1&\frac{1}{3}&0&0&2\\
e_2&0&-\frac{2}{3}&0&1&1\\\hline
&0&\frac{1}{3}&0&0&-4
\end{array}
\]
On applique la méthode du simplexe :
\[
\begin{array}{c|cccc|c}
&x&y&e_1&e_2&\\\hline
e_1&0&\boxed{\frac{5}{3}}&1&0&2\\
x&1&\frac{1}{3}&0&0&2\\
e_2&0&-\frac{2}{3}&0&1&1\\\hline
&0&\frac{1}{3}&0&0&-4
\end{array}
\]
\[
\begin{array}{c|cccc|c}
&x&y&e_1&e_2&\\\hline
y&0&1&\frac{3}{5}&0&\frac{6}{5}\\
x&1&0&-\frac{1}{5}&0&\frac{8}{5}\\
e_2&0&0&\frac{2}{5}&1&\frac{9}{5}\\\hline
&0&0&-\frac{1}{5}&0&-\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}\) .
