WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Optimierungsproblem

 

derEchteNoob
Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 22.07.2021, 08:46     Titel: Optimierungsproblem
  Antworten mit Zitat      
Hallo zusammen,

ich bräuchte dringende Hilfe bei einem Optimierungsproblem.

Kurzfassung: es geht um eine zweidimensionale Fläche, welche einen Raum von der Seitenansicht aus darstellen soll.

In diesem Raum gibt es verstellbare Flächen, worauf bestimmte Güter platziert werden sollen. (Im Prinzip wie ein Regal mit verstellbaren/ neigbaren Flächen)

Das System soll je nach dem, welche 8 Produkte man aus einer Produktpalette von ca. 14 Produkten vorher auswählt, eine optimierte Positionierung der Produkte vorgeben.


Ich hoffe, dass das Problem verständlich geschildert wurde.

Ich würde mich sehr über jegliche Art von Hilfe freuen, auch wenn es nur ein Denkanstoß sein sollte, da ich momentan nicht genau weiß, in welche Richtung das geht.


VG,

M.
_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen


Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 22.07.2021, 09:25     Titel:
  Antworten mit Zitat      
Hallo,

zunächst musst du das ganze etwas konkretisieren:
1. Was kannst du beeinflussen? Ich könnte mir z.B. vorstellen, die (x,y)-Koordinaten der linken unteren Ecke eines Produkts.
2. Welche Nebenbedingungen müssen (in Abhängigkeit von 1.) erfüllt sein? Müssen Produkte beispielsweise eine gewisse Entfernung voneinander einhalten?
3. Wie kann "optimale Positionierung" (in Abhängigkeit von 1.) quantifiziert werden? Was ist also das Ziel?

Ich könnte mir vorstellen, dass hier lokale Minima zu einem Problem werden. Du brauchst also einen guten Ausgangspunkt oder musst Ansätze der globalen Optimierung anwenden.

Als erstes würde ich aber googeln. Wahrscheinlich bist du nicht der erste, der sich mit einer solchen Problematik auseinandersetzt. Da wäre es ja interessant zu sehen, was andere gemacht haben und ob man darauf aufbauen kann.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
derEchteNoob
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 22.07.2021, 13:49     Titel:
  Antworten mit Zitat      
Hi, danke für die Antwort.

Zu 1. :
Die Produkte sind geometrische Polygone mit insgesamt 7 Eckpunkten.
Beeinflussen kann ich die Positionierung des Körpers im Raum bzw der einzelnen Eckpunkte (x-,y-Koordinaten). Es gibt für die Produkte auch nur 2 Etagen, worauf sie positioniert werden können.


Zu 2:
Zu den Nebenbedingungen:
Die Produkte müssen zueinander einen Abstand von ca. 10cm haben und zur oberen Ebene auch 10cm. Da das Objekt auf der Unterseite aufliegt, gibt es dort logischerweise keine Restriktionen.
Eine maximale Gesamtlänge, Gesamthöhe und ein max. Gesamtgewicht ist vorgegeben.
Eventuell kommen auch Restriktionen bezüglich einzelner Positionierungen hinzu:
Beispiel: Position 1 und 2 dürfen zusammen maximal 3 tonnen tragen


Zu 3:
Nicht jedes Produkt passt auch überall hin (aufgrund von geometrischen Bedingungen --> zu lang oder zu hoch)
Eine optimale Positionierung wäre vorerst, dass alle "Platzierebenen" horizontal bleiben, da es weniger Aufwand erfordert.
--> Es sollen alle Produkte auf den Ebenen positioniert werden mit so wenig wie möglich schrägen Flächen.

Da ich aber davon ausgehe, dass bei einer Auswahl von mehr als 5 Produkten immer Flächen geneigt werden müssen, denke ich dass es sinnvoll ist, folgendes als Ziel zu setzen:

Freie Flächen im Regal so belegen, dass alle Produkte so eng wie möglich beieinander sind.



Ich hoffe das hat ein wenig zum Verständnis beigetragen.


Vielen Dank,

M.
_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 22.07.2021, 18:12     Titel:
  Antworten mit Zitat      
Hallo,

