L’algorithme du simplexe a été introduit par George Dantzig à partir de 1946. Il est un algorithme de résolution des problèmes d’optimisation linéaire.
Il consiste à minimiser une fonction linéaire de n variables réelles,
où 
, sur un ensemble défini au moyen de contraintes affines (ou linéaires) d’égalité et d’inégalité. L’ensemble admissible du problème est donc un polyèdre convexe.
Méthode
La méthode du simplexe est une méthode itérative parcourant les sommets du polyèdre convexe jusqu’à ce que la fonction objectif ne puisse plus être améliorée. Le processus de résolution est le suivant :
- Le problème est écrit sous forme canonique.
- Une solution est trouvée.
- Trouver la colonne du pivot.
- Trouver la ligne du pivot et effectuer la méthode de Gauss
- STOP. Solution optimale trouvée ou pas de solution possible.
Exemple de résolution
Prenons le problème suivant pour appliquer la méthode du simplexe :
| Maximiser | Z=3x + 2y |
| sous les contraintes: | 2x + y ≤ 18 |
| 2x + 3y ≤ 42 | |
| 3x + y ≤ 24 | |
| x ≥ 0 , y ≥ 0 |
Étape 1 : Écriture sous forme canonique et solution de base
On transforme les inéquations en équations avec l’addition de variables d’écart.
Pour cela, on introduit une variable d’écart (x3, x4, x5) dans chacune des contraintes de la forme ≤, pour les transformer en égalités :
| 2·x1 + x2 + x3 = 18 |
| 2·x1 + 3·x2 + x4 = 42 |
| 3·x1 + x2 + x5 = 24 |
Ensuite, on ajuste la fonction objective à zéro : Z – 3·x1 – x2 – 0·x3 – 0·x4 – 0·x5 = 0. Dorénavant, il est possible d’initialiser le tableau de la méthode du simplexe.
Le tableau initial de la méthode du simplexe est composé par tous les coefficients des variables de décision du problème original et les variables d’écart.
| Itération 1ère | |||||||
|---|---|---|---|---|---|---|---|
| 3 | 2 | ||||||
| Base | Cb | b | x1 | x2 | x3 | x4 | x5 |
| x3 | 9 | 18 | 2 | 1 | 1 | 0 | 0 |
| x4 | 21 | 42 | 2 | 3 | 0 | 1 | 0 |
| x5 | 8 | 24 | 3 | 1 | 0 | 0 | 1 |
| Z | 0 | -3 | -2 | 0 | 0 | 0 | |
Aparté : dégénérescence du simplexe
Aparté : solution de base et dégénérescence
À la fin du simplexe, le coût minimal est nul sinon on a détecté l’impossibilité pour (PL). Si tout s’est déroulé normalement (coût nul), on cherche à éliminer de la base toutes les variables artificielles.
Deux cas possibles :
- On a réussi à faire sortir toutes les variables artificielles. On passe au simplexe comme présenté dans l’exemple.
- S’il reste des variables artificielles dans la base (base dégénérée) alors les lignes associées à ces variables sont des contraintes redondantes qu’on élimine.
Étape 2-3 : élection de la variable entrante et sortante de la base
D’abord, on établit la variable qui rentre en base. À cet effet, on choisit la colonne dont sa valeur dans la ligne Z est la plus basse entre tous les négatifs. Dans ce cas, cela serait la variable x1 de coefficient -3. La colonne de la variable qui rentre en base qu’on appelle colonne pivot (en vert).
Une fois obtenue la variable entrante en base, on détermine quelle sera la variable sortante. On prend la décision sur la base d’un simple calcul :
On opte par la ligne dont le résultat est minimal.
Dans cet exemple : Cb := 18/2 , 42/2 et 24/3.
Le terme de la colonne pivot qui avait entraîné le plus petit quotient positif non nul dans la division précédente indique la ligne de la variable d’écart qui sort de base. Dans ce cas, il se révèle x5, de coefficient 3. Cette ligne s’appelle ligne pivot (en rouge).
L’intersection de la ligne pivot et la colonne pivot fait ressortir l’élément pivot, dans ce cas le 3.
Étape 3 : actualisation du tableau
On calcule les nouveaux coefficients du tableau de la manière suivante (pivot de Gauss) :
- Dans la ligne d’élément pivot de chaque nouvel élément est calculé en tant que:
Élément ligne pivot = Élément ancienne ligne pivot / Pivot
- Dans la colonne du pivot: 0 sauf le pivot à 1.
- Dans les lignes restantes chaque élément est calculé (produit en croix):
Nouvel élément ligne = Élément ancienne ligne – (Projection ancienne ligne pivot *Projection ancienne colonne pivot / Élément ancienne pivot).
On montre les calculs pour la ligne x4 :
| Ancienne ligne x4 | 42 | 2 | 3 | 0 | 1 | 0 |
| – | – | – | – | – | ||
| projection | 2*24 | 2*1 | 2*0 | 2*0 | 2*1 | |
| / | / | / | / | / | ||
| pivot | 3 | 3 | 3 | 3 | 3 | |
| = | devient | = | = | = | = | |
| Nouvelle ligne P4 | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
Le tableau correspondant à cette deuxième itération est :
| Début itération 2-ième | |||||||
|---|---|---|---|---|---|---|---|
| 3 | 2 | 0 | 0 | 0 | |||
| Base | Cb | b | x1 | x2 | x3 | x4 | x5 |
| x3 | 0 | 2 | 0 | 1/3 | 1 | 0 | -2/3 |
| x4 | 0 | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
| x1 | 0 | 8 | 1 | 1/3 | 0 | 0 | 1/3 |
| Z | 24 | 0 | -1 | 0 | 0 | 1 | |
STOP : conditions d’arrêt
Si l’objectif est la maximisation, quand dans la dernière ligne (ligne indicatrice) n’existe aucune valeur négative parmi les coûts réduits, on obtient la condition d’arrêt.
La valeur de Z (colonne b) est la solution optimale du problème. Un autre cas possible, c’est que dans la colonne de la variable qui rentre en base toutes les valeurs sont négatives ou nulles. Face à cette situation il n’est pas nécessaire de continuer.
Lorsque cette condition n’est pas remplie, on ré-exécute les processus itérativement.
| Début itération 4ème | |||||||
|---|---|---|---|---|---|---|---|
| 3 | 2 | 0 | 0 | 0 | |||
| Base | Cb | b | x1 | x2 | x3 | x4 | x5 |
| x2 | 0 | 12 | 0 | 1 | -1/2 | 1/2 | 0 |
| x5 | 0 | 3 | 0 | 0 | -7/4 | 1/4 | 1 |
| x1 | 0 | 3 | 1 | 0 | 3/4 | -1/4 | 0 |
| Z | 33 | 0 | 0 | 5/4 | 1/4 | 0 | |
On découvre que dans la dernière ligne tous les coefficients sont positifs. La solution optimale est : 33 avec le vecteur de solution (12, 3). Le vecteur de solution est déterminé par la valeur de b sur les lignes des variables de base. Notons que x5 = 3, c’est-à-dire que la contrainte 3 (contenant la variable d’écart x5) n’est pas saturée avec 3 de marge.
Résumé
