Bonjour, il me faut implementer sous vba la résolution d'un problème d'affectation d'entrepots avec un algo exhaustif.
La recherche exhaustive est la méthode la plus simple, mais aussi souvent la plus coûteuse, pour trouver la
ou les solutions optimales à un problème. Comme son nom l'indique, on va énumérer l'ensemble des solutions
possibles, les parcourir une à une et conserver celle qui retourne le meilleur résultat. Comme le nombre de
solutions possibles est ni, la recherche nit toujours. Toutefois, si l'on a N variables binaires, on aura à
énumérer 2N solutions possibles.
Voici l'enoncé : Le territoire de Lordaeron est relativement grand. Pour alimenter les diérentes cités en grain, il faut
construire des entrepôts. Sur le plan page précédente, les cités à approvisionner sont :
- La capitale, Lordaeron (qui a besoin de 500 unités de nourriture)
- La citadelle de Dalaran (besoin : 350 unités)
- La cité de Stratholme (besoin : 300 unités)
- La forteresse de Mardenholde (besoin : 400 unités)
- La forteresse de Durnholde (besoin : 350 unités)
- La cité de Caer Darrow (besoin : 250 unités)
Les entrepôts peuvent être placés à Brill, Hearthglen, Andorhal et Strahnbrad. Les coûts de constructions
associés sont respectivement de 200, 250, 300 et 350 pièces d'or. On suppose pour l'instant que les entrepôts
sont de capacité in nie. Les coûts de transports entre les lieux possibles pour les entrepôts et les cités à desservir
sont les suivants (en pièces d'or).
Brill Hearthglen Andorhal Strahnbrad
Lordaeron 100 200 250 350
Dalaran 500 450 350 250
Stratholme 125 75 125 300
Mardenholde 175 50 175 300
Durnholde 300 300 200 100
Caer Darrow 350 350 250 150
Votre travail, en tant que conseiller, est de trouver la manière optimale de placer les entrepôts, sachant qu'il
faut que tous les besoins soient satisfaits, et que le coût total doit être le plus petit possible. Où placez-vous les
entrepôts ?
Supposons maintenant que la capacité maximale des entrepôts soit nie, et que les quatres lieux possibles
puissent stocker 1200 unités de nourriture chaque. Où doit-on alors construire les entrepôts ? Que se passe-t-il
si la capacité maximale est de 800 ?
J'ai déjà reussi à résoudre le probleme en methode exacte et B&b avec l'excel solver.
je suis arrivé a l'implementation exhaustive je plante.
Voici le Pseudo code :
//m = nombre d'entrepôts, modèle = tableaux décrivants le PL
xmax = vecteur_nul(n)
ymax = vecteur_nul(m)
vmax = MAXINT
Pour i de 1 à 2n Faire
y = convertir_en_vecteur(i,m)
[x,val,état] = résoudrePL(modèle,y)
Si état == ok Alors
Si val < vmax Alors
vmax = val
xmax = x
ymax = y
Fin Si
Fin Si
Fin Pour
Voila vous trouverz comme piece jointe mon fichier excel avec les premieres étapes de mon algo en fait j'ai du mal avec la fonction résoudrePL(modele,y) vous me direz c la plus difficile lol.
Pour ceux qui peuvent m'aider merci d'avanc et pour les autres aussi
.
La recherche exhaustive est la méthode la plus simple, mais aussi souvent la plus coûteuse, pour trouver la
ou les solutions optimales à un problème. Comme son nom l'indique, on va énumérer l'ensemble des solutions
possibles, les parcourir une à une et conserver celle qui retourne le meilleur résultat. Comme le nombre de
solutions possibles est ni, la recherche nit toujours. Toutefois, si l'on a N variables binaires, on aura à
énumérer 2N solutions possibles.
Voici l'enoncé : Le territoire de Lordaeron est relativement grand. Pour alimenter les diérentes cités en grain, il faut
construire des entrepôts. Sur le plan page précédente, les cités à approvisionner sont :
- La capitale, Lordaeron (qui a besoin de 500 unités de nourriture)
- La citadelle de Dalaran (besoin : 350 unités)
- La cité de Stratholme (besoin : 300 unités)
- La forteresse de Mardenholde (besoin : 400 unités)
- La forteresse de Durnholde (besoin : 350 unités)
- La cité de Caer Darrow (besoin : 250 unités)
Les entrepôts peuvent être placés à Brill, Hearthglen, Andorhal et Strahnbrad. Les coûts de constructions
associés sont respectivement de 200, 250, 300 et 350 pièces d'or. On suppose pour l'instant que les entrepôts
sont de capacité in nie. Les coûts de transports entre les lieux possibles pour les entrepôts et les cités à desservir
sont les suivants (en pièces d'or).
Brill Hearthglen Andorhal Strahnbrad
Lordaeron 100 200 250 350
Dalaran 500 450 350 250
Stratholme 125 75 125 300
Mardenholde 175 50 175 300
Durnholde 300 300 200 100
Caer Darrow 350 350 250 150
Votre travail, en tant que conseiller, est de trouver la manière optimale de placer les entrepôts, sachant qu'il
faut que tous les besoins soient satisfaits, et que le coût total doit être le plus petit possible. Où placez-vous les
entrepôts ?
Supposons maintenant que la capacité maximale des entrepôts soit nie, et que les quatres lieux possibles
puissent stocker 1200 unités de nourriture chaque. Où doit-on alors construire les entrepôts ? Que se passe-t-il
si la capacité maximale est de 800 ?
J'ai déjà reussi à résoudre le probleme en methode exacte et B&b avec l'excel solver.
je suis arrivé a l'implementation exhaustive je plante.
Voici le Pseudo code :
//m = nombre d'entrepôts, modèle = tableaux décrivants le PL
xmax = vecteur_nul(n)
ymax = vecteur_nul(m)
vmax = MAXINT
Pour i de 1 à 2n Faire
y = convertir_en_vecteur(i,m)
[x,val,état] = résoudrePL(modèle,y)
Si état == ok Alors
Si val < vmax Alors
vmax = val
xmax = x
ymax = y
Fin Si
Fin Si
Fin Pour
Voila vous trouverz comme piece jointe mon fichier excel avec les premieres étapes de mon algo en fait j'ai du mal avec la fonction résoudrePL(modele,y) vous me direz c la plus difficile lol.
Pour ceux qui peuvent m'aider merci d'avanc et pour les autres aussi
.
