Knapsack-Problem: Unterschied zwischen den Versionen
| [unmarkierte Version] | [gesichtete Version] |
Joos (Diskussion | Beiträge) |
(→Vorlesung) |
||
| (3 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 19: | Zeile 19: | ||
==Beispiel== | ==Beispiel== | ||
b=40 | b=40 | ||
| − | + | ||
| + | {| class="center" | ||
| + | | [[bild:Tabelle1.jpg]] | ||
| + | |- | ||
| + | |''Tabelle. 1'' | ||
| + | |} | ||
| + | |||
Zunächst ist alle Quotienten a<sub>j</sub> / c<sub>j</sub> zu bilden. Dieser Quotient gibt den Nutzen pro Kapazitätseinheit des Objekts j an. | Zunächst ist alle Quotienten a<sub>j</sub> / c<sub>j</sub> zu bilden. Dieser Quotient gibt den Nutzen pro Kapazitätseinheit des Objekts j an. | ||
| − | Die Objekte sind in absteigender Reihenfolge des Quotienten zu sortieren. | + | <br>Die Objekte sind in absteigender Reihenfolge des Quotienten zu sortieren. |
| + | |||
| + | |||
| + | {| class="center" | ||
| + | | [[bild:Tabelle2.jpg]] | ||
| + | |- | ||
| + | |''Tabelle. 2'' | ||
| + | |} | ||
| + | |||
| − | |||
| − | |||
Im Folgenden wird das Problem zunächst mit einem einfachen Entscheidungsbaumverfahren und anschließen mit dem Kaskadenbaumverfahren gelöst | Im Folgenden wird das Problem zunächst mit einem einfachen Entscheidungsbaumverfahren und anschließen mit dem Kaskadenbaumverfahren gelöst | ||
| Zeile 33: | Zeile 45: | ||
Bei diesem Verfahren wird verzweigt, indem die Variablen x<sub>j</sub> 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. | Bei diesem Verfahren wird verzweigt, indem die Variablen x<sub>j</sub> 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. | ||
| − | + | ||
| + | {| class="center" | ||
| + | | [[bild:Baum1.jpg]] | ||
| + | |- | ||
| + | |<br>''Abb. 1'' | ||
| + | |} | ||
| + | |||
| Zeile 42: | Zeile 60: | ||
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. | 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. | Im Beispiel werden zunächst die Variablen 1 gesetzt, die in der kontinuierlichen Optimallösung den Wert 0 haben. | ||
| − | + | ||
| − | + | ||
| − | + | {| class="center" | |
| − | <br> | + | | [[bild:Baum2.jpg]] |
| + | |- | ||
| + | |<br>''Abb. 2'' | ||
| + | |} | ||
| + | |||
| + | |||
Bei der ersten Verzweigung muss den Variablen x<sub>3</sub> , x<sub>4</sub> und x<sub>5</sub> abwechselnd der Wert 1 zugewiesen werden. Für den ersten Zweig wird x<sub>3</sub> = 1 gesetzt. Im zweiten Zweig wird x<sub>4</sub> der Wert 1 zugewiesen. Nun würde sich allerdings die Kombination x<sub>3</sub> = 1 und x<sub>4</sub> = 1 in beiden Zweigen befinden. Da allerdings immer disjunkte Mengen gebildet werden, wird x<sub>3</sub> = 0 gesetzt um diesem Kriterium gerecht zu werden. | Bei der ersten Verzweigung muss den Variablen x<sub>3</sub> , x<sub>4</sub> und x<sub>5</sub> abwechselnd der Wert 1 zugewiesen werden. Für den ersten Zweig wird x<sub>3</sub> = 1 gesetzt. Im zweiten Zweig wird x<sub>4</sub> der Wert 1 zugewiesen. Nun würde sich allerdings die Kombination x<sub>3</sub> = 1 und x<sub>4</sub> = 1 in beiden Zweigen befinden. Da allerdings immer disjunkte Mengen gebildet werden, wird x<sub>3</sub> = 0 gesetzt um diesem Kriterium gerecht zu werden. | ||
| − | + | ||
Der Zweig x<sub>4</sub> = 1 und x<sub>3</sub> = 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. | Der Zweig x<sub>4</sub> = 1 und x<sub>3</sub> = 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<sub>3</sub> = 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. | Alle Verzweigungen nach dem Tableu von x<sub>3</sub> = 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. | Nun werden die Variablen 0 gesetzt, die in der kontinuierlichen Optimallösung den Wert 1 haben. | ||
| − | + | ||
| − | + | ||
| − | <br> | + | {| class="center" |
| + | | [[bild:Baum3.jpg]] | ||
| + | |- | ||
| + | |<br>''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. | 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. | ||
| Zeile 62: | Zeile 91: | ||
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 [http://www.ifors.ms.unimelb.edu.au/tutorial/knapsack_new/index.html Tutorial der Universität Melbourne]. | 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 [http://www.ifors.ms.unimelb.edu.au/tutorial/knapsack_new/index.html Tutorial der Universität Melbourne]. | ||
| + | |||
| + | ==Vorlesung/Lecture== | ||
| + | Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen. | ||
| + | |||
| + | |||
| + | *[[media:Slides_08_Knapsack.wmv | Knapsack (English)]] | ||
Aktuelle Version vom 27. April 2011, 16:38 Uhr
Inhaltsverzeichnis
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 = ∑ cjxj
∑ajxj ≤ b
xj = 0 oder 1
cj = Nutzen des Objekts j
aj = 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 aj / cj 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 xj 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 x1=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 x3 , x4 und x5 abwechselnd der Wert 1 zugewiesen werden. Für den ersten Zweig wird x3 = 1 gesetzt. Im zweiten Zweig wird x4 der Wert 1 zugewiesen. Nun würde sich allerdings die Kombination x3 = 1 und x4 = 1 in beiden Zweigen befinden. Da allerdings immer disjunkte Mengen gebildet werden, wird x3 = 0 gesetzt um diesem Kriterium gerecht zu werden.
Der Zweig x4 = 1 und x3 = 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 x3 = 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.
