Solución:
En general, la programación de ascensores es un problema seriamente difícil (ver, por ejemplo, esta presentación y su lista de referencias para tener una idea de su complejidad). Su situación de ejemplo comienza a comprender por qué es difícil: para saber con qué frecuencia sucede esto, necesita saber qué tan rápido viaja el ascensor, en relación con la frecuencia con la que llega la gente. Y una vez que suceda, tal vez sea mejor enviar el elevador del décimo piso, pero tal vez el elevador del primer piso haga lo suyo con bastante rapidez y usted debería esperar a que se haga. Para responder a este tipo de preguntas, necesita muchos datos sobre la situación específica de su apartamento; una respuesta teórica basada en algunas suposiciones no lo llevará a ninguna parte útil.
Pero lo difícil es determinar qué hacer cuando los ascensores están ocupados. Estás preguntando sobre qué pisos quieres que descansen los ascensores, que es algo que solo importa cuando no están particularmente ocupados. Y en ese caso, junto con sus suposiciones, podemos encontrar algo manejable.
Entonces, además de las suposiciones que hizo, también asumiré que:
- Solo una persona quiere usar el ascensor a la vez, por lo que los ascensores siempre están en sus pisos de descanso cuando alguien quiere usarlos.
- Los ascensores se mueven de piso a piso a velocidad constante, por lo que el tiempo de espera de un pasajero es proporcional a la distancia al ascensor más cercano. (Esta suposición podría eliminarse y no dificultaría mucho el problema, pero es difícil saber con qué reemplazarlo).
Además, a menos que estemos en un cierto chiste matemático clásico, sus suposiciones implican que un pasajero querrá subir o bajar con la misma probabilidad.
Esto es suficiente para solucionar el problema. Tomamos una población representativa que consiste en una persona en cada piso superior que quiere bajar y 9 personas en la planta baja que quieren subir. Sobre esta población, minimizamos el tiempo total de espera; es decir, la distancia total al ascensor más cercano. La siguiente secuencia de comandos de Python simple hace esto para cada posible configuración de ascensor y luego le dice cuál es la mejor:
least_wait_time = float('inf')
passengers = [1 for i in range(0, 9)] + range(2, 11)
def wait_time(passenger, elevator1, elevator2):
return min(abs(passenger - elevator1), abs(passenger - elevator2))
for high_elevator in range(2, 11):
for low_elevator in range(1, high_elevator):
total_wait_time = sum(wait_time(passenger, low_elevator, high_elevator)
for passenger in passengers)
print 'Elevator positions: ' + str((low_elevator, high_elevator))
print 'Total wait time: ' + str(total_wait_time)
if total_wait_time < least_wait_time:
best_elevators = (low_elevator, high_elevator)
least_wait_time = total_wait_time
print ''
print 'Optimal elevator position: ' + str(best_elevators)
print 'Optimal wait time: ' + str(least_wait_time)
Resulta que lo óptimo, dadas todas estas suposiciones, es colocar un ascensor en el piso 1 y el otro en el piso 7. Esto da un tiempo de espera total de 15 (es decir, sobre la población de 18 personas, el El ascensor más cercano comenzará en promedio a 15/18 pisos de distancia).
¿Por qué esto es diferente de su resultado? Porque no asumimos que el ascensor del piso 1 se usa únicamente para subir. Si alguien quiere bajar del piso 2 o 3, el elevador del primer piso ya está más cerca de ellos que el elevador superior, incluso cuando el elevador superior está en el piso 6, por lo que no es útil mantener el elevador superior cerca de ellos. . Así que podríamos subir un poco el ascensor superior para mantener contenta a la gente de los pisos realmente altos.
Su modelo se refiere al “modo de baja frecuencia” de los ascensores: el edificio tiene $ n geq1 $ pisos de altura, por lo que los pisos están numerados de $ 0 $ a $ n $. Los ascensores están en reposo en los pisos $ r $ y $ s $ con $ 0 leq r[n]PS El tiempo de espera esperado de este cliente es $$ E (r, s) = {1 over2} r + {1 over2n} sum_ {k = 1} ^ r (rk) + {1 over2n} sum_ { k = r + 1} ^ {s-1} min {kr, sk } + {1 over2n} sum_ {k = s} ^ n (ks) . $$ En tu caso $ n = 9 PS Use su poder de hoja de cálculo para calcular el mínimo $ E (r, s) $. En cualquier caso, el ascensor inferior no debe reservarse para los clientes que deseen subir.