Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Problème du voyageur de commerce



  1. #1
    naya76

    Problème du voyageur de commerce


    ------

    Bonjour à tous,

    J'essaie d'utiliser le solveur EXCEL pour résoudre un problème de voyageur de commerce. Mes données sont (distances entre chaque dépôt):

    Distance en miles GAAM AGMP AGM6 ASW
    GAAM 10000 3.31 2.72 5.63
    AGMP 3.31 10000 0.59 3.04
    AGM6 2.72 0.59 10000 3.43
    ASW 5.63 3.04 3.43 10000

    Je cherche donc à minimiser la distance totale de mon parcours.
    J'ai des variables binaires correspondants à mes différentes arretes,
    et 2 contraintes

    Distance en miles GAAM AGMP AGM6 ASW
    GAAM VARIABLES BINAIRES somme =1
    AGMP VARIABLES BINAIRES somme =1
    AGM6 VARIABLES BINAIRES somme =1
    ASW VARIABLES BINAIRES somme =1

    somme =1 somme =1 somme =1 somme =1

    Or je n'arrive pas à la bonne solution, peut-être ai-je oublié une contrainte ?

    Merci d'avance,

    Cordialement,

    -----

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    skydancer

    Re : Problème du voyageur de commerce

    Bonjour,
    Je crois qu'il y a un problème dans les contraintes.

    Si x(i,j) sont tes variables binaires, la première contrainte doit exprimer le fait qu'il y a, pour chaque noeud h du graphe, une arrête arrivant et repartant ayant la vamleur x(i,j) = 1 :

    somme( i<h ) x(i,h) + somme (j>h) x(h,j) = 2

    La deuxième contrainte est que la somme des variables binaires est inférieure ou égale à |V| - 1, puisque l'on recherche un chemin reliant tout les noeuds:

    somme( i,j ) x(i,j) <= nombre de nœuds - 1

  5. #3
    naya76

    Re : Problème du voyageur de commerce

    Bonjour Skydancer, merci de ta réponse.

    Pas de problème pour la deuxième contrainte.

    Par contre pour la première,

    Je ne vois pas comment entrer cela comme contrainte dans Excel... Aurais-tu une idée ?

    Merci d'avance,

  6. #4
    skydancer

    Re : Problème du voyageur de commerce

    Je suis vraiment désolé, je ne connais pas bien Excel et son solveur. je crois que mes compétences s'arrête malheureusement ici....

  7. A voir en vidéo sur Futura
  8. #5
    naya76

    Re : Problème du voyageur de commerce

    Merci Skydancer,

    J'ai trouvé une autre solution avec EXCEL sur un fichier que j'ai récupéré sur un forum.

    Bonne fin de journée,

Discussions similaires

  1. Bac pro commerce puis ecole de commerce international à l'étranger ?
    Par tibordo dans le forum Orientation après le BAC
    Réponses: 3
    Dernier message: 21/09/2009, 01h03
  2. probleme du voyageur de commerce
    Par boussoute dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 15/03/2009, 22h09
  3. voyageur de Langevin
    Par wildcat dans le forum Physique
    Réponses: 15
    Dernier message: 27/06/2008, 13h58
  4. Voyageur à l'étranger atteint par la typhoïde
    Par jaisalmer dans le forum Santé et médecine générale
    Réponses: 0
    Dernier message: 20/10/2006, 06h35
  5. Voyageur du présent ?
    Par jojo17 dans le forum Discussions scientifiques
    Réponses: 13
    Dernier message: 26/04/2006, 14h11