<div class="csl-bib-body">
<div class="csl-entry">Fabi, K. (2010). <i>Auktionsalgorithmus zum Lösen von Zuordnungsproblemen</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-41782</div>
</div>
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description.abstract
In dieser Diplomarbeit wird das Zuordnungsproblem betrachtet.<br />Bei diesem Problem werden Personen und Objekte einander zugeordnet und Preise bzw.<br />Profite ermittelt. Dimitri P. Bertsekas hat einen sehr nützlichen Algorithmus konstruiert, der diese Art von Problemen löst.<br />Der einfachste Spezialfall ist das symmetrische Zuordnungsproblem, wobei es gleich viele Objekte wie Personen gibt, die einander zugeordnet werden sollen.<br />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.<br />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.<br />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.
de
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Auktionsalgorithmus
de
dc.subject
Auktion
de
dc.subject
Bertsekas
de
dc.subject
Zuordnungsproblem
de
dc.title
Auktionsalgorithmus zum Lösen von Zuordnungsproblemen