Problème du voyageur de commerce

[invite214ab636]

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,
-----

[invite79d10163]

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

[invite214ab636]

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,

[invite79d10163]

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....

[A voir en vidéo sur Futura]

[invite214ab636]

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,