El problema del jeep , [1] el problema del cruce del desierto [2] o el problema de exploración [3] es un problema matemático en el que un jeep debe maximizar la distancia que puede viajar al desierto con una determinada cantidad de combustible. El jeep solo puede transportar una cantidad fija y limitada de combustible, pero puede dejar combustible y recolectar combustible en vertederos de combustible en cualquier parte del desierto.
El problema apareció por primera vez en la colección del siglo IX Propositiones ad Acuendos Juvenes ( Problemas para agudizar a los jóvenes ), atribuida a Alcuin . [4] El De viribus quantitatis (c. 1500) de Luca Pacioli también analiza el problema. NJ Fine dio un tratamiento moderno en 1947. [1]
El problema del jeep está relacionado con varios otros problemas de optimización:
- El problema del camello y los plátanos [5] es un problema matemático en el que un comerciante debe maximizar el número de plátanos transportados a un mercado utilizando un camello que necesita comer plátanos para moverse. El camello solo puede transportar una cantidad fija y limitada de plátanos, pero el comerciante puede dejar los plátanos y recogerlos en cualquier lugar del desierto.
- El problema de los viajeros a través del desierto [6] , es un problema matemático que pide el número mínimo de viajeros acompañantes necesarios para llegar a otra base lejana, sin dejar morir de hambre a ningún viajero en el camino. Cada viajero solo puede llevar una cantidad fija y limitada de suministros, y no puede dejar suministros en el desierto para recogerlos más tarde. Sin embargo, los viajeros acompañantes pueden transferir suministros entre ellos.
- El problema de los coches a través del desierto , [7] es un problema matemático que pide el número mínimo de coches acompañantes necesarios para llegar a otra base lejana, con coches vacíos abandonados en el camino. Cada automóvil solo puede transportar una cantidad fija y limitada de combustible, y no puede dejar combustible en el desierto para recogerlo más tarde. Sin embargo, los vehículos acompañantes pueden transferir suministros entre ellos. Tenga en cuenta que este problema tiene similitudes con el funcionamiento de un cohete multietapa .
Problema
Hay n unidades de combustible almacenadas en una base fija. El jeep puede transportar como máximo 1 unidad de combustible en cualquier momento y puede viajar 1 unidad de distancia con 1 unidad de combustible (se supone que el consumo de combustible del jeep es constante). En cualquier punto de un viaje, el jeep puede dejar cualquier cantidad de combustible que esté transportando en un depósito de combustible, o puede recolectar cualquier cantidad de combustible que haya quedado en un depósito de combustible en un viaje anterior, siempre que su carga de combustible nunca exceda 1 unidad. Hay dos variantes del problema:
- Explorando el desierto : el jeep debe regresar a la base al final de cada viaje.
- Cruzando el desierto : el jeep debe regresar a la base al final de cada viaje, excepto en el viaje final, cuando el jeep viaja lo más lejos que puede antes de quedarse sin combustible.
En cualquier caso, el objetivo es maximizar la distancia recorrida por el jeep en su viaje final. Alternativamente, el objetivo puede ser encontrar la menor cantidad de combustible necesaria para producir un viaje final de una distancia determinada.
En el problema clásico, el combustible en el jeep y en los vertederos de combustible se trata como una cantidad continua . Se han propuesto variaciones más complejas del problema en las que el combustible solo puede dejarse o recogerse en cantidades discretas. [8]
En el problema del camello y el banano , el comerciante tiene n unidades de banano. El camello puede transportar como máximo 1 unidad de plátanos en cualquier momento y puede viajar 1 unidad de distancia con 1 unidad de plátanos. El mercado está a m unidades de distancia. En cualquier punto de un viaje, el camello puede dejar cualquier cantidad de plátanos que esté cargando en un campamento, o puede recolectar cualquier cantidad de plátanos que haya dejado en un campamento en un viaje anterior, siempre que su carga de plátanos nunca exceda 1 unidad. El problema pide las unidades máximas de banano que se pueden transportar al mercado.
En el problema de los viajeros a través del desierto , la base de partida tiene unidades ilimitadas de suministros. Cada viajero puede llevar como máximo 1 unidad de suministros en cualquier momento y puede viajar 1 unidad de distancia con 1 unidad de suministros. La otra base está a m unidades de distancia. Al contrario de los dos problemas anteriores, los viajeros no pueden dejar provisiones en el desierto; Sin embargo, en cualquier punto de un viaje, los viajeros acompañantes pueden transferir suministros entre ellos, siempre que cada viajero nunca lleve más de 1 unidad de suministros. Cada viajero que regresa debe tener suficientes suministros en el camino de regreso. El problema pide el número mínimo de viajeros acompañantes necesarios para llegar a la otra base. Una variante de este problema da el número total de viajeros disponibles y pregunta la distancia máxima que se puede alcanzar.
En los autos a través del problema del desierto , la base de partida tiene unidades ilimitadas de combustible. Cada automóvil puede transportar como máximo 1 unidad de suministros en cualquier momento y puede viajar 1 unidad de distancia con 1 unidad de combustible. La otra base está a m unidades de distancia. Los coches no pueden dejar combustible en el desierto; Sin embargo, en cualquier momento de un viaje, los vehículos que los acompañan pueden transferir combustible entre ellos, siempre que cada vehículo nunca lleve más de 1 unidad de combustible. Los coches vacíos sin combustible se abandonan en el desierto. El problema pide el número mínimo de coches acompañantes necesarios para llegar a la otra base. Una variante de este problema da el número total de coches disponibles y pregunta la distancia máxima que se puede alcanzar.
Solución
Una estrategia que maximiza la distancia recorrida en el viaje final para la variante "explorar el desierto" es la siguiente:
- El jeep hace n viajes. En cada viaje comienza desde la base con 1 unidad de combustible.
- En el primer viaje, el jeep recorre una distancia de 1 / (2 n ) unidades y deja ( n - 1) / n unidades de combustible en un depósito de combustible. El jeep todavía tiene 1 / (2 n ) unidades de combustible, lo suficiente para regresar a la base.
- En cada uno de los n - 1 viajes posteriores , el jeep recoge 1 / (2 n ) unidades de combustible de este primer depósito de combustible al salir, de modo que sale del depósito de combustible con 1 unidad de combustible. También recolecta 1 / (2 n ) unidades de combustible de este primer depósito de combustible en el camino de regreso, que es suficiente combustible para regresar a la base.
- En el segundo viaje, el jeep viaja al primer depósito de combustible y reposta. Luego recorre una distancia de 1 / (2 n - 2) unidades y deja ( n - 2) / ( n - 1) unidades de combustible en un segundo depósito de combustible. El jeep todavía tiene 1 / (2 n - 2) unidades de combustible, que es suficiente para regresar al primer depósito de combustible. Aquí recolecta 1 / (2 n ) unidades de combustible, que es suficiente combustible para regresar a la base.
- En cada uno de los siguientes n - 2 viajes, el jeep recoge 1 / (2 n - 2) unidades de combustible de este segundo depósito de combustible al salir, de modo que sale del depósito de combustible con 1 unidad de combustible. También recoge 1 / (2 n - 2) unidades de combustible del segundo depósito de combustible en el camino de regreso, que es suficiente combustible para regresar al primer depósito de combustible.
- El jeep continúa de esta manera, de modo que en el viaje k establece un nuevo k- ésimo depósito de combustible a una distancia de 1 / (2 n - 2 k + 2) unidades del depósito de combustible anterior y sale ( n - k ) / ( n - k + 1) unidades de combustible allí. En cada uno de los siguientes n - k viajes, recolecta 1 / (2 n - 2 k + 2) unidades de combustible del k- ésimo vertedero al salir y otras 1 / (2 n - 2 k + 2) unidades de combustible. en su camino de regreso.
Cuando el jeep comienza su viaje final, hay n - 1 descargas de combustible. El más lejano contiene 1/2 de una unidad de combustible, el siguiente más lejano contiene 1/3 de una unidad de combustible, y así sucesivamente, y al depósito de combustible más cercano le quedan solo 1 / n unidades de combustible. Junto con 1 unidad de combustible con la que parte desde la base, esto significa que el jeep puede recorrer una distancia total de ida y vuelta de
unidades en su viaje final (la distancia máxima recorrida en el desierto es la mitad de esto). [3] Recoge la mitad del combustible restante en cada vertedero al salir, lo que llena su tanque. Después de dejar el vertedero de combustible más lejano, viaja 1/2 unidad más hacia el desierto y luego regresa al vertedero de combustible más lejano. Recoge el combustible restante de cada depósito de combustible en el camino de regreso, lo que es suficiente para llegar al siguiente depósito de combustible o, en el paso final, para regresar a la base.
La distancia recorrida en el último viaje es el n- ésimo número armónico , H n . Como los números de armónicos son ilimitados, es posible exceder cualquier distancia dada en el viaje final, siempre que haya suficiente combustible disponible en la base. Sin embargo, la cantidad de combustible requerida y el número de descargas de combustible aumentan exponencialmente con la distancia a recorrer.
La variante "cruzar el desierto" se puede resolver con una estrategia similar, excepto que ahora no es necesario recolectar combustible en el camino de regreso en el viaje final. Entonces, en el viaje k, el jeep establece un nuevo k- ésimo depósito de combustible a una distancia de 1 / (2 n - 2 k + 1) unidades del depósito de combustible anterior y se va (2 n - 2 k - 1) / (2 n - 2 k + 1) unidades de combustible allí. En cada uno de los siguientes n - k - 1 viajes, recolecta 1 / (2 n - 2 k + 1) unidades de combustible del k- ésimo vertedero al salir y otras 1 / (2 n - 2 k + 1) unidades de combustible en su camino de regreso.
Ahora, cuando el jeep comienza su viaje final, hay n - 1 descargas de combustible. El más lejano contiene 1/3 de una unidad de combustible, el siguiente más lejano contiene 1/5 de una unidad de combustible, y así sucesivamente, y al depósito de combustible más cercano le quedan solo 1 / (2 n - 1) unidades de combustible. Junto con 1 unidad de combustible con la que parte desde la base, esto significa que el jeep puede recorrer una distancia total de
unidades en su último viaje. [1] [3] Recoge todo el combustible restante en cada vertedero al salir, lo que llena su tanque. Después de dejar el vertedero de combustible más lejano, recorre una distancia adicional de 1 unidad.
Tenga en cuenta que
por lo que, en teoría, es posible cruzar un desierto de cualquier tamaño con suficiente combustible en la base. Como antes, la cantidad de combustible requerida y el número de descargas de combustible aumentan exponencialmente con la distancia a recorrer.
En el problema de los camellos y los plátanos , la solución anterior para "cruzar el desierto" es óptima si, y las unidades máximas de banano que se pueden transportar es , que está entre 0 y 1. Sin embargo, si , entonces el puesto de campamento ( n −1) -ésimo es innecesario, porque su ubicación estaría más lejos que el mercado mismo. En cambio, el mercado mismo será el puesto de campo ( n −1) -ésimo. Por tanto, las unidades máximas de banano que se pueden transportar es, que está entre 1 y 2. Del mismo modo, si , entonces el puesto de campamento ( n −2) -ésimo y ( n −1) -ésimo son innecesarios, y las unidades máximas de plátanos que se pueden transportar es, que está entre 2 y 3. Y así sucesivamente.
En el problema de los viajeros a través del desierto , suponga que n viajeros partieron de la base inicial con n unidades de suministros. Después de 1 / ( n +1) unidades de distancia, ya habrían consumido n / ( n +1) unidades de suministros; En este punto, uno de los viajeros debe regresar con 1 / ( n +1) unidades de suministros, dejando al grupo exactamente ( n -1) unidades de suministros para que cada viajero restante lleve exactamente una unidad de suministros. Luego, el grupo viaja otras 1 / ( n +1) unidades de distancia, consumiendo ( n -1) / ( n +1) unidades de suministros; En este punto, uno de los viajeros restantes debe regresar con 2 / ( n +1) unidades de suministros para regresar con seguridad a la base inicial, dejando al grupo exactamente ( n -2) unidades de suministros. El grupo sigue moviendo 1 / ( n +1) unidades de distancia y reduciendo un viajero, hasta que solo queda un viajero que lleva exactamente una unidad de suministros. Finalmente, este viajero puede viajar una unidad de distancia para llegar al punto más lejano. En total, la distancia más larga que pueden alcanzar n viajeros es ( n -1) / ( n +1) + 1 = 2-2 / ( n +1); Igualando a esta m , uno puede hallar el número mínimo de los viajeros necesarios para los viajes m unidades de distancia. Tenga en cuenta que las soluciones solo existen para m <2.
En el problema de los coches a través del desierto , suponga que n coches parten de la base de partida con n unidades de combustible. Después de 1 / n unidades de distancia, el grupo ya habría consumido exactamente una unidad de combustible; En este punto, deben transferir combustible entre ellos, dejar un automóvil vacío y transportar ( n -1) unidades de combustible entre ( n -1) automóviles. Después de otras 1 / ( n -1) unidades de distancia, el grupo habría consumido otra unidad de combustible; Nuevamente, deben transferir combustible, dejar un automóvil vacío y transportar ( n -2) unidades de combustible entre ( n -2) automóviles. El grupo sigue moviéndose y reduciendo un automóvil, hasta que solo queda un automóvil que transporta exactamente una unidad de combustible. Finalmente, este automóvil puede viajar una unidad de distancia para llegar al punto más lejano. En total, la distancia más larga que pueden alcanzar n coches es el n- ésimo número armónico , H n ; Igualando a esta m , uno puede hallar el mínimo número de vehículos necesarios para los viajes m unidades de distancia.
Orden de independencia
Tenga en cuenta que el orden de los viajes en jeep no es fijo. Por ejemplo, en la versión "explorando el desierto" del problema, el jeep podría hacer n - 1 viajes de ida y vuelta entre la base y el primer depósito de combustible, dejando ( n - 1) / n unidades de combustible en el depósito de combustible cada vez. y luego hacer un n -ésimo viaje de ida hasta el primer depósito de combustible, llegando así con un total de ( n - 1) + 1 / (2 n ) unidades de combustible disponibles. Las unidades 1 / (2 n ) se guardan para el viaje de regreso a la base al final y las otras n - 1 unidades de combustible se utilizan para mover el combustible entre el primer y el segundo depósito de combustible, utilizando n - 2 viajes de ida y vuelta y luego un viaje ( n −1) -ésimo en un sentido hasta el segundo depósito de combustible. Y así.
Cantidad continua de combustible
No es necesario que el número de unidades de combustible disponibles en la base sea un número entero. En el caso general, la distancia máxima alcanzable para el problema de "explorar el desierto" con n unidades de combustible es
y la distancia máxima alcanzable para el problema de "cruzar el desierto" con n unidades de combustible es
Aplicaciones prácticas
El problema puede tener una aplicación práctica en situaciones de guerra, especialmente con respecto a la eficiencia del combustible. En el contexto del bombardeo de Japón en la Segunda Guerra Mundial por los B-29 , Robert McNamara dice en la película The Fog of War que comprender el problema de la eficiencia del combustible causado por tener que transportar el combustible a las bases avanzadas fue la razón principal por la que la estrategia de lanzar bombardeos desde China continental se abandonó en favor de la estrategia de isla en isla :
"Tuvimos que volar esos aviones desde las bases en Kansas hasta la India. Luego tuvimos que llevar combustible por encima de la joroba hacia China. [...] Se suponía que íbamos a tomar estos B-29 , no había aviones cisterna allí. eran llenarlos de combustible, volar de India a Chengtu ; descargar el combustible; volar de regreso a India; hacer suficientes misiones para acumular combustible en Chengtu; volar a Yawata , Japón ; bombardear las acerías ; y regresar a India. tenía tan poca capacitación sobre este problema de maximizar la eficiencia [del combustible], de hecho, descubrimos que para recuperar algunos de los B-29 en lugar de descargar combustible, tenían que hacerlo. Para abreviar la historia, no valía la pena Maldita sea. Y fue LeMay quien realmente llegó a esa conclusión y llevó a los Chiefs a trasladar todo el asunto a las Marianas , que devastó Japón ". [9]
(Las misiones de bombardeo atómico al final de la Segunda Guerra Mundial se volaron utilizando Superfortalezas B-29 de la isla de Tinian en el Pacífico en las Islas Marianas del Norte ).
Vea también Operación Black Buck para una aplicación de estas ideas. En estas misiones, llevadas a cabo durante la Guerra de las Malvinas , la Royal Air Force utilizó el reabastecimiento de combustible aire-aire colocando camiones cisterna para permitir que los bombarderos Vulcan basados en la Isla Ascensión bombardeen objetivos en las Islas Malvinas .
El problema también es un tema en el libro Small Gods de Terry Pratchett , donde el Ejército Omniano propaga un alijo de agua para cruzar un vasto desierto.
Ver también
- Serie armónica (matemáticas)
- Optimización (matemáticas)
Referencias
- ^ a b c Weisstein, Eric W. "Problema de Jeep" . MathWorld .
- ^ Gardner, Martin (1994). Mis mejores acertijos matemáticos y lógicos . Dover. págs. 53 . ISBN 0-486-28152-3.
- ^ a b c " Problemas de exploración. Otra cuestión común tiene que ver con la distancia máxima a un desierto a la que podría llegar un explorador capaz de transportar provisiones que le durarían unos días desde un asentamiento fronterizo ". WW Rouse Ball y HSM Coxeter (1987). Recreaciones y ensayos matemáticos , decimotercera edición, Dover, p32. ISBN 0-486-25357-0 .
- ^ Problemas para agudizar a los jóvenes , John Hadley y David Singmaster, The Mathematical Gazette , 76 , # 475 (marzo de 1992), págs. 102-126.
- ^ "Puzzle 15 | (Puzzle Camello y Plátano)" . GeeksforGeeks . 2015-03-11 . Consultado el 4 de febrero de 2020 .
- ^ "Viajeros por el desierto" . mathforum.org . Consultado el 4 de febrero de 2020 .
- ^ "Cars Across the Desert Puzzle - Solución" . www.mathsisfun.com . Consultado el 4 de febrero de 2020 .
- ^ Logística óptima para expediciones: el problema de Jeep con llenado completo , Gunter Rote y Guochuan Zhang, junio de 1996
- ^ Transcripción de la niebla de guerra , www.errolmorris.com