Bin packing 2D [Résolu]

Signaler
Messages postés
3
Date d'inscription
jeudi 5 avril 2012
Statut
Membre
Dernière intervention
29 avril 2012
-
Messages postés
1
Date d'inscription
mercredi 28 février 2018
Statut
Membre
Dernière intervention
28 février 2018
-
Bonjour, j'aimerai obtenir un code VB sur le problème de bin packing 2 D. je travaille sur un projet de découpe à deux dimension. A partir de plaques mères de dimension 48x96 dm je dois répondre a une commande client: Client1: commande 8 plaques de 36x50 dm
client2: commande 13 plaques de 24x36 dm
client3: commande 5 plaques de 20x60 dm
client4: commande 15 plaques de 18x30 dm
la commande doit être satisfaite tout en minimisant le nombre de plaques mères utilisées et la chute de matière première. il faudrait d'une part énumérer les coupes de plan possibles( c'est à dire toutes les manières possibles que l'on peut découper les commandes des clients sur les plaques mères(les combinaisons possibles), c'est un de mes problèmes majeur). si je peux avoir un système d'énumération sur VB ca m'aiderai beaucoup car jeu pourrai traduire ce problème en programme linéaire en nombres entiers et a partir d'un solveur le tour est quasiment joué. je ne m'y connais pas en algorithmes, merci!

3 réponses

Messages postés
1
Date d'inscription
mercredi 7 mai 2008
Statut
Membre
Dernière intervention
9 juin 2012

salut, j'ai eu cet algorithme par l'intermédiaire d'un ami qui la trouver sur le net.
je crois qu'il traite ce problème.

L, H : les dimensions du grand rectangle
S : l’ensemble fini, désignant les n petites rectangles à découper à partir des grands rectangles
Exemple : S = {(l1,h1), (l2,h2) ,…,(li,hi)}
(li,hi) : les dimensions du ième petit rectangle à découper de l’ensemble S, avec li sa longueur et hi sa hauteur
P : désigne l’ensemble fini de vecteurs représentant les différents plans de coupes, tel que :
t = (t1,…,tn)élément de P avec ti le nombre de répétitions du ième petit rectangle à découper
P est une combinaison des longueurs des petits rectangles à découper, appartenant à l’ensemble S
Exemple : P = (l1,l2,…,li)

Q : combinaison des hauteurs des petites plaques à découper, appartenant à l’ensemble S
Exemple : Q = (h1,h2,…,hi)

(a, b) : la première découpe ainsi effectuée, le sous rectangle restant de la découpe du grand rectangle est associé les dimensions a et b, avec a désignant la longueur et b la hauteur

Pab : l’ensemble des points représentant la combinaison des longueurs des petits rectangles entrants dans le sous-rectangle de dimension (a, b) limités à la moitié de a.

Qab : l’ensemble des points représentant la combinaison des hauteurs des petits rectangles entrants dans le sous-rectangle de dimension (a, b) limités par b/2.

(a0, b0) : représente les dimensions du sous-rectangle issu de la découpe du sous-rectangle de dimensions (a, b) avec a0 désignant la longueur et b0 désignant la hauteur.

a0 = sup {x/x ≤ a, x élément de P} : x désigne la longueur d’un petit rectangle (à découper de la longueur a et a0 est choisit tel que a0 soit supérieur à x et x≤ a


b0 = sup {y/y ≤ b, y élément de Q} : y désigne la hauteur d’un petit rectangle à découper de la hauteur b et b0 est choisit tel que b0 soit supérieur à y et y≤ b

NB : x et y représentent les dimensions d’un petit rectangle à découper.
Sab : représente la surface du sous-rectangle de dimensions (a, b).

V : désigne la valeur de la meilleure solution en cours.
v0 : désigne la différence entre la valeur v et la surface d’un sous-rectangle.
S(a-c)b et Sa(b-d)) : désignent des surfaces

###########################Algorithme#############################
Entrées : L, H : les dimensions du rectangle initiale ;
n : le nombre des pièces à découper ;
(li, hi), 1≤ i≤n : les dimensions des pièces.
Sorties : la solution optimale notée par OPT.
1. Construire les ensembles P et Q ;
2. OPT = R(L, H, 0) ;
3. Fonction R(a, b, v0) : entier ;
Si v0 ≥ Sab alors sortir avec R = 0
Sinon
On pose a0 sup {x/x ≤ a, x élément de P} et b0 sup {y/y ≤ b, y élément de P}
Si la valeur de (a0, b0) est connue alors sortir avec cette valeur
Sinon
Calculer la meilleure découpe homogène h
Si elle est pleine alors sortir avec R = h
Sinon poser V = h
Pour chaque c élément de Pab
Calculer w1 = R (c, b, max (V, v0) – S(a-c)b)
Et V1 = w1 + R (a-c, b, max (V, v0) – w1)
Si V1 est pleine alors sortir avec R = V1
Sinon V = max (V, V1)
Pour tout d élément de Qab
Calculer w2 = R ( a, d, max (V, v0) - Sa(b-d))
Et V2 = w2 + R ( a, b-d, max (V,v0) – w2)
Si V2 est pleine alors sortir avec R = V2
Sinon V = max (V, V2).
Sortir (avec la meilleure solution).
Messages postés
1
Date d'inscription
mercredi 28 février 2018
Statut
Membre
Dernière intervention
28 février 2018

Bonjour,
slvp,vous pouvez m'expliquer comment calculer la meilleure découpe homogène h
Messages postés
18038
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
236
Bonjour,
je ne m'y connais pas en algorithmes

C'est-à-dire : sur ce qui, dans une telle affaire, est l'essentiel !
De toutes manières : voir ma réponse dans ton autre discussion :
[je ne m'y connais pas en algorithmes Tapez le texte de l'url ici.]
Alors :
car jeu pourrai traduire ce problème en programme linéaire en nombres entiers et a partir d'un solveur le tour est quasiment joué

Euh ... c'est bien vite dit ! Commence par y réfléchir et à le "sortir", cet algo-là

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement vous dire ce qu'elle contient. Je n'interviendrai qu'en cas de nécessité de développ

Mais si tu veux en faire un programme linéaire pour le solver d'Excel, ou tou autre version du solver, c'est la cocologie qui va te permettre de faire tes (in)équations, par la programmation.

Si tu veux passer par le solver, tu peux toujours aller fouiller par là, le père des solvers.