Bin packing 2D [Résolu]

lamoye 3 Messages postés jeudi 5 avril 2012Date d'inscription 29 avril 2012 Dernière intervention - 29 avril 2012 à 21:18 - Dernière réponse : mouniroir 1 Messages postés mercredi 28 février 2018Date d'inscription 28 février 2018 Dernière intervention
- 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

4 réponses

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

Merci cs_lovekiss 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 75 internautes ce mois-ci

mouniroir 1 Messages postés mercredi 28 février 2018Date d'inscription 28 février 2018 Dernière intervention - 28 févr. 2018 à 20:16
Bonjour,
slvp,vous pouvez m'expliquer comment calculer la meilleure découpe homogène h
Commenter la réponse de cs_lovekiss
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionContributeurStatut 11 avril 2018 Dernière intervention - 29 avril 2012 à 21:50
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
Utilisateur anonyme - 30 avril 2012 à 17:54
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.