Re : Optimisation d'un enchainement de productions
Bonsoir à tous,
T'inquiète pas, tu as raison d'insister.
Moi aussi je vais insister une dernière fois car tu ne réponds pas à mes 2 questions :
1) sur l'amplitude des multiplicités de production des références? Leur somme peut monter jusqu'à combien?
2) le nombre de références est toujours de 4 ou il peut évoluer?
Maintenant, pour ton problème :
Tu ne cherches pas le plus court chemin mais plutôt le circuit hamiltonien le moins coûteux (problème du voyageur de commerce)
Même si ce problème a été très étudié, il devient vite retors avec des petites instances (quelques dizaines de références).
Le graphe dans lequel tu recherches ce circuit est issu du graphe complet de tes références (A, B, C et D) mais avec des répétitions de tes sommets à hauteur de la multiplicité de chaque référence.
Pour l'exemple que tu donnes avec 4*A, 3*B, 1*C et 2*D, ton graphe aura les sommets {A1, A2, A3, A4, B1, B2, B3, C, D1, D2}.
Ta matrice d'adjacence deviendra
et tu pourras lui faire subir les macros que les contributeurs te proposeront.
Tu remarqueras que j'ai ajouté des valeurs énormes aux intersections des Ai, Bi, C et Di avec eux-mêmes pour garantir l'alternance de références.
Ce nouveau graphe est ainsi devenu complet (tout sommet est connecté avec tout autre sommet).
Dans les graphes complets orientés à n sommets, il y a (n-1)! chemins hamiltoniens. Tu imagines ce que ça donne à partir d'une quinzaine de sommets......
Les algo exhaustifs comme celui que je t'ai proposé ne tiennent plus la route (d'où mes questions sur les multiplicités dans la vraie vie).
Il faut passer soit par des heuristiques, soit par un solveur.
Le solveur d'excel est limité à 200 variables et 100 contraintes. Donc tu peux l'oublier.
Je viens de tester avec le solveur GLPK et le résultat pour 10 références est obtenu en moins de 2 secondes.
Avec 16 références, il a fallu attendre 13 secondes.
Il y a donc de l'espoir si tes multiplicités restent raisonnables.
Je te laisse ingurgiter tout ça, mais sache qu'il est possible de piloter GLPK via VBA de façon à masquer toute la cuisine technique.
cordialement