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 c_j-z_j.

La valeur de c_j-z_j indique la quantité d’augmentation de la fonction objectif si on augmente la valeur de x_j 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 Q_i/a_ij indique le nombre maximal d’unité de x_j 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
(c_j-z_j) £ 0 pour toutes les variables (hors base), la solution obtenue est donc optimale. Sinon retourner à l’étape 5.

Si (c_j-z_j) £ 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.