La méthode du simplexe
Lorsque le problème fait apparaitre plus de 2 variables le principe reste le même est est basé sur le théorème stipulant que si la solution existe elle est sur une frontière du simplexe.
On se place donc sur un sommet, et on calcule la valeur de la fonction objectif.
On va ensuite regarder les sommets adjacents et observer si la fonction objectif peut prendre une
valeur supérieur ou pas. Si c'est le cas, on se déplace sur ce nouveau sommet et on recommence
l'étude sinon on s'arrête
et le maximum est trouvé.
Nous ne nous intéresserons pas aux problèmes de convergence mais signalons tout de même que
l'algorithme à ses limites :
- \( \bullet\)
- Si le maximum n'est jamais atteint.
- \( \bullet\)
- Si deux sommets adjacents maximise l'objectif, l'algorithme va boucler à l'infini.
- \( \bullet\)
- Si on ne trouve pas de solution initiale.
- \( \bullet\)
- Si la matrice des contraintes n'est pas de rang maximal (cas dégénéré qui arrive en général lorsqu'une des contraintes est une égalité au lieu d'une inégalité).
Détaillons à présent la méthode du simplexe pour n'importe quelle nombre de variables.
Définition
Soient \( n\) et \( p\) deux entiers strictement positifs,
\( A\in\M_{(p,n)}(\R)\) , \( B\in \M_{(p,1)}(\R)\) , \( C\in\M_{(1,n)}(\R)\) et \( X={}^t(X_i)_{i\in[\![1 ; n]\!]}\)
le vecteur colonne des indéterminées.
Un problème de la forme\( \left\{\begin{array}{c}
A.X = B\\
X\geqslant 0\\
Max(C.X)
\end{array}
\right.\)
est un programme linéaire sous
forme standard.
La première étape de la méthode du simplexe, consiste à transformer un problème linéaire sous forme normale en un problème linéaire sous forme standard en ajoutant des variables.
Proposition
Tout problème linéaire sous forme normale peut se mettre sous forme standard quitte à ajouter des variables, appelées variables d'écarts.
Démonstration
Reprenons le notations précédentes et considérons \( \left\{\begin{array}{c}
A.X \leqslant B\\
X\geqslant 0\\
Max(C.X)
\end{array}
\right.\)
un problème linéaire sous forme normale. Considérons
\[E_k=b_k-\sum_{i=1}^nA_{k,i}X_i\]
les variables d'écarts (toutes positives ou nulles). Le problème linéaire
se transforme en un problème linéaire standard de la forme :
\( \left\{\begin{array}{c}
A'.X' = B\\
X'\geqslant 0\\
Max(C.X)
\end{array}
\right.\)
où
\[
A'=
\begin{pmatrix}
A_{1,1} &\cdots &A_{1,n} & 1 & 0 & 0 &\cdots &0\\
\vdots & & \vdots &0 & 1 & 0 &\cdots &0\\
\vdots & & \vdots &\vdots & &\ddots & &\vdots\\
A_{p,1} & \cdots &A_{p,n} &0 & 0 &\cdots & &1
\end{pmatrix}
\]
est la matrice \( A\) juxtaposée avec la matrice \( Id_{\M_{(p,p)}(\R)}\) et où
\( X'={}^t(X_1,\dots,X_n,E_1,\dots,E_p)\) .
Bien sur, s'il s'agit d'une problème résoluble, il y a une infinité de solution puisqu'il y a plus d'inconnues que d'équations. Il faut choisir celle qui maximisera la fonction objectif. On va donc rajouter à la dernière ligne du système \( A'X'=B\) la fonction objectif :
\[\left\{
\begin{array}{cccccccccc}
A_{1,1}X_1 +& \cdots &+ A_{1,n}X_n & +E_1 &+0 & +0 &\cdots &+0&=&B_1\\
\vdots & & \vdots &+0 & +E_2 &+ 0 &\cdots &+0&=&B_2\\
\vdots & & \vdots &\vdots & &\ddots & &\vdots&=&\vdots\\
A_{p,1}X_1 +& \cdots &+A_{p,n}X_n &+0 & +0 &\cdots & &+E_p&=&B_p\\
C_1X_1 +& \cdots &+C_nX_n &+0 & & \cdots & & +0 &=&-val
\end{array}
\right.
\]
où \( val\) est la valeur de la fonction objectif à l'origine du repère.
Pour déterminer la colonne du pivot, on va choisir celle qui a le plus grand coefficient strictement positif \( C_i\) ; notons \( r\) cet indice.
Pour déterminer la ligne du pivot, on va choisir la ligne du plus petit coefficient strictement positif de la colonne des \( B_i/A_{i,r}\) .
On applique ensuite le pivot et on recommence jusqu'à ce qu'une des conditions de strict positivité dans le choix du pivot ne soit pas satisfaite.
§ Algorithme du simplexe
- \( \bullet\)
- On cherche la ligne du pivot (on parle de variable entrante) :
- 1
- Si tous les coefficients de la dernière ligne sont négatifs ou nuls : STOP.
- 2
- Sinon on choisit l'indice \( r\) du coefficient \( C_i\) strictement positif le plus grand.
- \( \bullet\)
- On cherche la colonne du pivot (on parle de variable sortante) :
- 1
- Si tous les \( B_i/A_{i,r}\) sont strictement négatifs ou infini : STOP.
- 2
- Sinon on choisit l'indice \( s\) du \( B_i/A_{i,r}\) positif ou nul le plus petit.
- \( \bullet\)
- Le pivot est \( A_{s,r}\) . On applique le protocole de Gauss.
- \( \bullet\)
- On réitère le processus.
Une condition nécessaire pour que cet algorithme permette d'arriver à une solution est que le point de départ, implicite dans la formulation, est l'origine du repère.
