La optimización de la esperanza

Question

El siguiente problema es acerca de la optimización. No es una tarea, sino más bien de una pregunta natural a uno mismo después. Aquí está.

Considere la posibilidad de un camino de longitud $L$ entre dos ciudades $A$$B$. Cuando un coche se queda sin combustible en este camino, la distancia entre el coche y la ciudad de $A$ es uniformely distribuida en el intervalo de $[0,L]$. Hay tres estaciones de gasolina en la carretera. Ahora la pregunta del ejercicio es comparar dos distribuciones diferentes del conjunto de estaciones de servicio a lo largo de la carretera. La primera distribución es poner una estación en Una y otro en la distancia $L/2$ $A$ y la tercera en $B$. La segunda distribución es poner las estaciones de distancia $L/4$, $L/2$ y $3L/4$.

Claramente la segunda distribución es mejor. Sin embargo, la referencia (desde que tomé el ejercicio), admite que la segunda entrega no es óptimo!

Pregunta: Dado $n$ gasolineras, donde para ponerlos en el camino de tal manera que la esperanza de la distancia desde una estación en el lugar de la avería es mínima?

Answer 1

Aquí es cómo resolver el $n=3$ de los casos.

Voy a asumir L=1.

Deje $x_1 < x_2 < x_3$ ser las ubicaciones de las tres estaciones. Luego hay seis intervalos a considerar para la ubicación de un combustible menos del coche: $(0,x_1),(x_1,(x_1+x_2)/2),((x_1+x_2)/2,x_2),(x_2,(x_2+x_3)/2),((x_2+x_3)/2),x_3),$$(x_3,1)$.

En cada uno de estos intervalos, es claro que el punto de $x_1, x_2$ o $x_3$ es el más cercano, y es fácil para determinar la probabilidad de que el coche está en el intervalo, y lo que el espera de la distancia a la estación más cercana. El resultado es que la distancia esperada $E$ a la estación más cercana puede ser expresado como $$ 2 E=x_1^2+\left( \frac{x_1+x_2}{2} - x_1\right)^2 +\left( x_2 - \frac{x1+x2}{2}\right)^2 + \left( \frac{x_2+x_3}{2}-x_2 \right)^2 $$ $$+ \left( x_3 - \frac{x_2+x_3}{2}\right)^2 + (1-x_3)^2$$ $$=\frac{3}{2}x_1^2-x_1 x_2 + x_2^2 - x_2 x_3 + \frac{3}{2} x_3^2 -2 x_3+1$$ La aplicación habitual de las técnicas de optimización para esto nos encontramos con el mínimo de $E$ se produce con $x_1=\frac{1}{6}, x_2=\frac{1}{2},$$x_3=\frac{5}{6}$.

Answer 2

La adición de Mateo Conroy la respuesta (mi respuesta fue compuesta en forma totalmente independiente, y da exactamente el mismo resultado).

Consideramos el caso $n=3$, $L=1$. Así que, sujeto a $0 \leq x_1 < x_2 < x_3 \leq 1$, se desea minimizar $$ \int_0^{x_1 } {(x_1 - u)\,du} + \int_{x_1 }^{\frac{{x_1 + x_2 }}{2}} {(u - x_1 )\,du} + \int_{\frac{{x_1 + x_2 }}{2}}^{x_2 } {(x_2 - u)\,du} $$ $$ + \int_{x_2 }^{\frac{{x_2 + x_3 }}{2}} {(u - x_2 )\,du} + \int_{\frac{{x_2 + x_3 }}{2}}^{x_3 } {(x_3 - u)\,du} + \int_{x_3 }^1 {(u - x_3 )\,du} , $$ o, después de su evidente cambio de variables, $$ \int_0^{x_1 } {u\,du} + \int_0^{\frac{{x_2 - x_1 }}{2}} {u\,du} + \int_0^{\frac{{x_2 - x_1 }}{2}} {u\,du} + \int_0^{\frac{{x_3 - x_2 }}{2}} {u\,du} + \int_0^{\frac{{x_3 - x_2 }}{2}} {u\,du} + \int_0^{1 - x_3 } {u\,du}, $$ es decir, $$ \frac{{x_1^2 }}{2} + \frac{{(x_2 - x_1 )^2 }}{4} + \frac{{(x_3 - x_2 )^2 }}{4} + \frac{{(1 - x_3 )^2 }}{2}. $$

Answer 3

Dividir el camino en $n$ intervalos iguales, y poner una gasolinera en el centro de cada intervalo. Para ver que esto es óptima, se necesitan dos lemas:

Lema 1: Dados tres consecutivos gasolineras $X,Y,Z$, si hemos de fijar las posiciones de $X$$Z$, entonces la única posición óptima de $Y$ se encuentra a medio camino entre el$X$$Z$.
Lema 2: Si fijamos la posición de la segunda gasolinera $S$ (de la ciudad de $A$), entonces la única posición óptima de la primera estación de gasolina $F$ es de un tercio del camino de$A$$S$.

Usted puede probar estas usando Mateo Conroy del método.

Answer 4

Para el caso general, se puede demostrar que:

1. en un intervalo de con ninguna de las estaciones en cada extremo, la posición óptima de una sola estación se encuentra en el medio (usted sólo necesita saber esto si $n=1$);
2. en un intervalo con una estación en cada extremo, la posición óptima de una sola estación se encuentra en el medio (Mateo Conway respuesta muestra esto para la media estación);
3. en un intervalo sin una estación en un extremo, pero con una estación en el otro, la posición óptima de una sola estación es de un tercio del camino a lo largo de la final con ninguna estación (Mateo Conway respuesta también se muestra esto para las otras dos estaciones).

Así que con $n$ estaciones colocadas en un intervalo de longitud de $L$ con ninguna de las estaciones en ambos extremos, el óptimo posiciones en

$$\frac{1}{2n}L, \frac{3}{2n}L, \frac{5}{2n}L, \ldots , \frac{2n-1}{2n}L.$$