Méthode du Simplexe

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,

simplexe

simplexe2, 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 :

  1. Le problème est écrit sous forme canonique.
  2. Une solution est trouvée.
  3. Trouver la colonne du pivot.
  4. Trouver la ligne du pivot et effectuer la méthode de Gauss
  • STOP. Solution optimale trouvée ou pas de solution possible.

simplex-method

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

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.

Aparté : solution de base et dégénérescence

Pour obtenir une solution de base réalisable ou bien pour détecter l’impossibilité, on introduit un problème de programmation linéaire auxiliaire pour des variables supplémentaires appelées variables artificielles.
Sans titre13.png
Un (PL) admet une solution réalisable si et seulement si le problème auxiliaire (PLA) admet une solution de base optimale avec a=0. On applique l’algorithme du simplexe au problème auxiliaire (PLA).

À 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 :

  1. On a réussi à faire sortir toutes les variables artificielles. On passe au simplexe comme présenté dans l’exemple.
  2. 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 :

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).

On opte par la ligne dont le résultat est minimal.

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 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é

simplex

Publicités