Discussion :

[lemonstrike]

Salut à vous,

je suis en train d'essayer de coder un simplexe et je me demandais comment ça se passait pour choisir la variable entrante lorsque son coeff est négatif dans la matrice des coefficients.

Par exemple, maximiser z avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
x4 = 4 -  x1 - x2 -2x3
x5 = 5 - 2x1      -3x3
x6 = 7 - 2x1 - x2 -3x3
----------------------
 z =     3x1 +2x2 +4x3

Les variables x4, x5, x6 étant des variables d'écart.
Si on fait rentrer x3 en base, en faisant sortir x4 car c'est la contrainte la plus forte, on obtient le dictionnaire suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
x3 =  5/3 -2/3 x1          -1/3 x5
x4 =  2/3 +1/3 x1 - x2     +2/3 x5
x6 =  2           - x2         +x5
----------------------------------
 z = 20/3 +1/3 x1 +2x2     -4/3 x5

Ma question porte sur le point suivant : Si on veut faire rentrer x1 en base, quelle variable doit-on faire sortir ?
Parce que on est sensé pouvoir faire rentrer x1 car son coeff est positif dans z (1/3) mais la deuxième ligne (où x4 est en base) est la plus limitante pour x1 mais contraint x1 à être négatif, non ?

Donc, comment faire rentrer x1 à ce stade ?

En vous remerciant d'avance.

[nihao]

Bonjour,

Le systeme x1=x3=x4=1, x2=x5=0, x6=2, z=21/3 est une solution admissible ou x1 (et les autres) est positif.

Ceci dit,

1- dans l'étape 1, vous faites entrer x3 qui à le plus gros coefficient dans la fonction à maximiser mais c'est x5 qui sort. Pour visualiser tout ça :
http://http://www.phpsimplex.com/en/index.htm
2- Pas forcement une bonne idée de coder soi même un simplex général sauf à but pédagogique (voir numerical recipes). Il existe des librairies optimisées pour ça comme : http://http://lpsolve.sourceforge.net/
Cordialement

[lemonstrike]

Bonjour, merci pour ta réponse !

Je n'ai pas trouvé ce que je cherchais sur les liens que tu m'as envoyé mais sur youtube !
Je passe le lien si quelqu'un en a besoin :

[ame="http://www.youtube.com/watch?v=pg9l7Mx27t8"]Linear Algebra Tutorial - Simplex Method - Pooyan.avi - YouTube[/ame]

En réalité, il suffit simplement d'ignorer les rapports négatifs !

Cordialement