Bin packing 2D [Résolu]

Messages postés
3
Date d'inscription
jeudi 5 avril 2012
Dernière intervention
29 avril 2012
- - Dernière réponse : mouniroir
Messages postés
1
Date d'inscription
mercredi 28 février 2018
Dernière intervention
28 février 2018
- 28 févr. 2018 à 20:16
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!
Afficher la suite 

Votre réponse

3 réponses

Meilleure réponse
Messages postés
1
Date d'inscription
mercredi 7 mai 2008
Dernière intervention
9 juin 2012
3
Merci
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).

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources a aidé 106 internautes ce mois-ci

mouniroir
Messages postés
1
Date d'inscription
mercredi 28 février 2018
Dernière intervention
28 février 2018
-
Bonjour,
slvp,vous pouvez m'expliquer comment calculer la meilleure découpe homogène h
Commenter la réponse de cs_lovekiss
Messages postés
18039
Date d'inscription
lundi 7 décembre 2009
Statut
Contributeur
Dernière intervention
11 avril 2018
0
Merci
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
Commenter la réponse de ucfoutu
0
Merci
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.
Commenter la réponse de Utilisateur anonyme

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.