La traversée de la jungle

[raptor77]

Bonjour. Trois explorateurs sont dans leur camp de base. Ils disposent de rations alimentaires individuelles journalières sous forme de sacs hermétiques. Ils décident d’aller photographier un site archéologique situé en pleine jungle à 7 jours de marche de leur camp de base. La durée de l’expédition ne doit pas dépasser 14 jours. Un seul d’entre eux ira jusqu’au bout faire les photographies. Ils peuvent éventuellement déposer les rations aux points prévus pour les bivouacs. Chacun d’eux ne peut porter à la fois plus de 8 rations alimentaires. Lorsqu’ils se trouvent au camp de base, ils n’utilisent pas leurs rations.

Combien de rations au minimum doivent-ils dépenser pour revenir dans une forme normale au camp de base après avoir mangé à leur faim.

Combien de rations supplémentaires faut-il prévoir si le site se trouve non pas à 7 mais à 8 jours du camp de base ?

Merci d'avance pour vos solutions.
Raptor :ptdr: :ptdr: :ptdr:

[raptor77]

ca fait plus d'une journée que j'attens une réponse :cry:

[Flodelarab]

Et t'a pensé a prendre ta ration alimentaire individuelle journalière ?

[Flodelarab]

Moi je pense que 32 rations collent pile poil pour 7 jours.
pour 8, voir avec mon avocat.

[musichien]

"Un seul d’entre eux ira jusqu’au bout faire les photographies."
Je comprends pas bien cette condition... si de toutes façons il n'y en a qu'un qui va au bout, pourquoi les autres l'accompagnent? Tu veux dire qu'ils vont marcher, déposer les rations au bivouac, aller en rechercher, puis... etc?
(je pense que c'est ça, je vais partir de ce point là)

[BancH]

Moi je pense que 32 rations collent pile poil pour 7 jours.
pour 8, voir avec mon avocat.

Moi j'ai 30 rations, et sans utiliser les bivouacs.

[raptor77]

et pour 8 jours?

[Flodelarab]

avec 30 rations, g les photos mais un des gars creve sur place.
Bof, on est dans les quotas.... c bon...

[BancH]

Pour les 30 rations j'ai fait :

J0 départ du camp de a et de b qui ont pris respectvement 8 et 6 rations.
J2 b donne 2 rations à a qui continue sa route alors que b retourne au camp
J4 arrivée de b au camp
J6 second départ de b avec 8 rations
J7 a arrive sur le site et prend les photos
J8 a fait demi-tour
J10 rencontre de a et de b, qui donne 2 rations suplémentaires à a
J11 a et b retournent au camp ensemble - départ de c du camp avec 8 rations
J12 les trois protagonistes se rencontrent, c file 2 rations aux deux autres, ils repartent tous vers le camp
J14 a, b et c arrivent au camp en pleine forme et en ayant utilisé 30 rations

[Flodelarab]

:++: welldone boy!

[buzard]

Bonjour,

Pour le spot à 7 jours de marche, j'ai une solution à 22. (ha ha une vrai pince celui qui gère le budget :we: ). C'est le mieux qu'on puisse faire en 14 jours.

Code: Tout sélectionner

  :                                                                           
 0:[3,22][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ]
  :      3,22                                                                 
-------------------------------------------------------------------------------
  :      1, 1                                                                 
 1:[ ,  ][3,19][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ]
  :                2,16                                                       
-------------------------------------------------------------------------------
  :                                                                           
 2:[1,  ][ , 2][2,14][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ]
  :                          2,12                                             
-------------------------------------------------------------------------------
  :                          1, 1                                             
 3:[1,  ][ , 2][ , 2][2,10][ ,  ][ ,  ][ ,  ][ ,  ]
  :                                    1, 8                                   
-------------------------------------------------------------------------------
  :                1, 1                                                       
 4:[1,  ][ , 2][1, 2][ , 1][1, 7][ ,  ][ ,  ][ ,  ]
  :                                              1, 7                         
-------------------------------------------------------------------------------
  :      1, 1                                                                 
 5:[1,  ][1, 2][ , 1][ , 1][ ,  ][1, 6][ ,  ][ ,  ]
  :                                                        1, 6               
-------------------------------------------------------------------------------
  :                                                                           
 6:[2,  ][ , 1][ , 1][ , 1][ ,  ][ ,  ][1, 5][ ,  ]
  :                                                                  1, 2     
-------------------------------------------------------------------------------
  :                                                                  1, 1     
 7:[2,  ][ , 1][ , 1][ , 1][ ,  ][ ,  ][ , 3][1, 1]
  :                                                                           
-------------------------------------------------------------------------------
  :                                                        1, 3               
 8:[2,  ][ , 1][ , 1][ , 1][ ,  ][ ,  ][1, 3][ ,  ]
  :                                                                           
-------------------------------------------------------------------------------
  :                                              1, 2                         
 9:[2,  ][ , 1][ , 1][ , 1][ ,  ][1, 2][ ,  ][ ,  ]
  :                                                                           
-------------------------------------------------------------------------------
  :                                    1, 1                                   
10:[2,  ][ , 1][ , 1][ , 1][1, 1][ ,  ][ ,  ][ ,  ]
  :                                                                           
-------------------------------------------------------------------------------
  :                          1, 1                                             
11:[2,  ][ , 1][ , 1][1, 1][ ,  ][ ,  ][ ,  ][ ,  ]
  :                                                                           
-------------------------------------------------------------------------------
  :                1, 1                                                       
12:[2,  ][ , 1][1, 1][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ]
  :                                                                           
-------------------------------------------------------------------------------
  :      1, 1                                                                 
13:[2,  ][1, 1][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ][ ,  ]
  :                                                                           
-------------------------------------------------------------------------------
  :
14:[3,  ][ |  ][ |  ][ |  ][ |  ][ |  ][ |  ][ |  ]
  :


un peu lourd je sais, mais c'étais surtout pour vérifier simplement si ça marche bien.

Pour le spot à 8 jours de marche j'ai un minimum à 32 (pour 16 jours au total). Je ne met pas le résultat, car c'est un peut encombrant, mais le principe est le même que pour n=7.

Ce genre de problème est un excelent moyen de s'entrainer à la programmation linéaire, pour ceux qui veulent faire des études supérieur en mathématique (ou dans l'ingiéneurie). ça peut leur servir de modéliser le problème avec un programme linéaire (ici en nombre entier). C'est d'ailleur avec cette outil mathématique (ainsi qu'un ordinateur) que j'ai obtenu ces résultats.

[raptor77]

Il faut réfléchir avec sa tête et non avec un ordinateur. Que feras-tu le jour où y'aura plus d'ordinateur?

[buzard]

Il faut réfléchir avec sa tête et non avec un ordinateur. Que feras-tu le jour où y'aura plus d'ordinateur?

L'ordinateur ne réflechit pas, il ne fait qu'executer le programme qu'on lui à ecrit en mémoire. Donc si le raisonnement initiale est faux, la réponse le sera sûrment aussi.

Par contre je ne voit pas ce que tu reproche aux ordinateurs, est surtout à ce qui s'en serve (à tort ou à raison d'ailleur, là n'est pas le problème)

C'est l'aboutissement de l'outils, une extension parfaite (dans le sens de finie ou achevée) et rationnelle de l'esprit humain. qui ne sert qu'à executer les tâches répététives. Je me voit mal appliquer à la main une résolution d'un PLNE (programme linéaire en nombre entier), surtout quand il y a plus de 10 variable, déjà ça serais un gâchis de feuilles blanche (et donc d'arbre qui ont servit à les faire), et le risque de se tromper est trop grand.

De nombreuses questions mathématiques seraient encore en suspens sans l'informatique, comme certains résultat de la théorie des nombre ou de la théorie de graphes. Mais surtout, les classifications dans la théorie des groupes serait simplement impossible à mener à terme.

Sans l'ordinateur, on roulerait tous en ford T1 (la première ford) ou en trabant (la version communiste). Personne ne serait allé sur la lune, les satélites seraient inutiles. Tout un pan de la physique théorique (la théorie quantique) nous serait totallement inaccéssible.

Et j'en passe ....

Je vois mal aussi, les comptables du tresor publique, dactylographier les 20 à 30 millions feuilles d'imposition. Ou encore une secraitaire quelconque ce farcier les centaines, de fiches de paie des employés de la boite.

Certe cela ne répond pas à la question que feras-t-on si il n'y a plus d'ordinateur? Mais montre déjà son incontournable nécéssité. Pour répondre à ta question, j'opposerais donc ce petit exemple :
on ne pourras plus participer à ce forum mathématique. Ou alors à une version par correspondance, t'envoie tes réponses par la poste, y'a un gentil gas qui fais des photocopies. Et régulièrement (hebdomadaire ou mensuelle) tu recoit tes 20 kilos de feuilles, plein de photocopie des intervention des membres.
outre l'aspect non écologique, tu sera confronté à la dure réalité d'une attente indéfini que quelqu'un veuille bien remarquer ta contribution.

donc oui à l'ordinateur, et si t'es pas content, pourquoi l'utiliser pour participer à ce forum?

[raptor77]

Je n'est pas dis que j'étais contre l'ordinateur ou quelque chose comme ca.Je te dis juste qu'il faut utiliser pour ce genre de problèmes mathématique son cerveau a la place d'un ordi, c'est beaucoup plus ludique et au moins ca nous entraîne.
Tu as sur-interprêté mes phrases, moi aussi je reconnais l'aspect très positif de l'ordinateur.

[buzard]

Le faite même de modéliser le problème en un programme linéaire, est un excercice assez difficile à réaliser. ensuite savoir ce servir des outils qui permette d'obtenir un résultat meilleurs, n'est pas une tarre à ce que je sache. Tu ne reproche pas à un charpentier d'utiliser des clous et un marteau pour faire une charpente. Pourquoi reproche tu à un mathématicien de se servir d'une calculatrice (bon une grosse calculette c'est vrai, mais ...), pour résoudre un problème?

Encore une fois, ce n'est pas la calculette qui réfléchit, elle ne fait que les calculs. Tout le travail qui à été fournis derrière n'apparait peut-etre pas, mais il est bien présent, j'ai passer une bonne heure à modéliser le problème, et à le réglé (faire les bonnes relaxation de contraintes) pour obtenir en 5 petite minutes de calcul les résultats pour n=7 et n=8.
Et dans la lancée je peut même répondre au cas n=9, (là c'est vrai je ne suis pas sûre de l'optimalité, car mon PC n'etant pas assez puissant je ne l'ai pas laissé finir les calculs).
Au delà , mon PC rame beacoup trop (plus de 1500 variables dans le primal et 1500 dans le dual, ça demande des ressources)

C'est vrai, j'aurais pu chercher une heuristique, mais son efficacité aurait-été plus que douteuse. Tu peut d'ailleurs constater toi même la différence entre les solutions trouvé à la main (~30) et la solution fournis par une résolution méthodique (22).

Pour info, parce qu'il y a peut-etre des intérêssés, il existe des langages de modélisation assez puissant pour résoudre ce genre de problème orienté vers la résolution (comme GNU MathProg qui est un sous ensemble du langage AMPL) et que dans ce language une modélisation de ce problème est :

[PHP]# a journey in jungle
########################################
# Parameters
########################################
param n integer > 0;
/* The distance in day of the goal */

param m integer > 0;
/* The number of people in the expedition */

param c integer > 0;
/* The capacity of nutrient transport of each people */

set S := 0 .. n;
set S1 := 1 .. n;
/* set of steps, 0 is base camp */

param last integer > 0;
/* maximum number of day allowed */

set D := 0 .. last;
set D1 := 1 .. last;
set D2 := 2 .. last;
/* set of days here majored by 3n */

set Lu := setof{i in S1}(i-1, i );
set Ln := setof{i in S }(i , i );
set Ld := setof{i in S1}(i , i-1);
set L within S cross S := Ld union Ln union Lu;
/* set of links between steps */

param cost{(i,j) in L} := if (i==0 and j==0) then 0 else 1;

########################################
# Variables
########################################
var x {D, S} integer >= 0;
/* number of people a day at a step */

var s {D, S} integer >= 0;
/* quantity of stocks a day at a step */

var y {D, L} integer >= 0;
/* number of people moving on a link */

var t {D, L} integer >= 0;
/* quantity of nutrient transported on a link */

########################################
# Objective
########################################
minimize needs : s[0,0];
/* total amount of nutrient stock needed at start for the trip */

########################################
# Subject to
########################################
/* initial and final state */
ppl_0 : x[0, 0] = m;
ppl_i {i in S1} : x[0, i] = 0;
stk_i {i in S1} : s[0, i] = 0;

ppl_n : x[last, 0] = m;
test : s[0, 0] = 1;

/* nutrient transport limits */
trs {d in D, (i,j) in L : ij} : t[d, i, j] <= c * y[d, i, j];
eat {d in D, (i,j) in L} : cost[i, j] * y[d, i, j] <= t[d, i, j];

########################################
# Data
########################################
data;
param n := 7;
param last := 14;
param m := 3;
param c := 8;
end;[/PHP]

Moi je trouve ça réconfortant que de tels langages existent, ça serait mieux si ils servaient à réduire la faim dans le monde, ou à mieux distribuer les richesses. Mais ce n'est pas la faute à impossible, c'est plutôt que l'avarice et la cruauté sont des caractères innés chez l'homme occidental.

*Edit d'Igor: remarque raciste supprimée. Si tu recommences tu es banni.*