Make your own free website on Tripod.com

INDEX

V. Résumé de la procédure de la méthode du simplexe

(dans le cas d'un problème de maximisation sous contraintes £ et avec un second membre positif)

Etapes

Justification

1. Formuler un programme linéaire pour le problème réel.

Pour obtenir une représentation mathématique du problème

2. Vérifier que le second membre du programme linéaire est positif

Ceci est nécessaire pour obtenir comme variable de base initiale l’origine

3. Ecrire le programme linéaire sous une forme standard

Mettre toutes les contraintes sous forme d’égalité

4. Construire le premier tableau de simplexe

Ce tableau correspond à la solution initiale de base

5. Choisir comme variable entrante dans la base celle qui admet le plus grand effet net positif cj-zj.

La valeur de cj-zj indique la quantité d’augmentation de la fonction objectif si on augmente la valeur de xj d’une unité.

6. Choisir la variable sortante de la base celle qui admet le plus petit ratio supérieur à zéro.

La plus petite valeur de Qi/aij indique le nombre maximal d’unité de xj qu’on peut introduire avant que la variable de base de l’ième ligne ne soit égale à zéro.

7. Construire le nouveau tableau en utilisant la règle de pivot

Cette règle nous permet entre autre de calculer les valeurs des nouvelles variables de décision

8. Faire le test d’optimalité. Si
(cj-zj)
£ 0 pour toutes les variables (hors base), la solution obtenue est donc optimale. Sinon retourner à l’étape 5.

Si (cj-zj) £ 0 alors on n’a pas d’intérêt à faire entrer dans la base aucune de ces variables. Une telle introduction engendra une diminution de la fonction objectif.

 

Cliquer ici pour enregistrer le chapitre 3 en format Word sur votre disque dur (151 Ko)


Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com