Bin packing 2D
Résolu
lamoye
Messages postés
3
Date d'inscription
jeudi 5 avril 2012
Statut
Membre
Dernière intervention
29 avril 2012
-
29 avril 2012 à 21:18
mouniroir Messages postés 1 Date d'inscription mercredi 28 février 2018 Statut Membre Dernière intervention 28 février 2018 - 28 févr. 2018 à 20:16
mouniroir Messages postés 1 Date d'inscription mercredi 28 février 2018 Statut Membre Dernière intervention 28 février 2018 - 28 févr. 2018 à 20:16
A voir également:
- Bin packing excel
- Excel vba modulo - Forum Visual Basic
- Tan-1 excel - Forum C++ & C++ .NET
- Arctangente excel ✓ - Forum Visual Basic 6
- Excel gmao - Forum Visual Basic 6
- Vpm excel - Forum PHP
3 réponses
cs_lovekiss
Messages postés
1
Date d'inscription
mercredi 7 mai 2008
Statut
Membre
Dernière intervention
9 juin 2012
9 juin 2012 à 10:24
9 juin 2012 à 10:24
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).
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).
ucfoutu
Messages postés
18038
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
211
29 avril 2012 à 21:50
29 avril 2012 à 21:50
Bonjour,
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 :
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
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
Utilisateur anonyme
30 avril 2012 à 17:54
30 avril 2012 à 17:54
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.
Si tu veux passer par le solver, tu peux toujours aller fouiller par là, le père des solvers.
28 févr. 2018 à 20:16
slvp,vous pouvez m'expliquer comment calculer la meilleure découpe homogène h