Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Le pont aux ânes : recherche d'un optimum?
Soient deux villes A et B, situées à distance et du même côté d'une rivière rectiligne (D). Un pont doit être construit sur la rivière en un point P, de façon à minimiser la longueur des routes à construire pour relier A, B et P.
I et J sont respectivment les projections de A et B sur (D)
Vous trouverez un autre énoncé de ce problème sur cette page http://www.crdp.ac-grenoble.fr/imel/xenon/nts/pont... avec les solutions de base suivantes :
- pont en I, routes AI et AB
- pont en J, routes AB et BJ
- pont en P, routes AP et BP
Dans certaines configurations de A, B et (D), ces solutions ne sont pas optimales : si X est un point situé à l'intérieur du quadrilatère ABJI, il apparaît que la longueur de route est inférieure en construisant AX, BX et XH, H étant le projeté de X sur (D).
Une bonne position pour X est le barycentre de ABH, avec H milieu de IJ ; mais ce n'est pas la position optimale, car je peux trouver par tâtonnement d'autres points pour lesquels il y a moins de route à construire.
Sauriez-vous trouver une méthode pour construire X à sa position optimale, c'est-à-dire celle qui minimise AX+BX+XH ?
Une justification possible de ce problème mathématique est que les villes A et B peuvent trouver de l'autre côté de la rivière une ressource dont elles ont besoin, celle-ci étant répartie uniformément le long du cours de la rivière.
Ainsi, la position du pont se détermine uniquement en fonction des positions des villes A et B.
4 réponses
- Anonymeil y a 1 décennieRéponse favorite
Problème intéressant.
Voilà une solution toute simple.
Tout d'abord il faut savoir que si tu as un triangle ABC et que tu veux placer un point Z tel que AZ+BZ+CZ soit minimal, il faut et il suffit que les angles AZB, BZC et CZA soient tous égaux à 120°.
Dans ton problème, il suffit donc de tracer:
- la demi-droite partant de A, se rapprochant de B et de la rivière et faisant un angle de 30° avec la rivière,
- la demi-droite partant de B, se rapprochant de A et de la rivière et faisant un angle de 30° avec la rivière,
et de prendre pour X le point d'intersection des deux demi-droites.
Edit: Si le point X ainsi trouvé est du mauvais coté de la rivière, alors la solution est parmi les 3 proposées sur le site de Grenoble.
PS: pourquoi le pont aux ânes?
Edit2: Pour l'histoire du triangle ABC, j'ai oublié de préciser que ses angles doivent être tous inférieurs à 120°. Si c'est pas clair, hésite pas à me le dire; dans ce cas là je reformulerai ma réponse.
- harghoLv 7il y a 1 décennie
Tu es sûr que ce n'est pas la position optimale ?
Sinon, il y a la méthode rapide, que j'appelle "statistique" : tu connais A et B, donc I et J, donc H. Tu peux tirer aléatoirement des points dans ABJI et calculer ta somme à chaque fois. Tu stockes le résultat le plus petit et c'est terminé. Disons 1000 points ou 10000, par exemple. C'est rapide et ça te donne un résultat !
.
Ah, ça aussi : ça dépend peut-être de la position de la ville Z de l'autre côté de la rivière, vers laquelle le pont doit conduire :)
- Anonymeil y a 1 décennie
Du même côté de la rivière il n'y a pas besoin de pont
Mais si on veut aller de A à B en touchant une droite représentant la rivière , il suffit de symétriser B en B' (par rapport à la droite )
Joindre A Ã B' et on a le plus court chemin.(la ligne droite)
- Anonymeil y a 1 décennie
Je ne voudrais pas paraître macabre, mais le squelette de Voronoï semblerait assez articulé pour optimiser ton chemin.