camino mínimo

Question

Se debe construir un ferrocarril entre las ciudades A y B, pero una cuña de terreno difícil PQR se encuentra entre ellas. Encuentra la mejor ruta para el ferrocarril.

Este problema (de "Mathematian's Delight") se puede resolver simplemente usando una regla y calculando los diferentes costos, pero ¿qué regla geométrica se usa en la realidad?

Answer 1

Este es un problema básico de optimización de restricciones:

$min$$c_1 \left\| {X - Y} \right\| + c_2 \left\| {X - A} \right\| + c_2 \left\| {Y - B} \right\|$ (minimizar las distancias ponderadas)

Sujeto a:

$(P - X)\times (X - Q) = 0$

(X debe estar en la línea entre$Q$ y$P$)

y

$(R - Y)\times (Y - Q) = 0$

(Y debe estar en la línea entre$Q$ y$R$)

donde se conocen$c_1$ = 20,000 y$c_2$ = 10,000$P$,$Q$,$R$,$A$ y$B$.

Answer 2

Suponga que la trayectoria óptima ha sido encontrado.

Trazar perpendiculares a $XQ$ e $YQ$; se reúnen en un punto de $P$ dentro del ángulo de $\angle XQY$. Deje $M$ ser el punto de intersección de las $PQ$ e $XY$. Snell de la ley implica que $\angle PXM=\angle PYM$, lo $\triangle PXY$ es isósceles,$|PX|=|PY|$. De ello se desprende que $\triangle PXQ$ es congruente a $\triangle PYQ$ y que, por ende, $XY$ es perpendicular a $PQ$, que se divide $\angle XQY$.

A continuación,$\angle PXQ=\angle PMX=\pi/2$, e $\angle XPQ=\angle MPX$, lo $\triangle PXM$ es similar a $\triangle PQX$, e $\angle PXM=\angle XQM$, la mitad de ángulo en $Q$.

Extender $AX$ e $BY$ cumplir $PQ$ a $R$. Dibujar un círculo $C$ con centro en $X$ y radio de $|XP|$, vamos a $U$ ser el punto donde $C$ intersecta $AX$, y deje $V$ ser el punto diametralmente opuesto $P$. De Snell de la ley también dice que $$\sin\angle UXV=2\sin\angle PXM\;.$$

Dibuja una línea a través de $U$ paralelo a $XP$ y una línea a través de $M$ paralelo a $XQ$, y deje $T$ ser su punto de intersección. Deje $S$ ser el punto de intersección de las $MT$ e $XP$. Entonces $$\sin\angle PXM=\frac{|MS|}{|XP|}$$ and $$\sin\angle UXV=\frac{|TS|}{|XP|}\;,$$

por lo $|TS|=2|MS|$. Por lo tanto, la búsqueda de la ruta óptima reduce a encontrar $X$, de modo que cuando esta construcción se realiza, $|TS|=2|MS|$. El diagrama a continuación debe ayudar.

Esto se puede lograr mediante la selección de un punto arbitrario $X$ sobre la parte superior ray de $Q$, dibujando una línea paralela a la bisectriz $MQ$, y levantar una perpendicular a $MQ$ a $Q$ para satisfacer esa línea en un punto de $H$. De $H$ caída perpendicular a $XQ$, cumpliendo $XQ$ a $I$, y extenderla para satisfacer $MQ$ a $J$. Dibujar un círculo $C'$ de centro $H$ y radio de $|HJ|$. Deje $K$ ser el punto en $XQ$ tal que $|KI|=2|IQ|$. Levantar una perpendicular a $XQ$ a $K$, y deje $L$ ser su punto de intersección con la $C'$ en el lado opuesto de $XH$. Ahora dibuje una línea a través de $A$ paralelo a $LH$; el punto en el que se encuentra con la parte superior ray de $Q$ es el punto deseado $X$. $Y$ se encuentra caer a un perpendicular de $X$ a de la bisectriz $MQ$ y de la ampliación para satisfacer el menor rayo de $Q$ a $Y$. He añadido este desorden en la figura de abajo.