| Die ungarische Methode - ein Algorithmus für Bipartite Matchings Contributor(s): Voß, Meike (Author) |
|
 |
ISBN: 3640938089 ISBN-13: 9783640938087 Publisher: Grin Verlag OUR PRICE: $40.76 Product Type: Paperback Language: German Published: June 2011 |
| Additional Information |
| BISAC Categories: - Mathematics | Reference - Mathematics | Applied |
| Physical Information: 0.18" H x 5.83" W x 8.27" (0.24 lbs) 76 pages |
| Descriptions, Reviews, Etc. |
| Publisher Description: Bachelorarbeit aus dem Jahr 2010 im Fachbereich Mathematik - Angewandte Mathematik, Note: 2,3, Technische Universit t Carolo-Wilhelmina zu Braunschweig, Sprache: Deutsch, Abstract: Diese Bachelorarbeit besch ftigt sich mit der ungarischen Methode, bzw. dem ungarischen Algorithmus. Dieser Algorithmus stammt aus dem Bereich der Graphentheorie. Genauer gesagt l sst er sich der linearen Optimierung zuordnen. Der ungarische Algorithmus ist eine Methode zur L sung von ungewichteten und gewichteten Zuordnungsproblemen in bipartiten Graphen. In dieser Arbeit werde ich mich aber ausschlie lich mit dem ungarischen Algorithmus f r ungewichtete Graphen besch ftigen. Alle genannten Begriffe werden im Laufe dieser Arbeit gekl rt. Da die Optimierungsprozesse mich im Studium sehr interessiert haben, entschied ich mich f r ein Thema aus diesem Bereich. Besonders interessant ist, dass sich die teilweise komplexen Probleme und deren L sungen sehr gut durch Beispiele aus dem Alltag veranschaulichen lassen. So ist es auch mit dem ungarischen Algorithmus. Er liefert in einem ungewichteten Graphen die gr tm gliche Zuordnung und in einem gewichteten Graphen die Zuordnung mit der besten Bewertung. Ein Beispiel f r eine solche Art von Zuordnung ist, die Paarung von Arbeitssu-chenden zu freien Arbeitspl tzen, wobei jeder Arbeitssuchende f r eine bestimmte Anzahl von Arbeitspl tzen qualifiziert ist. Auch die Zuordnung von Maschinen zu bestimmten Standorten l sst sich unter diesen Bereich fassen. Hierbei wird angestrebt, die Kosten, die bei dem Transport einer Maschine zu einem Standort entstehen, m glichst 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. m glichst viele, Damen einen Herren heiraten, der ihnen gef llt. Hierauf werde ich sp ter noch genauer eingehen, wenn ich zu dem sogenannten Heiratssatz komme, der von dem Engl nder Philip Hall entwickelt wurde. |