es geht mir weniger darum, das zu verstehen, als dir dabei zu helfen, das in eine Form zu bringen, die du in einen MATLAB-Befehl stecken kannst. Ich denke hier momentan an ga oder surrogateopt , da das Problem nichtlinear ist und du Integer-Constraints hast (auf welches Brett soll etwas gestellt werden). Idealerweise stellst du eine mathematische Formulierung auf: Formeln statt Text. :)

zu 1.: du brauchst doch nur eine (x,y)-Koordinate für jeden Körper und vielleicht noch die Ausrichtung? Wobei die Ausrichtung wiederum für alle Körper auf einer Etage gleich sein dürfte.

zu 2.: dies muss dann in Formeln gegossen werden.

zu 3.:
Zitat:
Eine optimale Positionierung wäre vorerst, dass alle "Platzierebenen" horizontal bleiben, da es weniger Aufwand erfordert.

D.h. z.B. mathematisch dann
Code:
min( abs(winkel1) + abs(winkel2) )


Zitat:
Freie Flächen im Regal so belegen, dass alle Produkte so eng wie möglich beieinander sind.

Das klingt dann für mich eher so, dass man gar nicht die Position an sich optimieren muss, sondern nur die Reihenfolge. Das könnte deutlich einfacher sein.

Generell kann ich nur dazu raten, sich die Problemformulierung möglichst genau zu überlegen, bevor man sich an die Umsetzung macht, damit man keinen vielfachen Aufwand hat.

Bei einer überschaubaren Anzahl an insgesamten Möglichkeiten würde ich auch in Betracht ziehen, alle Möglichkeiten durchrechnen zu lassen.

Wenn z.B. 8 Produkte gegeben sind, dann gibt es "nur" 8! = 40320 Möglichkeiten sie zu platzieren. Du könntest also jede durchprobieren und schauen, ob das überhaupt machbar ist bzw. mit welchem Neigungswinkel.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
derEchteNoob
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 26.07.2021, 09:09     Titel:
  Antworten mit Zitat      
Vorerst: vielen Dank für deine Mühe und Untertützung!

Zitat:
Das klingt dann für mich eher so, dass man gar nicht die Position an sich optimieren muss, sondern nur die Reihenfolge.


genau so ist es, jedoch kann durch Veränderung der Flächen einer Ebene (Drehen/ Kippen) die Reihenolge beeinflusst werde, da dann eventuell ein anderes Produkt auch hinpassen könnte (durch die Drehung der Fläche).


zu meinem Vorgehen:
ich habe bisher das ganze System (Produkte mit 7 Punkten, Flächen und Funktionen zum drehen, spiegeln, positionieren der Produkte) in Matlab hinterlegt und auch geplottet. Per Abruf kann ich die Produkte an der gewünschten Position platzieren (über die Koordinaten eines Eckpunktes). Das ganze soll aber später vollautomatisiert laufen.

Die Idee, alle Positionierungen durchzuprobieren ist sehr gut, jedoch muss man noch beachten, dass jede Fläche kippbar ist und somit sich viel mehr Varianten ergeben können. Klar sind es nur 8! Positionierungsmöglichkeiten, aber die Anzahl der "Durchläufe" wird weitaus mehr sein.



Ich habe mir überlegt, jede Position mit einem "Kasten" darzustellen und die Produkte dann mit einem Geometrie-Fitting-Algorithmus per trial and error durchzuprobieren.
Das System soll dann das Produkt (unter Einhaltung der Nebenbedingungen, wie zum Beispiel maximaler Neigungswinkel 30° bis -30°) versuchen in diesem Kasten optimal zu platzieren. Zu diesem Thema habe ich aber große Schwierigkeien etwas zu finden bzw. wie ich dabei vorgehen soll. Ist es immer noch ein lineares Optimierungsproblem?

Auch beim Aufstellen der Zielfunktion und Nebenbedingungen tu ich mir sehr schwer, da wir in den Vorlesungen nur diese ganz einfachen Problemstellungen hatten.
In welche Richtung könnte die Funktion gehen?


Viele Grüße,

