Déterminer la solution optimale pour un réseau routier


  • M

    Bonjour, j'ai un problème avec un exercice de maths avec 2 questions que je n'arrive pas à résoudre.
    Voici l'énoncé :
    Un livreur d'une société de ventes à domicile doit, dans son après midi, charger son camion à l'entrepôt noté A, livrer cinq clients notés B,C,D,E et F, puis retourner à l'entrepôt. Le réseau routier tenant compte des sens de circulation, et les temps de parcours en minutes sont indiqués sur le graphe G ci-dessous.

    1. Donner la matrice M associée au graphe G (voir la photo)
      Ma réponse :
      0 0 0 0 1 0
      1 0 0 0 0 1
      0 1 0 1 0 1
      1 0 0 0 0 1
      0 0 0 1 0 0
      1 1 1 0 0 0

    2. On donne la matrice M6M^6M6(voir photo)
      On s'intéresse aux chemins partant de l'entrepôt A et se terminant en A.

    a) Combien existe-t-il de chemins de longueur 6 reliant A à A ?
    J'ai trouvé qu'il y en avait 8.

    b) Citer ces chemins
    Je n'en ai trouvé que 7:
    A-E-D-C-B-F-A
    A-E-D-F-B-F-A
    A-E-D-F-C-B-A
    A-E-D-c-D-F-A
    A-E-D-C-F-B-A
    A-E-D-F-C-D-A
    A-E-D-F-C-F-A. Pas moyen de trouver le dernière.

    c) Parmi ceux qui passent par tous les sommets du graphe, lequel minimise le temps de parcours ?
    Sur cette question j'ai aussi un problème. Je trouve 2 chemins qui ont la même durée :21 minutes.

    d) Quelle conséquence peut tirer le livreur du dernier résultat ?
    J'ai mis qu'il pouvait minimiser son temps de parcours tout en livrant tous ses clients.

    1. Au départ de sa tournée, le livreur a choisi de suivre l'itinéraire le plus rapide.
      Malheureusement, le client C était absent au passage du livreur, et celui-ci décide de terminer sa tournée par ce client. Indiquer quel est le chemin le plus rapide pour revenir à l'entrepôt A à partir de C. La réponse devra être justifiée.
      Ici j'ai utilisée l'Algorithme de Dijkstra et j'ai trouvé C-D-F-B-A pour un temps de 10 minutes.

    Voilà j'aimerais savoir si mes réponses sont bonnes et de l'aide pour les question 2)b) et 2)c).

    Merci d'avance !

    http://i50.tinypic.com/bdsljl.jpg

    http://i50.tinypic.com/wk6bu9.jpg


  • S

    Salut,

    Quid du chemin A E D A E D A ?

    "Sur cette question j'ai aussi un problème. Je trouve 2 chemins qui ont la même durée :21 minutes."

    À priori ce n'est pas un souci.

    Je réponds au reste plus tard.


  • S

    Tu n'as pas mis DC dans la matrice ?


  • M

    Bonjour, pour le chemin que tu m'as proposé, le problème c'est que je ne sais pas si j'ai le droit de passer par A avant d'y revenir à la fin. Je ne sais pas si c'est possible...

    Et pour le chemin qui minimise la durée du parcours, apparemment il n'y en a qu'un puisqu'il est écrit "lequel". Non ? Voilà pourquoi je ne sais pas si j'ai bon.

    Effectivement je n'avais pas mis DC, merci de me l'avoir fait remarquer !


  • S

    Si ce n'est pas précisé, ce n'est pas un souci. À priori la multiplication matricielle ne discrimine pas les chemins qui repassent par leur point de départ.

    Sinon je n'en trouve qu'un pour 21, tu peux expliciter tes résultats ?


  • M

    D'accord merci.

    Pour moi deux chemins sont égaux à 21 minutes :
    A-E-D-C-B-F-A
    et
    A-E-D-C-F-B-A.


  • S

    A-E-D-C-B-F-A mesure 21 ???


  • M

    Euh... En revérifiant non. Je ne sais pas ce que j'ai fait. Encore une erreur de ma part, encore merci de me l'avoir fait remarquer.


  • S

    😉


  • M

    Le reste est bon ? 😄


  • S

    Ça me paraît correct.


  • M

    Merci beaucoup. Bonne fin de soirée.


  • S

    De même.


Se connecter pour répondre