Titelaufnahme

Titel
Social Choice Methoden zur Lösung von mehrdimensionalen Rucksackproblemen / Christoph Schury
Verfasser/ VerfasserinSchury, Christoph
Begutachter / BegutachterinPferschy Ulrich
Erschienen2013
UmfangIV, 55 Bl. : 2 Zsfassungen
HochschulschriftGraz, Univ., Masterarb., 2013
Anmerkung
Zsfassung in dt. und engl. Sprache
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Rucksackproblem / Kollektiventscheidung / Rucksackproblem / Kollektiventscheidung / Online-Publikation
URNurn:nbn:at:at-ubg:1-47652 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Social Choice Methoden zur Lösung von mehrdimensionalen Rucksackproblemen [0.39 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Das mehrdimensionale Rucksackproblem ist ein einfaches Optimierungsmodell der kombinatorischen Optimierung, bei dem auf Basis von mehreren vorgegebenen Restriktionen eine Teilmenge an Gegenständen zur Maximierung des Zielfunktionswertes ausgewählt wird. In der Literatur wurden zur Lösung dieser Probleme bisher eine Vielzahl an approximativen Algorithmen vorgestellt. Bekannte Vertreter dieser Approximationsverfahren waren beispielsweise Dobson (1982), Senju und Toyoda (1968) sowie Loulou und Michaelides (1979). Ihre Greedy-Verfahren ermitteln in überschaubarer Zeit brauchbare Annäherungen an den optimalen Zielfunktionswert. Völlig gegensätzlich hierzu werden auch Social Choice Methoden als Lösungsverfahren für Rucksackprobleme verwendet. Dabei verwaltet ein Individuum jeweils eine Ressource und reiht die Gegenstände anhand der Effizienz. Haben alle Individuen diese Reihung vorgenommen, erfolgt die Stimmenvergabe für jeden Gegenstand und die finale Sortierung für das Einpacken des Rucksacks. Bekannte Methoden sind beispielsweise Single-Vote, Borda-Vota oder auch Approval-Vote. In der vorliegenden Arbeit wird nun geklärt, welches der vielen Verfahren für das mehrdimensionale Rucksackproblem die höchste Maximierung erzielt. Hierfür werden die Testinstanzen von Chu und Beasley (1998) herangezogen und mit den Greedy-Verfahren sowie Social Choice Methoden getestet. Grundsätzlich ist erkennbar, dass die Greedy-Verfahren im Gesamten bessere Ergebnisse liefern, als die Verfahren der Social Choice Methoden. Lediglich Borda-Vota ist konkurrenzfähig und erzielt aufgrund der vollständigen Präferenzordnung der Individuen gute Resultate. Eine eindeutige Tendenz für die verschiedenen Variablen- und Restriktionskombinationen gibt es bei keinen einzigen Verfahren, vielmehr hängen die Zielfunktionswerte und die Häufigkeit der besten Zielfunktionswerte stark von den zu Grunde liegenden Testinstanzen ab, weshalb es kein Universalverfahren gibt.

Zusammenfassung (Englisch)

The multidimensional knapsack problem is known as a simple combinatorial optimization model, which packs a subset of items into a restricted knapsack to maximize the target value. It can be applied on real-life problems e.g. transportation and logistics problems, portfolio problems and of course production scheduling problems to solve them in a fast and appropriate way. In literature the multidimensional knapsack problem is known quite well, especially approximate greedy algorithms from Dobson (1982), Senju and Toyoda (1968) as well as from Loulou und Michaelides (1979) are applied rather often and determine the target value. In contrast to these greedy algorithms also social choice methods like single vote, borda vota or approval vote generate acceptable results for multidimensional knapsack problems. There individuals manage a resource on their own and sort the items on the basis of their efficiency. Afterwards a collective subset of items is identified and being packed into the knapsack. This paper will now clarify the question which of the above mentioned algorithms maximizes the test instances of Chu and Beasly (1998) at most. Basically greedy algorithms generate better results than social choice methods do, except of borda vote, which includes all individual preferences and therefore has a high target value. All in all there is no significant tendency for all variable and resource combinations, because the results of each method is strongly determined by the test instances and a universal method is hardly to name. For the selection of a method the trade-off between accuracy and velocity is relevant.