Utilisateur:Dfeldmann/brouillon7

Une page de Wikipédia, l'encyclopédie libre.

Ceci est un brouillon de traduction ; prière de ne pas le modifier ⇒ brouillon suivant


Le problème de la traversée du désert (connu aussi sous le nom de problème de la jeep) est un problème d'optimisation où un véhicule ne pouvant transporter qu'une quantité limité de carburant, mais ayant la possibilité de construire des réserves, doit parcourir la plus grande distance possible avec une quantité fixée de carburant au départ. De nombreuses variantes du problème existent, avec une flotte de véhicules, la nécesssité de revenir au point de départ à la fin du voyage, etc.

Historique et variantes[modifier | modifier le code]

Le problème apparait pour la première fois au 8e siècle dans Propositiones ad acuendos juvenes (Problèmes pour aiguiser la jeunesse) de Alcuin ; vers 1500, il est également discuté dans le De viribus quantitatis de Luca Pacioli. Un exposé moderne, sous le nom du problème de la jeep, est dû à Nathan Fine en 1947[1].

Dans la forme exposée par Fine, la jeep tranporte une quantité de carburant limitée, avec lequel elle parcourt une distance proportionnelle au carburant consommé ; elle peut faire des dépots de carburant de taille arbitraire en des points arbitraires, et part d'une base contenant une quantité fixée de carburant. On demande la distance maximale qu'elle peut parcourir, soit en revenant à sa base (problème de l'exploration du désert), soit en arrivant au point le plus éloigné le réservoir vide (problème de la traversée du désert)[2]. La mise en équation donnée plus bas précisera les ambiguïtés éventuelles de ces énoncés.

Le problème connait plusieurs variantes, souvent exposées sous une forme imagée :

  • Le problème du chameau et des bananes[3] : un marchand doit transporter le plus de bananes possibles à un marché, utilisant un chameau qui doit consommer des bananes pour avancer ; il peut créer autant de réserves qu'il veut. En un certain sens, c'est le problème dual du problème de la jeep : la distance est fixe, et on veut amener à l'arrivée le maximum de « carburant » (dans la version de base, peu réaliste, on suppose qu'on peut faire des réserves de fractions de bananes aussi petites qu'on veut).
  • Le problème du groupe de voyageurs[4] : il s'agit de minimiser l'effectif du groupe, sachant que l'un au moins doit effectuer la traversée, que tous les autres doivent retourner à la base, et qu'ils peuvent échanger leurs rations, mais pas constituer de réserves.
  • Le problème de la flotille de véhicules[5]  : les contraintes sont les mêmes que précédemment, mais on peut cette fois abandonner un véhicule sur place quand il n'a plus de carburant.

Mise en équation du problème[modifier | modifier le code]

La mise en équation du problème et de ses différentes variantes, outre qu'elle est nécessaire pour déterminer la solution par une analyse mathématique, permet de préciser les contraintes exactes de l'énoncé

Problème de la jeep[modifier | modifier le code]

La base continent une réserve de n (unités de carburant). La jeep a une capacité de 1 (unité de carburant). Se déplacer de x (unités de distance) coûte x unités de carburant, x étant un réel quelconque compris entre 0 et 1[6]. Les dépôts de carburants sont faits à des endroits arbitraires, et en quantité arbitraire. Chaque voyage amène la jeep à retourner à sa base dans la variante d'exploration du désert, mais le dernier voyage se termine réservoir vide le plus loin possible dans la variante de traversée du désert.

Une mise en équation rigoureuse passe par l'introduction d'un ensemble de suites décrivant les états de la jeep et des dépôts de carburants après le i-ème voyage (avec des règles de transition donnant, par exemple, le nouveau contenu de chaque dépôt), mais cela ne sera pas nécessaire pour décrire la solution.

Variantes[modifier | modifier le code]

Dans le problème du chameau et des bananes, le merchant a une réserve (à sa base) de n paquets de bananes. Le chameau peut transporter 1 paquet au maximum, et doit consommer un paquet chaque fois qu'il parcourt une unité de distance ; le marché est à m unités de distance away. Les règles de dépot et de collecte sont les mêmes que dans le problème de la jeep ; la question est de maximiser la quantité de bananes apportées au marché.

Dans le problème du groupe de voyageurs, les réserves à la base sont illimitées, il y a m unités de distance à traverser, chaque voyageur transporte une unité de nourriture au maximum, et consomme une unité de nourriture par unité de distance ; il est impossible de faire des réserves, mais les voyageurs peuvent échanger de la nourriture entre eux. Un voyageur doit effecteur la traversée, et tous les autres doivent retourner à la base. Le problème demande le nombre minimum de voyageurs nécessaire pour une distance donnée (ou parfois la distance maximum traversable par un groupe de taille donnée).

Dans le problème de la flotille de véhicules, les contraintes sont les mêmes que pour le problème du groupe de voyageurs, mais une seule voiture doit parvenir à destination, les autres pouvant être abandonnées en route lorsque leurs réservoirs sont vides.

Solutions[modifier | modifier le code]

Problème de la jeep[modifier | modifier le code]

A strategy that maximizes the distance traveled on the final trip for the "exploring the desert" variant is as follows:

  • The jeep makes n trips. On each trip it starts from base with 1 unit of fuel.
  • On the first trip the jeep travels a distance of 1/(2n) units and leaves (n − 1)/n units of fuel at a fuel dump. The jeep still has 1/(2n) units of fuel – just enough to return to base.
  • On each of the subsequent n − 1 trips the jeep collects 1/(2n) units of fuel from this first fuel dump on the way out, so that it leaves the fuel dump carrying 1 unit of fuel. It also collects 1/(2n) units of fuel from this first fuel dump on the way back, which is just enough fuel to return to base.
  • On the second trip the jeep travels to the first fuel dump and refuels. It then travels a distance of 1/(2n − 2) units and leaves (n − 2)/(n − 1) units of fuel at a second fuel dump. The jeep still has 1/(2n − 2) units of fuel, which is just enough to return to the first fuel dump. Here it collects 1/(2n) units of fuel, which is just enough fuel to return to base.
  • On each of the subsequent n − 2 trips the jeep collects 1/(2n − 2) units of fuel from this second fuel dump on the way out, so that it leaves the fuel dump carrying 1 unit of fuel. It also collects 1/(2n − 2) units of fuel from the second fuel dump on the way back, which is just enough fuel to return to the first fuel dump.
  • The jeep continues in this way, so that on trip k it establishes a new kth fuel dump at a distance of 1/(2n − 2k + 2) units from the previous fuel dump and leaves (n − k)/(n − k + 1) units of fuel there. On each of the subsequent n − k trips it collects 1/(2n − 2k + 2) units of fuel from the kth dump on its way out and another 1/(2n − 2k + 2) units of fuel on its way back.

When the jeep starts its final trip, there are n − 1 fuel dumps. The farthest contains 1/2 of a unit of fuel, the next farthest contain 1/3 of a unit of fuel, and so on, and the nearest fuel dump has just 1/n units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total round trip distance of

units on its final trip (the maximum distance traveled into the desert is half of this).[7] It collects half of the remaining fuel at each dump on the way out, which fills its tank. After leaving the farthest fuel dump it travels 1/2 a unit further into the desert and then returns to the farthest fuel dump. It collects the remaining fuel from each fuel dump on the way back, which is just enough to reach the next fuel dump or, in the final step, to return to base.

The distance travelled on the last trip is the nth harmonic number, Hn. As the harmonic numbers are unbounded, it is possible to exceed any given distance on the final trip, as along as sufficient fuel is available at the base. However, the amount of fuel required and the number of fuel dumps both increase exponentially with the distance to be traveled.

The "crossing the desert" variant can be solved with a similar strategy, except that there is now no requirement to collect fuel on the way back on the final trip. So on trip k the jeep establishes a new kth fuel dump at a distance of 1/(2n − 2k + 1) units from the previous fuel dump and leaves (2n − 2k − 1)/(2n − 2k + 1) units of fuel there. On each of the next n − k − 1 trips it collects 1/(2n − 2k + 1) units of fuel from the kth dump on its way out and another 1/(2n − 2k + 1) units of fuel on its way back.

Now when the jeep starts its final trip, there are n − 1 fuel dumps. The farthest contains 1/3 of a unit of fuel, the next farthest contain 1/5 of a unit of fuel, and so on, and the nearest fuel dump has just 1/(2n − 1) units of fuel left. Together with 1 unit of fuel with which it starts from base, this means that the jeep can travel a total distance of

units on its final trip.[1][7] It collects all of the remaining fuel at each dump on the way out, which fills its tank. After leaving the farthest fuel dump it travels a further distance of 1 unit.

Note that

so it is possible in theory to cross a desert of any size given enough fuel at the base. As before, the amount of fuel required and the number of fuel dumps both increase exponentially with the distance to be traveled.

Variantes[modifier | modifier le code]

In the camel and bananas problem, the above solution for "crossing the desert" is optimal if , and the maximum units of bananas that can be transported is , which is between 0 and 1. However, if , then the (n−1)-th camp post is unnecessary, because its location would be farther than the market itself. Instead, the market itself will be the (n−1)-th camp post. Therefore, the maximum units of bananas that can be transported is , which is between 1 and 2. Similarly, if , then the (n−2)-th and (n−1)-th camp post are both unnecessary, and the maximum units of bananas that can be transported is , which is between 2 and 3. And so on.

In the travelers across the desert problem, assume that n travelers set out from the starting base with n units of supplies. After 1/(n+1) units of distance, they would have already consumed n/(n+1) units of supplies; At this point, one of the travelers should return with 1/(n+1) units of supplies, leaving the group exactly (n-1) units of supplies so that each remaining traveler carries exactly one unit of supplies. The group then travels another 1/(n+1) units of distance, consuming (n-1)/(n+1) units of supplies; At this point, one of the remaining travelers should return with 2/(n+1) units of supplies to safely get back to the starting base, leaving the group exactly (n-2) units of supplies. The group keeps moving 1/(n+1) units of distance and reducing one traveler, until there is only one traveler left carrying exactly one unit of supplies. Finally, this traveler can travel one unit of distance to reach the farthest point. In total, the longest distance n travelers can reach is (n-1)/(n+1)+1=2-2/(n+1); Equating this to m, one may solve for the minimum number of travelers needed to travel m units of distance. Note that solutions only exist for m<2.

In the cars across the desert problem, assume that n cars set out from the starting base with n units of fuel. After 1/n units of distance, the group would have already consumed exactly one unit of fuel; At this point, they should transfer fuel between them, leave an empty car behind, and carry (n-1) units of fuel among (n-1) cars. After another 1/(n-1) units of distance, the group would have consumed another one unit of fuel; Again, they should transfer fuel, leave an empty car behind, and carry (n-2) units of fuel among (n-2) cars. The group keeps moving and reducing one car, until there is only one car left carrying exactly one unit of fuel. Finally, this car can travel one unit of distance to reach the farthest point. In total, the longest distance n cars can reach is the nth harmonic number, Hn; Equating this to m, one may solve for the minimum number of cars needed to travel m units of distance.

Indépendance de l'ordre des voyages[modifier | modifier le code]

Note that the order of the jeep trips is not fixed. For example in the "exploring the desert" version of the problem, the jeep could make n − 1 round-trips between the base and the first fuel dump, leaving (n − 1) / n units of fuel at the fuel dump each time and then make an n-th trip one-way to the first fuel dump, thus arriving there with a total of (n − 1) + 1/(2n) units of fuel available. The 1/(2n) units are saved for the return trip to base at the very end and the other n − 1 units of fuel are used to move fuel between the first and second fuel dump, using n − 2 round-trips and then an (n−1)-th trip one-way to the second fuel dump. And so on.

Le cas continu[modifier | modifier le code]

The number of fuel units available at the base need not be an integer. In the general case, the maximum distance achievable for the "explore the desert" problem with n units of fuel is

and maximum distance achievable for the "cross the desert" problem with n units of fuel is

Applications pratiques[modifier | modifier le code]

The problem can have a practical application in wartime situations, especially with respect to fuel efficiency. In the context of the bombing of Japan in World War II by B-29s, Robert McNamara says in the film The Fog of War that understanding the fuel efficiency issue caused by having to transport the fuel to forward bases was the main reason why the strategy of launching bombing raids from mainland China was abandoned in favor of the island hopping strategy:

« "We had to fly those planes from the bases in Kansas to India. Then we had to fly fuel over the hump into China. [...] We were supposed to take these B-29s—there were no tanker aircraft there. We were to fill them with fuel, fly from India to Chengtu; offload the fuel; fly back to India; make enough missions to build up fuel in Chengtu; fly to Yawata, Japan; bomb the steel mills; and go back to India.

We had so little training on this problem of maximizing [fuel] efficiency, we actually found to get some of the B-29s back instead of offloading fuel, they had to take it on. To make a long story short, it wasn't worth a damn. And it was LeMay who really came to that conclusion, and led the Chiefs to move the whole thing to the Marianas, which devastated Japan."[8] »

(The atomic bombing missions at the end of World War II were flown using B-29 Superfortresses from the Pacific island of Tinian in the Northern Marianas Islands.)

See also Operation Black Buck for an application of these ideas. In these missions, conducted during the Falklands War, the Royal Air Force used air to air refueling by staging tankers to enable the Vulcan bombers based on Ascension Island to bomb targets in the Falkland Islands.

The problem is also a theme in Terry Pratchett's book Small Gods, where the Omnian Army propagates a stash of water to cross a vast desert.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. a et b (en) Eric W. Weisstein, « Jeep Problem », sur MathWorld
  2. (en) Martin Gardner, My Best Mathematical and Logic Puzzles, Dover, , 53 p. (ISBN 0-486-28152-3, lire en ligne)
  3. (en-US) « Puzzle 15 | (Camel and Banana Puzzle) », sur GeeksforGeeks, (consulté le 4 février 2020)
  4. (en) « Travelers across a desert », sur puzzling.stackexchange.com (consulté le 4 février 2020)
  5. « Cars Across the Desert Puzzle - Solution », sur www.mathsisfun.com (consulté le 4 février 2020)
  6. Il existe des variantes dans lesquelles x est une fraction de la forme k/p, avec p fixé ; voir Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, Gunter Rote and Guochuan Zhang, June 1996
  7. a et b "Exploration problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by an explorer capable of carrying provisions that would last him for a days." W. W. Rouse Ball and H.S.M. Coxeter (1987). Mathematical Recreations and Essays, Thirteenth Edition, Dover, p32. (ISBN 0-486-25357-0).
  8. Fog of War transcript, www.errolmorris.com