graphische verteilung von rechtecken < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:02 Di 22.06.2004 | | Autor: | buschke |
Aufgabenstellung:
gegeben sei ein Rechteck der Länge a und der Breite b. Ferner sind die Maße eines kleineren Rechtecks gegeben (Länge c, Breite d). Es soll nun bestimmt werden, wieviele kleine Rechtecke in das große Rechteck hineinpassen und wie diese liegen müssen, ohne sich zu überlappen.
Leider habe ich nicht viel Ahnung von graphischer Mathematik. Ich hoffe, mir kann jemand helfen.
vielen Dank,
buschke
|
|
| |
|
Hallo,
ich habe das Problem gelöst. Die Lösung findet Ihr unter:
http://rov.eding.de
Das Ergebnis wird berechnet und grafisch ausgegeben.
Gruß
Bert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:32 Mi 23.06.2004 | | Autor: | buschke |
Ja, meine Frage ist quasi genau das gleiche. Bei meiner Aufgabe geht es auch um Pakete, die auf eine Palette gestapelt werden sollen. den Lösungsansatz, der dort vorgeschlagen wird, hatte ich auch schon getestet. Beim Zeichnen verschiedener Paletten- und Paketgrößen habe ich allerdings festgestellt, daß es bessere Verteilungsmöglichkeiten gibt. Ich konnte diese Lösungen aber nur zeichnerisch lösen und habe dafür leider keine mathematische Lösung gefunden. bin mir aber sicher, daß es dafür eine geben müßte.
Ich hoffe, jemand hat noch eine Idee.
Danke, buschke
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:50 Mi 23.06.2004 | | Autor: | Marc |
Hallo buschke,
> Ja, meine Frage ist quasi genau das gleiche. Bei meiner
> Aufgabe geht es auch um Pakete, die auf eine Palette
> gestapelt werden sollen. den Lösungsansatz, der dort
> vorgeschlagen wird, hatte ich auch schon getestet. Beim
> Zeichnen verschiedener Paletten- und Paketgrößen habe ich
> allerdings festgestellt, daß es bessere
> Verteilungsmöglichkeiten gibt. Ich konnte diese Lösungen
> aber nur zeichnerisch lösen und habe dafür leider keine
> mathematische Lösung gefunden. bin mir aber sicher, daß es
> dafür eine geben müßte.
> Ich hoffe, jemand hat noch eine Idee.
Wie ich aus der Diskussion in dem anderen Forum gelesen habe, sind die kleineren Rechtecke ja alle verschieden groß, aber fest vorgegeben.
Ich fürchte, dieses (Optimierungs-) Problem läßt sich im wesentlichen nur durch Ausprobieren lösen, es ähnelt zudem sehr dem ![[]](/images/popup.gif) Rucksackproblem, welches leider NP-vollständig ist (im schlimmsten Fall müssen alle Möglichkeiten durchprobiert werden).
Anders sieht es vielleicht aus, wenn über die Größen der verschiedenen Pakete etwa im vorhinein bekannt wäre, z.B., dass es nur n verschiedene Größen [mm] $A_1,\ldots,A_n$ [/mm] gibt und dass [mm] $2*A_1=A2, 2*A_2=A_3, A_3=\ldots$ [/mm] (in der Art der DIN Ai-Serie) etc.
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:19 Mi 23.06.2004 | | Autor: | buschke |
hallo marc,
erst mal schönen dank.
Mein Problem ist doch etwas weniger kompliziert, aber ich habe es wohl etwas undeutlich beschrieben.
Die kleinen Pakete sind in meiner Aufgabe bei einer Berechnung alle gleich groß. Sie können nur von Berechnung zu Berechnung geändert werden.
z.B.:
1. Berechnung: Palette 1000x1200 und alle Pakete 120x140.
2. Berechnung: Palette 800x1400 und alle Pakete 70x100. usw.
wäre super, wenn du dazu auch einen Lösungsansatz parat hättest.
Danke,
buschke
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:30 Di 29.06.2004 | | Autor: | buschke |
Hallo,
ich möchte noch einmal mein Problem präzisieren:
Gegeben ist ein Rechteck(E*F). Dieses soll optimal mit kleineren Rechtecken (a*b) gefüllt werden. Alle kleinen Rechtecke sind gleich groß. Alle Längen (E, F, a, b) sind konstant und vorgegeben.
Gesucht ist eine allgemeine Lösung.
zur Erklärung:
Es soll ein Palettierprogramm entstehen, bei dem die Größe der Palette (E*F) und die Größe der zu palettierenden Kartons (a*b) eingegeben wird und die größtmögliche Anzahl an Kartons, die auf die Palette passen, berechnet wird.
momentane Lösung:
ich optimiere zunächst eine Seite des großen Rechtecks, durch x*a + y*b <= E und E-(x*a + y*b) -> 0.
Danach fülle ich die Kartons in dieser Lage in F-Richtung auf.
Leider kann ich die Berechnungsmethode nicht gleichzeitig für die F-Seite des großen Rechtecks verwenden, da sich die kleinen Rechtecke überschneiden würden.
es muß also eine bessere Lösung geben, die ich leider noch nicht gefunden habe. Ich hoffe, mir kann jemand helfen.
Vielen Dank
Ich habe diese Frage in keinem weiteren Forum gestellt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:46 Do 01.07.2004 | | Autor: | Marc |
Hallo buschke,
> Gegeben ist ein Rechteck(E*F). Dieses soll optimal mit
> kleineren Rechtecken (a*b) gefüllt werden. Alle kleinen
> Rechtecke sind gleich groß. Alle Längen (E, F, a, b) sind
> konstant und vorgegeben.
> Gesucht ist eine allgemeine Lösung.
>
> zur Erklärung:
> Es soll ein Palettierprogramm entstehen, bei dem die Größe
> der Palette (E*F) und die Größe der zu palettierenden
> Kartons (a*b) eingegeben wird und die größtmögliche Anzahl
> an Kartons, die auf die Palette passen, berechnet wird.
>
> momentane Lösung:
> ich optimiere zunächst eine Seite des großen Rechtecks,
> durch x*a + y*b <= E und E-(x*a + y*b) -> 0.
> Danach fülle ich die Kartons in dieser Lage in F-Richtung
> auf.
> Leider kann ich die Berechnungsmethode nicht gleichzeitig
> für die F-Seite des großen Rechtecks verwenden, da sich die
> kleinen Rechtecke überschneiden würden.
>
> es muß also eine bessere Lösung geben, die ich leider noch
> nicht gefunden habe. Ich hoffe, mir kann jemand helfen.
ich denke immer noch, dass die optimale Lösung im worst case nur durch Probieren aller Möglichkeiten gefunden werden kann; immerhin gibt es nur endlich viele Möglichkeiten 
In der Praxis befriedigende Lösungen werden aber schon Heuristiken liefern. Wenn ich dieses Programm schreiben müßte, würde ich wahrschlich mehrere Pack-Arten berechnen und dann die (jeweils) wählen, die den Platz am besten ausnutzt.
Eine schöne Heuristik ist dann beispielsweise deine oben vorgeschlagene:
Es sei [mm] $E\le [/mm] F$ und [mm] $a\le [/mm] b$.
Ich versuche zunächst, die Seite E (die kleinere der beiden!) optimal auszuschöpfen, also zwei natürliche Zahlen n und m zu finden, so dass
[mm] $E-(n*a+m*b)\to \min$
[/mm]
Entlang der Seite E liegen also n kleine Rechtecke quer und m kleine Rechtecke längs.
Jetzt gilt es, die Länge F aufzufüllen.
Man kann dort s Reihen kleine Rechtecke quer legen (das sind dann insgesamt n*s kleine Rechtecke) und
t Reihen kleine Rechtecke länge legen (das sind dann insgesamt m*t kleine Rechtecke).
Für jede Wahl von s, t entstehen zwei rechteckige Freiflächen (die Aufteilung ist nicht eindeutig, ich betrachte im Folgenden einfach alle möglichen Aufteilungen (über eine Schleife)).
Also schaue ich mir alle Paare von Zahlen (s,t) an (über eine Schleife), bilde die möglichen Teilrechtecke der Freifläche -- und wenn das Verfahren rekursiv auf die Teilrechtecke an, und diese Freiflächen wieder optimal zu füllen.
Ich denke, dass diese Heuristik eine gute Näherung der optimalen Lösung ist, und die Laufzeit dürfte auch akzeptabel sein, wenn man nicht gerade versucht, ein Fußballfeld mit Streicholzschachteln optimal zu bedecken.
Diese Holzhammer-Heuristik kann noch verbessert werden, wenn man etwas mehr über a und b wüßte, z.B., dass das kgV ihrer Millimeterzahlen recht klein ist.
Solange die Fälligkeit nicht abgelaufen ist, lasse ich die Frage noch offen, vielleicht fällt jemand anderem hier ja auch noch eine Lösung ein.
Viele Grüße,
Marc
|
|
|
|
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
