Ungarische Methode

Aufgabenstellung

Es sind zwei Gruppen von Objekten gegeben, meist gleichgroß und grob als „Quellen“ S und „Ziele“ T bezeichnet, zwischen denen eine eineindeutige Zuordnung herzustellen ist, d. h. jeder Quelle wird höchstens ein Ziel und jedem Ziel höchstens eine Quelle zugeordnet. Dabei hat jede (zulässige) Zuordnung einer „Quelle“ zu einem „Ziel“ einen Preis oder einen Gewinn. Das Ziel des Algorithmus ist es, je nach Problemtyp, den Gesamtpreis (= Summe der Einzelpreise) zu minimieren oder den Gesamtgewinn (= Summe der Einzelgewinne) zu maximieren. Dabei ist immer eine maximale Anzahl an Paaren zu bilden.

Übliche Beispiele sind

• das Heiratsproblem, bei dem die zwei Gruppen aus heiratswilligen Frauen bzw. Männern bestehen und einer Verbindung ein „Sympathiemaß“ als Gewinngröße zugeordnet wird. Ziel ist dann, möglichst viele Paare bei einer maximalen „Sympathiesumme“ zu finden.
• das Auktionsmodell, bei dem eine Anzahl Kunstgegenstände auf eine gleiche Anzahl Kunstliebhaber zu verteilen ist, wobei jeder Kunstliebhaber zu den ihn interessierenden Gegenständen eine Preisvorstellung hat. Ziel der Auktion ist es, einen maximalen Gesamtpreis zu erzielen.
• das Jobproblem, worin eine Anzahl von Arbeitsaufträgen auf eine gleiche Anzahl Arbeiter oder Maschinen zu verteilen ist. Dabei kann die Bewertung entweder die Eignung eines Arbeiters für den Auftrag darstellen, oder die Kosten, einen Auftrag auf einer Maschine auszuführen.

Es gibt zwei äquivalente abstrakte Modellierungen des Zuordnungsproblems. Zum einen können Quellen und Ziele als Knoten eines bipartiten Graphen aufgefasst werden, dessen Kanten die zulässigen Zuordnungen sind. Jede Kante wird mit der Bewertung dieser Zuordnung gewichtet.

Eine zweite Darstellung sammelt die Daten des Zuordnungsproblems in einer quadratische Matrix. Jeder Zeile entspricht dabei eine Quelle, jeder Spalte ein Ziel (oder umgekehrt), und jede Matrixkomponente enthält die Bewertung der Zuordnung ihrer Quelle zu ihrem Ziel. Diese Matrix ist gleichzeitig auch eine gewichtete Adjazenzmatrix des kantengewichteten bipartiten Graphen. Fehlende Kanten des Graphen, d. h. unzulässige Zuordnungen, werden durch sehr kleine negative Zahlen oder den künstlichen Wert in der Matrix dargestellt.

Es gibt aber auch Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt: n Mitarbeiter machen k Eignungstests für k zu besetzende Positionen (k < n). In diesen Fällen löst man das Problem entweder durch einen graphentheoretische Version der Ungarischen Methode. Man kann aber auch die Matrix künstlich quadratisch machen, indem n - k Dummy-Positionen („keine Position“) eingeführt werden. Dummy-Positionen werden üblicherweise mit lauter Nullen oder negativen Werten besetzt.

Ist eine maximale Zuordnung (maximales Matching) gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört. Deshalb kann die Problemstellung auch anders formuliert werden: Ordne die Zeilen-/Spaltenvektoren so um, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer n×n-Matrix genau n! Möglichkeiten gibt, die Zeilen-/Spaltenvektoren zu ordnen und dass es außer bei kleinen Matrizen nahezu aussichtslos ist, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es an die 3,63 Millionen zulässiger Lösungen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ungarische Methode aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung