www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - graphische verteilung von rechtecken
graphische verteilung von rechtecken < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

graphische verteilung von rechtecken: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
graphische verteilung von rechtecken: Lösung
Status: (Antwort) fertig Status 
Datum: 20:27 Mi 31.05.2006
Autor: bert2000

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

Bezug
        
Bezug
graphische verteilung von rechtecken: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:10 Di 22.06.2004
Autor: Marc

Hallo buschke,

[willkommenmr]

vielleicht hilft das weiter: []Parallele Diskussion, und falls nicht: Woher stammt deine Aufgabe und wie steht sie mit der dortigen Aufgabe in Verbindung?

Viele Grüße,
Marc

Bezug
                
Bezug
graphische verteilung von rechtecken: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
graphische verteilung von rechtecken: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 []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

Bezug
                                
Bezug
graphische verteilung von rechtecken: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
graphische verteilung von rechtecken: optimale Packungsdichte eines Rechtecks
Status: (Frage) beantwortet Status 
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.

Bezug
                
Bezug
graphische verteilung von rechtecken: optimale Packungsdichte eines Rechtecks
Status: (Antwort) fertig Status 
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



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de