Das Knapsack – bzw. Rucksackproblem ist ein klassisches Optimierungsproblem der Kombinatorik, in anderen Worten: Die Qual der Wahl bei zu vielen Möglichkeiten.
Man stellt sich vor, einen Rucksack zu haben, der höchstens ein bestimmtes vorgegebenes Gewicht T trägt. T wird als Gewichtsschranke bezeichnet. Neben dem Rucksack gibt es eine Menge von n Objekten, die jeweils ein Gewicht und einen Nutzen haben. Gesucht wir eine nutzenmaximale Teilmenge der Objekte, die man in den Rucksack packen kann, ohne die Gewichtsschranke T zu überschreiten.
Intuitiv erscheint es sinnvoll, diejenigen Objekte zuerst auszuwählen, die den größten Nutzen pro Gewichtseinheit stiften. Dieses Verhältnis zwischen Nutzen und Gewicht lässt sich als Nutzendichte bezeichnen.
Um mit Sicherheit die beste Lösung zu finden, probiert man einfach alle möglichen Kombinationen aus. Allerdings gibt es sehr viele derartiger Kombinationsmöglichkeiten. Für jedes Objekt ist zu entscheiden, ob es in den Rucksack gepackt wird oder nicht. Hat man beispielsweise acht Gegenstände zur Auswahl, ergeben sich 28 = 256 Kombinationen, die überprüft werden müssen.
Folgende Grundidee liefert einen effizienteren Algorithmus als das Probieren: Eine Teilmenge von Objekten kann nicht optimal sein, wenn es eine andere Teilmenge gibt, die leichter – oder gleich schwer – ist und gleichzeitig einen größeren Nutzen hat. Eine solche Lösung wäre unabhängig von der Gewichtsschranke immer besser. Derartige Teilmengen werden Pareto – optimal genannt.
Mit Hilfe der dynamischen Optimierung, einer Methode des Operations Research, löst man dieses Problem als ein mehrstufiges Entscheidungsproblem.
Das Knapsack – Problem lässt sich auf die Investitionsprogrammplanung anwenden: Aus einer Menge nutzbringender Investitionsobjekte ist diejenige Teilmenge zu bestimmen, die den höchsten Gesamtnutzen stiftet, ohne eine Reihe vorgegebener Kapazitäts – Restriktionen zu verletzen.
Posts
Keine Kommentare:
Kommentar veröffentlichen