Empfehlungen
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z  
  Home Top 10 Fachbereiche News Hilfe & FAQ
 

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 : Informationsselektierer | Rohstofftermingeschäfte | Arbeitsformen

   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

   Beliebte Artikel

Bestimmte Erklärungen und Begriffsdefinitionen erfreuen sich bei unseren Lesern ganz besonderer Beliebtheit. Diese werden mehrmals pro Jahr aktualisiert.

  Cash Flow

  Bausparen

  Fremdwährungskonto


     © 2015 Wirtschaftslexikon24.com       All rights reserved.      Home  |  Datenschutzbestimmungen  |  Impressum  |  Rechtliche Hinweise
Aktuelles Wirtschaftslexikon