Salve, sto cercando di risolvere il seguente problema, ma sono bloccata.
Ora ve lo enuncio:
Tre città sono ai vertici A, B, C di un triangolo qualunque. Un punto P, complanare col triangolo, deve essere collegato con A, con B, con C; il collegamento con A costa "a" euro al metro, quello con B costa "b" euro al metro e quello con C costa "c" euro al metro. Devo individuare la posizione di P affinchè la spesa complessiva di collegamento a*PA+b*PB+c*PC sia minima.
Ebbene, se "a" fosse la spesa massima per metro, e se a<=b+c il problema saprei risolverlo tramite Tolomeo. Ma se ad esempio a=10, b=3 e c=2 sono bloccata. Qualcun ha qualche idea?
Mille grazie
Roberta
Un problema MOLTO carino sul triangolo
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
-
mathmum
- Livello 5
- Messaggi: 337
- Iscritto il: sab nov 19, 2005 5:39 pm
- Località: World (Wide Web) - IT
La teoria in breve...http://it.wikipedia.org/wiki/Problema_d ... iaggiatore
qualche idea di tipo"euclideo" ... http://www.ams.org/featurecolumn/archive/tsp.html
la bibbia...http://mathworld.wolfram.com/TravelingS ... oblem.html
ciao!
qualche idea di tipo"euclideo" ... http://www.ams.org/featurecolumn/archive/tsp.html
la bibbia...http://mathworld.wolfram.com/TravelingS ... oblem.html
ciao!
mathmum
...la vita è complessa: ha componenti reali ed immaginarie...
...la vita è complessa: ha componenti reali ed immaginarie...
Benvenuta, Roberta. 
Non spaventarti, in realtà mathmum esagera...
. Il tuo è semplicemente un problema di baricentro: se i pesi sono uguali il baricentro coincide con il baricentro del triangolo; in caso contrario devi identificare su ciascun lato del triangolo il baricentro dei due vertici corrispondenti (principio della leva) e tracciare il segmento che lo unisce al terzo vertice: i tre segmenti si incontrano nel baricentro.
Se fai uso della geometria analitica è sufficiente fare la media pesata delle coordinate dei vertici
$\left \{ {x_{\script O} = \frac {a \/ x_{\script A} + b \/ x_{\script B} + c \/ x_{\script A}} {a + b + c} = \frac {10 \/ x_{\script A} + 2 \/ x_{\script B} + 3\/ x_{\script A}} {15} \\ y_{\script O} = \frac {a \/ y_{\script A} + b \/ y_{\script B} + c \/ y_{\script A}} {a + b + c} = \frac {10 \/ y_{\script A} + 2 \/ y_{\script B} + 3 \/ y_{\script A}} {15}} \right.$
Che la somma delle distanze dei vartici dal baricentro corrisponda al minimo si prova con la disuguaglianza triangolare (almento credo
)
P.S.: per gli amanti della matematica, se si sceglie di pesare ciascun vertice in ragione del lato opposto il "baricentro" coincide con l'incentro e i segmenti di cui sopra giacciono sulle bisettrici
P.P.S.: mi sono accorto che Roberta voleva 10, 3, 2 (io ho messo 10, 2, 3
)
Non spaventarti, in realtà mathmum esagera...
. Il tuo è semplicemente un problema di baricentro: se i pesi sono uguali il baricentro coincide con il baricentro del triangolo; in caso contrario devi identificare su ciascun lato del triangolo il baricentro dei due vertici corrispondenti (principio della leva) e tracciare il segmento che lo unisce al terzo vertice: i tre segmenti si incontrano nel baricentro. Se fai uso della geometria analitica è sufficiente fare la media pesata delle coordinate dei vertici
$\left \{ {x_{\script O} = \frac {a \/ x_{\script A} + b \/ x_{\script B} + c \/ x_{\script A}} {a + b + c} = \frac {10 \/ x_{\script A} + 2 \/ x_{\script B} + 3\/ x_{\script A}} {15} \\ y_{\script O} = \frac {a \/ y_{\script A} + b \/ y_{\script B} + c \/ y_{\script A}} {a + b + c} = \frac {10 \/ y_{\script A} + 2 \/ y_{\script B} + 3 \/ y_{\script A}} {15}} \right.$
Che la somma delle distanze dei vartici dal baricentro corrisponda al minimo si prova con la disuguaglianza triangolare (almento credo
)P.S.: per gli amanti della matematica, se si sceglie di pesare ciascun vertice in ragione del lato opposto il "baricentro" coincide con l'incentro e i segmenti di cui sopra giacciono sulle bisettrici
P.P.S.: mi sono accorto che Roberta voleva 10, 3, 2 (io ho messo 10, 2, 3
)il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
-
mathmum
- Livello 5
- Messaggi: 337
- Iscritto il: sab nov 19, 2005 5:39 pm
- Località: World (Wide Web) - IT
Pan, a te la risposta, visto che io sono esagerata!
(gormiciao!)
roberta, ciao e benvenuta, scusa il quiquoqua tra me e panurgo, ma ti ci abituerai... e mi raccomando, non ci mollare, che qui le donne sono in esagerata minoranza....
(gormiciao!)
roberta, ciao e benvenuta, scusa il quiquoqua tra me e panurgo, ma ti ci abituerai... e mi raccomando, non ci mollare, che qui le donne sono in esagerata minoranza....
mathmum
...la vita è complessa: ha componenti reali ed immaginarie...
...la vita è complessa: ha componenti reali ed immaginarie...
Ostrega! Era un pezzetto che non scrivevo una sciocchezza di tali proporzioni! (Roberta, cancella tutto)
matemamma, baciamo le mani...
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
-
mathmum
- Livello 5
- Messaggi: 337
- Iscritto il: sab nov 19, 2005 5:39 pm
- Località: World (Wide Web) - IT
(dai diari deliranti della mathmum)panurgo ha scritto:
eh, sì ragazzo mio, si invecchia, eccome che si invecchia! (io per prima!)
superati i 23 anni che corrispondono al massimo della creatività matematica (hai visto The Proof?) inizia la fase discendente.... (ma io dubito di aver mai raggiunto un qualsivoglia "picco"...)
... pensa che io sono ancora lì fissata sui triangoli di Br1...
... ci vogliono un po' di vacanze, sciò, aria nuova, gente nuova, profumi nuovi... (forse un po' di chirurgia estetica?)
hehehe
ciao!
mathmum
...la vita è complessa: ha componenti reali ed immaginarie...
...la vita è complessa: ha componenti reali ed immaginarie...
penso sia cosi
Ciao a tutti....
credo che basti trovere il minimo della funzione di costo
a*PA(xc,yc)+b*PB(xc,yc)+c*PC(xc,yc)
dove xc e yc denotano la posizione del centro.
Un problema di minimo insomma, basta trovare in che punto il gradiente
vale zero.
Ciao
archimede
credo che basti trovere il minimo della funzione di costo
a*PA(xc,yc)+b*PB(xc,yc)+c*PC(xc,yc)
dove xc e yc denotano la posizione del centro.
Un problema di minimo insomma, basta trovare in che punto il gradiente
vale zero.
Ciao
archimede
Chiedo scusa, ma vorrei tornare sul problema del triangolo.
Il problema era:
Tre città sono ai vertici A, B, C di un triangolo qualunque. Un punto P, complanare col triangolo, deve essere collegato con A, B, C; il collegamento con A costa “a” euro al metro, il collegamento con B costa “b” euro al metro ed il collegamento con C costa “c” euro al metro. Individuare la posizione di P affinché la spesa complessiva di collegamento a*PA+b*PB+c*PC sia minima.
Supponiamo a=b=c
Allora devo individuare P tale che PA+PB+PC sia minimo.
Supponiamo anche che gli angoli B e C siano acuti.
Su BC, nel semipiano non contenente A, disegno il triangolo equilatero BCD.
Sia P un punto qualunque del piano; considero il quadrilatero BPCD.
(figura allegato TOLOMEO1)
Per il teorema di Tolomeo generalizzato:
BP*CD+PC*BD>=BC*PD
Essendo ABC equilatero posso scrivere:
BP+PC>=PD
Sommo PA ad entrambi i termini:
PA+PB+PC>=PA+PD
Ovviamente PA+PD>=DA
Quindi, se P non appartiene al segmento AD allora PA+PB+PC>=PA+PD>DA
Ma se P appartiene al segmento AD allora PA+PB+PC>=PA+PD=DA
Quindi, per minimizzare PA+PB+PC dovrà essere P appartenente al segmento DA
In tal caso sarà PA+PB+PC>=PA+PD=DA
Per minimizzare totalmente PA+PB+PC dovrò avere = al posto del >= nella riga precedente.
Questo accade solo se P appartiene alla circonferenza circoscritta al triangolo equilatero BCD e al segmento AD.
(figura allegato TOLOMEO2)
Ma allora P non è necessariamente il baricentro del triangolo ABC (pur essendo uguali i pesi “a”, “b”, “c”).
Scusate davvero, ma non riesco a capire!!
HELP
roberta
Il problema era:
Tre città sono ai vertici A, B, C di un triangolo qualunque. Un punto P, complanare col triangolo, deve essere collegato con A, B, C; il collegamento con A costa “a” euro al metro, il collegamento con B costa “b” euro al metro ed il collegamento con C costa “c” euro al metro. Individuare la posizione di P affinché la spesa complessiva di collegamento a*PA+b*PB+c*PC sia minima.
Supponiamo a=b=c
Allora devo individuare P tale che PA+PB+PC sia minimo.
Supponiamo anche che gli angoli B e C siano acuti.
Su BC, nel semipiano non contenente A, disegno il triangolo equilatero BCD.
Sia P un punto qualunque del piano; considero il quadrilatero BPCD.
(figura allegato TOLOMEO1)
Per il teorema di Tolomeo generalizzato:
BP*CD+PC*BD>=BC*PD
Essendo ABC equilatero posso scrivere:
BP+PC>=PD
Sommo PA ad entrambi i termini:
PA+PB+PC>=PA+PD
Ovviamente PA+PD>=DA
Quindi, se P non appartiene al segmento AD allora PA+PB+PC>=PA+PD>DA
Ma se P appartiene al segmento AD allora PA+PB+PC>=PA+PD=DA
Quindi, per minimizzare PA+PB+PC dovrà essere P appartenente al segmento DA
In tal caso sarà PA+PB+PC>=PA+PD=DA
Per minimizzare totalmente PA+PB+PC dovrò avere = al posto del >= nella riga precedente.
Questo accade solo se P appartiene alla circonferenza circoscritta al triangolo equilatero BCD e al segmento AD.
(figura allegato TOLOMEO2)
Ma allora P non è necessariamente il baricentro del triangolo ABC (pur essendo uguali i pesi “a”, “b”, “c”).
Scusate davvero, ma non riesco a capire!!
HELP
roberta
- Allegati
-
- TOLOMEO 1.JPG (17.79 KiB) Visto 10032 volte
-
- TOLOMEO 2.JPG (17.37 KiB) Visto 10032 volte
Infatti, il baricentro non c'entra per nulla: quando i pesi sono uguali, il percorso minimo che collega tre punti è quello per il quale i tre segmenti si incontrano formando angoli di 120°...panurgo ha scritto:
Quanto a risolvere il problema minimizzando le derivate della sommatoria delle distanze, la vedo dura!
$d_{\script {\text A}} \/ = \/ \sqrt {\left ( x \/ - \/ x_{\script {\text A}} \right)^{\script 2} + \left ( y \/ - \/ y_{\script {\text A}} \right)^{\script 2}} \\ \left \{ \frac {\partial d_{\script {\text A}}} {\partial x} \/ = \/ \frac {x \/ - \/ x_{\script {\text A}}} {d_{\script {\text A}}} \\ \frac {\partial d_{\script {\text A}}} {\partial y} \/ = \/ \frac {y \/ - \/ y_{\script {\text A}}} {d_{\script {\text A}}} \right . \\ \left \{ a \/ \frac {x \/ - \/ x_{\script {\text A}}} {d_{\script {\text A}}} \/ + \/ b \/ \frac {x \/ - \/ x_{\script {\text B}}} {d_{\script {\text B}}} \/ + \/ c \/ \frac {x \/ - \/ x_{\script {\text C}}} {d_{\script {\text C}}} \/ = \/ 0 \\ a \/ \frac {y \/ - \/ y_{\script {\text A}}} {d_{\script {\text A}}} \/ + \/ b \/ \frac {y \/ - \/ y_{\script {\text B}}} {d_{\script {\text B}}} \/ + \/ c \/ \frac {y \/ - \/ y_{\script {\text C}}} {d_{\script {\text C}}} \/ = \/ 0 \right .$
Auguri!
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
OK, ora una parte mi è chiara. Il punto P, se l'angolo maggiore di ABC non supera i 120°, coincide con il primo punto di Fermat. La ricerca + dimostrazione geometrica del punto P tale che PA+PB+PC sia minimo praticamente ce l'ho se "a", se"b", se"c" sono uguali (teorema di Tolomeo generalizzato).
Ho curiosato in internet per cercare informazioni sul 1° punto di Fermat e ho letto che è costruibile solo per triangoli acutangoli. Ma io posso oppure no costruirlo anche per triangoli il cui angolo maggiore non sia superiore ai 120°? Ho controllato con cabri, lavorando con un triangolo il cui angolo maggiore, supponiamo A, non superi i 120°: la costruzione di P con Tolomeo coincide con la costruzione di P come 1° punto di Fermat. Se l'angolo maggiore A = 120° entrambe le costruzioni portano P in A. Se invece A supera i 120° so che il punto P soluzione del problema deve coincidere con A, mentre la costruzione del primo punto di Fermat porta P a sballare.
Oltre al quesito sul 1° punto di Fermat rimane aperta ancora la caccia di P, con "a", "b", "c", non uguali tra loro, tralasciando pure il caso in cui max(a,b,c)<=della somma degli altri due perchè è risolvibile ancora con Tolomeo.
Spero di essermi spiegata perchè ho scritto di getto.
Grazie davvero
roberta
Ho curiosato in internet per cercare informazioni sul 1° punto di Fermat e ho letto che è costruibile solo per triangoli acutangoli. Ma io posso oppure no costruirlo anche per triangoli il cui angolo maggiore non sia superiore ai 120°? Ho controllato con cabri, lavorando con un triangolo il cui angolo maggiore, supponiamo A, non superi i 120°: la costruzione di P con Tolomeo coincide con la costruzione di P come 1° punto di Fermat. Se l'angolo maggiore A = 120° entrambe le costruzioni portano P in A. Se invece A supera i 120° so che il punto P soluzione del problema deve coincidere con A, mentre la costruzione del primo punto di Fermat porta P a sballare.
Oltre al quesito sul 1° punto di Fermat rimane aperta ancora la caccia di P, con "a", "b", "c", non uguali tra loro, tralasciando pure il caso in cui max(a,b,c)<=della somma degli altri due perchè è risolvibile ancora con Tolomeo.
Spero di essermi spiegata perchè ho scritto di getto.
Grazie davvero
roberta
Vorrei spararne una anch'io...
Secondo me questo è un problema di programmazione lineare, con funzione obiettivo:
a*PA+b*PB+c*PC
da minimizzare; i vincoli sono (solo uno):
PA + PB + PC = costante.
La funzione obiettivo definisce un piano, per cui il metodo del simplesso ci dice che essa è minima nei seguenti casi:
1) se X è la città il cui collegamento PX costa di più, allora P = X;
2) se X e Y sono due città i cui collegamenti PX e PY costano uguali, e sono quelli che costano di più, allora P sta in mezzo al lato XY;
3) se i collegamenti hanno tutti lo stesso costo di costruzione, la soluzione è quella di panurgo.
Secondo me questo è un problema di programmazione lineare, con funzione obiettivo:
a*PA+b*PB+c*PC
da minimizzare; i vincoli sono (solo uno):
PA + PB + PC = costante.
La funzione obiettivo definisce un piano, per cui il metodo del simplesso ci dice che essa è minima nei seguenti casi:
1) se X è la città il cui collegamento PX costa di più, allora P = X;
2) se X e Y sono due città i cui collegamenti PX e PY costano uguali, e sono quelli che costano di più, allora P sta in mezzo al lato XY;
3) se i collegamenti hanno tutti lo stesso costo di costruzione, la soluzione è quella di panurgo.
No, putroppo non va bene. Ora mi spiego meglio.
Siano “a, b, c” i costi al metro per collegare il punto P rispettivamente con la città A, B, C.
Se sono uguali il problema è già risolto. Supponiamo quindi che non lo siano.
Supponiamo che “a” sia la spesa max al metro.
Calcolo x=BC/a
Definisco D così:
• D appartiene al semipiano confinante con BC e non contenente A
• DB=x*c
• DC=x*b
Affinché il triangolo BCD sia costruibile dovremo chiedere a=b, a+b>=c sono già garantite perché “a” è la spesa max)
Sia P un punto qualunque del piano.
(vedere figura 1 allegata)
Applico il teorema di Tolomeo generalizzato al quadrilatero BPCD:
PD*BC=DA, quindi:
a*DA<=a*(PA+PD)<= b*BP+c*PC+a*PA
Il primo <= diventa = se P appartiene al segmento AD.
Il secondo <= diventa = se P appartiene alla circonferenza circoscritta al triangolo BCD (ovviamente con P interno al triangolo ABC)
Quindi per minimizzare a*PA+b*PB+c*PC (con “a” spesa max al metro e con a<=b+c) dovrò prendere P come intersezione tra la cfr circoscritta al triangolo BCD (costruito come indicato) ed il segmento AD (escludendo ovviamente D)
(vedere figura 2 allegata)
Ora, il problema aperto (cioè invisibile per me, ma spero non per voi) è quello di trovare la soluzione quando, chiamata ancora “a” la spesa max al metro, non è più garantita la condizione a<=b+c
(spero di non aver fatto errori nella trascrittura)
Grazie,
roberta
Siano “a, b, c” i costi al metro per collegare il punto P rispettivamente con la città A, B, C.
Se sono uguali il problema è già risolto. Supponiamo quindi che non lo siano.
Supponiamo che “a” sia la spesa max al metro.
Calcolo x=BC/a
Definisco D così:
• D appartiene al semipiano confinante con BC e non contenente A
• DB=x*c
• DC=x*b
Affinché il triangolo BCD sia costruibile dovremo chiedere a=b, a+b>=c sono già garantite perché “a” è la spesa max)
Sia P un punto qualunque del piano.
(vedere figura 1 allegata)
Applico il teorema di Tolomeo generalizzato al quadrilatero BPCD:
PD*BC=DA, quindi:
a*DA<=a*(PA+PD)<= b*BP+c*PC+a*PA
Il primo <= diventa = se P appartiene al segmento AD.
Il secondo <= diventa = se P appartiene alla circonferenza circoscritta al triangolo BCD (ovviamente con P interno al triangolo ABC)
Quindi per minimizzare a*PA+b*PB+c*PC (con “a” spesa max al metro e con a<=b+c) dovrò prendere P come intersezione tra la cfr circoscritta al triangolo BCD (costruito come indicato) ed il segmento AD (escludendo ovviamente D)
(vedere figura 2 allegata)
Ora, il problema aperto (cioè invisibile per me, ma spero non per voi) è quello di trovare la soluzione quando, chiamata ancora “a” la spesa max al metro, non è più garantita la condizione a<=b+c
(spero di non aver fatto errori nella trascrittura)
Grazie,
roberta
- Allegati
-
- FIGURA 2.GIF (4.2 KiB) Visto 9993 volte
-
- FIGURA 1.GIF (3.44 KiB) Visto 9991 volte