Algorithmus zur Schnittoptimierung
-
Hallo zusammen,
ich habe vor, ein kleines Programmchen zur Optimierung des Zuschnitts von Metallprofilen zu erstellen.
Beispiel:
Vom Profil RR 60x40x3 benötige ich 15 Längen a 1,53m , 3 Längen a 2,55m
Vom Profil IPE 180 benötige ich 34 Längen a 1,2m , 31 Längen a 0,8m
...usw.
In welcher Reihenfolge, muss man nun die einzelnen Längen beim Schneiden anordnen, dass möglichst wenig Verschnitt entsteht wenn die Stangen standartmäßig bei RR 6m und bei IPE 12m lang sind?
Problem:
Kennt jemand ein Algorithmus der dieses löst, oder hat jemand einen Ansatz. Im Netz habe ich dazu etwas vom Guillotine-Algorithmus gelesen. Leider habe nichts gefunden wie er funktioniert, bzw. auf welchem Grundgedanke er beruht. Hat jemand einen Ansatz für mich?Danke im Vorraus
-
Hallo
Klingt für mich wie nach dem Problem des Handlungsreisenden, oder etwas ähnlichem.
bis bald
akari
-
Möchtest du ins Mathe-Forum oder nach Rund um die Programmierung verschoben werden?
-
-
Das Problem des Handlusngsreisenden trifft die ganze Sache meiner Meinung nach nicht. Dieser Algorithmus wird in der Technik eher verwendet, um die Verfahrwege eines Fräsers zu optimieren oder wenn man z.B. 100 Löcher mit bestimmten Koordinaten in ein Blech bohren will und dabei den geringsten Verfahrweg sucht. Wüsste nicht, wie ich das auf mein Problem anwenden sollte.
Das Rucksackproblem ist so eine Sache, hatte das ja auch schon gelesen aber es trifft es glaub ich nicht ganz, weil das Rucksackproblem berechnet, wie man einen Rucksack begrenzter Tragfähigkeit am günstigsten packt. Mein Problem ist jedoch, dass es nicht über den Rucksack hinausschaut. Angewandt auf mein Problem, hieße das ,das der Rechner die Optimalen Längen in eine Stange packt, so dass wenig Verschnitt übrig bleibt. Dies könnte er bei der nächsten Stange wiederholen bis er keine Längen mehr im Container hat. Aber garantiert mir das die optimale Lösung? Und warum arbeiten die meisten handelsüblichen Programme mit dem Guillotine-Algorithmus (was immer das genau sein mag). Hat jemand davon schon mal was gehört?@Jansen
Weiß nit ob ich im Matheforum besser aufgehoben bin. Thematisch sicherlich, aber ist das auch so gut besucht? Entscheide du das, kannst das sicherlich besser einschätzen, wo ich höhere Chancen auf die Lösung meines Problems hab.Gruß Sebastian
-
Du kannst auch kg wegstreichen und dafür m hinschreiben.
Beim Rucksackproblem ist es das Gewicht und bei dir halt die Länge.
Das ist der einzigste Unterschied.
-
Dieser Thread wurde von Moderator/in Jansen aus dem Forum VCL (C++ Builder) in das Forum Mathematik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Ist das nicht eher BIN-PACKING? Er muß die abzusägenden Stangen in möglichst wenige lange Stangen (die Bins) verpacken. Das Problem ist NP-vollständig, es lässt sich also vermutlich nicht schnell exakt lösen. Es gibt aber Approximationsalgorithmen, denen Du angeben kannst wie weit du maximal von der optimalen Lösung weg sein magst. Je genauer desto größer die Laufzeit. Vielleicht reicht dir ja eine Lösung, die bis auf 5% optimal ist oder so.
-
http://de.wikipedia.org/wiki/Zuschnittsproblem triffts glaub ich ganz gut...
-
D-U-D-E schrieb:
http://de.wikipedia.org/wiki/Zuschnittsproblem triffts glaub ich ganz gut...
Das ist doch das Bin-Packing.
-
Hallo,
kennt Jemand (gute) Open Source implementierungen von einem der beschriebenen Alghortihmen im Wiki-Artikel? Wo könnte ich sowas überhaupt finden abseits von Google?
-
Such mal nach Nemhauser-Ullmann. Oder schreibs dir in fünf Minuten selbst.
-
Im prinzip lässt sich das doch auch als ganzzahlig lineares Optimierungsproblem (linear integer programming) formulieren. Wikipedia hat 'ne Liste für Optimierungssoftware