Problème
Cette année, Denis va passer une semaine au ski à la station EuroNeige. Il voudrait optimiser son temps sur les skis et il se pose la question : quel est le temps minimum pour réussir à faire toutes les pistes en comptant également le temps passé dans les remontées mécaniques ?
Le tableau ci-dessous donne la liste des pistes ainsi que le temps de descente pour chacune de ces pistes :
Et le tableau suivant donne les différentes remontées mécaniques avec le temps de montée :
Vous devez donner le temps total pour descendre ces 9 pistes ainsi que le programme que doit suivre Denis.
Exemple : A, 7, A, 1, etc. signifie que Denis commence par remonter avec le télésiège A, puis descend la piste 7, remonter avec le télésiège A, descend la piste 1, etc.
Résolution
Il y a évidemment plusieurs solutions équivalentes car les pistes peuvent être descendues dans des ordres différents mais avec un temps total identique.
Nous allons chercher à déterminer le temps minimum nécessaire. Tout d’abord, comme Denis doit descendre les 9 pistes, ce temps minimum inclut nécessairement la somme des temps de descente des 9 pistes soit 114 minutes.
En ce qui concerne les remontées mécaniques, étant donné que 2 pistes démarrent en haut du télécabine C, il faudra forcément l’emprunter 2 fois. De la même manière, il est nécessaire d’emprunter 2 fois le télésiège B. A l’arrivée du télésiège D, il y a les 3 pistes 2, 4 et 5 qui démarrent et la piste 9 qui arrive. Il est donc possible d’arriver par la piste 9 et d’enchainer par l’une des autres 3 pistes. Ainsi, seules 2 remontées par le télésiège D sont nécessaires. Enfin, à la station intermédiaire entre les télésièges A et B, les pistes 2, 3 et 6 arrivent et seules les 2 pistes 1 et 7 repartent. Pris isolément, cela pourrait dire qu’il n’est pas nécessaire de prendre le télésiège A mais étant donné que le télésiège B doit être emprunter 2 fois, cela nécessite donc que le télésiège A doit être emprunter au moins une fois (= nombre de montées du télésiège B – nombre de pistes qui arrivent + nombre de pistes qui repartent). Au total, cela fait donc un temps minimum de montée de 102 minutes.
Pour finir, en additionnant les temps minima de descente et de montée, nous obtenons 216 minutes. Nous avons prouvé qu’il n’est pas possible de trouver une solution inférieure à 216 minutes. Il s’agit d’une borne minimum de ce problème d’optimisation.
Le programme ci-dessous permet d’obtenir 216 minutes. Nous savons donc qu’il n’est pas possible de trouver mieux.
