[PDF] LES ÉTAPES DE L 'ALGORITHME DU SIMPLEXE

Qu'est-ce que la méthode du simplexe ?

Le principe de la méthode du simplexe est d’éviter de calculer tous lessommets. A partir d’un sommet donné, la méthode calculera une suite de sommets adjacentsl’un par rapport au précédent et qui améliore la fonction objective. Dé?nition3.1.1Deux sommetsxetysont dits adjacents si les variables de base nedi?èrent que d’un seul élément. 4x2

Comment initialiser le tableau de la méthode du simplexe ?

Dorénavant, il est possible d’initialiser le tableau de la méthode du simplexe. Le tableau initial de la méthode du simplexe est composé par tous les coefficients des variables de décision du problème original et les variables d’écart. Une solution de base réalisable est dite dégénérée si au moins une des variables de base est nulle.

Comment calculer la solution optimale d'un simplexe ?

Ensuite, on poursuit avec la méthode standard du simplexe. Dans notre cas, on choisit lacolonnej= 1et la lignei= 2de pivot. On ne peut améliorer ce résultat car la fonction objectivez=x0= 0. Donc, selon le théorème, nous avons obtenu la solution optimale de la Phase I(4;0;6;0;0)avec la basefx1; x3g.

Comment choisir la base initiale d’un simplexe ?

On notera parBle choix de la base à chaque étape du simplexe. a11 a12 : : : a1n 1 0 : : : 0 a21 a22 : : : a2n 0 1 : : : 0 ........................ La base initiale de l’espace-colonne serafxn+1; xn+2; : : : ; xn+mg.