Optimierungsproblem Logistikunternehmen: Auslieferung mit möglichst wenig Kraftstoffverbrauch

Question

Aufgabe:

Bei der Planung des Versands von 10.000 Kisten mit Ski-Schuhen steht ein Logistikunternehmen vor der Aufgabe, bei der Auslieferung zum Lager möglichst wenig Kraftstoff zu verbrauchen. Für den Transport stehen 10 große und 40 kleine Lastkraftwagen (LKW) zur Verfügung, deren Eigenschaften in folgender Tabelle beschrieben sind:

	große LKW	kleine LKW	Einheit
Krafstoffverbrauch	20	15	l/100 km
Fassungsvermögen	416	166	Kisten pro LKW
Max. verfügbare Anzahl	10	40	LKW

Stellen Sie aus diesen Angaben ein Optimierungsproblem auf.

Ich weiß, dass hier ein Minimierungsproblem vorliegt, nur fällt mir die Aufstellung der Aufgabe schwer.

Comments

Bei Wolframalpha sieht das wie folgt aus

https://www.wolframalpha.com/input/?i=minimize+20x%2B15y+with+416x%2…

Answer 1

Hallo Laura,

Ein Spediteur würde rechen, dass der Kraftstoffverbrauch $\kappa$ pro Kiste bei großen LKWs bei $$\kappa_g = 20 \frac{\text l}{100 \text{km}} \cdot \frac 1{416} = 0,048 \frac{\text l}{100 \text{km}}$$liegt und die kleinen LKWs $$\kappa_k = 15 \frac{\text l}{100 \text{km}} \cdot \frac 1{166} = 0,90 \frac{\text l}{100 \text{km}}$$brauchen. Also ist ein großer LKW wesentlich günstiger. Er transponiert also $10 \cdot 416 = 4160$ Kisten mit den $10$ großen LKWs, die er hat, und die restlichen $10000-4160=5840$ Kisten mit $\lceil 5840/166 \rceil = 36$ kleinen LKWs.

Aber Du sollst es wahrscheinlich mit dem Simplex-Verrfahren lösen. Dazu benötigen wir eine Zielfunktion. Der gesamte Kraftstoffverbrauch $\kappa_{\text{ges}}$ soll minimiert werden. Und der ist $$\kappa_{\text{ges}} = n_g \cdot 20 \frac{\text l}{100 \text{km}} + n_k \cdot 15 \frac{\text l}{100 \text{km}}$$wenn $n_g$ die Anzahl der großen LKWs und $n_k$ die Anzahl der kleinen LKWs ist.

Die Restriktionen sind: die Anzahl der Kisten muss 10000 ergeben und die Anzahl der vorhandenen LKWs:$$n_g \cdot 416 + n_k \cdot 166 \ge 10000 \\ 0 \le n_g \le 10 \\ 0 \le n_k \le 40$$Das kann man nun graphisch wie folgt darstellen

Plotlux öffnen

f₁(x) = (10000-166x)/417x = 40f₂(x) = 10Zoom: x(-2…50) y(-3…15)f₃(x) = (720-15x)/20f₄(x) = (730-15x)/20

In dem Koordinatensysten steht die waagerechte Achse für die Anzahl der kleinen LKWs und die senkrechte für die Anzahl der großen LKWs. Da die Anzahl jeweils begrenzt ist, habe ich die Grenzen in das Koordinatensystem eingetragen, Die rote Senkrechte begrenzt die Anzahl der kleinen LKWs und die grüne horizontale die Anzahl der großen LKWs, Die Lösung befindet sich also irgendwo in dem Rechteck aus roter und grüner LInie und den Koordinatenachsen. Die Zwangsbedingung $$n_g \cdot 416 + n_k \cdot 166 \ge 10000$$dass in den LKWs für mindestens 10000Kisten Platz sein muss, habe ich als blauen Graphen eingezeichnet. Damit reduzieren sich unsere Lösungen auf das blaue Streckenstück zwischen der roten und grünen Grenze.

Die rosane und die gelbe Gerade sind Linien gleichen Kraftstoffverbrauchs - also $$\kappa_{\text{ges}} = n_g \cdot 20 \frac{\text l}{100 \text{km}} + n_k \cdot 15 \frac{\text l}{100 \text{km}}$$Die rosane LInie steht für ein $\kappa_{\text{ges}} = 720 \,\text{l/100km}$ und die gelbe für ein $\kappa_{\text{ges}} = 730 \,\text{l/100km}$. Der Kraftverbrauch wird geringer, umso näher diese Geraden am Ursprung liegen. Somit ist die Lösung der Schnittpunkt der grünen mit der blauen Geraden.

Nachtrag:

