Recherche Opérationnelle
3ème Année
Chapitre 3 – Simplexe (Max)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Introduction
La méthode du simplexe est une méthode de résolution algébrique d’un P.L.
Qui peut traiter des problèmes avec un nombre de variables très grand
C’est une méthode itérative
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Introduction
Description générale
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Approche par un exemple (le problème de l’usine des meubles)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 1. (Ecriture du Pb sous forme standard)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 2 : (Identification de la 1ère solution de base et Tableau de départ)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 2 : (Identification de la 1ère solution de base et Tableau de départ)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 2 : (1ère solution de base et Tableau de départ)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 2 : (1ère solution de base et Tableau de départ)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 2 : (Forme standard d’un Tableau simplexe)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3
Variable Entrante
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Entrante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Entrante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Entrante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Entrante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Sortante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Sortante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Variable Sortante)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Amélioration de la solution)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Amélioration de la solution)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Retour au Tableau du simplexe)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Retour au Tableau du simplexe)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (Le Nouveau Tableau du simplexe)
Itération 1
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
2ème Itération
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (2ème Itération)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Etape 3 : (2ème Itérartion)
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Principe du simplexe
Interprétation: On est parti d’un premier sommet 0(0,0) …….. On a évolué vers un
deuxième sommet D (11,0) c’est la 1 ère itération…….En 2ème itération on est arrivé à un
autre sommet C(10,2) qui est l’optimum.
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Procédé général du simplexe
Chapitre 3
Résolution d’un P.L. par la méthode du simplexe
Interprétation du simplexe
On sait que la solution optimale du P.L.
se trouve en un sommet de l’ensemble convexe des solutions admissibles.
Définition : Deux sommets A et B sont dits adjacents si les variables de base ne diffèrent que
d’un seul élément.