praktisches Optimierungsproblem

07.07.2008, 09:40

Frühaufsteher

praktisches Optimierungsproblem

Hallo. Ich habe ein Problem mit einer Optimierungsaufgabe.

Und zwar ist es eine Aufgabe aus der Praxis. Eine Firma stellt Walzen her. Diese Walzen sollen in verschiedenen Breiten(Stufen) angeboten werden. Meine Aufgabe ist es jetzt die Breiten so zu wählen, dass die Kundenseitige Überdimensionierung minimal wird (bezogen auf die Kundenbestellungen der letzten 2 jahre, welche mir vorliegen), hierbei sei die Anzahl der Stufen zunächst vorgegeben, z.B. 6 Stufen.

Die Überdimensionierung, welche beim Kunden entsteht berechnet sich beispielsweise wie folgt:

es werden z.b. eine Walze mit Breite 100mm und eine mit Breite 200mm angeboten. Der Kunde möchte jetzt aber eine Walze haben die 150 Breit ist, dann muss er zur grösseren greifen und hat eine Überdimensionierung von 50mm.

Ich habe mir schon ein paar gedanken gemacht bin aber mit der Zielfunktion die ich finde alles andere als zufrieden.

Die 6 Stufen habe ich mit $\begin{eqnarray*} x_{1} \end{eqnarray*}$ bis $\begin{eqnarray*} x_{6} \end{eqnarray*}$ bezeichnet

die Kundenanfragen mit $\begin{eqnarray*} b_{1} \end{eqnarray*}$ bis $\begin{eqnarray*} b_{124} \end{eqnarray*}$ da mir 124 Anfragen aus der Vergangenheit vorliegen.

Die erste Schwierigkeit war für mich eine Formulierung zufinden, damit jede Kundenanfrage b mit dem nächstgrösseren x kombiniert. ich habe das gelöst, indem ich für jede einezelne Kundenanfrage eine Nebenbedingung eingeführt habe. Durch den Minimum-Operator und der Bedingung dass die Diferenz positiv sein soll, wird jeweils genau die Differenz oder Überdimensionierung der Kundenanfrage mit der nächst höheren Stufe gebildet.

$\begin{eqnarray*} min(x_{1}-b_{1};...x_{6}-b_{1})\geq0 \end{eqnarray*}$
...

$\begin{eqnarray*} min(x_{1}-b_{124};...x_{6}-b_{124})\geq0 \end{eqnarray*}$

Meine Zielfunktion ist dann einfach die Summe über alle meine Nebenbedingungen, ich möchte also die komulierten Überdimensionierungen minimieren.

Zielfunktion

$\begin{eqnarray*} f(x_{1},...,x_{6})= \sum_{k=1}^{124}~ min(x_{1}-b_{k},...,x_{6}-b_{k})=z \end{eqnarray*}$ z soll minimiert werden.

Wenn ich das richtig sehe, ist meine Zielfunktion nicht linear und unstetig. ich weiss nicht wie ich hier ein Optimum finden kann, bzw welches tool mir da evtl helfen kann. ich hoffe jemand von Euch kann mir weiterhelfen. Evtl. habt Ihr auch einen Vorschlag, wie man die Zielfunktion vereinfachen kann oder anders formulieren kann und so zu einer leichteren Optimierung kommen kann. Ich danke aufjedenfall schon einmal jedem, der sich mein Problem durchgelesen hat.

Sollte die Aufgabenstellung nicht ganz klar geworden sein, oder wenn noch Fragen bestehen, editiere ich meinen Eintrag gerne nocheinmal.

Gruss

der Frühaufsteher.

p.s. als nächsten Schritt möchte ich möglichst die Anzahl der Stufen als zusätzliches Ziel mit aufnehmen und ebenfalls minimieren. Zunächst muss ich aber mit dem einfachen Fall weiterkommen.

edits: Rechtschreibung Augenzwinkern

07.07.2008, 10:09

Auf diesen Beitrag antworten »

Zitat:

Original von Frühaufsteher
Zielfunktion

$\begin{eqnarray*} f(x_{1},...,x_{6})= \sum_{k=1}^{124}~ min(x_{1}-b_{k},...,x_{6}-b_{k})=z \end{eqnarray*}$ z soll minimiert werden.

Die Schreibweise ist so nicht in Ordnung: Was du meinst ist

