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
