Hoi,
Ik wil een X-aantal rechthoeken (l x b) zodanig verdelen dat de totale oppervlakte(L x B) zo klein mogelijk is.
Er zijn 2 randvoorwaarden:
1) De totale oppervlak breedte(B) mag maximaal 3 meter zijn
en minimaal de grootst ingevoerde rechthoek breedte (b)
2) De totale oppervlak lengte (L) mag maximaal 15 meter zijn
en minimaal de grootst ingevoerde rechthoek lengte (l)
Note: Het X-aantal rechthoeken wordt willekeurig ingevoerd
Is hier een wiskundige berekening voor?
Alvast bedankt,
Gerben
2-d rechthoeken optimaal verdelen
Re: 2-d rechthoeken optimaal verdelen
Het is niet helemaal duidelijk wat je bedoelt.
- hebben je kleine rechthoeken geheeltallige lengte en breedte?
- hebben je kleine rechthoeken dezelfde of verschillende afmetingen?
Bijvoorbeeld:
Met kleine rechthoeken:
5x2
3x2
3x2
4x1
2x1
kan je een rechthoek met oppervlak 7x4 = 28 precies vullen, maar gegeven je begrenzingen 15x3 heeft de kleinste rechthoek die je nodig hebt om ze allemaal te plaatsen 10x3 = 30 eenheden.
Is dit ongeveer wat je bedoelt en heb je zelf ook een concreet voorbeeld?
- hebben je kleine rechthoeken geheeltallige lengte en breedte?
- hebben je kleine rechthoeken dezelfde of verschillende afmetingen?
Bijvoorbeeld:
Met kleine rechthoeken:
5x2
3x2
3x2
4x1
2x1
kan je een rechthoek met oppervlak 7x4 = 28 precies vullen, maar gegeven je begrenzingen 15x3 heeft de kleinste rechthoek die je nodig hebt om ze allemaal te plaatsen 10x3 = 30 eenheden.
Is dit ongeveer wat je bedoelt en heb je zelf ook een concreet voorbeeld?
Re: 2-d rechthoeken optimaal verdelen
Een bedrijf maakt panelen, deze panelen worden geperst en bestaan uit een aantal lagen verschillende materialen. De maximale maat van zo'n plaat is 14500 x 3950 mm en de minimale maat is 300 x 300 mm.
Omdat het persen van deze panelen vrij kostbaar is, bepaald men aan de hand van de bestelling hoe groot de geperste plaat moet worden om zo min mogelijk zaagverlies te hebben. Als de plaat is geperst, worden de panelen er als een puzzel op uitgetekend en vervolgens uitgezaagd. Het komt nogal eens voor dat men verkeerd puzzelt en dat de geperste plaat te klein of te groot is voor de bestelling(en). De bestelde panelen zijn altijd rechthoekig of vierkant, groter dan 300 x 300 mm maar maximaal 14500 x 3950 mm. Binnen deze maximale en minimale maat is de maat van elke rechthoek dus mogelijk in hele millimeters.
Ik wil de bestelling van de klant(en) invoeren in een programma (c#) dat ik hiervoor wil gaan maken, die berekend welke maat de plaat moet worden om zo min mogelijk zaagverlies te hebben en vervolgens de berekende volgorde van de panelen uittekent in AutoCAD.
Het is me al duidelijk geworden dat deze puzzel (lijkt een beetje op spelletje tetris) niet gemakkelijk is.
er kunnen maximaal 48 x 13 = 624 panelen van 300 x 300 mm op de maximale plaat, maar dit zijn panelen met allemaal de zelfde maat en dat is gemakkelijk te verdelen.
Het liefste wil men natuurlijk de maximale plaat benutten, maar vanwege levertijden moet men ook platen persen die kleiner zijn dan de maximale maat. Of de bestelling is zodanig dat er 3 maximale platen en 1 gedeeltelijk gevuld kan worden.
Stel dat er met 20 verschillende paneelmaten een minimale oppervlakte berekend moet worden, zijn dit er eigenlijk 40 omdat een rechthoek in 2 richtingen gelegd kan worden. behalve als de panelen vierkant zijn.
Ik heb het vermoeden dat ik de maten van de panelen in een array moet invoeren en met itereren de minimale oppervlakte moet bepalen. Het is een puzzel van 40 stukjes die iedere keer als de puzzel in een bepaalde volgorde is gelegd de oppervlakte onthouden wordt, met als criterium dat bij de volgende iteratie van 40 stukjes alleen de oppervlakte onthouden wordt die kleiner is dan de vorige. Dit kunnen dus heel veel mogelijkheden zijn, waarbij het ook nog mogelijk is dat na de 3e iteratie eigenlijk de laagste oppervlakte al is bepaald.
Ik hoop dat ik het zo duidelijk is.
Grtzzzz
Omdat het persen van deze panelen vrij kostbaar is, bepaald men aan de hand van de bestelling hoe groot de geperste plaat moet worden om zo min mogelijk zaagverlies te hebben. Als de plaat is geperst, worden de panelen er als een puzzel op uitgetekend en vervolgens uitgezaagd. Het komt nogal eens voor dat men verkeerd puzzelt en dat de geperste plaat te klein of te groot is voor de bestelling(en). De bestelde panelen zijn altijd rechthoekig of vierkant, groter dan 300 x 300 mm maar maximaal 14500 x 3950 mm. Binnen deze maximale en minimale maat is de maat van elke rechthoek dus mogelijk in hele millimeters.
Ik wil de bestelling van de klant(en) invoeren in een programma (c#) dat ik hiervoor wil gaan maken, die berekend welke maat de plaat moet worden om zo min mogelijk zaagverlies te hebben en vervolgens de berekende volgorde van de panelen uittekent in AutoCAD.
Het is me al duidelijk geworden dat deze puzzel (lijkt een beetje op spelletje tetris) niet gemakkelijk is.
er kunnen maximaal 48 x 13 = 624 panelen van 300 x 300 mm op de maximale plaat, maar dit zijn panelen met allemaal de zelfde maat en dat is gemakkelijk te verdelen.
Het liefste wil men natuurlijk de maximale plaat benutten, maar vanwege levertijden moet men ook platen persen die kleiner zijn dan de maximale maat. Of de bestelling is zodanig dat er 3 maximale platen en 1 gedeeltelijk gevuld kan worden.
Stel dat er met 20 verschillende paneelmaten een minimale oppervlakte berekend moet worden, zijn dit er eigenlijk 40 omdat een rechthoek in 2 richtingen gelegd kan worden. behalve als de panelen vierkant zijn.
Ik heb het vermoeden dat ik de maten van de panelen in een array moet invoeren en met itereren de minimale oppervlakte moet bepalen. Het is een puzzel van 40 stukjes die iedere keer als de puzzel in een bepaalde volgorde is gelegd de oppervlakte onthouden wordt, met als criterium dat bij de volgende iteratie van 40 stukjes alleen de oppervlakte onthouden wordt die kleiner is dan de vorige. Dit kunnen dus heel veel mogelijkheden zijn, waarbij het ook nog mogelijk is dat na de 3e iteratie eigenlijk de laagste oppervlakte al is bepaald.
Ik hoop dat ik het zo duidelijk is.
Grtzzzz
Re: 2-d rechthoeken optimaal verdelen
Dit is een 2D variant van het bin packing problem, zie bijvoorbeeld
http://en.wikipedia.org/wiki/Bin_packing_problem
De "objects of different volumes" zijn in jouw geval de panelen van verschillende afmetingen,
de "bins" zijn je platen die verzaagd gaan worden.
Je wilt je objects (=panelen) zodanig verdelen (=packen) over de bins (=platen) dat het aantal bins dat je nodig hebt zo laag mogelijk is.
Dit is een NP-hard probleem, dwz er bestaat geen algoritme dat binnen afzienbare tijd voor een enigszins gangbaar aantal objecten de optimale oplossing vindt (als je met brutekracht je platen in leesrichting zou vullen heb je met 20 panelen al 20!*2^20 ~= 2.55*10^24 mogelijkheden die je zou moeten nagaan, dit zal niet lukken).
Voor dergelijke problemen bestaan wel een groot aantal zoekmethoden die in redelijke tijd een redelijke benadering van de optimale oplossing kunnen geven.
Op de wiki site noemen ze al het first fit en best fit algoritme (voorafgegaan door sorteren van je panelen op grootte).
Mogelijk krijg je daar al goede resultaten mee.
Als je betere zoek-algoritmen wilt, dan zou je in eerste instantie eens kunnen kijken naar "tabu search" of "simulated annealing", die je relatief eenvoudig kunt implementeren en instellen.
Nog een stap geavanceerder zijn neurale netwerken en genetische algoritmen.
Maar ik zou beginnen met het meest eenvoudige, zoals het voorbeeld algoritme op de wiki pagina.
Kom je hiermee verder?
http://en.wikipedia.org/wiki/Bin_packing_problem
De "objects of different volumes" zijn in jouw geval de panelen van verschillende afmetingen,
de "bins" zijn je platen die verzaagd gaan worden.
Je wilt je objects (=panelen) zodanig verdelen (=packen) over de bins (=platen) dat het aantal bins dat je nodig hebt zo laag mogelijk is.
Dit is een NP-hard probleem, dwz er bestaat geen algoritme dat binnen afzienbare tijd voor een enigszins gangbaar aantal objecten de optimale oplossing vindt (als je met brutekracht je platen in leesrichting zou vullen heb je met 20 panelen al 20!*2^20 ~= 2.55*10^24 mogelijkheden die je zou moeten nagaan, dit zal niet lukken).
Voor dergelijke problemen bestaan wel een groot aantal zoekmethoden die in redelijke tijd een redelijke benadering van de optimale oplossing kunnen geven.
Op de wiki site noemen ze al het first fit en best fit algoritme (voorafgegaan door sorteren van je panelen op grootte).
Mogelijk krijg je daar al goede resultaten mee.
Als je betere zoek-algoritmen wilt, dan zou je in eerste instantie eens kunnen kijken naar "tabu search" of "simulated annealing", die je relatief eenvoudig kunt implementeren en instellen.
Nog een stap geavanceerder zijn neurale netwerken en genetische algoritmen.
Maar ik zou beginnen met het meest eenvoudige, zoals het voorbeeld algoritme op de wiki pagina.
Kom je hiermee verder?