LES ÉTAPES DE L’ALGORITHME DU SIMPLEXE
LES ÉTAPES DE L’ALGORITHME DU SIMPLEXE
Mathematics, Programming · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente les étapes essentielles de l'algorithme du simplexe, méthode fondamentale pour résoudre les programmes linéaires (PL). Il s'adresse aux étudiants en optimisation, mathématiques appliquées ou gestion qui souhaitent comprendre la transformation des contraintes, la construction des solutions de base, ainsi que le déroulement itératif de l'algorithme jusqu'à son critère d'arrêt.
Un programme linéaire (PL) est dit sous forme standard lorsque toutes ses contraintes sont des équations et que toutes ses variables sont non négatives. Cette forme est notée (PL=). L'algorithme du simplexe nécessite que le programme soit sous cette forme pour pouvoir être appliqué efficacement.
Avant d'appliquer l'algorithme du simplexe, il faut convertir le programme linéaire en un programme équivalent où toutes les contraintes sont des équations et toutes les variables sont non négatives.
Un programme linéaire contenant uniquement des contraintes ≤ est noté (PL), tandis qu’un programme avec contraintes ≤, ≥, et = est noté (PG). Lorsqu’ils sont convertis pour que toutes les contraintes soient des équations avec variables non négatives, ils sont notés respectivement (PL=) et (PG=).
Considérons un système de m équations à n variables avec n ≥ m. Une solution de base est obtenue en procédant ainsi :
Une solution de base est dite admissible si toutes ses variables sont supérieures ou égales à zéro. Il est important que le nombre de variables soit égal au nombre d’équations pour que cette solution soit bien définie.
Une solution de base admissible de (PL=) est une solution de base pour laquelle toutes les variables sont non négatives. Cette solution correspond à un point extrême du domaine admissible du programme linéaire.
Pour illustrer l’algorithme du simplexe, considérons l’exemple suivant :
Maximiser Z = 1000x1 + 1200x2 Sous contraintes : 10x1 + 5x2 ≤ 200 2x1 + 3x2 ≤ 60 x1 ≤ 34 x2 ≤ 14 x1, x2 ≥ 0
Après ajout des variables d’écart s1, s2, s3, s4, le système devient :
10x1 + 5x2 + s1 = 200 2x1 + 3x2 + s2 = 60 x1 + s3 = 34 x2 + s4 = 14 x1, x2, s1, s2, s3, s4 ≥ 0
Les variables hors base initiales sont x1 et x2 (fixées à 0), et les variables de base sont s1, s2, s3, s4.
Le tableau initial se construit avec :
| Base | Coef. Z | x1 | x2 | s1 | s2 | s3 | s4 | bi |
|---|---|---|---|---|---|---|---|---|
| s1 | 0 | 10 | 5 | 1 | 0 | 0 | 0 | 200 |
| s2 | 0 | 2 | 3 | 0 | 1 | 0 | 0 | 60 |
| s3 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 34 |
| s4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 14 |
Pour un problème de maximisation, on choisit la variable hors base dont le coefficient Cj – zj est le plus grand.
Dans notre exemple, la variable x2 a le plus grand Cj – zj, donc elle entre dans la base.
La variable sortante est déterminée par le minimum des rapports bi / aij, où aij est le coefficient de la variable entrante dans la contrainte i, et bi la valeur de la contrainte i.
Calculs dans notre exemple :
La variable s4 sort donc de la base.
Le pivot est l’élément à l’intersection de la ligne de la variable sortante et de la colonne de la variable entrante (ici 1).
Le pivotage consiste à :
Après pivotage, on obtient un nouveau tableau où la variable entrante remplace la variable sortante dans la base. Les coefficients sont recalculés selon la formule :
Cj – zj = Cj – Σ (Coef. Z de la base * coefficient de la variable dans la contrainte)
Par exemple, le coefficient 10 dans le tableau initial se calcule ainsi :
10 – 0 * 5 / 1 = 10
Un autre exemple pour obtenir -3 :
0 – 3 * 1 / 1 = -3
Les autres coefficients sont calculés de la même manière. Une fois le tableau rempli, on peut passer à l’itération suivante.
L’algorithme du simplexe s’arrête lorsque le critère d’optimalité est atteint :
À ce stade, la solution courante est optimale.