M.
_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 26.07.2021, 09:48     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
Auch beim Aufstellen der Zielfunktion und Nebenbedingungen tu ich mir sehr schwer

Als Zielfunktion hatte ich min( abs(winkel1) + abs(winkel2) ) vorgeschlagen.

Wenn du durchprobierst, musst du die Nebenbedingungen nicht in dem Sinn aufstellen, sondern nur prüfen, ob sie verletzt sind.

Zitat:
da wir in den Vorlesungen nur diese ganz einfachen Problemstellungen hatten.

Wenn es um ein Projekt zum Abschluss einer Vorlesung oder ähnliches geht, kannst du dich vielleicht auch mal mit dem Aufgabensteller darüber austauschen, wie er sich das gedacht hat?

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
derEchteNoob
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 27.07.2021, 10:19     Titel:
  Antworten mit Zitat      
Hallo,

ich habe mir überlegt die Zielfunktion so zu gestalten, dass der linke untere Punkt (s. Anhang rote Ecken) so weit "links" ist wie möglich. D.h. die x-Koordinate der linken unteren Ecke des Produktes sollte Minimal sein, unter Einhaltung der Nebenbedingungen.

Am weitesten links wäre der Punkt dann logischerweise auch, wenn das Produkt einen Winkel von 0° hat und somit horizontal auf der Ebene steht. Wenn das für ein bestimmtes Produkt aber nicht geht, dann wird versucht die Fläche zu neigen und das Produkt über das andere "überlappen" zu lassen, ohne dass sie kollidieren und unter Einhaltung der geometrischen Randbedingungen (des Regals).

Wie könntest du dir hierbei eine ZF vorstellen?

Zum Anhang: es sind 8 Produkte unterschiedlicher Foren zu sehen, links, rechts und oben wurden Grenzen eingezeichnet.

Konzeptskizze.png
 Beschreibung:

Download
 Dateiname:  Konzeptskizze.png
 Dateigröße:  29.19 KB
 Heruntergeladen:  248 mal

_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 29.07.2021, 19:16     Titel:
  Antworten mit Zitat      
Hallo,

Die Zielfunktion sollte skalarwertig sein. Natürlich könnte man das "irgendwie" hinbiegen, es erscheint mir aber nicht zielführend. Du hast ja geschrieben, dass die Winkel möglichst klein sein sollen, und dann würde ich eben auch das (wie beschrieben) als Zielfunktion verwenden.

Ein Bild sagt bekanntlich mehr als 1000 Worte. Wenn du also ein Bild hast, das die Problematik skizziert, dann teile es doch bitte von Anfang an. Ich bin bisher beispielweise davon ausgegangen, dass alle Produkte auf den unteren bzw. oberen Plätzen auf einer durchgehend geneigten Plattform stehen. Das Bild lässt das ganz anders aussehen. Rückfragen:
* Sind die oberen Plattformen neigbar? Sind sie voneinander unabhängig vertikal verschiebbar?
* Sind die unteren Plattformen alle neigbar oder nur, wie in der Skizze, die erste und dritte in Beladerichtung?

Vorschläge:
Du sagtest ja, idealerweise soll es keine Neigung der Plattformen geben. Ich würde also zunächst alle Kombinationen von Produkten durchprobieren, ob die Summe der Längen kleiner als die max. x-Länge ist und andere Nebenbedingungen erfüllt sind.
Ich würde zudem mitloggen, wie stark die x-Länge überschritten wird. Kombinationen mit starker Überschreitung können bestenfalls mit starker Neigung der Plattformen zulässig werden.
Ist es eigentlich realistisch, dass durch geneigte Plattformen zwei Produkte auf einer Ebene teilweise übereinander sind? Nach der Skizze könnte das durchaus möglich sein, es hängt aber natürlich von den Höhen der Produkte in Relation zur zulässigen y-Höhe ab, ob das als realistisch in Betracht gezogen werden muss.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
derEchteNoob
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 04.08.2021, 08:51     Titel:
  Antworten mit Zitat      
Hallo Harald,

danke für deine Antwort und die Skizze habe ich erst zwischenzeitlich erstellt.

Zitat:
* Sind die oberen Plattformen neigbar? Sind sie voneinander unabhängig vertikal verschiebbar?

