Un simplexe est une portion de ℝn délimitée par des
hyperplans.
L’algorithme du simplexe sert à maximiser une fonction linéaire
sous des contraintes d’égalité ou d’inégalité linéaire.
Le principe de l’algorithme consiste à trouver un sommet du simplexe
défini par les contraintes, puis à sélectionner une arête
et la suivre jusqu’au sommet suivant, la sélection se faisant
de sorte à ne jamais diminuer la valeur de la fonction linéaire.
On effectue donc les étapes suivantes
Un sommet va être caractérisé dans la suite par ses composantes nulles et ses composantes non nulles. La représentation matricielle associée à un sommet des contraintes d’égalité fait apparaitre une sous-matrice identité dans les colonnes correspondant aux composantes non nulles du sommet. Par exemple, si on part du problème, chercher :
max(2x+y−z+4) lorsque | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
on pose x=1−X, y=Y+2, donc on cherche :
max(−2X+Y−z+8) lorsque | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
puis on élimine z par la contrainte d’égalité z=5−X+3Y et on cherche :
max(−2X+Y−(5−X+3Y)+8) lorsque | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
cela revient donc à chercher :
max(−X−2Y+3) lorsque | ⎧ ⎨ ⎩ |
|
Il faut ici ajouter une variable d’écart t ≥ 0 pour
transformer la dernière inégalité en égalité :
on pose t=3−(−3X +2Y) et on a alors
t ≥ 0 et −3X +2Y+t=3 est équivalent à −3X +2Y ≤ 3, et
cela donne un sommet de départ évident.
La matrice correspondant à ces conditions est alors la ligne
(−3, 2, 1, 3 ) |
le sommet de départ associé est (X,Y,t)=(0,0,3) la sous-matrice identité utilise la 3ème colonne (t est le coefficient non nul). On pourrait passer le coefficient non nul en 2ème colonne (sommet (X,Y,t)=(0,3/2,0)) en réécrivant l’égalité sous la forme
(−3/2, 1, 1/2, 3/2 ) |
mais on ne pourrait passer le coefficient non nul en 1ère colonne
(il n’y a en effet que 2 sommets à ce simplexe).
Avec Xcas, on tape :
On obtient :
En général, le passage d’un sommet à un autre sommet consiste alors à effectuer une opération de réduction de Gauss qui fait sortir une colonne et entrer une autre colonne dans les composantes non nulles du sommet, ce qui revient à déplacer la sous-matrice identité. On doit prendre garde à effectuer l’opération de réduction de Gauss en conservant la positivité du membre de droite des contraintes de l’égalité, et ce sans diminuer la valeur de la fonction à optimiser. Pour pouvoir réaliser cette dernière condition, on augmente la matrice des contraintes d’égalité par une ligne formée des opposés des coefficients de la fonction à maximiser, sauf en dernière colonne (on y met le coefficient constant de la fonction à maximiser). Dans l’exemple ce serait
⎛ ⎜ ⎝ |
| ⎞ ⎟ ⎠ |
On crée (si nécessaire) des zéros dans cette dernière ligne dans les colonnes correspondant à la sous-matrice identité (donc aux composantes non nulles du sommet), de sorte que le coefficient constant de la ligne (après cette réduction) représente la valeur de la fonction à optimiser en ce sommet. Plus générallement pour un point du simplexe, au cours de la réduction la somme de la fonction à maximiser et du produit scalaire des coordonnés du point avec cette dernière ligne (privé du dernier coefficient) vaut le dernier coefficient. On aura donc un sommet réalisant le maximum si tous les coefficients de la ligne sont positifs (sauf le dernier). C’est le cas ici, le maximum est 3, atteint pour X=Y=0 (donc x=1, y=2 et z=5).
L’instruction simplex_reduce de Xcas applique l’algorithme du simplexe dans deux situations distinctes : soit le problème est posé sous forme “canonique” et on lui donne 3 arguments (cf. infra), soit on lui donne un seul argument qui doit être une matrice “associée à un sommet” au sens de ce paragraphe.