Inscription / Connexion Nouveau Sujet
Une histoire de d'autoroute
On décide de construire une autoroute d entre les villes A, B et C.
Chacun des maires des communes A, B et C doit minimiser le coût de la route reliant leur commune à l'autoroute.
Question :
Trouver la position de la droite d par rapport à A, B et C si on a dist(A,d) + dist(B,d) + dist(C,d) la plus petite possible.
Bonne route
Je ne savais pas où mettre ce problème. Je l'ai donc placé dans la catégorie "autre".
Avant toute chose, je n'ai pas encore la solution, je planche dessus.
J'essaye de voir ce qui se passe quand on place la figure dans un repère.
Je vais bientot obtenir la distance
D(m,p) = dist(A,d) + dist(B,d) + dist(C,d)
où m et p sont tel que d
y =mx + p
Par contre je me demande comment minimiser cette fonction à deux inconnues ?
Autre chose, comment trouver géométriquement la solution ?
Qui planche sur la question?
on a pas le droit de faire passer l'autoroute par une commune je suppose
Normalement elle ne devrait pas passer par une commune.
J'ai déjà vu ce probléme quelque part sur l'ile
C'est possible, mais j'ai imaginé ce problème en fumant (c'est pas bien...) ma cigarette ce matin.
Je pensais introduire un cours sur les médiatrices avec mais vu la complexité j'abandonne.
Toutefois, la curiosité mathématique m'incite à trouver la réponse.
Quitte à dire des bêtises. (ce qui est bien probable).
Il est impensable que les 3 villes soient d'un même coté de la route pour que la somme des distances soit minimum.
Il y a donc 2 villes d'un coté de la route et la 3 ème de l'autre coté (comme sur le dessin)
Supposons encore connaître la bonne direction de la route (donc le m de l'équation y = mx + p) mais pas le p.
Cherchons alors la valeur de p.
A partir du dessin, si on déplace la route parallèmement à elle-même, dans le sens d'aller vers les 2 villes qui sont d'un même coté de la route, on va vers une situation plus favorable (puisque la distance dC augmente mais que dA et dB diminuent pareillement)
On déplace ainsi la route jusqu'à ce qu'elle rencontre une des villes (par exemple B)
Si on dépasse la ville B avec la route déplacée toujours parallèlement à elle-m^^eme, la distance vers A diminue mais les 2 autres distances (de B et de C) augmentent pareillement
--> On part vers une position moins favorable de la route.
De là on conclut que la route DOIT passer par une des villes.
On choisit donc une des villes comme origine du repère B(0 ; 0)
L'équation de la route est y = kx
Tant qu'à faire, on prend un repère orthonormal pour avoir A(1 ; 0) et C(a ; b). avec a et b connu.
La somme des distances est dA + dC ne dépend que de la seule variable k.
Sauf erreur, on a quelque chose comme d(k) = (|k| + |ak-b|)/V(k²+1) (V pour racine carrée).
Fonction dont il est facile de trouver les minima (il peut y en avoir plusieurs à cause des ||). Il faut alors choisir le mimimum minimurum.
---
Rien ne dit que le meilleur des cas était la route passant par B.
Il faudrait étudier les 3 cas (route passant par A ou par B ou par C) pour trouver le meilleurs des cas.
-----
Sauf déconnade 
Il y a encore un cas plus simple : la route passe par 2 villes (A et B) par exemple.
La aussi il y a 3 cas à étudier.
On constate donc que le problème est très simple si on autorise que la route traverse une ou plusieurs ville(s).
Si on interdit ce fait, la tâche devient ardue.. Pourtant une petite voix intérieure me fait dire qu'il y a une solution...
bonjour
n'est-ce pas tout simplement la définition de la droite de régression calculée pour les trois points A,B et C ?
peut-être dis-je une "déconnade " ? 
Je n'ai pas suggéré de faciliter le problème en faisant passer la route par une des villes.
J'ai tenté de montrer que si la contrainte était d'avoir la somme des distances la plus petite possible, la solution était que le route DEVAIT passer par une des villes.
Si mon raisonnement est correct (reste à voir), et que l'on veut empêcher la route de passer par une des villes, il FAUT ajouter des contraintes supplémentaires, par exemple sur la différence max des trajets entre villes-route ou ...
En l'absence de ces contraintes supplémentaires, et à condition que mon raisonnement soit correct, on n'a pas le choix, le route DOIT passer par une des villes.
Oui mikayaou, la droite de régression tente bien de minimiser la somme des distances.
Mais comme il existe plusieurs approches pour déterminer les coefficients de cette droite, (méthode des moindres carrés mais aussi d'autres que j'ai oubliées), il faudrait montrer que toutes ces méthodes aboutissent au même résultat et je n'en suis pas sûr du tout.
Si oui, alors la méthode est bonne.
Mais que penses-tu toi de ceci ?:
On ne connait pas au départ la direction de la route à trouver, mais cette direction existe.
Je dessine donc une direction (en bleu) sur mon dessin, mais je pourrais dessiner n'importe quelle autre pourvu qu'il y ait 2 villes d'un coté de la route et 1 de l'autre (les 3 d'un même coté étant une idiotie pour minimiser les distances).
Dans ces "n'importe quelles autres directions", il y a forcément la bonne direction.
Il est clair qu'en déplaçant la route parallèlement à elle même (mais sans dépasser les limites qui mettraient les 3 villes d'un même coté), On a dans le cas du dessin : dB + dC = constante.
--> dA + dB + dC est forcément minimum pour dA = 0, donc pour la route passant par A.
Evidemment, au départ, pour dessiner la ligne bleue (route), on doit laisser une ville d'un coté et 2 de l'autre, il y a donc 3 cas (A ou B ou C seule d'un coté de la route), mais quoi qu'il en soit, la route DOIT passer par une des villes pour minimiser la somme des distances.
Déconne-je ?
avec 3 points, je suis d'accord avec toi, J-P, qu'il faille que la route passe par un des points
ça doit d'ailleurs (facilement) se démontrer en calculant les a et b de la droite de régression y=ax+b qui doit passer par un des points A(xa,ya) ou B(xb,yb) ou C(xc,yc)
il suffirait d'exprimer a et b = f(xa,ya,xb,yb,xc,yc) et de le prouver...
Une simple approche expérimentale sur "Déclic" montre que la distance est minimisée si la route passe par 2 points.
Par contre je cale tjr si j'impose la contrainte "la route ne doit pas passer par une des trois villes"
bonjour olivierl
rien ne t'empêche de faire passer la route très proche d'un des points mais tu n'auras pas, sauf erreur, la distance minimum minimorum
Il faut se méfier des "fausses contraintes".
Dire que la route de peut pas passer par une des villes est une fausse contrainte mathématiquement parlant.
Si on cherche la solution en ajoutant cette "fausse contrainte", on va forcément trouver que la route doit passer infimiment près d'une des villes mais par sur la ville (la distance entre la route et une des villes ne sera pas 0 mais tendra vers 0) et donc on n'est pas plus avancé.
Une vraie contrainte est d'imposer une distance minimum entre les villes et la route, mais c'est un autre problème.
Le problème pourrait être:
Ou placer la route (droite) pour que la somme des distances route-villes soit minimum mais avec chacune des distances route-ville supérieure ou égale à une "certaine" distance à donner.
olivierl
quand tu dis, le 20/02/2007 à 18:33, que :
Q : on a pas le droit de faire passer l'autoroute par une commune je suppose ?
R : Normalement elle ne devrait pas passer par une commune.
est-ce une contrainte de l'énoncé ou une éventualité que tu émets ?
Car, sauf erreur, la distance minimale, avec 3 points fait passer la route par un des points.
Au départ, j'ai imaginé ce problème pour introduire les médiatrices. Très rapidement je me suis rendu compte qu'il était impossible de l'exploité car trop complexe.
Car, sauf erreur, la distance minimale, avec 3 points fait passer la route par un des points.
Personellement je reste convaincu que la distance minimale fait passer la droite par 2 points.
Par contre, est-ce que la contrainte "les trois distances villes/route doivent être égalent" est une vraie ou une fausse contrainte?
Oui, c'est une vraie contrainte, sauf si les 3 villes sont alignées.
Si elles ne sont pas alignées, c'est facile:
Il faut choisir le meilleur cas parmi ces 3 constructions :
Dans le cas du dessin prendre la 3 ème.
C'est ce qui me semblait.
En terme géométrique, la solution deviendrait "Si M, N et P, sont les milieux respectifs de AB, BC et AC, on choisira la route parmi MN, MP ou NP."
olivierl le 21/02/2007 à 11:26
Personellement je reste convaincu que la distance minimale fait passer la droite par 2 points.
sauf erreur, si la distance minimale fait passer la droite par 2 points, alors elle passe obligatoirement par le troisième
sauf erreur, si la distance minimale fait passer la droite par 2 points, alors elle passe obligatoirement par le troisième
Dans ce cas, les trois points sont alignés. Ce qui ne va pas...
Regarde l'illustration.
On voit bien que la distance (C, route 1) et plus courte que dist(C,route2)+dist(B,route2)
oui mais c'est parce que tu t'obliges à faire passer la droite par 2 points...
je ne dis pas que la droite optimale passera par 2 points,
je dis que, SI la droite optimale passe par 2 points, ALORS elle passe par le 3°
Cà ne n'est pas évident mikayaou.
J'ai, me semble-t-il, démontré que la droite optimale passait par une des villes. (mais on ne sait pas laquelle).
Il fautrait démontrer que, ce fait acqui, la droite optimale passe ou non par une seconde ville.
Si c'était le cas (je n'y ai pas réfléchi), la route passerait obligatoirement par 2 villes, mais il resterait quant même 3 cas possibles parmi lesquels il faudrait choisir le meilleur.
Cela dit, il me semble que depuis, l'énoncé a été modifié.
Annuler
connectez vous
géométrie en post-bac