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 standard.
- 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 standard et solution de base
On transforme les inéquations en équations avec l’addition de variables.
Pour cela, on introduit une variable d’écart (x3, x4, x5) dans chacune des contraintes de la forme ≤, pour les transformer en égalités (voir cours sur la forme standard) :
| 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. C’est à dire que les variables du programme canonique sont à zéro, les variables d’écarts sont égales à l’élément de droite (b). 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 | |||||||
|---|---|---|---|---|---|---|---|
| c | 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
Une solution de base réalisable est dite dégénérée si au moins une des variables de base est nulle. Si au cours de l’algorithme du simplexe, aucune base rencontrée n’est dégénérée, alors l’algorithme se termine en un nombre fini d’itération. S’il existe une base dégénérée, alors on peut rencontrer un éventuel cyclage de l’algorithme : on retrouve une base déjà rencontrée et on boucle indéfiniment. Pour traiter les cas de dégénérescence, on peut appliquer la règle de Bland (1977) qui assure l’arrêt de l’algorithme en un nombre fini d’itération. Lorsque plusieurs variables sont susceptibles d’entrer ou de sortir de la base, on choisit toujours celle qui a l’indice le plus petit.
É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).
Cette variable est choisi car son impact sur la valeur de Z est le plus important (plus grand gradient). Rentrer cette variable dans la base consiste à trouver une solution dans l’espace des solutions en suivant le gradient de cette variable. Dans le schéma suivant, l’ordonnée à le plus grand gradient par rapport à la solution Z=0, nous allons donc longer son axe (considérer max z= xB) jusqu’à ne plus pouvoir améliorer la solution.
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 : diviser chaque terme indépendant (colonne b) entre l’élément correspondant de la colonne pivot, à condition que les deux éléments soient strictement positifs (supérieures à zéro).
Cela revient à considérer que notre variable sortante va faire un pivot de Gauss avec la variable entrante. En d’autres termes, la variable entrante prendra une valeur non nulle tandis que la variable sortante deviendra nulle.
On opte par la ligne dont le résultat est minimal. En effet, ce calcul permet de savoir jusqu’à quelle valeur peut-on augmenter la variable entrante. Le programme linéaire ayant des contraintes, il n’est pas possible de dépasser la contrainte la plus « contraignante », c’est à dire limitant le plus la valeur de la variable entrante.
Dans cet exemple : Cb := 18/2 , 42/2 et 24/3.
S’il y aurait un élément plus bas ou égal à zéro on n’effectue pas ce quotient. Lorsque tous les éléments de la colonne pivot sont de cette condition on aurait accompli la condition d’arrêt et le problème aurait une solution sans partie bornée.
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 x4 | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
Le tableau correspondant à cette deuxième itération est (notons que x5 est sorti et que x1 est rentré à sa place, de plus, la fonction objectif ne s’exprime plus en x1 mais en x5, et sa valeur est de 24):
| Début itération 2-ième | |||||||
|---|---|---|---|---|---|---|---|
| 3 | 2 | 0 | 0 | 0 | |||
| Base | Cb | b | x1 | x2 | x3 | x4 | x5 |
| x3 | 2 | 0 | 1/3 | 1 | 0 | -2/3 | |
| x4 | 26 | 0 | 7/3 | 0 | 1 | -2/3 | |
| x1 | 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 (il n’y a pas de variable avec un gradient améliorant la solution), on obtient la condition d’arrêt.
La valeur de Z (colonne b) est la solution optimale du problème.
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, 0, 0, 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é
Cas particuliers
- Solutions infinies : lorsque le simplexe s’arrête et que des variables hors base ont pour valeur 0 dans la ligne Z, cela signifie qu’il y a une infinie de solution. Pour connaitre les limites de l’hyperplan (ou le segment) de solutions, il suffit de recalculer le simplexe en rentrant la (ou les) variable(s) dans la base.
- Pas de solution : avec la méthode du grand M, il est possible que le domaine de définition soit vide. Dans ce cas, lors du calcul du grand M certaines variables artificielles ont une valeur non nulle.
- Choix de la variable entrante : lorsqu’il y a un choix parmi les variables entrantes (même valeur), il faut choisir en priorité une variable de base du programme linéaire.
- Choix de la variable sortante : lorsqu’il y a un choix parmi les variables sortantes, on choisit en priorité les variables artificielles, puis les variables d’excès, puis les variables d’écarts puis enfin les variables de base.
- Solution dégénérée : si la solution optimale possède des variables de base nulles, alors elle est dite dégénérée, c’est le cas quand il y a plus de variables de base qu’il y a de contraintes.
Exemple
A noter que parfois le tableau est écrit avec la valeur de -Z avec les coefficients de c, dans ce cas la solution optimale est obtenu lorsque tous les coefficients sont négatifs. Prenons le programme linéaire suivant :
Première itération :
Ce qui donne après pivot :
Voici la deuxième itération avant et après pivot :
Tous les termes de -Z sont négatifs, nous avons donc une solution optimale (0, 250, 0, 200, 500, 0, 100, 0), première et troisième contrainte ne sont pas saturées (variables d’écarts à 500 et à 100); la fonction objectif vaut 350000.
