Diskrete Lineare Optimierung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:28 Mi 28.07.2010 | | Autor: | tom20ked |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo Community,
Ich würde gerne auf einer Fläche der Länge B_LKW*L_LKW Schachteln lagern.
Die Schachteln sind alle rechteckig mit der Fläche B_S1*L_S1,B_S2*L_S2.
Es ist nicht dringend notwendig zu wissen wo welche Schachtel stehen muss, über die Anzahl sei nur Bekannt Anzahl(S1)=2*Anzahl(S2).
Beide Schachteln passen sowohl in der Länge als auch in der Breite auf den LKW, es gilt natürlich das Länge und Breite des LKW's nicht überschritten werden dürfen
Falls es die Sache vereinfacht, dürfen die Schachteln nur um 90° Gedreht werden.
Wie lauten meine Gleichungen?
Vielen Dank im Voraus!
|
|
| |
|
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Hallo Community,
>
> Ich würde gerne auf einer Fläche der Länge B_LKW*L_LKW
> Schachteln lagern.
> Die Schachteln sind alle rechteckig mit der Fläche
> B_S1*L_S1,B_S2*L_S2.
>
> Es ist nicht dringend notwendig zu wissen wo welche
> Schachtel stehen muss, über die Anzahl sei nur Bekannt
> Anzahl(S1)=2*Anzahl(S2).
> Beide Schachteln passen sowohl in der Länge als auch in
> der Breite auf den LKW, es gilt natürlich das Länge und
> Breite des LKW's nicht überschritten werden dürfen
> Falls es die Sache vereinfacht, dürfen die Schachteln nur
> um 90° Gedreht werden.
>
> Wie lauten meine Gleichungen?
>
> Vielen Dank im Voraus!
Hallo tom20ked,
ich vermute sehr, dass es für dieses trotz allem recht offen
gestellte Packungsproblem wohl überhaupt keine einfache
Lösungsformel gibt. Unter der zusätzlichen Nebenbedingung,
dass alle Längen- und Breitenmaße ganzzahlig sein sollen,
hätte man ein schwieriges zahlentheoretisches Problem.
Eine einfache notwendige Bedingung dafür, dass alle Schachteln
wirklich (ohne Stapeln) auf die LKW-Ladefläche passen, kann
man allerdings leicht aufstellen. Sie besteht darin, dass die
Gesamtgrundfläche aller Schachteln die Ladefläche nicht
übersteigen darf.
LG Al-Chw.
|
|
|
| |
|
Ich habe so etwas befürchtet, dachte aber das mit klassischer LOP also Simplexprogrammierung so etwas möglich wäre. Leider bin ich in Simplexprogrammierung nicht sehr fit.
Mein Chef meinte er hätte gerne ein Excel-Sheet mit dem er so was berechnen könnte.
Ich dachte sofort an Backtracking-Algorithmen, wie in der Diskreten Mathematik vorhanden, aber er dachte das ganze sollte mit LOP zu lösen sein
edit: Kann also weitergeben dass die Lösung per Simplexalgorithmen... zumindest nicht so trivial ist wie er dachte? oder gar unmöglich?
|
|
|
| |
|
> Ich habe so etwas befürchtet, dachte aber das mit
> klassischer LOP also Simplexprogrammierung so etwas
> möglich wäre. Leider bin ich in Simplexprogrammierung
> nicht sehr fit.
>
> Mein Chef meinte er hätte gerne ein Excel-Sheet mit dem er
> so was berechnen könnte.
>
> Ich dachte sofort an Backtracking-Algorithmen, wie in der
> Diskreten Mathematik vorhanden, aber er dachte das ganze
> sollte mit LOP zu lösen sein
>
> edit: Kann also weitergeben dass die Lösung per
> Simplexalgorithmen... zumindest nicht so trivial ist wie er
> dachte? oder gar unmöglich?
Hallo Tom,
ich habe nochmals im Netz über solche Packungsprobleme nach-
geschaut. Die Suche war relativ ernüchternd, denn offenbar ge-
hören derartige Packungsprobleme zu den "echt schwierigen" NP-
Problemen. Es kann also extrem schwierig sein, die absolut beste
Lösung zu finden. Für praktische Zwecke ist es aber oft schon
gut genug, nur in die Nähe der optimalen Lösung zu kommen.
Und sowas sollte sogar ohne Simplex etc. möglich sein. Wenn ich
mir das große Rechteck der LKW-Ladefläche (Länge L, Breite B) und
die darauf zu ladenden [mm] 2\,n [/mm] Rechtecke der Sorte [mm] S_1 [/mm] (mit den Sei-
tenlängen a,b) und die n Rechtecke der Sorte [mm] S_2 [/mm] (mit den Seiten-
längen c,d) vorstelle, so würde ich mir zunächst eine ziemlich
einfache Ladeordnung vorstellen, beispielsweise so, dass in den
hinteren Teil der Ladefläche einige Reihen der [mm] S_1- [/mm] Schachteln
kommen (entweder alle längs oder alle quer ausgerichtet) und in
den vorderen Teil alle n Schachteln der Sorte [mm] S_2, [/mm] ebenfalls entweder
alle längs oder alle quer hineingestellt.
Aus den einigen Möglichkeiten betr. Ausrichtung der Schachteln
kann man mit einem Programm die beste aussuchen lassen für
den Fall, dass sich die [mm] S_1- [/mm] Querreihen nicht mit den [mm] S_2- [/mm] Reihen
überschneiden sollen.
Im Allgemeinen bleibt dabei aber ein Gebiet zwischen den Reihen
übrig, in welches allenfalls noch ein paar Schachteln beider Sorten
passen würden. Beim praktischen Beladen würde diese Lücke mit
Hilfe der Intelligenz der Arbeiter noch ziemlich optimal gefüllt.
Vielleicht kann man dafür auch noch ein geeignetes Zusatzprogramm
entwerfen.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Fr 30.07.2010 | | Autor: | tom20ked |
Irgendwie dachte ich mir das schon.
Entweder ein Algorithmus der alle [mm] n!*6^n [/mm] Möglichkeiten der Beladung durchrechnet, oder etwas intelligentes das sofort Kisten stapelt... aber ohne Programmierung geht da wohl nix.
Dachte eigentlich ich könnte da ein Tableau malen, oder eine Excel Tabelle... aber hilft nix.
VIELEN VIELEN DANK TROTZDEM!
|
|
|
| |
|
> Irgendwie dachte ich mir das schon.
> Entweder ein Algorithmus der alle [mm]n!*6^n[/mm] Möglichkeiten
> der Beladung durchrechnet, oder etwas intelligentes das
> sofort Kisten stapelt... aber ohne Programmierung geht da
> wohl nix.
>
> Dachte eigentlich ich könnte da ein Tableau malen, oder
> eine Excel Tabelle... aber hilft nix.
>
> VIELEN VIELEN DANK TROTZDEM!
Hallo tom20ked,
ich würde da wohl ein Programm erstellen, welches zunächst
bestimmt, auf welche Weise die beiden Sorten Schachteln
ausgerichtet werden sollen und in einem zweiten Schritt die
Anzahl voller Reihen für jede Schachtelsorte berechnet. Dann
käme noch der Schritt des Ausfüllens der verbliebenen Lücke.
Ich denke mir, dass man die dazu notwendigen Rechnungen
auch in Excel realisieren könnte.
Eine weitere Möglichkeit wäre eine schrittweise Befüllung der
Ladefläche: wir bestimmen zuerst (wie oben) die Ausrichtung
der Schachteln. Dann fangen wir auf der Ladefläche oben
links mit den [mm] S_1- [/mm] Schachteln an (in jedem Schritt 2 Sück)
und unten rechts mit den [mm] S_2 [/mm] (eine Schachtel pro Schritt).
Dann wird systematisch zeilenweise (die [mm] S_1 [/mm] in jeder Zeile
von links nach rechts und die Zeilen dicht an dicht unterein-
ander, die [mm] S_2 [/mm] in jeder Zeile von rechts nach links und die
Zeilen übereinander) weiter beladen, solange sich keine der
jeweils eingeladenen Schachteln gegenseitig überschneiden.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:20 Sa 31.07.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Ich habe mich hingesetzt und für die schrittweise Beladung
(stets wieder zwei Pakete hinten und eines vorne einreihen,
wobei alle Pakete einer Sorte gleich orientiert sind) ein Pascal-
Programm geschrieben.
In der Realisation sieht das dann etwa so aus:
[Dateianhang nicht öffentlich] [Dateianhang nicht öffentlich]
Im letzten Bild sieht man natürlich deutlich, dass man noch
mehr Schachteln auf die Ladefläche bringen könnte, wenn
nicht verlangt würde, dass alle Schachteln einer Sorte gleich
ausgerichtet werden sollen.
Außerdem kann man (leider) feststellen, dass mein Programm
offenbar auch das Problem mit gleich ausgerichteten Schachteln
nicht vollständig löst: In der letzten Figur könnte man der obersten
Reihe des unteren Blocks noch eine große Schachtel anfügen
und unter die letzte (unvollständige) Reihe des oberen Blocks
noch eine weitere solche, ebenfalls aus zwei kleinen Schachteln,
anfügen ...
LG Al-Chw.
Dateianhänge:
Anhang Nr. 1 (Typ: unbekannt) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
Anhang Nr. 3 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:31 Di 03.08.2010 | | Autor: | tom20ked |
Meine Idee (noch nicht umgesetzt)
Den Container diskret aufteilen in Streifen der Breite [mm] l_i_max, [/mm] der maximalen Breite irgendeiner Schachtel.
Dann per Kopf eine Lösungsbasis finden, alle Kombinationen aus Boxen die in einen solchen Streifen passen. Eventuell diese Basis per Computerprogramm finden. Dann aus dieser Basis den Container optimal zusammensetzen. n Streifen mit diesen Teilen und m Streifen mit diesen Teilen etc.
Dadurch sollte ich eine optimale Lösung auf den Vorher erstellten Lösungsraum garantieren können.
MfG, tom
|
|
|
|
