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 muss 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$ (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. Damit ergibt sich ein Optimierungsproblem.

Rucksackproblem: Gesucht sind die Werte $x_j$ $\left(j=1,\dots ,n\right)$ mit

$$x_j=\left\{\begin{array}{cc}1& \text{wenn der Gegenstand }j\text{ in den Rucksack kommt,}\hfill \\ 0& \text{wenn der Gegenstand }j\text{ nicht in den Rucksack kommt.}\hfill \end{array}\right.$$

unter den Bedingungen

$\sum _{j=1}^n{w}_j\cdot x_j=\text{Max!}$			(5)
$\sum _{j=1}^n{w}_j\cdot x_j\le b$	und	$x_j\in \left\{0,1\right\}$	(6)

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.