algorithme simplexe: 1 question
Bonjour à tous,
J'ai une petite question concernant l'algorithme simplexe: quand termine t-on ? Du moins je ne comprends pas la condition d'arrêt dans l'exemple de ci-dessous.
minimiser -2X-Y
avec X et Y positifs
et on a:
X+A=2
Y+B=2
X+Y+C=3
il faut trouver le minimum.
Je pose donc:
A1=2-X-A
A2=2-Y-B
A3=3-X-Y-C
donc (*) min A1+A2+A3=7-2X-2Y-A-B-C
je choisis Y:
A1=2-X-A
Y=2-A2-B
A3=1-X+A2+B-C
donc (**) min 3-2X+2A2+B-A-C (on a remplacé Y dans (*) )
je choisis ensuite X:
A1=1-A2-B+C+A3-1
Y=2-A2-B
X=1+A2+B-C-A3
(***) min 1-B+C+2A3-A (on a remplacé X dans (**) )
A=1-A1-A2-B+C+A3
Y=2-A2-B
X=1+A2+B-C-A3
min A1+A2+A3 (on a remplacé A dans (***) )
on met A1,A2 et A3 en positifs
on obtient:
A=1-B+C
Y=2-B
X=1+B-C
min -4+B+2C
puis ensuite
B=1-A+C
Y=1+A-C
X=2-A
min -5+A+C
FIN !
Voilà, et bien c'est ça que je n'arrive pas à comprendre: pourquoi sommes nous à la fin ? Pourquoi ne serait-ce pas l'étape précédente la fin ? Et pourquoi n'y aurait-il pas une étape supplémentaire.
Merci de votre aide
J'ai une petite question concernant l'algorithme simplexe: quand termine t-on ? Du moins je ne comprends pas la condition d'arrêt dans l'exemple de ci-dessous.
minimiser -2X-Y
avec X et Y positifs
et on a:
X+A=2
Y+B=2
X+Y+C=3
il faut trouver le minimum.
Je pose donc:
A1=2-X-A
A2=2-Y-B
A3=3-X-Y-C
donc (*) min A1+A2+A3=7-2X-2Y-A-B-C
je choisis Y:
A1=2-X-A
Y=2-A2-B
A3=1-X+A2+B-C
donc (**) min 3-2X+2A2+B-A-C (on a remplacé Y dans (*) )
je choisis ensuite X:
A1=1-A2-B+C+A3-1
Y=2-A2-B
X=1+A2+B-C-A3
(***) min 1-B+C+2A3-A (on a remplacé X dans (**) )
A=1-A1-A2-B+C+A3
Y=2-A2-B
X=1+A2+B-C-A3
min A1+A2+A3 (on a remplacé A dans (***) )
on met A1,A2 et A3 en positifs
on obtient:
A=1-B+C
Y=2-B
X=1+B-C
min -4+B+2C
puis ensuite
B=1-A+C
Y=1+A-C
X=2-A
min -5+A+C
FIN !
Voilà, et bien c'est ça que je n'arrive pas à comprendre: pourquoi sommes nous à la fin ? Pourquoi ne serait-ce pas l'étape précédente la fin ? Et pourquoi n'y aurait-il pas une étape supplémentaire.
Merci de votre aide
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tu es à la fin parce que A et C prennent des valeurs positives ou nulles, donc le min, obtenu pour A=C=0, vaut -5.
J'ai un peu de mal à comprendre ton exemple. Tu écris :
"minimiser -2X-Y
avec X et Y positifs
et on a:
X+A=2
Y+B=2
X+Y+C=3
il faut trouver le minimum.
Je pose donc:
A1=2-X-A "
Déja une remarque inquiétante : d'après la condition X+A=2, on a A1=0.
Ensuite je ne comprends pas ton problème (il n'est pas posé clairement) :
* Quelles sont les variables ?
* Où te sers-tu de l'hypothèse X est positif ?
J'ai l'impression qu'il va te falloir revenir à ton cours. Au fait, quelles études fais-tu ?
Cordialement
Tout d'abord, pour répondre à Gérard, il s'agit ici d'une correction de mon cours, et l'algorithme stipule de transformer X+A=2 en X+A-2=0 puis de poser: A1=2-X-A
Il en est de même pour tous les autres exemples de mon cours.
Quant à la réponse de sclormu, je ne comprends pas vraiment: "A et C prennent des valeurs positives ou nulles", c'est possible d'avoir une petite explication ?
l'algo de mon cours stipule:
- choisir une variable y avec un coeff negatif dans la fonction objective
- trouver l'equation x=b+cy+... où c positif et -b/c est minimal
- réécrire cette équation vers y=-b/c + (1/c)x+... (pivoter)
- substituer -bc+(1/c)x+... pour y dans toutes les autres équations et dans la fonction objective
jusqu'à ce qu'il n'existe pas une telle variable y ou une telle équation
si un tel y n'existe pas une solution optimale est trouvé
sinon il n'y a pas de solution optimale
Voilà, merci d'avance !
Sinon comme demandé, master d'informatique
Alors, je m'interroge sur ce que fait ton prof. Car -2X-Y n'est en rien minimisé! Il est simplement écrit en tenant compte des équations qui relient X et Y à A, B et C :
Comme X = 2- A et Y = 2 - B, -2X-Y = 2A+B-6 (Si A et B sont constantes, ceci est constant, si ce sont des variables il reste à minimiser 2A+B-6 en tenant compte des domaines de variation de A et B : Par exemple si a et B sont positifs, le minimum est -6).
Comme X+Y+C = 3, C = 3 - X - Y = -1 -A - B
Ce qui permet de remplacer B dans le résultat pour retrouver -2X-Y = -5+A+C
Il doit y avoir des hypothèses que tu oublies dans ta présentation.
Cordialement
NB : L'idée géométrique qui est derrière la méthode est qu'une expression linéaire correspond à une hypersurface, que les contraintes définissent un simplexe (forme connexe limitée par des hypersurfaces, ou seulement son bord), et que les extrema se trouvent sur les bords. Un dessin en dimesion 3 est assez explicite.
Effectivement je comprends bien avec ce raisonnement, mais l'application de l'algorithme du corrigé est bien plus long comme montré ci-dessus.
Pour précision, je n'oublie pas des hypothèses:
l'exercice demande:
" minimiser -2X-Y par rapport à X>=0 ^ Y>=0 ^ X <=2 ^ Y<=2 ^ X+Y <= 3 "
Tu donnes enfin le bon énoncé !
Je ne connais pas bien l'algorithme que tu présentes (je l'ai vu en théorie, et en notation matricielle dans les cours de BTS de mon épouse il y a 20 ans). C'est une retraduction de l'idée : les extrémums sont sur les sommets du simplexe. La transformation que l'on choisit revient à choisir l'arète qui fera le plus diminuer la fonction objectif. L'existence de " l'equation x=b+cy+... où c positif et -b/c est minimal " revient à l'existence d'une arète qui fait diminuer, donc lorsqu'il n'y a plus d'équation on a fini, on est au point qui réalise le minimum.
Mais je ne comprends pas vraiment le corrigé, car nulle part on ne traite les valeurs de X et Y et la valeur recherchée de -2X-Y. A toi d'aller voir.
Tu peux illustrer tes calculs par un dessin dans le plan (coordonnée X et Y), en recherchant les demi plans donné par les conditions et en regardant comment sont les droites d'équations -2x-Y = Cte.
Cordialement
Merci bien Gérard pour l'aide !