Das Rucksackproblem

Eine mathematische Modellierung einer alltäglichen Situation: Geht ein Bergsteiger auf eine mehrtägige Wanderung, hat er sich reiflich zu überlegen, welche Dinge er unbedingt mitführen sollte. Dabei muß er die begrenzte Tragefähigkeit seines Körpers beachten, sein Rucksack sollte also nicht zu schwer sein.

Kann unser Bergsteiger unter n Gegenständen auswählen, hat jeder Gegenstand j eine bestimmte Masse m_j und einen für die Wanderung wichtigen, nicht unbedingt nur materiellen Wert w_j, ergibt sich somit ein Optimierungsproblem. (Der Wert eines Gegenstandes läßt sich sicherlich mit Hilfe eines Beispiels erfassen. Man überdenke nur die Nützlichkeit von Schlafsäcken und Sonnenschirmen für eine Bergwanderung.)
Zusätzlich wollen wir das Fassungsvermögen des Rucksacks außer Acht lassen und annehmen, dass der Bergsteiger höchstens eine Masse von b kg mit sich herumschleppen kann.

Rucksackproblem: Gesucht sind die Werte x_j, (j = 1,…, n) mit

Die Zielfunktion (5) kennzeichnet, dass der Rucksack bei der Wanderung den größtmöglichen Wert enthält, die Nebenbedingung (6) sorgt dafür, dass die zulässige Masse nicht überschritten wird und gebietet die Ganzzahligkeit der Anzahl der Gegenstände.
Wählt man x_j ganzzahlig auch größer als 1, so kann der Fall beschrieben werden, dass mehrere gleichartige Gegenstände im Rucksack einen Platz erhalten.

Dieses Optimierungsproblem ist ein Problem aus der Diskreten Optimierung, man kann es bspw. durch Zerlegung in Teilprobleme lösen. Interessant ist die Frage der Ermittlung des Wertes der einzelnen Gegenstände, ein Problem, dass nicht unbedingt mathematischer Natur ist, jedoch in die Problemdiskussion mit einbezogen werden sollte.