Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Entraide (supérieur)
- » Optimisation
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- freddy
- 19-06-2014 13:47:48
Re,
c'est très simple : comme on ne s'entend pas sur le net, on ne connait pas le ton sur lequel on cause. Donc on utilise des phrases plus amicales comme : bonjour et merci de ta réponse. Il y a pourtant un point que j'ai du mal à comprendre ...
du coup, si tu expliques bien ce que tu ne comprends pas, c'est plus facile pour nous (oui, nous sommes quelques-uns à apporter un soutien sans faille à ceux qui en ont besoin, nous rendons ce que nous avons reçu il y a longtemps ) de comprendre ta difficulté et de trouver le bon chemin explicatif.
Je sais, nous sommes trop "vieux" pour bien avoir compris le langage en mode flash des sms et autres forum ... c'est comme ça, nos ancêtres non plus ne comprenaient pas tout ce que nous leur disions, alors nous faisions des efforts et nous nous appliquions ! :-)
A te lire !
- hollye
- 19-06-2014 13:37:32
D'accord merci.
Ps : je vois pas en quoi j'ai parlé méchamment , on doit pas avoir la même définition ... mais c'est pas grave , merci de votre aide .
- freddy
- 19-06-2014 13:25:15
Re,
1) faut voir à me parler gentiment, sinon je m'énerve et quand je m'énerve, je ne parle plus :-)
2) si tu sais lire, reporte toi aux posts #6 et 7 . Si tu ne sais pas lire, retourne à l'école élémentaire. ;-)
3) [tex]x_3[/tex] doit être non négatif. C'est flou par rapport à une information du genre [tex]x_1[/tex] doit être non négatif ET ne peut excéder 4, non ?
4) le polyèdre des contraintes qui forme l'ensemble de résolution est défini par l'orthant positif de [tex]\mathbb{R}^m[/tex] considéré (qui forme un ensemble de contraintes naturelles) + un ensemble de contraintes techniques dont chacune forme un hyperplan séparateur quand on passe de l'inégalité large à l'égalité. C'est ce qu'on appelle "saturer une contrainte".
Un sommet non dégénéré est un point intersection de [tex]m[/tex] contraintes techniques saturées choisies parmi [tex]p \ge m[/tex] contraintes techniques. Sinon, il est dit dégénéré.
- hollye
- 19-06-2014 13:05:27
Re,
je continue mes recherches. Donc on dit qu'un sommet est non dégénéré si le point qui est à l'intersection de toutes les contraintes contient un nombre de valeur non nulle égale au nombre de contraintes. Sinon, il est dit "dégénéré".
Dans ce problème, on travaille sur l'orthant positif de [tex]\mathbb{R}^3[/tex].
On a quatre contraintes définissant chacune un plan dans l'espace. A priori, il y a donc 4 sommets.
Un sommet est défini par l'intersection de 3 contraintes sur 4. On observe que [tex] p_1[/tex] n'est pas un sommet, [tex]p_2[/tex] est en dehors du polyèdre, et [tex]p_3[/tex] est aussi un sommet dégénéré.
Tout cela bien entendu au bénéfice d'inventaire, car si j'ai bien compris, un sommet dégénéré ne peut pas être retenu comme étape de calcul dans l'algorithme du simplexe.
A suivre !
D'accord ,m ais là vous disiez que p1 n'était pas un sommet , donc c'est oui au final ?
Puis pourquoi x3=0 n'est pas une contrainte saturée ?
- freddy
- 19-06-2014 10:21:53
Salut,
je pense ne pas me tromper en disant que l'important dans cette affaire est que chaque sommet non dégénéré est l'intersection de trois plans non colinéaires, chaque plan correspondant à une contrainte technique saturée.
La contrainte de positivité siginifie que les input ne peuvent être négatifs (ça vaudrait dire que tu fais du + avec du - ...).
Donc tu peux chercher les sommets non dégénérés de cette manière.
Quand un point n'est pas un sommet au sens de l'intersection de trois plans non colinéaires, mais qu'il appartient à une arrête (intersection de deux plans) + une valeur particulière dans le polyèdre des contraintes, c'est alors un point particulier que l'algorithme du simplexe traitera de manière particulière.
PS : les quatre sommets sont les points de coordonnées (0,6,1), (4,0,2), (4,6,1) et enfin (4,6, -1). Manifestement, le dernier est en dehors du domaine de résolution.
- freddy
- 18-06-2014 21:45:50
Salut,
j'attendais que tu donnes signe de vie :-). Si tu pouvais préciser ta question, ça m'arrangerait.
Si on reprend de manière simple, [tex]p_1=(2,\,6,\,0)^T[/tex] est l'intersection des trois plans suivants :
[tex]\begin{cases} x_1+x_2+2x_3=8 \\ x_2=6 \\ x_3=0 \end{cases}[/tex]
C'est bien un sommet, mais il est dégénéré car les deux premiers plans sont des contraintes effectives et saturées, pas la troisième. C'est pour cela que j'ai dit que le point était à l'intérieur du domaine de résolution.
De la même manière, [tex]p_3=(4,\,0,\,2)^T[/tex] est l'intersection des trois plans suivants :
[tex]\begin{cases} x_1+x_2+2x_3=8 \\ x_2+6x_3=12 \\ x_1=4 \end{cases}[/tex]
Dans ce cas, c'est aussi un sommet, et il n'est pas dégénéré, car les trois plans correspondent bien à trois contraintes effectives et saturées. En particulier, les valeurs [tex]x_2=0[/tex] et [tex]x_3=2[/tex] se déduisent du système d'équation.
On retrouve bien la définition de sommet non dégénéré et de sommet dégénéré.
- hollye
- 17-06-2014 22:31:13
Merci de ta réponse.
J'ai une question ...en fait je ne comprend pas pourquoi p3 est l'intersection des trois plans ?
pourquoi p1 ne l'est pas ?
Donc même si un point sature les contraintes , il peut ne pas être un sommet?
- freddy
- 17-06-2014 10:19:40
Re,
je continue mes recherches. Donc on dit qu'un sommet est non dégénéré si le point qui est à l'intersection de toutes les contraintes contient un nombre de valeur non nulle égale au nombre de contraintes. Sinon, il est dit "dégénéré".
Dans ce problème, on travaille sur l'orthant positif de [tex]\mathbb{R}^3[/tex].
On a quatre contraintes définissant chacune un plan dans l'espace. A priori, il y a donc 4 sommets.
Un sommet est défini par l'intersection de 3 contraintes sur 4. On observe que [tex] p_1[/tex] n'est pas un sommet, [tex]p_2[/tex] est en dehors du polyèdre, et [tex]p_3[/tex] est aussi un sommet dégénéré.
Tout cela bien entendu au bénéfice d'inventaire, car si j'ai bien compris, un sommet dégénéré ne peut pas être retenu comme étape de calcul dans l'algorithme du simplexe.
A suivre !
- freddy
- 16-06-2014 22:25:42
Re,
je reformule;
On considère le polyèdre [tex]\mathcal{P}[/tex] défini par ces inégalités :
[tex]\begin{cases} x_1+x_2+2x_3 \le 8
\\ x_2+6x_3 \le 12
\\ 0 \le x_1 \le 4
\\ 0 \le x_2 \le 6
\\ x_3 \ge 0
\end{cases}[/tex]Parmi les points suivants :
[tex]p_1=(2,6,0)^T,\, p_2=(4,6,0)^T,\, p_3=(4,0,2)^T[/tex] , trouver ceux qui sont des sommets et déterminer ceux qui sont dégénérés. Justifier les réponses
On voit que [tex]p_1[/tex] est à l'intérieur de [tex]\mathcal{P}[/tex] et qu'il sature deux contraintes sur 4, [tex]p_2[/tex] à l'extérieur et [tex]p_3[/tex] à l'intersection des trois plans définis par les trois premières inégalités.
- freddy
- 16-06-2014 19:02:41
Salut,
tu n'as pas dû bien chercher : Simplexe et sommet dégénéré
1 - vérifie que chaque point est bien à l'intérieur du polyèdre des contraintes ;
2 - vérifie les points qui saturent les contraintes et les autres ;
3 - déduis !
- hollye
- 16-06-2014 17:15:07
Bonjour,
J'ai un exercice que je n'arrive pas à faire .
On considère le polyèdre défini par ces inégalités :
x1+x2+2x3<=8
x2+6x3<=12
x1<=4
x2<=6
x1,x2,x2>=0
Parmi les points suivants :
p1(2,6,0)^T p2=(4,6,0)^T p3=(4,0,2)^T , trouver ceux qui sont des sommets et déterminer ceux qui sont dégénérés . Justifier les réponses
Je ne trouve pas dans mon cours comment prouver ça , j'ai regardé sur internet également je n'ai pas de définition .
Pouvez vous m'aider ?
Merci