Title: Auktionsalgorithmus zum Lösen von Zuordnungsproblemen
Language: Deutsch
Authors: Fabi, Katharina 
Qualification level: Diploma
Keywords: Auktionsalgorithmus; Auktion; Bertsekas; Zuordnungsproblem
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.
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:

File Description SizeFormat
Auktionsalgorithmus zum Loesen von Zuordnungsproblemen.pdf729.69 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

16
checked on Feb 18, 2021

Download(s)

69
checked on Feb 18, 2021

Google ScholarTM

Check


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