$\begin{eqnarray*} f(x_1,\ldots,x_6) = \sum_{k=1}^{124} \min\Big\{ x_j-b_k \Bigm| 1\leq j\leq 6:\, x_j\geq b_k \Big\} \to \min \end{eqnarray*}$ ,

d.h. das Minimum wird nur über die $\begin{eqnarray*} j \end{eqnarray*}$ gebildet, für die $\begin{eqnarray*} x_j\geq b_k \end{eqnarray*}$ zutrifft.

Zur Lösung:

Da stellt sich erstmal die Frage, ob du die Breiten $\begin{eqnarray*} x_1,\ldots,x_6 \end{eqnarray*}$ nur hinsichtlich der 124 Kundenuafträge festlegen willst, oder auch schon zukünftige (noch nicht genau bekannte) Aufträge im Auge hast - letzteres wäre natürlich erheblich schwieriger und ist mit zusätzlichen Annahmen verbunden. Daher gehe ich zunächst von ersterem aus, d.h., dass du das Optimum hinsichtlich der festen Aufträge $\begin{eqnarray*} b_1,\ldots,b_n \end{eqnarray*}$ (hier mit n=124) suchst.

Klar ist, dass im Optimum auf jeden Fall $\begin{eqnarray*} x_1,\ldots,x_6 \in \{b_1,\ldots, b_n\} \end{eqnarray*}$ gelten wird, d.h., dass die Optimalwerte mit irgendwelchen der Ausgangswerte zusammenfallen. Bei der o.B.d.A. aufsteigenden Sortierung $\begin{eqnarray*} x_1<\ldots < x_6 \end{eqnarray*}$ sowie $\begin{eqnarray*} b_1\leq \ldots \leq b_n \end{eqnarray*}$ folgt dann ebenso klar, dass $\begin{eqnarray*} x_6=b_n \end{eqnarray*}$ im Optimum gelten muss.

Wie es weiter geht, ist dann allerdings nicht mehr so einfach. Angenommen, unter den $\begin{eqnarray*} n \end{eqnarray*}$ Werten $\begin{eqnarray*} b_1,\ldots,b_n \end{eqnarray*}$ gibt es insgesamt $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene. D.h., im ungünstigsten Extremfall sind alle n=124 Breiten voneinander verschieden, dann wäre m=n, i.a. gilt jedenfalls $\begin{eqnarray*} m\leq n \end{eqnarray*}$ .

Der oberste Wert ist wie gesagt festgelegt ( $\begin{eqnarray*} x_6=b_n \end{eqnarray*}$ ), verbleibt noch die Wahl der fünf unteren Werte $\begin{eqnarray*} x_1,\ldots,x_5 \end{eqnarray*}$ aus den $\begin{eqnarray*} m-1 \end{eqnarray*}$ Auftragswerten kleiner (!) als das Maximum $\begin{eqnarray*} b_n \end{eqnarray*}$ . Per Brute Force wären da insgesamt $\begin{eqnarray*} \binom{m-1}{5} \end{eqnarray*}$ Varianten durchzurechnen, im ungünstigsten Fall m=n=124 also

$\begin{eqnarray*} \binom{123}{5} = 216\,071\,394 \end{eqnarray*}$

Das ist heutzutage nicht mehr so viel: Das erledigt selbst ein handelsüblicher PC einsfixdrei. smile

Also würde ich mir erst ernsthafte Gedanken hinsichtlich eines besseren, intelligenteren Algorithmus machen, wenn die Anzahl deiner echt verschiedenen (!) Aufträge diese 124 und/oder die Anzahl deiner Klassen die Anzahl 6 übersteigt. In dem Fall wird Brute Force dann sehr schnell nicht mehr sinnvoll. Augenzwinkern

07.07.2008, 11:21

lostgeek

Auf diesen Beitrag antworten »

Ich hab zwar keine Ahnung von sowas, aber wenn du schon eine Zielfunktion hast, würde es mit einem genetischen Algorithmus gehen.

Kurzzusammenfassung von diesem Wikiversitykurs:

Schritt 1: Erzeugung von Walzenkombinationen
Ich würde sagen, da bieten sich die 124 bisherigen Aufträge an.

Schritt 2: Mutationen
Hier und dort bei rund 5% der Kombinationen bisschen was zufällig ändern.

Schritt 3: Kreuzung
Man nimmt zwei Kombinationen und die "zeugen" eine neue Kombination (z.B. 3 Walzen von der einen und 3 Walzen von der anderen).

Schritt 4: Selektion
Möglich wäre zwei Kombinationen gegeneinander "kämpfen" zu lassen (die mit der besseren Zielfunktion gewinnt).

Schritt 5: Wieder zu Schritt 2

Schritt 6: Irgendwann stoppen und den besten rausnehmen.

Wenn du ein wenig Ahnung vom Programmieren hast, ist es leicht zu bauen.

Aber ich weis nicht, ob da nicht mit Kanonen auf Spatzen geschossen wird Augenzwinkern

Gruss,
lostgeek

07.07.2008, 11:49

Frühaufsteher

Auf diesen Beitrag antworten »

Vielen Dank Euch beiden für die schnellen Antworten, hat mich echt überrascht wie schnell das ging!!

Das mit den genetischen Algorythmen werde ich mir durchlesen!

@Arthur Dent leider ist mir mit einfachem durchprobieren nicht geholfen, ich muss eine systematische Lösung finden, die sich auch auf andere, komplexere Fälle anwenden lässt. Also wenn ich z.B. neben der Breite noch weitere Merkmalsausprägungen dazu bekomme.
Dann glaube ich auch, dass ich wie Du auch schon gesagt hast mit durchprobieren schnell an die Grenzen komme.

Aber würdet Ihr bei der gegebenen Aufgabenstellung die Zielfunktion genauso formulieren (abgesehen von den Formfehlern Augenzwinkern

danke Dent!), oder sehe ich da irgendwie den Wald vor lauter Bäumen nicht wie man das ganze einfacher anpacken kann?

07.07.2008, 12:05

Auf diesen Beitrag antworten »

Zitat:

Original von Frühaufsteher
Also wenn ich z.B. neben der Breite noch weitere Merkmalsausprägungen dazu bekomme.

Da wäre dann aber wieder die Frage zu klären, was du dann als optimal hinsichtlich einer "mehrdimensionalen" Zielfunktion verstehst.

Wirklich schade, das obige Problem ist in einigen Sekunden Rechenzeit exakt lösbar.

Zitat:

Original von Frühaufsteher
@Arthur Dent leider ist mir mit einfachem durchprobieren nicht geholfen, ich muss eine systematische Lösung finden, die sich auch auf andere, komplexere Fälle anwenden lässt.

Wenn du das eher gesagt hättest, dann hätte ich mir die Mühe sparen können. Ich hatte das

Zitat:

Original von Frühaufsteher
als nächsten Schritt möchte ich möglichst die Anzahl der Stufen als zusätzliches Ziel mit aufnehmen und ebenfalls minimieren. Zunächst muss ich aber mit dem einfachen Fall weiterkommen.

für bare Münze genommen - leider.

07.07.2008, 13:35

Frühaufsteher

Auf diesen Beitrag antworten »

Arthur. Es tut mir leid wenn Du den Eindruck hast, du hättest umsonst Mühe und Zeit investiert. Ich versicherer Dir, so ist es nicht. Es hilft mir in jedemfall weiter was andere Leute über mein Problem denken, inbesondere wenn sie einen weiteren Horizont haben als ich selber Augenzwinkern

Und, ja, ich hätte es schon in der Aufgabenstellung erwähnen sollen, das durchprobieren nicht meine gesuchte Lösung ist, insbesondere wenn es wie in diesem konkreten Fall als die naheliegenste Lösung erscheint, entschuldige.

Und was den nächsten Schritt angeht, das war auch so gemeint. Wenn ich einen Algorithmus gefunden habe, der mit der Aufgabe umgehen kann. Möchte ich gerne die Minimierung der Stufenanzahl ebenfalls als Zielfunktion formulieren.

07.07.2008, 13:40

Auf diesen Beitrag antworten »

Zitat:

Original von Frühaufsteher
das durchprobieren nicht meine gesuchte Lösung ist

Woher weißt du das eigentlich so genau, dass das nicht deine Lösung ist? Es gibt auch "intelligentes" systematisches Probieren. Deine voreilige Ablehnung enttäuscht mich schon einigermaßen. Na ich hoffe, du findest was besseres. Wink

07.07.2008, 13:58

Frühaufsteher

Auf diesen Beitrag antworten »

Vielleicht habe ich mich da wieder schlecht ausgedrückt. Was ich als Lösung nicht benutzen kann ist ein Durchprobieren aller möglichen Lösungen, weil es sozusagen eine "Folgeaufgabe" gibt die man mit der Methode nciht mehr erschlagen kann. Trotzdem danke für dein Hilfe soweit.

Intelligentes Probieren will ich nicht ausschließen, es gibt ja glaube ich Verfahren die von zufällig gewählten Startlösungen aus versuchen eine Verbesserung zu erreichen. Ich weiss aber nicht, wie das mit der Zielfunktion, die ich habe zusammengeht, da die meisten denke ich mit Gradienten (Bergsteiger, etc.) arbeiten und ich glaube meine Zielfkt. ist nicht differenzierbar.

Am besten wäre es daher zunächst, meiner Meinung nach, eine Formulierung ohne den min-Operator in Zielfunktion oder Nebenbedingungen zu finden, das krieg ich aber einfach nicht gebacken.

Anderen Lösungswegen gegenüber bin ich aber auch offen.

07.07.2008, 14:03

Auf diesen Beitrag antworten »

Zitat:

Original von Frühaufsteher
Ich weiss aber nicht, wie das mit der Zielfunktion, die ich habe zusammengeht

Bisher habe ich keine Vorstellung, wie deine Zielfunktion in deinem wie auch immer erweiterten Problem aussehen soll - das hast du ja noch nicht konkret gesagt, sondern nur nebulös angedeutet. verwirrt

Und solange das so ist, kann man auch kaum Vorschläge unterbreiten.

07.07.2008, 14:13

Frühaufsteher

Auf diesen Beitrag antworten »

meine Zeilfunktion sollte die sein, die Du mir verbessert hast.

also diese:

$\begin{eqnarray*} f(x_1,\ldots,x_6) = \sum_{k=1}^{124} \min\Big\{ x_j-b_k \Bigm| 1\leq j\leq 6:\, x_j\geq b_k \Big\} \to \min \end{eqnarray*}$

edit:
die erweiterung möchte ich gerne ersteinmal draussen lassen. Ich habe sie nur erwähnt um zu begründen warum ich ein Durchprobieren aller Lösungen als Lösungsweg nicht so gerne machen würde.

07.07.2008, 14:30

Auf diesen Beitrag antworten »

Zitat:

Original von Frühaufsteher
die erweiterung möchte ich gerne ersteinmal draussen lassen.

Ich sehe, du brauchst noch etwas Zeit, um dir überhaupt klar zu werden, wie dein erweitertes Problem überhaupt mathematisch zu fassen ist. Wenn du soweit bist, kannst du dich ja gern wieder melden.

07.07.2008, 15:33

Tomtomtomtom

Auf diesen Beitrag antworten »

Die Erweiterung ist wirklich ziemlich unausgegoren, die Minimalwerte der Zielfunktion f_n(x_1,...,x_n) sind mit steigender Stufenzahl monoton fallend, und ab 124 Stufen hast du einen Minimalwert f_n(x_1,x_n)=0, du brauchst ja nur die 124 entsprechende der vergangenen Aufträge zu wählen.

Darüber hinaus ist es wenig üblich, eine Optimierung anhand der exakten Daten der letzten Jahre vorzunehmen. Viel eher schätzt man anhand dieser Daten die Verteilung der Zufallsvariable "Größe eines Auftragseingangs", und minimiert deren Erwartungswert. Auch wenn das mathematisch ein zusätzlicher Abstraktionsschritt ist, wird die Lösung damit in der Regel leichter fassbar, und mehr Methoden zugänglich.

Ich verstehe den Wunsch nicht so richtig, eine exakte Lösung zu berechnen aufgrund der vorliegenden Daten. Die nützt dir für die Zukunft nur in genau einem Fall etwas, nämlich wenn nochmal genau dieselben Auftragseingänge ankommen.

Da ist eine Zufallsvariable, deren Erwartungswert minimiert wird, eine deutlich stärkere Aussage. Damit hast du zwar dann wenn du dir im nachhinein die wirklichen Auftragseingänge anschaust wahrscheinlich nie das Optimum erwischt, aber im Schnitt kommst du trotzdem viel besser weg.

Neue Frage »

Antworten »

praktisches Optimierungsproblem

Verwandte Themen