Ja, alle Flächen sind neigbar.

Zitat:
* Sind die unteren Plattformen alle neigbar oder nur, wie in der Skizze, die erste und dritte in Beladerichtung?

Ja, alle Flächen sind neigbar.

Zitat:
Du sagtest ja, idealerweise soll es keine Neigung der Plattformen geben. Ich würde also zunächst alle Kombinationen von Produkten durchprobieren, ob die Summe der Längen kleiner als die max. x-Länge ist und andere Nebenbedingungen erfüllt sind.

Als ersten Schritt finde ich diese Idee sehr gut, alle Positionierungen (8!) durchzuprobieren und ggf. das mit der kleinsten Gesamtlänge auszuwählen.

Zitat:
Ich würde zudem mitloggen, wie stark die x-Länge überschritten wird. Kombinationen mit starker Überschreitung können bestenfalls mit starker Neigung der Plattformen zulässig werden.


Also erst wenn die zul. Gesamtlänge bei nicht geneigten Plattformen nicht unterschritten werden kann, beginne ich mit der Neigung der Flächen.

Zitat:
Ist es eigentlich realistisch, dass durch geneigte Plattformen zwei Produkte auf einer Ebene teilweise übereinander sind? Nach der Skizze könnte das durchaus möglich sein, es hängt aber natürlich von den Höhen der Produkte in Relation zur zulässigen y-Höhe ab, ob das als realistisch in Betracht gezogen werden muss.


Ja ist es, solange die Randbedingungen (Höhe etc.) eingehalten werden, s. Anhang.

Screenshot.png
 Beschreibung:

Download
 Dateiname:  Screenshot.png
 Dateigröße:  15.59 KB
 Heruntergeladen:  218 mal

_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 04.08.2021, 09:22     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
Als ersten Schritt finde ich diese Idee sehr gut, alle Positionierungen (8!) durchzuprobieren und ggf. das mit der kleinsten Gesamtlänge auszuwählen.


Solange du keine anderen Nebenbedingungen hast, sind es sogar deutlich weniger Kombinationen: du musst ja nur für jedes Produkt entscheiden, ob es oben oder unten stehen soll. Wenn mich meine Stochastik-Kenntnisse nicht im Stich lassen, sind das nur
nchoosek(8, 4) = 70 Möglichkeiten.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
derEchteNoob
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 04.08.2021, 09:27     Titel:
  Antworten mit Zitat      
Hallo Harald,

ja, das stimmt.


Was mache ich für den Fall, wenn ich gezwungen bin, die Flächen zu neigen?

Ich habe dazu ehrlich gesagt keine Idee, auch wie ich das mathematisch umsetzen soll.
Ist es eventuell sinnvoll, immer zwei Produkte in einem "Kasten" zu betrachten und beide so anzuordnen, dass sie so weit links sind wie möglich?


Vielen Dank für deine Hilfe.

Gruß

M.
_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 04.08.2021, 10:05     Titel:
  Antworten mit Zitat      
Hallo,

du brauchst z.B. eine Möglichkeit, aus den Neigungswinkeln der einzelnen Plattformen die Gesamtlänge zu berechnen. Dann kannst du ein Optimierungsproblem lösen:
min (max( abs(winkel) )) unter der Bedingung Gesamtlänge <= erlaubte Länge

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
derEchteNoob
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 49
Anmeldedatum: 21.07.21
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 10.08.2021, 14:11     Titel:
  Antworten mit Zitat      
Hallo,


wie könnte das Problem gelöst werden, wenn es hierbei um die Beladung eines Autotransporters mit verschiedenen Fahrzeugen geht?
Ich denke die Problemstellungen sind fast identisch und mit dem Autotransporter leichter vorzustellen.

Grüße,

M
_________________

Servus
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.458
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 10.08.2021, 15:29     Titel:
  Antworten mit Zitat      
Hallo,

die Problemstellungen sind in der Tat so ähnlich, dass ich bei der Skizze dachte, dass es genau darum geht. Allerdings habe ich selbst noch nie einen Autotransporter beladen oder mir nähere Gedanken darüber gemacht.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.