la méthode du simplexe

IdC 2A Jeudi 16 octobre La méthode du simplexe sur un exemple. Mise en place du cadre. On étudie le programme linéaire suivant écrit sous forme canonique . max z = 5x + y n 30x + y sous contraintes or 5 Sni* to View Dé nition 1. 1 On appelle variable d’écart la quantité mer une contrainte d’inégalité en contrainte d’égalité. } sont hors base. 10 3. La famille (xl , K2 , x3 } forme une base car la sous matrice associée 030 1 01 inversible. Ici, {x4 , x5 sont hors base. OO est n’est pas inversible. Dé nition 2. 2 .

On appelle solution de base une solution du système Ax = b où n variables hors bases sont nulles et les valeurs des m variables de base sont solution du système BF = b où les est le vecteur m x 1 contenant les variables de base. 2. On appelle solution de base réalisable une solution de base qui véri e les contraintes de positivité, c. à. d dont toutes les composantes sont positives ou nulles. aux variables de base sont nuls, 2. La matrice associée aux variables de base est la matrice identité (à une permutation rès), on dit qu’il est écrit sous forme canonique par rapport à la base B correspondante.

Ici par exemple, le programme suivant est écrit sous forme canonique par rapport à la base {x3 , x4, x5 max z = 5×1 + x2 n xi 30X1 +X2+ x4 x2 + xl = 150 60 x4 , x5 Cette écriture est le point de départ de l’algorithme du simplexe. 3. 1 sort de la base est la première à s’annuler quand la variable entrante augmente. Ici, c’est la variable x3 qui sort car les relations 150 – 30X1 montrent que x3 s’annule en premier pour XI = 4 . Donnons également le critère mathématique suivant pour déterminer la variable sortante : Proposition 3. Soit s l’indice de la variable entrante. Si il existe un Indice r pour lequel le mln abk , ak,s > O est attelnt, alors xr est la variable sortante. Sinon, le problème est non borné. Il faut donc le reformuler. 3. 4 Changement de base On va écrire le problème sous forme canonique par rapport à la nouvelle base choisie en utilisant le pivot de Gauss. Ici, la nouvelle base est {XI , x4 , x5 Il est plus commode de travailler sur le système suivant . PAGF optimale.

L’algorithme du simplexe est alors terminé. Sinon, on recommence les opérations de changement de base. 4 Le simplexe en tableaux Le simplexe en tableaux permet de rendre les étapes du simplexe plus rapides. Voici l’ecriture sous forme de tableau pour notre exemple (attention, on a changé l’ordre des équations et des variables d’écart). On applique les critères vu plus haut pour déterminer les variables entrantes et sortantes. Puis on e ectue le pivot de Gauss sur le tableau directement. 30 x2