Optimisation linéaire, plus petit triangle contenant n points

[CongEjz9]

Problème résolu.

[zygomatique]

salut

beaucoup d'indices qui n'aident pas vraiment ...

ensuite considère-t-on que les points sur les côtés appartiennent au triangle ou non ? je suppose que oui et donc des inégalités larges dans la suite ...



je considérerais le triangle équilatéral OAB avec O(0, 0), A(a, 0) et

donc on a un triangle équilatéral de côté a

on cherche les points M(x, y) à coordonnées entières (je suppose) tels que

0 = (1 - \sqrt 3 )x \le 0[/TEX]


il faut ensuite l'équation de la droite (AB) ... et écrire en core une fois qu'on a x=< y

....

[Robot]

Tu es assez mal parti.
Il convient de minimiser une fonction (linéaire) adéquate de avec des contraintes correspondant au fait que tous les points donnés sont contenus dans le triangle déterminé par .

Edit : j'ajoute que je ne vois pas trop l'intérêt de formuler ça comme un problème de programmation linéaire !

[CongEjz9]

Tu es assez mal parti.
Il convient de minimiser une fonction (linéaire) adéquate de avec des contraintes correspondant au fait que tous les points donnés sont contenus dans le triangle déterminé par .

Edit : j'ajoute que je ne vois pas trop l'intérêt de formuler ça comme un problème de programmation linéaire !

Bonjour,

Merci de répondre aussi vite. J'avais bien compris l'idée générale de l'exercice. Par contre ça ne m'éclair pas beaucoup puisque je je reviens à ma question. puisque c'est un triangle équilatéral n'est-ce pas ? Je comprend bien qu'il faut minimiser une fonction linéaire contenant ces trois d mais quelles sont les coefficients ? Si , quelles sont les coefficients de la matrice colonne c ? Les contraintes sont-elles bien de la forme donné par l'indice ?
En gros, par exemple, si je donne n=5 points tels que, au hasard, (3,3) (3,4) (4,4) (5,5) et (2,5) sont les points donnés, comment se présenterai mon programme linéaire ?
Pour tester, j'utiliserai Matlab.

Merci encore pour votre réponse

PS: Il existe un problème du plus petit cercle contenant n points, cad un problème similaire à celui-ci mais ici on utilise un triangle équilatéral. La méthode utilisée d'après la littérature et Wikipédia est la programmation linéaire. Le fait que l'on utilise la programmation linéaire pour résoudre notre problème est donc justifiable, et puis ça fait aussi un bon exercice. Il n'est pas forcément nécessaire d'avoir un intérêt. Je suis d'accord que la programmation non-linéaire serait plus simple, il suffirait de minimiser l'aire du triangle équilatéral mais ici je galère... s'agirait-il de minimiser le périmètre ? Cad . A ce moment là, si on remplace les d par leur valeurs, il s'agirait de minimiser et ça me semble louche.

[CongEjz9]

salut

beaucoup d'indices qui n'aident pas vraiment ...

ensuite considère-t-on que les points sur les côtés appartiennent au triangle ou non ? je suppose que oui et donc des inégalités larges dans la suite ...



je considérerais le triangle équilatéral OAB avec O(0, 0), A(a, 0) et

donc on a un triangle équilatéral de côté a

on cherche les points M(x, y) à coordonnées entières (je suppose) tels que

0 = (1 - \sqrt 3 )x \le 0[/TEX]


il faut ensuite l'équation de la droite (AB) ... et écrire en core une fois qu'on a x=< y

....

Bonjour, tout d'abord merci de votre réponse, je crois comprendre l'idée derrière votre méthode. Par contre je crains que vous ayez mal compris le problème. Nous ne cherchons pas le nombre de points à mettre dans un triangle mais plutôt le triangle le plus petit possible contenant n points (qui sont déjà donnés) via une méthode de programmation linéaire. J'ai besoin de connaitre les contraintes, la fonction à minimiser. La variable dont il faut trouver les valeurs est le côté du triangle. ça peut / doit être un vecteur colonne et c'est pour ça qu'il faut s'aider de mais ce qui me gêne c'est le fait qu'il s'agisse d'un triangle équilatéral et du coup ces trois valeurs sont les mêmes, n'est-ce pas ? Enfin bref je suis un peu perdu pour être honnête.

