Scribd
Importer
20 vues15 pages

Optimisation du Simplexe en Programmation Linéaire

Ce document décrit les étapes de la méthode du simplexe pour résoudre un programme linéaire. Il introduit les notions de variables d'écart et d'excédent pour transformer les contraintes en équations, ainsi que les notions de variables de base et hors base. Les étapes de choix de la variable entrante, de la variable sortante et le pivotage sont également détaillées.

Transféré par

Rabah Madrid
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd
20 vues15 pages

Optimisation du Simplexe en Programmation Linéaire

Ce document décrit les étapes de la méthode du simplexe pour résoudre un programme linéaire. Il introduit les notions de variables d'écart et d'excédent pour transformer les contraintes en équations, ainsi que les notions de variables de base et hors base. Les étapes de choix de la variable entrante, de la variable sortante et le pivotage sont également détaillées.

Transféré par

Rabah Madrid
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd

ChapitreVI/Optimisation et méthode de Simplexe

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


2. 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.
a. Contraintes de type (≤) : on rajoute une variable d’écart ei ≥ 0
Exemple : se transforme en

b. Contraintes de type (≥) : on retranche une variable d’excédent ei ≥ 0

Exemple : se transforme en
Remarque:
3. Variables de base et variables hors base

Considérons un système d’équations à n variables et m équations où


n≥m
Une solution de base pour ce système est obtenue de la manière suivante :

a)On pose n-m variables égales à 0. Ces variables sont appelées variables hors
base (V.H.B.).

b) On résout le système pour les m variables restantes. Ces variables sont


appelées les variables de base (V. B.)

c) Le vecteur de variables obtenu est appelé solution de base (il contient les
variables de base et les variables hors base)

Une solution est admissible si toutes les variables de la solution de base sont
≥ 0.
4. 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.

5. Résolution du programme linéaire (PL)


Étape B : choix de la variable entrante (dans la base)

Étape C : choix de la variable sortante

Dans un problème de min OU de max, la variable sortante sera le minimum des


Dans notre exemple, nous devons évaluer :
Var. entrante

c’est le minimum, donc e4 est la variable qui sort de la base.


Étape D : pivotage

La cellule bleue est nommée le pivot. Pour passer au tableau suivant et donc
effectuer la première itération, il est essentiel d’utiliser le pivot.
Le pivotage s’effectue de la manière suivante :
On commence par diviser la ligne du pivot par le chiffre du pivot.
Dans notre exemple, on divise par 1.
Nous poursuivons avec la matrice identité pour les variables de base. Nous
inscrivons 1 à l’intersection de chaque variable et 0 ailleurs.
Nous devons calculer les nouvelles valeurs pour les cases restantes à partir
du tableau précédent (tableau initial pour la première itération).
Les cases restantes se calculent de la même façon. Lorsque le tableau est rempli
(comme ci‐dessus), il est possible de passer à la deuxième itération qui s'effectue
de la même façon.
6. 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:

Vous aimerez peut-être aussi