Knapsack-Problem

Einführung

Beim Knapsack-Problem (auch Rucksackproblem) wird aus einer Gesamtmenge von Objekten, die jeweils eine bestimmte Kapazität beanspruchen und einen bestimmten Nutzwert haben, die Teilmenge ausgewählt, die den höchsten Nutzen aufweist und die vorgegebene Kapazität nicht überschreitet.
Der Name Rucksackproblem entstammt folgendem Beispiel:
Ein Wanderer möchte die bevorstehende Tour einen Rucksack packen. Ihm stehen dabei verschiedene Gegenstände (z.B.: Schlafsack, Campingkocher, Zahnbürste, Dosenwurst) zur Verfügung, die einen bestimmten Nutzwert und ein bestimmtes Gewicht aufweisen (Eine entsprechende metrische Messung des Nutzwertes sei unterstellt; das Volumen der Gegenstände wird nicht berücksichtigt). Allerdings darf der Rucksack ein bestimmtes Gewicht (z.B. 20kg) nicht überschreiten. Der Wanderer muss also eine Auswahl treffen, da er nicht alle Gegenstände mitnehmen kann. Natürlich möchte er dabei seinen Nutzen maximieren.

formale Darstellung

Max z = ∑ c_jx_j
∑a_jx_j ≤ b
x_j = 0 oder 1
c_j = Nutzen des Objekts j
a_j = benötigte Kapazität des Objekts j
b = vorhandene Kapazität

Beispiel

                                b=40

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle. 1

Zunächst ist alle Quotienten a_j / c_j zu bilden. Dieser Quotient gibt den Nutzen pro Kapazitätseinheit des Objekts j an.
Die Objekte sind in absteigender Reihenfolge des Quotienten zu sortieren.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Tabelle. 2

Im Folgenden wird das Problem zunächst mit einem einfachen Entscheidungsbaumverfahren und anschließen mit dem Kaskadenbaumverfahren gelöst

Entscheidungsbaumverfahren nach Kolesar

Bei diesem Verfahren wird verzweigt, indem die Variablen x_j absteigend gleich 0 und gleich 1 gesetzt werden. Es wird zunächst bei der Lösung weiterverzweigt, die den höheren Zielfunktionswert liefert. Ist der Zielfunktionswert kleiner, als der Wert, den die bis dahin beste ganzzahlige Lösung liefert, wird nicht weiterverzweigt.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1

Wenn x₁=0 gesetzt wird beträgt z=5,66. An dieser Stelle wird nicht weiterverzweigt, da dieser Wert kleiner als 6, dem Wert der besten ganzzahligen Lösung, ist und der Zielfunktionswert bei jeder Verzweigung kleiner wird oder höchstens gleich bleibt.

Kaskadenbaumverfahren nach Müller-Merbach

Die Tableaus des Kaskadenbaums zwei Spalten auf. In der Linken steht die kontinuierliche Lösung. In der Rechten wird die ganzzahlige Lösung, durch Nullsetzen der maximal einen kontinuierlichen Variablen (Wert ungleich 0 oder 1)1 bestimmt. Gegebenenfalls wird diese Lösung durch weitere Variablen, deren benötigte Kapazität geringer ist als die Restkapazität, aufgefüllt. Die linke Seite bestimmt die Obergrenze, die weiteren (von diesem Tableau ausgehend) Lösungen nicht überschreiten können. Von der rechten Spalte ausgehend wird in disjunkte Teilmengen (Mengen ohne gemeinsame Elemente) weiterverzweigt. Dies geschieht im Gegensatz zum ersten Verfahren allerdings nicht dadurch, dass die Variablen nacheinander Gleich 0 und 1 gesetzt werden, sondern indem alle Variablen, die in der Lösung den Wert 1 (0) hatten, den Wert 0 (1) zugewiesen bekommen. Im Beispiel werden zunächst die Variablen 1 gesetzt, die in der kontinuierlichen Optimallösung den Wert 0 haben.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2

Bei der ersten Verzweigung muss den Variablen x₃ , x₄ und x₅ abwechselnd der Wert 1 zugewiesen werden. Für den ersten Zweig wird x₃ = 1 gesetzt. Im zweiten Zweig wird x₄ der Wert 1 zugewiesen. Nun würde sich allerdings die Kombination x₃ = 1 und x₄ = 1 in beiden Zweigen befinden. Da allerdings immer disjunkte Mengen gebildet werden, wird x₃ = 0 gesetzt um diesem Kriterium gerecht zu werden.

Der Zweig x₄ = 1 und x₃ = 0 wird nicht weiter verfolgt, da sein Zielfunktionswert 6,1 ist. Weitere Tableus können nur Werte annehmen die kleiner (und zwar um mindestens eine Dezimalstelle, da der Nutzten der Objekte maximal eine aufweist) sind als dieser.

Alle Verzweigungen nach dem Tableu von x₃ = 1 sind deshalb gestrichelt dargestellt, da sie folgende Überlegung überflüssig macht: Die Nachkommastellen des Nutzen der Objekte sind gerade. Deshalb können die nachfolgenden Tableaus maximal einen Nutzwert aufweisen, der um 0,2 geringer ist als 6,2, also maximal 6. Das ist allerdings schon der Nutzwert der besten ganzzahligen Lösung.

Nun werden die Variablen 0 gesetzt, die in der kontinuierlichen Optimallösung den Wert 1 haben.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3

Man erkennt, dass man mit diesem Ansatz wesentlich schneller zur Optimallösung kommt. Desshalb sollten, wenn in der Optimallösung mehr Variablen den Wert 1 annehmen, als den Wert 0, zunächst die "0-Variablen" gleich 1 gesetzt werden. Ansonsten sollten die "1-Variablen" gleich 0 gesetzt werden.

Tutorial

Wenn Sie sich eingehender mit dem Thema beschäftigen möchten und Knapsack-Probleme am Computer lösen wollen, so können Sie dies mit einem Tutorial der Universität Melbourne.

Vorlesung/Lecture

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

• Knapsack (English)