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 "Numerik linearer Gleichungssysteme" - Diskrete Lineare Optimierung
Diskrete Lineare Optimierung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Diskrete Lineare Optimierung: Aufstellen eines LKW-Problems.
Status: (Frage) beantwortet Status 
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!


        
Bezug
Diskrete Lineare Optimierung: Antwort
Status: (Antwort) fertig Status 
Datum: 17:17 Mi 28.07.2010
Autor: Al-Chwarizmi


> 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.
  


Bezug
                
Bezug
Diskrete Lineare Optimierung: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 08:08 Do 29.07.2010
Autor: tom20ked

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?

Bezug
                        
Bezug
Diskrete Lineare Optimierung: Antwort
Status: (Antwort) fertig Status 
Datum: 16:07 Do 29.07.2010
Autor: Al-Chwarizmi


> 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.



Bezug
                                
Bezug
Diskrete Lineare Optimierung: Vielen Dank
Status: (Mitteilung) Reaktion unnötig Status 
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!

Bezug
                                        
Bezug
Diskrete Lineare Optimierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:36 Fr 30.07.2010
Autor: Al-Chwarizmi


> 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.




Bezug
                        
Bezug
Diskrete Lineare Optimierung: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:20 Sa 31.07.2010
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                        
Bezug
Diskrete Lineare Optimierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:07 Sa 31.07.2010
Autor: Al-Chwarizmi

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]
Bezug
                                
Bezug
Diskrete Lineare Optimierung: Idee
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de