Problème de la traversée du désert
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 flottille de véhicules, la nécessité de revenir au point de départ à la fin du voyage, etc.
Historique et variantes
modifierLe 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 transporte une quantité de carburant limitée, avec lequel elle parcourt une distance proportionnelle au carburant consommé ; elle peut faire des dépôts 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 flottille 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
modifierLa 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
modifierLa base contient 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
modifierDans le problème du chameau et des bananes, le marchant 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. Les règles de dépôt 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 flottille 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
modifierProblème de la jeep
modifierUne solution au problème de l'exploration du désert (optimale, à l'ordre des voyages près) est la suivante[7] :
- La jeep fait voyages, partant de la base à chaque fois en ayant fait le plein (une unité de carburant).
- Au premier voyage, la jeep crée un dépôt à une distance , y laisse unités de carburant et revient à la base (arrivant réservoir vide).
- Au second voyage , la jeep refait le plein au premier dépôt, avance de unités et laisse unités à un second dépôt, ce qui lui laisse juste assez de carburant pour revenir au premier dépôt, y prendre unités et retourner à la base.
- La stratégie est la même à chaque voyage : avancer jusqu'au dernier dépôt établi, en refaisant le plein à chaque dépôt, construire un nouveau dépôt, et revenir en reprenant dans chaque dépôt juste assez de carburant pour atteindre le dépôt précédent. Plus précisément, au -ème voyage, le nouveau dépôt est établi à une distance du précédent, et la jeep y laisse unités de carburant.
On vérifie facilement qu'à son dernier voyage, la jeep avance en prenant à chaque fois la moitié de ce qui reste dans chaque dépôt, refaisant le plein, atteint le dernier dépôt (où il y a unités de carburant) avec unités, refait le plein, puis avance de 1/2 et revient enfin en vidant chaque dépôt, ce qui lui permet tout juste d'atteindre la base, en ayant parcouru lors de ce dernier voyage le double de , la distance explorée maximum :
- , étant le -ème nombre harmonique (on a ) .
Cet encadrement montre qu'il est possible de parcourir lors du dernier voyage une distance arbitraire, mais que cela nécessite une réserve initiale de carburant et un nombre de dépôts grandissant exponentiellement avec la distance parcourue.
La variante de traversée du désert utilise une stratégie analogue, mais il n'y a plus besoin de laisser du carburant pour le retour lors du dernier voyage. Aussi, lors du -ème voyage, le nouveau dépôt est établi à une distance du précédent, et la jeep y laisse unités de carburant ; au cours des voyages suivants, elle prend dans ce dépôt unités de carburant à l'aller, et la même quantité au retour.
Au début du dernier voyage, dépôts ont été établis ; le dernier contient unités, le précédent , et ainsi de suite, le dépôt le plus proche contenant ; partant avec 1 unité de la base et refaisant le plein à chaque dépôt, la jeep parcourra finalement une distance de ; on voit facilement que , et donc comme précédemment, on peut traverser un désert arbitrairement large, mais le nombre de dépôts croit exponentiellement avec la distance[1],[7].
Variantes
modifierDans le problème du chameau et des bananes, la solution précédente est optimale si , et le nombre maximum de paquets de bananes qui peuvent être transportées est , nombre compris entre 0 et 1. Cependant, si , alors la (n−1)-ème réserve est inutile, car elle serait au delà du marché. Dans ce cas, le nombre maximum de paquets transportables est , qui est entre 1 et 2. De même, si , les (n−2)-èmes et (n−1)-èmes réserves sont inutiles, et on peut tranporter , qui est entre 2 et 3, et ainsi de suite.
Dans le problème du groupe de voyageurs, les voyageurs partent de la base avec rations. Après unité de distance, ils ont consommé rations ; l'un des voyageurs retourne à la base avec ration, ce qui laisse au groupe rations. Le groupe avance encore de unité de distance, consommant rations ; un autre voyageur retourne alors à la base avec rations, ce qui laisse le groupe avec rations. Continuant cette stratégie, le groupe avance de et il ne reste qu'un voyageur, qui franchit une unité de distance supplémentaire ; au total, il aura pu atteindre un point situé à ; pour traverser unités de distance, il faudra donc au moins voyageurs.
La limitation précédente vient de la nécessité de la survie des voyageurs. Dans le problème de la flottille de véhicules, la possibilité de les sacrifier pour le bien commun permet d'atteindre une distance aussi grande que l'on veut : après unité de distance, le groupe a consommé 1 unité de carburant ; on refait le plein de véhicules et on en abandonne un, puis le groupe parcourt unité, et ainsi de suite ; finalement, un seul véhicule arrive à destination en ayant parcouru , une distance qui peut être aussi grande que l'on veut, mais au prix d'une flottille de taille exponentielle.
Indépendance de l'ordre des voyages
modifierDans la solution du problème de la jeep, la position des dépôts ne peut être améliorée, ni même modifiée, mais l'ordre des voyages pour les approvisionner est libre. Par exemple (dans le version d'exploration du désert), la jeep pourrait commencer par faire n − 1 aller-retours entre la base et le premier dépôt, y laissant unités de carburant à chaque fois, faire encore un voyage vers le premier dépôt, où elle trouvera disponible un total de , et recommencer en faisant à partir du premier dépôt n − 2 aller-retours vers le seconde dépôt (les étant laissés pour l'ultime retour vers la base) , etc.
Applications pratiques
modifierLe problème a connu une application pratique dans le contexte du bombardement du Japon durant la Seconde Guerre mondiale. Robert McNamara déclare dans le film The Fog of War que résoudre le problème de transport efficace du carburant (alors que la technique du ravitaillement en vol était encore expérimentale) est la raison pour laquelle les bombardements à partir de la Chine furent abandonnés en faveur de la stratégie de saut d'îles en îles dans le Pacifique.
Les mêmes stratégies furent utilisées durant la guerre des Malouines, au cours des opérations Black Buck.
Dans le livre de Terry Pratchett, Les Petits dieux, l'armée omnienne tente de même de transporter une réserve d'eau à travers un vaste désert, se heurtant au problème de la croissance rapide de la fonction exponentielle.
Références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Jeep problem » (voir la liste des auteurs).
- (en) Eric W. Weisstein, « Jeep Problem », sur MathWorld.
- Martin Gardner, My Best Mathematical and Logic Puzzles, Dover, , 53 (ISBN 0-486-28152-3, lire en ligne
).
- (en-US) « Puzzle 15 | (Camel and Banana Puzzle) », sur GeeksforGeeks, (consulté le ).
- (en) « Travelers across a desert », sur puzzling.stackexchange.com (consulté le ).
- (en)(en) « Cars Across the Desert Puzzle - Solution », sur www.mathsisfun.com (consulté le ).
- Il existe des variantes dans lesquelles x est une fraction de la forme k/p, avec p fixé ; voir Gunter Rote et Guochuan Zhang, (en) Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling, juin 1996.
- W. W. Rouse Ball et H.S.M. Coxeter, Mathematical Recreations and Essays, treizième édition (1987), Dover, p. 32. (ISBN 0-486-25357-0).