Bibliographic Metadata

Title
Auktionsalgorithmus zum Lösen von Zuordnungsproblemen / von Katharina Fabi
AuthorFabi, Katharina
CensorMehlmann, Alexander
Published2010
DescriptionII, 95 S. : graph. Darst.
Institutional NoteWien, Techn. Univ., Dipl.-Arb., 2010
LanguageGerman
Document typeThesis (Diplom)
Keywords (DE)Auktionsalgorithmus / Auktion / Bertsekas / Zuordnungsproblem
URNurn:nbn:at:at-ubtuw:1-41782 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Auktionsalgorithmus zum Lösen von Zuordnungsproblemen [0.71 mb]
Links
Reference
Classification
Abstract (German)

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.