Die ungarische Methode - ein Algorithmus für Bipartite Matchings

ISBN-13: 9783640938087 / Niemiecki / Miękka / 2011 / 76 str.

Meike Vo

Opis

Bachelorarbeit aus dem Jahr 2010 im Fachbereich Mathematik - Angewandte Mathematik, Note: 2,3, Technische Universitat Carolo-Wilhelmina zu Braunschweig, Sprache: Deutsch, Abstract: Diese Bachelorarbeit beschaftigt sich mit der ungarischen Methode, bzw. dem ungarischen Algorithmus. Dieser Algorithmus stammt aus dem Bereich der Graphentheorie. Genauer gesagt lasst er sich der linearen Optimierung zuordnen. Der ungarische Algorithmus ist eine Methode zur Losung von ungewichteten und gewichteten Zuordnungsproblemen in bipartiten Graphen. In dieser Arbeit werde ich mich aber ausschlielich mit dem ungarischen Algorithmus fur ungewichtete Graphen beschaftigen. Alle genannten Begriffe werden im Laufe dieser Arbeit geklart. Da die Optimierungsprozesse mich im Studium sehr interessiert haben, entschied ich mich fur ein Thema aus diesem Bereich. Besonders interessant ist, dass sich die teilweise komplexen Probleme und deren Losungen sehr gut durch Beispiele aus dem Alltag veranschaulichen lassen. So ist es auch mit dem ungarischen Algorithmus. Er liefert in einem ungewichteten Graphen die grotmogliche Zuordnung und in einem gewichteten Graphen die Zuordnung mit der besten Bewertung. Ein Beispiel fur eine solche Art von Zuordnung ist, die Paarung von Arbeitssu-chenden zu freien Arbeitsplatzen, wobei jeder Arbeitssuchende fur eine bestimmte Anzahl von Arbeitsplatzen qualifiziert ist. Auch die Zuordnung von Maschinen zu bestimmten Standorten lasst sich unter diesen Bereich fassen. Hierbei wird angestrebt, die Kosten, die bei dem Transport einer Maschine zu einem Standort entstehen, moglichst gering zu halten. Das wohl bekannteste Beispiel ist aber die Zuordnung von Damen zu heiratswilligen Herren. Dabei soll eine derartige Paarung gefunden werden, sodass alle, bzw. moglichst viele, Damen einen Herren heiraten, der ihnen gefallt. Hierauf werde ich spater noch genauer eingehen, wenn ich zu dem sogenannten Heiratssatz komme, der von dem Englander Philip Hall entwickelt wurde.