Algorithme du simplexe

[lulu2468]

Bonjour,

J'ai une question par rapport à l'algorithme du simplexe. Je l'ai étudié cette année, mais je voudrais savoir comment il est possible de calculer un optimum (maximum ou minimum) mais pas seulement avec des contraintes de type inférieur ou égal:

Après avoir fait beaucoup de recherche sur cet algorithme, je retrouve tout le temps pour rechercher une valeur optimale des contrainte sous la forme :

x1 + 2x2 <= 6
3x1 - 5x2 <= 3
2x1 + x2 <= 1
avec x1 >=0 et x2 >=0

(Ceci est un exemple bien sur)

Ma question est de savoir comment on peut trouver une valeur optimale (minimum ou maximum toujours), mais avec des contraintes sous la forme :

x1 + 2x2 = 6
3x1 - 5x2 >= 3
2x1 + x2 <= 1
avec x1 >=0 et x2 >=0

(J'ai repris les même valeur ais en changeant les signes des inégalités).

Je sais comment utiliser cet algorithme dans le premier exemple, mais pas dans le deuxième.
Comment le met on sous forme canonique dans ce cas la ?
Comment fait on la suite de l'algorithme ?

Merci de votre aide !

[Ben314]

Toutes les égalitées permettent d'identifier une des variables en fonctions des autres :

Dans ton exemple,
x1 + 2x2 = 6 équivaut à x1 = 6 - 2x2 et , si tu remplace tout les x1 par 6 - 2x2 dans toutes les autres formules, tu peut ensuite "oublier" le x1 et résoudre le reste (attention au fait que, en général, il est sous entendu que x1 doit être positif, donc il faut rajouter l'inéquation 6 - 2x2 >= 0)

Ensuite, pour les inégalités, il fut bien ce dire que, par exemple
3x1 - 5x2 >= 3 peut se réécrire -3x1 + 5x2 <= -3 qui est "dans le bon sens".

Le problème profond est que, si tu as "un peu n'importe quoi" comme inégalités, il n'est pas clair du tout que le domaine vérifiant toutes ces inégalités ne soit pas... vide.
Evidement, dans ce cas, chercher le max ou le min n'a plus aucun sens...

Il me semble que, assez souvent, dans la pratique, on a un domaine (i.e. des inégalités) qui contient le point (0,0,...,0) ce qui assure que le domaine n'est pas vide et permet aussi d'avoir un "point de départ" pour l'algo. du simplexe.

Si ce n'est pas le cas, (par exemple l'inégalité 3x1 - 5x2 >= 3 n'est pas vrai pour x1=x2=0) tu est trés embèté pour trouver de quel "point de départ" tu va partir pour l'algo.

[fatal_error]

salut,

je rajoute aussi que d'un point de vue info, tu peux ecrire legalite comme deux inegalites :
x1+x2 = 6
donne
x1 + x2 <= 6
et
x1 + x2 >= 6 <=> -x1 - x2 <= -6