Discussion :

[luchio13579]

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 !

[Biribibi]

Bonjour,

Une réponse un peu naïve:
Si tu as une clause du type AX >= b, tu remplaces par -AX <= -b
Si c'est une égalité AX = b, tu la remplaces par deux clauses AX <= b et -AX <= -b

Ca donne:

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

[biaggi]

Bonjour,

Je ne sais pas si la question est toujours d'actualité mais je vais essayer d'y répondre.

Modifier le sens des contraintes n'est pas vraiment indiqué car, dans un sens comme dans l'autre, les variables d'écart (qui doivent être >=0) ajoutées sont créditées d'un coefficient -1 lors de la mise sous forme canonique. La forme canonique ne peut alors être obtenue...

La méthode pour utiliser le simplex est alors d'introduire des variables d'écart (à coefficient -1 pour les contraintes de type >=) puis d'autres variables (dites artificielles) à coefficient 1. On modifie ensuite la fonction objectif du modèle, on cherche en effet désormais à minimiser la somme des variables artificielles. On résout ce premier modèle jusqu'à obtenir un optimum nul, correspondant à des variables artificielles toutes nulles. On dispose alors automatiquement d'une base canonique pour le modèle initial. On reprend après cela en compte la fonction objectif initiale du modèle et on peut commencer à résoudre le modèle initial via le simplex.

La non-convergence vers un optimum nul lorsqu'on minimise la somme des variables artificielles est équivalente à une non réalisabilité du modèle initial: il est impossible d'obtenir une base canonique, et donc une solution réalisable.

Cette méthode s'appelle la méthode des deux phases. Une autre méthode, dite de Big M existe, elle a un fonctionnement analogue mais permet de prendre en compte directement les variables artificielles dans une seule et même phase. Google doit regorger d'explications à ce sujet.

En espérant avoir un peu aidé...