Title: Auktionsalgorithmus zum Lösen von Zuordnungsproblemen
Other Titles: Auction algorithm for solving assignment problems
Language: Deutsch
Authors: Fabi, Katharina 
Qualification level: Diploma
Advisor: Mehlmann, Alexander
Issue Date: 2010
Number of Pages: 95
Qualification level: Diploma
Abstract: 
In dieser Diplomarbeit wird das Zuordnungsproblem betrachtet.
Bei diesem Problem werden Personen und Objekte einander zugeordnet und Preise bzw.
Profite ermittelt. Dimitri P. Bertsekas hat einen sehr nützlichen Algorithmus konstruiert, der diese Art von Problemen löst.
Der einfachste Spezialfall ist das symmetrische Zuordnungsproblem, wobei es gleich viele Objekte wie Personen gibt, die einander zugeordnet werden sollen.
In einer naiven Weise wird ein Algorithmus hergeleitet, der einen schweren Fehler beinhaltet. Für eine große Gruppe von Beispielen erzeugt dieser Algorithmus eine Endlosschleife. Daher wird die sogenannte epsilon-komplementäre Schlupfbedingung eingeführt. Mit dieser zusätzlichen Bedingung wird ein Algorithmus kreiert, der jegliche zulässige symmetrische Zuordnungsprobleme löst.
Durch Betrachten des Problems aus einer anderen Perspektive wird ein zweiter Algorithmus hergeleitet, der die Zuordnung und den Profit jeder Person bestimmt. Dieser Algorithmus wird als Rückwärtsauktion bezeichnet, da er das Problem umgekehrt löst.
Nachdem beide Algorithmen dasselbe Problem lösen, werden diese beiden in einem dritten Schritt kombiniert und dadurch ein neuer Algorithmus gebildet, der später auf eine größere Bandbreite an Problemen adaptiert werden kann. Durch die Anwendung von Graphentheorie und Dualität können asymmetrische Probleme derart transformiert werden, sodass es möglich ist den Auktionsalgorithmus auf diese Probleme anzupassen. Allerdings müssen neue komplementäre Schlupfbedingungen eingeführt werden, um dies zu ermöglichen. Auf diese Art und Weise können auch asymmetrische und Mehrfachzuordnungsprobleme mit Hilfe eines angepassten Auktionsalgorithmus gelöst werden.
Keywords: Auktionsalgorithmus; Auktion; Bertsekas; Zuordnungsproblem
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-41782
http://hdl.handle.net/20.500.12708/11691
Library ID: AC07808535
Organisation: E105 - Institut für Wirtschaftsmathematik 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

14
checked on May 27, 2021

Download(s)

69
checked on May 27, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.