Merci encore pour votre réponse

[zygomatique]

ok d'ac ...

effectivement les n points sont donnés au départ ...

désolé ...

[Robot]

puisque c'est un triangle équilatéral n'est-ce pas ?

Absolument pas ! Le fait que ce soit un triangle équilatéral est donné par les pentes des droites.

Je comprend bien qu'il faut minimiser une fonction linéaire contenant ces trois d mais quelles sont les coefficients ? Si , quelles sont les coefficients de la matrice colonne c ?

Je ne vais pas te le dire, ça serait faire l'exo à ta place. Réfléchis ! On cherche à "faire monter" la droite horizontale le plus haut possible, à "faire descendre" la droite qui supporte le côté droit le plus possible, etc.

Les contraintes sont-elles bien de la forme donné par l'indice ?
En gros, par exemple, si je donne n=5 points tels que, au hasard, (3,3) (3,4) (4,4) (5,5) et (2,5) sont les points donnés, comment se présenterai mon programme linéaire ?

Encore une fois, hors de question que je fasse l'exo à ta place. Réfléchis à partir des indices qui te sont fournis et de l'indication que j'ai donnée sur la nature des contraintes portant sur .

PS: Il existe un problème du plus petit cercle contenant n points, cad un problème similaire à celui-ci mais ici on utilise un triangle équilatéral. La méthode utilisée d'après la littérature et Wikipédia est la programmation linéaire. Le fait que l'on utilise la programmation linéaire pour résoudre notre problème est donc justifiable, et puis ça fait aussi un bon exercice. Il n'est pas forcément nécessaire d'avoir un intérêt. Je suis d'accord que la programmation non-linéaire serait plus simple, il suffirait de minimiser l'aire du triangle équilatéral mais ici je galère... s'agirait-il de minimiser le périmètre ? Cad . A ce moment là, si on remplace les d par leur valeurs, il s'agirait de minimiser et ça me semble louche.

Qui parle d'optimisation non linéaire ? Le problème se traite tout bêtement en prenant un maximum (ou des minima) de valeurs.

[CongEjz9]

Absolument pas ! Le fait que ce soit un triangle équilatéral est donné par les pentes des droites.

Je ne vais pas te le dire, ça serait faire l'exo à ta place. Réfléchis ! On cherche à "faire monter" la droite horizontale le plus haut possible, à "faire descendre" la droite qui supporte le côté droit le plus possible, etc.


Encore une fois, hors de question que je fasse l'exo à ta place. Réfléchis à partir des indices qui te sont fournis et de l'indication que j'ai donnée sur la nature des contraintes portant sur .


Qui parle d'optimisation non linéaire ? Le problème se traite tout bêtement en prenant un maximum (ou des minima) de valeurs.

Si j'ai bien compris, mes contraintes seraient de trouver les n (ou plus) inégalités en utilisant alpha. Si alpha positif alors les points sont dans le triangle. Donc on fixe alpha >= 0. Après il faudrait trouver les pentes des droites définissants le triangle (0 , sqrt3 et -sqrt3).

[Robot]

Euh ... d'après ce que tu écris, je ne suis pas sûr que tu aies bien compris. Me suis-je mal exprimé ? Je retente un coup.

