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.

Standardmodelltyp der kombinatorischen Optimierung (vgl. Beispiel zum Branch and Bound). Aus den Elementen j = 1, 2,..., n ist eine solche Auswahl zu treffen, dass der Wert der Zielfunktion knapsack Problem

maximiert (bzw. minimiert) und die (einzige) Restriktion knapsack Problem

eingehalten werden. Dabei bedeuten die Variablenwerte Xj = 1 die Wahl, Xj = 0 die Nichtwahl des Elementes j. Zur Bewertung der einzelnen Zweige in den Entscheidungsbaumverfahren wird die 0-1- Bedingung der Variablen durch die Relaxation 0 < Xj < 1 ersetzt. Die Verfahren zur Lösung des Knapsack- Problems bilden die Grundlage für die Bewältigung einer Vielfalt von Auswahlproblemen der kombinatorischen Optimierung. Die Bezeichnung dieses Modelltyps kommt von dem englischen Namen für "Rucksack" her, der eine Kapazität von b hat. Die für eine Wanderung gebrauchten Gegenstände j mögen einen Nutzen von Cj stiften, vom Raum des Rucksackes aber aj beanspruchen. Für die Planungspraxis bedeutsam wird dieser Modelltyp immer dann, wenn eine Ressource (z.B. Finanzmittel) nur in begrenztem Ausmass zur Verfügung steht und verschiedene diskrete Verwendungszwecke um diese Ressource konkurrieren. Zur Lösung des Knapsack-Problems stehen verschiedene Entscheidungsbaumverfahren zur Verfügung, und zwar sowohl solche des Branch and Bound, der begrenzten Enumeration und der dynamischen Optimierung als auch heuristische Verfahren.

Vorhergehender Fachbegriff: Knappschaftsversicherung | Nächster Fachbegriff: Knebelvertrag

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Treppenumlageverfahren | Geplanter Bruttogewinn | POSDCORB-Modell

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer