Discussion :

[Pierre845]

Bonjour à tous,

J'ai un algo à faire sur de l'optimisation d'une liste de longueurs pour la production dans une usine et je me demandais si l'un d'entre vous avait une/des idées, des pistes, un conseil de fonction sous excel/VBA, ou autre ..

Le problème:

voici un exemple de liste:

[4200, 3900, 2620, 3620, 5200, 4250]
c'est des longueurs de barres.

hors le fournisseur ne vends que des barres de 7000. Vous voyez où je veux en venir ?

Le but est de trouver le nombre de barres de 7000 minimum à acheter pour faire toutes les longueurs de la liste.

Dans le cas présent, 5 barres sont à acheter, pour faire les longueurs:
1) 4200
2) 3900+2620 = 6520
3) 3620
4) 5200
5) 4250

Mais quelques fois les listes peuvent être plus longues, et les valeurs plus petites, autre exemple [5400, 1350, 1350, 600, 3200, 1200].

Vu le nombre de listes qu'il y a à traiter par jour il est nécessaire d'informatiser le processus.

J'ai commencé à faire un truc de malade, en testant 1er avec 2ème, 1er avec 3ème .. etc mais je me demande si y'a pas moins lourd; et en plus je ne suis même pas sûr que ce dans quoi je m'embarque aboutisse.

Merci pour votre éventuelle aide/conseils

[SeByDocKy]

Ton problème ressemble à un problème de MultiKnapsack 0-1.

[Pierre845]

Ton problème ressemble à un pb de MultiKnapsack 0-1.

ouaouuww

c'est ça que j'aime sur le forum Matlab.
j'ai toujours des réponses/pistes pointues.

bon c'est pas ça qui va me donner la solution, mais je connaissais pas, alors je m'en vais y jeter un oeil, merci.

[Pierre845]

Bon alors pour info, il s'agit du Cutting Stock Problem ..

http://en.wikipedia.org/wiki/Cutting_stock_problem


j'y travaille mais j'ai du mal niveau programmation à adapter l'exemple de wikipedia à mes barres

[SeByDocKy]

Bon alors pour info, il s'agit du Cutting Stock Problem ..

http://en.wikipedia.org/wiki/Cutting_stock_problem


j'y travaille mais j'ai du mal niveau programmation à adapter l'exemple de wikipedia à mes barres

Ok tu as trouvé ton bonheur ... En tout cas c'est un problème d'optimisation linéaire sous contraintes (d'inégalités linéaires) à variables entiières.

Il y a pleins de solvers disponibles pour Matlab pour ces genre de pb. Va dans FEX tu y trouvera ton bonheur :
mots-clefs : MILP


En voilà un par exemple :

http://www.dii.unisi.it/~hybrid/tool...s.html#glpkmex

[Pierre845]

okay, merci..