Je note , pour les points. (Entendons-nous bien, les en haut ne sont pas des puissances, d'accord ?)
La droite du bas du triangle recherché a une équation de la forme. (ça t'est donné dans les indices). Les points sont "du bon côté" de cette droite (c.-à-d. ils sont tous au dessus) quand on a pour ; ça te donne des contraintes linéaires (portant uniquement sur ). Pour avoir le triangle le plus petit possible, on cherche a monter cette droite horizontale le plus haut possible, c.-à-d. à avoir le plus grand possible (clair ? fais-toi un dessin dans ta tête). La "fonction d'objectif" à minimiser (fonction linéaire de ) doit posséder la propriété de décroître quand croit ; ça te dit quelque chose sur le signe du coefficient de dans la fonction d'objectif.

Voila. Dans le paragraphe ci-dessus je ne me suis occupé que du côté bas du triangle, c.-à-d. je ne me suis occupé que de . Je te laisse t'occuper des deux autres côtés (c.-à-d. de et ). Les équations de ces deux autres côtés te sont données dans les indices, ton travail est tout mâché !

Tu seras sans doute troublé par le fait que tu n'as pas assez d'information pour déterminer la fonction d'objectif, même à un facteur positif près. C'est normal, il y a une infinité de choix possibles et il suffit de choisir une fonction d'objectif qui a les propriétés voulues (autant la prendre la plus simple possible).

Le fait que les contraintes ne portent que sur une seule des variables à la fois explique pourquoi je dis qu'il est complètement farfelu de se poser ce problème comme un problème d'optimisation linéaire.

[CongEjz9]

Euh ... d'après ce que tu écris, je ne suis pas sûr que tu aies bien compris. Me suis-je mal exprimé ? Je retente un coup.

Je note , pour les points. (Entendons-nous bien, les en haut ne sont pas des puissances, d'accord ?)
La droite du bas du triangle recherché a une équation de la forme. (ça t'est donné dans les indices). Les points sont "du bon côté" de cette droite (c.-à-d. ils sont tous au dessus) quand on a pour ; ça te donne des contraintes linéaires (portant uniquement sur ). Pour avoir le triangle le plus petit possible, on cherche a monter cette droite horizontale le plus haut possible, c.-à-d. à avoir le plus grand possible (clair ? fais-toi un dessin dans ta tête). La "fonction d'objectif" à minimiser (fonction linéaire de ) doit posséder la propriété de décroître quand croit ; ça te dit quelque chose sur le signe du coefficient de dans la fonction d'objectif.

Voila. Dans le paragraphe ci-dessus je ne me suis occupé que du côté bas du triangle, c.-à-d. je ne me suis occupé que de . Je te laisse t'occuper des deux autres côtés (c.-à-d. de et ). Les équations de ces deux autres côtés te sont données dans les indices, ton travail est tout mâché !

Tu seras sans doute troublé par le fait que tu n'as pas assez d'information pour déterminer la fonction d'objectif, même à un facteur positif près. C'est normal, il y a une infinité de choix possibles et il suffit de choisir une fonction d'objectif qui a les propriétés voulues (autant la prendre la plus simple possible).

Le fait que les contraintes ne portent que sur une seule des variables à la fois explique pourquoi je dis qu'il est complètement farfelu de se poser ce problème comme un problème d'optimisation linéaire.

Merci beaucoup pour votre réponse, c'est vraiment plus clair. Du coup j'ai pu trouver les contraintes pour les autres d. J'ai commencé différemment hier mais je pense que c'est quand proche de votre méthode. Voilà ma nouvelle méthode:

Je choisi un triangle, je prend un point (x,y) et une distance d positive. Je choisi ensuite un triangle au hasard tel que sa base est parallèle à l'axe des x et dont le sommet est au dessus de sa base. On peut traduire les positions des trois sommets du triangle dans le repère par ( et . L'aire du triangle est , donc minimiser A revient à minimiser d puisque d est positif. Maintenant, comme vous avez fais, je prend n points décris par . Les points doivent donc vérifier .
Ensuite, concernant le côté gauche, l'inégalité doit vérifier
Finalement, au côté droit, , soit
Du coup je dois minimiser d tel que avec les 3n contraintes décrites ci-dessus et x y n'ont pas de contraintes de positivités, ils sont libres. Les variables sont x, y et d. Le programme linéaire se présente sous cette nouvelle forme



, x et y libres
où

Mon nouveau soucis, c'est lorsque je veux tester mon programme sur Matlab pour n=5 points (les mêmes que ceux en haut, i.e. (3,3) (3,4) (4,4) (4,5) (2,5)), je reçois une erreur qui me dit que le problème n'a pas assez de contraintes. J'utilise la commande linprog et je force l'utilisation du Simplexe (les autres c'est pareil). Mes matrices ressemblent à ça:

avant d'avoir ajouter les variables d'écarts pour plus de lisibilité.



sans les variables d'écarts

J'ai passé pas mal de temps à débugger le code, mais voilà là j'ai l'impression que ça ne veut juste pas fonctionner xD