I. Trajets optimaux
|
Du lundi au vendredi, Jones fait de bon matin sa distribution de bouteilles de lait dans cinq quartiers différents de la grande banlieue londonienne. Selon les jours de la semaine,il dessert un quartier constitué de n2 blocs carrés, chacun de 100 mètres de côté, bordés par des rues perpendiculaires entre elles qui forment des quadrillages de dimension n x n avec n = 2,3,4,5 et 6 (voir schéma ci-dessus). En partant des points A,B,C,D et E, Jones dépose ses bouteilles devant chacune des quatre façades de chaque bloc d’immeubles avant de revenir à son point de départ.Comme Jones cherche à réduire la durée de ses tournées, calculer la distance totale minimale parcourue à la fin de la semaine.
|