Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse kann als Spezialfall der Linearen Optimierung formuliert werden, die ungarische Methode ist dann eine angepasste primal-duale Lösungsmethode. Die originale Implementierung hatte eine Komplexität von , durch geeignete Datenstrukturen und optimierte Unterroutinen konnte diese aber auf gesenkt werden.
Die Ungarische Methode wurde 1955 von Harold W. Kuhn unter Einbeziehung vorheriger Ideen der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry entwickeltH. W. Kuhn (1955): The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, S. 83–97. und von James Munkres 1957, einer Analyse der Laufzeit folgend, verbessert.J. Munkres (1957): Algorithms for the Assignment and Transportation Problems, Journal of the Society of Industrial and Applied Mathematics, Vol. 5 Nr. 1, S. 32–38.
Das Zuordnungsproblem wurde schon im 19. Jahrhundert von Carl Gustav Jacob Jacobi gelöst. Die Lösung wurde im Jahr 1890 veröffentlicht.Carl Gustav Jacob Jacobi: De investigando ordine systematis æquationum differentialium vulgarium cujuscunque
Aufgabenstellung
Es sind zwei Gruppen von Objekten gegeben, meist gleicher Anzahl und grob als „Quellen“ S (nach engl.: „source“) und „Ziele“ T (nach engl.: „target“) 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“ s zu einem „Ziel“ t einen Preis oder einen Gewinn c(s,t). Das Ziel des Algorithmus ist es, je nach Problemtyp, den Gesamtpreis (= Summe der Einzelpreise) der Zuordnung zu minimieren oder den Gesamtgewinn (= Summe der Einzelgewinne) der Zuordnung zu maximieren. Dabei ist immer eine maximale Anzahl an Paaren zu bilden.
Anschauliche Beispiele Ü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 oder sonstigen Waren auf eine gleiche Anzahl Kunstliebhaber oder allgemeiner Käufer 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. Auch zur Lösung einiger Fälle des Briefträgerproblems (chinese postman problem) kann die Ungarische Methode eingesetzt werden.
Mathematische Modellierung 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 quadratischen 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.
Unterschiedliche Anzahl von Quellen und Zielen Es gibt aber auch Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt: Mitarbeiter machen Eignungstests für zu besetzende Positionen (). In diesen Fällen löst man das Problem entweder durch die graphentheoretische Version der Ungarischen Methode oder man macht die Matrix künstlich quadratisch, indem Dummy-Positionen („keine Position“) eingeführt werden. Dummy-Positionen werden üblicherweise mit der größten vorhandenen Zahl aus der Matrix besetzt.WikiHow.com: https://www.wikihow.com/Use-the-Hungarian-Algorithm
Matrix-Transversale 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, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. Deshalb kann die Problemstellung auch anders formuliert werden: Ordne die Zeilen- oder die Spaltenvektoren so um, dass die Summe der Elemente in der Hauptdiagonale maximal wird. Hieraus wird sofort ersichtlich, dass es in einer ×-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von n Elementen gibt, also . Außer bei kleinen Matrizen ist es nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer 10×10-Matrix gibt es nahezu 3,63 Millionen (3.628.800) zu berücksichtigender Permutationen.
11 Rechenschritte ohne Formeln
Wird ein Minimum gesucht (wie in den Beispielen unten), dann überspringe diesen Schritt. Finde die „größte Zahl“ in der Matrix. Bilde eine neue Matrix und befülle sie mit den Differenzen aus der „größten Zahl“ und dem alten Element an dieser Stelle. Wenn kein Fehler gemacht wurde, so hat die neue Matrix nur positive Werte, und an den Stellen, an denen die „größte Zahl“ stand, stehen nun Nullen. Bilde die Spaltenminima (s. Beispiel 1 Matrix 1). Subtrahiere von jedem Element einer Spalte das jeweilige Spaltenminimum (s. Beispiel 1 Matrix 2). Bilde die neuen Zeilenminima. Subtrahiere von jedem Element einer Zeile das jeweilige Zeilenminimum (s. Beispiel 1 Matrix 3). Suche eine Kombination von Nullen derart, dass in jeder Zeile und in jeder Spalte genau eine Null ausgewählt ist. Dazu ein Tipp: Steht in einer Zeile oder Spalte nur eine einzige Null, so muss sie natürlich in die Lösung. Markiere zuerst diese Nullen, dann findet man den Rest der zulässigen Zuordnungen etwas leichter. Gibt es eine solche Kombination von Nullen, repräsentieren die Plätze der Nullen dieser Kombination die optimalen Zuordnungen, und das Verfahren ist beendet. (Das ist in Beispiel 1 der Fall, weshalb sich in Beispiel 1 die nun folgenden Rechenschritte erübrigen). Gibt es keine solche Kombination von Nullen, weil in bestimmten Zeilen oder Spalten keine Nullen gefunden werden können, die die Bedingung des Punktes 6 nicht verletzen, dann finde die minimale Zahl an (horizontalen und vertikalen) Linien, mit welchen sämtliche Nullen der Matrix gestrichen werden können. Wenn dabei in einer -Matrix wenigstens Striche erforderlich sind, um alle Nullen zu streichen, dann steht in dieser Matrix bereits die optimale Lösung. Finde das Minimum der Koeffizienten, die nicht gestrichen sind. Nun wird eine neue -Matrix angefertigt und die Koeffizienten aus der Ursprungsmatrix übertragen. Koeffizienten, die durch genau eine Linie gestrichen worden waren, sind dabei unverändert in die neue Matrix zu übernehmen. Bei zuvor nicht gestrichenen Koeffizienten ist dabei das im vorherigen Punkt ermittelte Minimum zu subtrahieren. Ist ein Koeffizient dagegen durch zwei Linien gestrichen, so ist das zuvor ermittelte Minimum zu addieren. Gehe zu Punkt 6, transformiere die Matrix und versuche erneut, eine zulässige Kombination von Nullen in der neuen Matrix zu finden.
Bemerkung: Aus Symmetriegründen sind in den Punkten 2 bis 5 die Begriffe „Zeilen“ und „Spalten“ gegeneinander austauschbar.
Beispiel 1 Vater vernimmt Streit aus dem Kinderzimmer. Seine vier Kinder Anna, Berta, Chiara und David zanken sich wieder einmal um die Spielsachen: Eisenbahn, Kaufmannsladen, Puppe und den Zoo. Da es zu keiner friedlichen Einigung kommt, schreitet Vater ein und befragt die Kinder nach der Rangordnung ihrer Vorlieben bezüglich der vier Spielzeuge. Aus diesen Rangordnungen bildet Vater eine 4×4-Matrix und versucht, durch geschickte Zuordnung der Spielzeuge zu den Kindern die „Summe der Tränen“ zu minimieren. Er kann sich bei diesem Vorhaben der Ungarischen Methode bedienen, wie folgende Abbildung zeigt.
Zeilen: Spielzeuge E, K, P und Z
Spalten: Kinder A, B, C und D
Spaltenelemente: Rangordnung der Vorlieben der Kinder A, B, C, D für Spielzeuge E, K, P, Z: 1 bedeutet höchste, 4 bedeutet geringste Vorliebe.
+ Rangordnung der Präferenzen A B C D min E 1 1 1 2 1 K 3 2 4 1 1 P 4 4 2 4 2 Z 2 3 3 3 2 min 1 1 1 1
+ Reduktion der Spaltenelemente um das Spaltenminimum A B C D min E 0 0 0 1 0 K 2 1 3 0 0 P 3 3 1 3 1 Z 1 2 2 2 1 min 0 0 0 0
+ Reduktion der Zeilenelemente um das Zeilenminimum A B C D min E 0 0 0 1 0 K 2 1 3 0 0 P 2 2 0 2 0 Z 0 1 1 1 0 min 0 0 0 0
+ optimale Zuordnung Kind Spielzeug Präferenz A Z 2 B E 1 C P 2 D K 1
Die optimale Zuordnung der Spielzeuge zu den Kindern, die die „Gesamtfrustration“ im Kinderzimmer minimiert, lautet:
Anna bekommt den Zoo, Berta die Eisenbahn, Chiara die Puppe, David spielt mit dem Kaufmannsladen.
In diesem Fall wäre jede alternative Zuordnung schlechter.
Die ideale Rangsumme wäre 4, wenn jedes Kind sein Lieblingsspielzeug bekäme. Diese Zuordnung ist aber nicht möglich, sonst hätte es keinen Streit gegeben. Das ginge nur, wenn in jeder Zeile und Spalte der Ausgangsmatrix nur je eine 1 stünde. Die minimale Rangsumme beträgt daher 6.
Beispiel 2 Gegeben sind vier Aufträge und vier Personen. Jeder Auftrag soll genau einer Person zugeordnet werden. Dabei fallen Kosten oder Zeitaufwand an. Die Zuordnungen sollen so vorgenommen werden, dass diese Aufwände minimiert werden. Eine Firma besitzt vier verschiedene Maschinen M1, M2, M3, M4. Jede Maschine kann einen von vier Aufträgen A1, A2, A3, A4 ausführen. Der Zeitaufwand für jede Maschine und jeden Auftrag sei bekannt. Die Zuordnung der Maschinen zu den Aufträgen soll die Gesamtzeit minimieren.
Um die Ungarische Methode auf diese Aufgabenstellung anzuwenden, erstellt man eine Matrix mit den Kosten. In diesem sind dies die Zeitaufwände für jeden Auftrag:
A1 A2 A3 A4 min M1 14 5 8 7 M2 2 12 6 5 M3 7 8 3 9 M4 2 4 6 10 min Subtrahiert man die Mindestzeiten aus jeder Zeile, dann erhält man die folgende Matrix. Die Summe der Zeiten beträgt 12 Minuten, das bisherige Minimum. A1 A2 A3 A4 min M1 9 0 3 2 5 M2 0 10 4 3 2 M3 4 5 0 6 3 M4 0 2 4 8 2 min 12 Wenn man sich die Zeilen ansieht, scheint es so, als würde die Bearbeitung von Auftrag 4 unabhängig davon, welcher Maschine er zugewiesen wird, jeweils zusätzlich 2 Minuten dauern. Daher wird der niedrigste Wert jeder Spalte unten notiert und die Differenz zwischen den Spalten berechnet (in diesem Fall nur Spalte 4). Man addiert die beiden Werte zu 12 und erhalten 14. Das bedeutet, dass die Bearbeitung der Aufträge unabhängig von der Zuweisung mindestens 14 Minuten dauern wird. A1 A2 A3 A4 min M1 9 0 3 0 5 M2 0 10 4 1 2 M3 4 5 0 4 3 M4 0 2 4 6 2 min 0 0 0014 Die minimale Anzahl an horizontalen oder vertikalen Linien, mit denen alle Nullen der Matrix gestrichen werden können, ist drei. A1 A2 A3 A4 min M1 9 0 3 0 5 M2 0 10 4 1 2 M3 4 5 0 4 3 M4 0 2 4 6 2 min 0 0 0014 Aus den verbleibenden, nicht abgedeckten Einträgen ergibt sich eine minimale zusätzliche Zeit von 1 Einheit. Daher subtrahiert man diese von den Zeilen 2, 3 und 4 und addiert sie zur Spalte ganz rechts. A1 A2 A3 A4 min M1 9 0 3 0 5 M2 −1 9 3 0 3 M3 3 4 −1 3 4 M4 −1 1 3 5 3 min 0 0 0017 Leider ergibt das Subtrahieren von 1 einige negative Zeitwerte. Man addiert 1 in den Spalten 1 und 4. Dadurch steigt die Mindestzeit auf 15. A1 A2 A3 A4 min M1 10 0 4 0 5 M2 0 9 4 0 3 M3 4 4 0 3 4 M4 0 1 4 5 3 min −1 0 −1215 Folgendes Endergebnis ergibt sich beim Übergang von der Ausgangsmatrix zur endgültigen Matrix nach Addition und Subtraktion des Minimalwerts: