nichtlineare ganzzahlige Optimierung

04.12.2008, 08:22	GetBack	Auf diesen Beitrag antworten »
nichtlineare ganzzahlige Optimierung Hallo, ich habe da folgendes Problem: Ich hab einen Studentenjob in einer Werbeagentur. Diese hat einen Shop programmiert und es wurde jetzt festgestellt, dass an den Versandkosten nachgearbeitet werden muss. Die Versandkosten sollen folgendermaßen gestaffelt sein: bis 10kg 6,90€, bis 20kg 9,90€ und bis 31,5kg 13,90€. Bestellungen mit einem Gewicht über 31,5kg müssen auf mehrere Pakete aufgeteilt werden. Damit konnte ich folgendes nichtlineare ganzzahlige Optimierungsproblem (P) aufstellen: Sei a die Anzahl der Pakete mit einem Gewicht von max. 10kg, b die Anzahl der 20kg Pakete und c die Anzahl der 31,5kg Pakete. Weiter sei g das Gewicht der Bestellung. (P) $\begin{eqnarray} 6,90a + 9,90b + 13,90c \to Min! \end{eqnarray}$ unter den Nebenbedingungen: $\begin{eqnarray} g \leq 10a+20b+31,5c \end{eqnarray}$ und $\begin{eqnarray} a,b,c\in \mathbb Z \end{eqnarray}$ Hättet ihr da einen mathematischen Lösungsansatz für mich, denn ich bin da gerade hilflos? Ich könnte mir sonst nur vorstellen, da das ganze ja auf einen Apache-Webserver laufen soll, das Gewicht g durch die kleinste Paketgröße zu teilen (also 10kg), um damit die maximale Anzahl an Paketen m zu erhalten. Dann müßten alle Kombinationen von 10kg, 20kg und 31,5kg Paket verglichen werden (bei denen die Kombination das gewünschte Gewicht verpackt und die Gesamtpaketanzahl kleiner ist als m) und die Kombination mit den geringsten Preis herausgefunden werden. Wie ich das jetzt aber genau algorithmisch umsetzen soll, weiss ich auch noch nicht. Ich hoffe Ihr könnt mir helfen. Viele grüße GetBack
04.12.2008, 08:44	AD	Auf diesen Beitrag antworten »
Der Algorithmus ist soweit in Ordnung - allerdings musst du nicht alle Tripel $\begin{eqnarray} (a,b,c) \end{eqnarray}$ mit $\begin{eqnarray} a+b+c \leq m \end{eqnarray}$ betrachten. Du kannst sukzessive so vorgehen: Es ist $\begin{eqnarray} m = \left\lceil \frac{g}{10} \right\rceil \end{eqnarray}$ . Du startest mit $\begin{eqnarray} a=m \end{eqnarray}$ , da kommt zwangsläufig nur das Tripel $\begin{eqnarray} (m,0,0) \end{eqnarray}$ als Minimumkandidat in Frage. Dann betrachtest du $\begin{eqnarray} a=m-1,m-2,\ldots,1,0 \end{eqnarray}$ , und für jedes dieser $\begin{eqnarray} a \end{eqnarray}$ ist laut NB $\begin{eqnarray} g-10a \leq 20b+31.5c \end{eqnarray}$ . Startend von oben mit $\begin{eqnarray} m' = \left\lceil \frac{g-10a}{20} \right\rceil \end{eqnarray}$ gehst du jetzt der Reihe nach $\begin{eqnarray} b=m',m'-1,\ldots,1,0 \end{eqnarray}$ durch. Für $\begin{eqnarray} c \end{eqnarray}$ schließlich kommt sowieso dann nur der Wert $\begin{eqnarray} c = \left\lceil \frac{g-10a-20b}{31.5} \right\rceil \end{eqnarray}$ in Frage. ----------------------- Auf diese Weise hangelst du dich wenigstens nur entlang der sinnvollen Gitterpunkte benachbart der NB-Ebene $\begin{eqnarray} 10a+20b+31.5=g \end{eqnarray}$ weiter. P.S.: Ich hoffe, ihr verkauft keine Großgeräte (z.B. 50"-TV) auf diese Weise...
04.12.2008, 09:03	GetBack	Auf diesen Beitrag antworten »
Danke, das sind richtige gute Tipps. Ne, ne es sollen Produkte wie Lebensmittel, Geschenkkörbe und Souvernirs verkauft werden. Viele Grüße GetBack
04.12.2008, 09:28	GetBack	Auf diesen Beitrag antworten »
Nachfrage Gibt es neben der Methode die oben beschrieben ist auch noch andere Herangehensweisen? Viele grüße GetBack
04.12.2008, 09:49	AD	Auf diesen Beitrag antworten »
Möglich, dass es da effizientere Verfahren gibt, ich kenne mich da nicht so aus. Ich weiß nur, dass es gefährlich ist, den optimalen Gitterpunkt nur "in der Nähe" der reellen optimalen Lösung dieses Linearen Optimierungsproblems zu suchen. Meistens liegt er in der Nähe (was auch immer das ist), aber in gewissen Konstellationen eben nicht. P.S.: Mir fällt gerade auf, dein "nichtlinear" in der Überschrift ist falsch - dein Optimierungsproblem ist zwar ganzzahlig, aber trotzdem auch linear.
04.12.2008, 10:04	GetBack	Auf diesen Beitrag antworten »
Da hast du natürlich recht und ich bin wohl etwas über das Ziel hinausgeschossen, aber da ich mich inzwischen angemeldet habe, kann ich den ersten post nicht mehr ändern. Der Beitrag kann dann als geschlossen betrachtet werden. Viele grüße GetBack
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »