0 Daumen
574 Aufrufe

Guten Morgen Liebe Mathegenuis,

ich habe eine Frage bezüglich einem kleinem Rucksackproblem. Leider finde ich im Internet kein geeignetes Kochbuch für ein kleines Rucksackproblem.

Ich weiß, dass sich ein kleines Rucksackproblem auf ein binäres Problem zurückführen lässt. Somit haben wir dann zwei Entscheidungsvariabeln 1 und 0.


Die Aufgabe lautet:

Ein Lastkraftwagen mit maximalen Zuladungsgewicht von G = 50t soll bis zu drei Güter G1, G2, G3 mit den Einzelgewichten g1 = 10t, g2 = 20t, g3= 30t transportieren. Die Auslieferung der einzeln Güter ist mit den Gewinnen c1 = 60 GE, c2 = 100 GE, c3 = 120 GE (GE = Geldeinheiten) verbunden.

Mit welchen Gütern muss der LKW beladen werden, damit der Gewinn maximal wird?

Finden Sie (per Rechnung von Hand) die optimale Lösung x* und den optimalen Wert -z* mittels vollständiger Enumeration. Wie viele Elemente hat die zulässige Menge X?



Mein Lösungsweg was bis jetzt:

xi = { 1 Wenn Gut Gi transportiert wird; 0 wenn Gut Gi nicht transportiert wird , i = 1,2,3

Nun muss ich die Zielfunktion und die NB aufstellen.

Es soll ja der Gewinn maximiert werden, daher sind die Gewinne meine Zielfunktion

Zielfunktion:

-z = 60 * x1 + 100 * x2 + 120 * x3 -> max

z = -60 * x1 - 100 * x2 - 120 * x3 -> min

NB:

10 * x1 + 20 * x2 + 30 *x3 <= 50

x1,x2,x3 ist Element von {0,1}


Wie gehe ich nun weiter? Wie läuft das Rucksackproblem ab? Es wäre sehr nett, wenn mir jemand weiter helfen könnte und sagen könnte wie ich weiter vorgehen muss. Hat jemand vielleicht einen guten Link für ein gutes Kockbuch?


Vielen Dank im Voraus, freue mich sehr über Antworten.


Euer WilderWind

Avatar von

1 Antwort

0 Daumen

Die 50 t Ladegewicht sind auf auf eine der 5 folgenden Arten ausgelastet:

g3+g2

g3+2g1

2g2+g1

g2+3g1

5g1

Für welche dieser Ladungen ist der Gewinn am höchsten?

Avatar von 123 k 🚀

Danke für deine Antwort.

Wie kommst du dadrauf?

Wie kann man aus den Summanden 10, 20 und 30 die Summe 50 erreichen?

0·10+20+30

1·10+2·20

2·10+30

3·10+20

4·10 keine Auslastung möglich

5·10

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community