Polytope

[Ben314]

ce qui est surprenant est le fait que S soit borné (sous certaines conditions) est un théorème
signé Minkowski,Steiniz,Weyl.

Quelles sont les conditions et est-ce trivial ?

Pour ce que j'en comprend, le "théorème", il dit que, si est une partie bornée, alors il existe un ensemble fini de vecteurs tel que soit l'enveloppe convexe de cet ensemble : perso, ça me semble "visuellement plus ou moins clair", mais... pas trivial à démontrer...

[mathelot]

Cliffe demande si sa définition d'un polyèdre est un polytope.
si on comprend la question, est ce qu'une intersections d'hyperplans contenant 0 est enveloppe convexe d'un certain nombre de points ? :hum:

[Cliffe]

pk contiendrait-il forcément 0 ? C'est faux.

[Ben314]

Cliffe demande si sa définition d'un polyèdre est un polytope.
si on comprend la question, est ce qu'une intersections d'hyperplans contenant 0 est enveloppe convexe d'un certain nombre de points ? :hum:

Il me semble assez évident que le fait que soit ou pas borné va dépendre de la matrice que l'on a choisi.

Dans le cas n=2,
Si alors est borné.
Si alors n'est pas borné.
Si alors est
- borné si a>1 (indépendamment de b)
- non borné si a<1 (indépendamment de b)
- soit vide, soit non borné (dépend de b) si a=1

[Cliffe]

J'ai trouvé la réponse à ma question, merci à vous :lol3:.

Pour les curieux : http://fr.wikipedia.org/wiki/Algorithme_du_simplexe dans la partie Détection d'un problème non borné.

[zygomatique]

Cliffe demande si sa définition d'un polyèdre est un polytope.
si on comprend la question, est ce qu'une intersections d'hyperplans contenant 0 est enveloppe convexe d'un certain nombre de points ? :hum:

attention il ne contient pas forcément 0

mais x >= 0 et Ax =< b fait qu'en vérifiant en 0 on pourra répondre simplement

si 0 est du même bon côté que l'ensemble des solutions de Ax =< b


enfin il me semble que je suis pas loin d'être à côté de dire une bêtise .... :ptdr: ... peut-être ....

[Ben314]

J'ai trouvé la réponse à ma question, merci à vous :lol3:.

D'un autre coté, tu aurais signalé AU DEPART que c'était pour appliquer l'algo. du simplexe, je pense qu'il y a pas mal de monde qui t'aurais répondu que l'algo en question, on l'attaquait sans savoir si on allait trouver une solution ou pas et que, c'est au cours de l'algo. qu'on fini par savoir si le problème est borné ou pas.

Perso., vu ton énoncé, j'étais persuadé que tu cherchais une condition simple à énoncer pour savoir si ton ton truc était borné ou pas.

[Cliffe]

Perso., vu ton énoncé, j'étais persuadé que tu cherchais une condition simple à énoncer pour savoir si ton ton truc était borné ou pas.

oui c'est bien ça.
l'algo du simplexe ne répond pas tout à fait a mon problème (c'est assez compliqué et je veux pas entré dans les détails) mais je m'en contenterai pour l'instant.

[zygomatique]

oui c'est bien ça.
l'algo du simplexe ne répond pas tout à fait a mon problème (c'est assez compliqué et je veux pas entré dans les détails) mais je m'en contenterai pour l'instant.

cependant comme le dit ben314 il eut été plus simple de préciser ce que tu voulais ...

quand j'ai vu ton énoncé j'ai tout de suite pensé optimisation linéaire ....

la réponse est donné dans le premier lien (polytope et polyèdre convexe) :: il y a une solution .... mais répond-elle aux contraintes de l'énoncé (x >= 0, minimum, maximum, ...) .... c'est un autre problème donné dans ton lien ....

[Cliffe]

oui, sauf que je cherchais autre chose que le simplexe que je connais déjà.