Knapsack-Problem

Ein wichtiges Grundproblem der kombinatorischen Optimierung ist das Knapsack-Problem. Eine anschauliche Darstellung dieses auch für betriebswirtschaftliche Sachverhalte wie Investitionsentscheidungen und Budgetierungsentscheidungen relevanten Problems lautet: Ein Wanderer möchte aus einer Menge von n Gegenständen diejenigen aussuchen, die bei Einhalten des Maximalgewichtes G seines Rucksacks zu maximalem Gesamtnutzen führen. Jeder Gegenstand j = 1, ..., n besitzt ein Gewicht gj und verursacht einen Nutzen in Höhe von uj. Mit Hilfe von Binärvariablen xj, die den Wert 1 haben, falls Gegenstand j mitgenommen wird, lässt sich das Knapsack-Problem wie folgt als binäres Optimierungsmodell formulieren: Zur Lösung des NP-schweren Knapsack- Problems lassen sich B&B-Verfahren verwenden.

<< vorhergehender Begriff

nächster Begriff >>

Knappschaftsversicherung

Knebelvertrag