Cours PL: Méthode Simplexe
Ghislain PANDRY
Chercheur, Traitement du signal et des images
Ghislain PANDRY Cours PL: Méthode Simplexe
Introduction
Un programme linéaire (PL) mis sous la forme particulière où
toutes les contraintes sont des équations et toutes les variables sont
non négatives est dit sous forme standard. Il est noté (PL=).
Ghislain PANDRY Cours PL: Méthode Simplexe
Variables d'écart et d'excédent
Avant que l'algorithme du simplexe puisse être utilisé pour résoudre
un programme linéaire, ce programme linéaire doit être converti en
un programme équivalent où toutes les contraintes technologiques
sont des équations et toutes les variables sont non négatives.
Ghislain PANDRY Cours PL: Méthode Simplexe
Contraintes de type (≤) :
Pour chaque contrainte i de ce type, on rajoute une variable
d'écart ei , tel que ei est une variable positive ou nulle.
Ghislain PANDRY Cours PL: Méthode Simplexe
Contraintes de type (≥)
Pour chaque contrainte i de ce type, on retranche une variable
d'excédent ei , tel que ei est une variable positive ou nulle.
Ghislain PANDRY Cours PL: Méthode Simplexe
Remarque
Un programme linéaire qui contient des contraintes
(technologiques) de type ≤ est noté (PL). Un programme linéaire
qui contient des contraintes (technologiques) de type ≤, ≥, =) est
noté (PG). Un programme linéaire (PL) resp (PG) converti tel que
toutes les contraintes technologiques sont des équations et toutes
les variables sont non négatives est noté (PL=) resp (PG=).
Ghislain PANDRY Cours PL: Méthode Simplexe
Variables de base et variables hors base
Il est vraiment important d'avoir le même nombre de variables que
d'équations
Ghislain PANDRY Cours PL: Méthode Simplexe
Solutions admissibles
Toute solution de base de (PL=) pour laquelle toutes les variables
sont non négatives, est appelée solution de base admissible. Cette
solution de base admissible correspond à un point extrême.
Ghislain PANDRY Cours PL: Méthode Simplexe
Résolution du programme linéaire (PL)
Ghislain PANDRY Cours PL: Méthode Simplexe
Résolution du programme linéaire (PL)
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape A : tableau initial
Ghislain PANDRY Cours PL: Méthode Simplexe
Construction du Tableau
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape B : choix de la variable entrante (dans la base)
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape C : choix de la variable sortante
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape C : choix de la variable sortante
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape C : choix de la variable sortante
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape D : pivotage
La cellule bleue est nommée le pivot. Pour passer au tableau
suivant et donc eectuer la première itération, il est essentiel
d'utiliser le pivot.
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape D : pivotage
Le pivotage s'eectue de la manière suivante : On commence par
diviser la ligne du pivot par le chire du pivot. Dans notre exemple,
on divise par 1.
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape D : pivotage
Nous poursuivons avec la matrice identité pour les variables de base.
Nous inscrivons 1 à l'intersection de chaque variable et 0 ailleurs.
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape D : pivotage
Nous devons calculer les nouvelles valeurs pour les cases restantes à
partir du tableau précédent (tableau initial pour la première
itération).
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape D : pivotage
Ghislain PANDRY Cours PL: Méthode Simplexe
Étape D : pivotage
Ghislain PANDRY Cours PL: Méthode Simplexe
Le critère d'arrêt
Nous arrêtons lorsque nous obtenons le critère d'optimalité.
L'algorithme du simplexe s'arrête lorsque :
Cj − Zj ≤ 0 pour un problème de max
Cj − Zj ≥ 0 pour un problème de min
Ghislain PANDRY Cours PL: Méthode Simplexe
