¿En qué orden la mujer debe traer a los gatos para minimizar el tiempo?

Question

Una mujer observa a sus gatos irse uno por uno con diferentes velocidades en diferentes direcciones. Tomó una motocicleta con un asiento adicional, sigue a los gatos, recoge un gato a la vez y los lleva de vuelta a casa. Cada gato se mueve con una velocidad individual constante$V_i$ y se va a casa en el momento$T_i$. ¿En qué orden la mujer debe traer a los gatos para minimizar el tiempo?

Estoy tratando de resolver este problema pero no sé cómo empezar.

Answer 1

Yo sugeriría considerando ejemplo sencillo con dos gatos. Supongamos que la mujer tiene que decidir cual gato a ir después de la primera. En la actualidad, tanto los gatos ya se han ido y se $D_{1}$ e $D_{2}$ lejos. Supongamos que la mujer decidió ir después de cat $1$ primero y, a continuación, después de $2$. A qué hora tiene que hacer? (Suponga que el de las mujeres de la velocidad es $V_{0}$ y es mayor que cualquiera de los gatos.)

Para ponerse al día con el primer gato que ella necesita $t_{1}$ que resuelve $t_{1}V_{0}=D_{1}+t_{1}V_{1}$ o, de manera equivalente, $t_{1}=\frac{D_{1}}{V_{0}-V_{1}}$. Por $2t_{1}$ ella está de vuelta a casa con el primer gato al punto que el segundo gato es $D_{2}+2t_{1}V_{2}$ lejos. Para ponerse al día con el segundo gato que ella necesita $t_{2}$ que resuelve $t_{2}V_{0}=D_{2}+2t_{1}V_{2}+t_{2}V_{2}$ o, de manera equivalente, $t_{2}=\frac{D_{2}+2t_{1}V_{2}}{V_{0}-V_{2}}$. De ahí que toda la operación se lleva a $2(t_{1}+t_{2})$.

Sustituyendo en los parámetros del modelo, la duración de la operación es $$2\frac{D_{2}(V_0-V_1)+D_{1}(V_0+V_2)}{(V_0-V_1)(V_0-V_2)}=2\frac{V_{0}(D_{1}+D_{2})+D_{1}V_{2}-D_{2}V_{1}}{(V_0-V_1)(V_0-V_2)}$$ Del mismo modo, si la mujer elige otro orden, la operación se lleva a $$2\frac{D_{1}(V_0-V_2)+D_{2}(V_0+V_1)}{(V_0-V_1)(V_0-V_2)}=2\frac{V_{0}(D_{1}+D_{2})+D_{2}V_{1}-D_{1}V_{2}}{(V_0-V_1)(V_0-V_2)}$$

Por lo tanto, el $(1,2)$ orden es óptima si $\frac{D_{1}}{V_{1}}>\frac{D_{2}}{V_{2}}$. Mi conjetura es que la solución general se va después de los gatos en el orden decreciente de $\frac{D_{i}}{V_{i}}$, lo que, nota, es igual a $\frac{tV_{i}}{V_{i}}=t$ a tiempo $t$ para todos los gatos si todos los gatos de la izquierda al mismo tiempo. En otras palabras, lo que estoy conjeturas es que si todos los gatos de la izquierda al mismo tiempo, el orden no importa. De hecho (más evidencia de apoyo, no una prueba), Mathematica piensa, así como también para $5$ arroja:

t1 = d1/(v0 - v1);
t2 = (d2 + 2*t1*v2)/(v0 - v2);
t3 = (d3 + 2*(t1 + t2)v3)/(v0 - v3);
t4 = (d4 + 2(t1 + t2 + t3)v4)/(v0 - v4);
t5 = (d5 + 2(t1 + t2 + t3 + t4)v5)/(v0 - v5);
Simplificar[t1+t2+t3+t4+t5/.d1->tv1/.d2->tv2/.d3->tv3/.d4->tv4/.d5->tv5]