Du sollst ja nur das Optimierungsproblem aufstellen, also ich nehme an die Zielfunktionen und die Restriktionen. Für die Aufgabe 1 habe ich das oben bereits gemacht. Für Aufgabe 2 sieht es so aus: Die Zielfunktion ist die Strommenge $W$, die benötigt wird. Die Variablen sind die Menge $m_{\text{Al}}$ an Altaluminium und die Menge $m_{\text B}$ an Bauxit$$W = m_{\text{Al}} \cdot 0,75 \frac{\text{kWh}}{\text{kg}} + m_{\text B} \cdot 15 \frac{\text{kWh}}{\text{kg}}$$Die Restriktionen sind die verfügbaren Mengen und die geforderte Menge an Aluminium$$0 \le m_{\text{Al}} \le 60 \text{kg} \\ 0 \le m_{\text B} \le 115 \text{kg} \\ \frac{m_{Al}}{1,15} + \frac{m_{\text B}}{2} \ge 100 \,\text{kg}$$

Gruß Werner

Comments

Ich soll beide Aufgaben nochmal als duales Problem formulieren, wenn z.B. eine Restriktion gegeben ist " max 40 Lkws" dann schreibe ich ja x kleiner gleich (<=)40 ,aber wenn ich nun das ganze als Minimierungsproblem vorliegen habe, dann müssen die Restriktionen ja alle größer gleich sein oder (=>)?

---

... dann schreibe ich ja x kleiner gleich (<=)40 ,aber wenn ich nun das ganze als Minimierungsproblem vorliegen habe, dann müssen die Restriktionen ja alle größer gleich sein oder (=>)?

Ja da knabbere ich auch gerade dran - ich melde mich später noch mal.

---

Hallo Laura,

ich muss da leider passen. Ich habe das nicht so hingekriegt, dass ich es Dir einwandfrei erklären kann. Tu mir leid.

Bis wann brachst Du das?

Answer 2

Versandaufgabe:

x=Anzahl der großen LKW

y=Anzahl der kleinen LKW

Zu optimieren ist der Kraftstoffverbrauch V=20x+15y

Die möglichen Punkte (x|y) sind grau unterlegt:

                                                   416x+166y=10000

Die grüne Gerade ist aus der Schaar 20x+15y=V und geht durch (8|40). Der günstigste Kraftsoffverbrauch erfordert den Einsatz von 8 großen und 40 kleinen LKW.

Comments

Ich soll die Aufgabe mit dem simplex algorithmus lösen.. wie müsste ich es aufschreiben?

---

Zu deiner ersten Frage:

Der grau unterlegte Bereich wird begrenzt durch

(1) 0≤x≤10

(2) 0≤y≤400

(3) 416x+166y=10000

Für welches V berührt die Gerade 20x+15y=V diesen Bereich.

Zu deiner zweiten Frage:

Den Simplex-Algorithmus kenne ich nicht.

---

Wie müsste ich die andere Aufgabe lösen ?


Vielen Dank :)

---

Besser, du stellst die Frage an Werner (s.u.).

Answer 3

Hm, ich komme da auf was anderes - gerechnet auf 100 km

Die Gleichungen

Z= 20x+15y -> min

{416x + 166y ≥ 10000, -x ≥ -10, -y ≥ -40}

als Tableau

$\scriptsize \left(\begin{array}{rrr}416&166&10000\\-1&0&-10\\0&-1&-40\\20&15&0\\\end{array}\right)$

erstelle das Duale Programm

$\scriptsize \left(\begin{array}{rrrrrr}416&-1&0&1&0&20\\166&0&-1&0&1&15\\-10000&10&40&0&0&0\\\end{array}\right)$

$\scriptsize \left(\begin{array}{rrrrrr}1&-0.002&0&0.002&0&0.048\\0&0.399&-1&-0.399&1&7.019\\0&-14.038&40&24.038&0&480.769\\\end{array}\right)$

$\scriptsize \left(\begin{array}{rrrrrr}1&0&-0.006&0&0.006&0.09\\0&1&-2.506&-1&2.506&17.59\\0&0&4.819&\small 10&\small 35.181& \small 727.711 \\\end{array}\right)$

 Auch grafisch

Könnt ihr da noch mal drüber schauen?

Comments

erstmal vielen Dank für deine Mühe :)

Wie bist du auf die -10 000 im Ausgangstableau gekommen?

In der Matrix sind es doch 10 000 -10 -40

In der ZF-Zeile müsste dann doch folglich 10 000 -10 -40 stehen?

Hast du nochmal die ZF-Zeile mal -1 genommen um im Tableau operieren zu können?

Wenn ich solche Optimierungsaufgaben vorliegen habe, kann ich eine Restriktion immer mal -1 nehmen damt ich die Voraussetzungen dafür habe ein Max\Min Optimierungsproblem aufzustellen?

Vielen Dank nochmal :)

---

Ach so,

bei meinem Algorithmus wird die Zielfunktion negativ im Tableau eingetragen und er stoppt, wenn alle Koeffizienten positiv sind. Sorry hab vergessen diesen Hinweis zu geben.

Guckst Du https://www.geogebra.org/m/BpqJ28eP#chapter/265052

Zum Umdrehen der NB, da bin ich noch nicht ganz dahinter gestiegen - ehrlich gesagt ich probiere es aus ;-). Wenn Du dem Link folgst (in der javascript app) stelle ich mehrere Verfahren vor die von den StandardNB abweichen.