Ungarische Methode

Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Diese Problemklasse ist ein Spezialfall der Linearen Optimierung, für die Algorithmen der Größenordnung O(n³) existieren.

Die Ungarische Methode wurde 1955 von Harold W. Kuhn unter Einbeziehung vorheriger Ideen der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry entwickelt^[1] und von James Munkres 1957, einer Analyse der Laufzeit folgend, verbessert^[2].

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 $-\infty$ 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.

Typische Zuordnungsprobleme

Beispiele:

1. Hilfsverfahren für das Travelling-Salesman-Problem
2. Finden von Clustern
3. Mutung von Cliquen in soziologischen Gruppierungen

11 Rechenschritte ohne Formeln

1. 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 wo die „größte Zahl“ stand eine Null.
2. Bilde die Spaltenminima (s. Beispiel 1 Matrix 1).
3. Subtrahiere von jedem Element einer Spalte das jeweilige Spaltenminimum (s. Beispiel 1 Matrix 2).
4. Bilde die neuen Zeilenminima.
5. Subtrahiere von jedem Element einer Zeile das jeweilige Zeilenminimum (s. Beispiel 1 Matrix 3).
6. Suche eine Kombination von Nullen derart, dass in jeder Zeile und in jeder Spalte nur 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 findest du den Rest der zulässigen Zuordnungen etwas leichter.
7. 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).
8. 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 Linien, mit welchen sämtliche Nullen der Matrix gestrichen werden können (horizontale und vertikale Linien sind erlaubt). Wenn du in einer n×n-Matrix alle Nullen mit nicht weniger als n Strichen streichen kannst, dann steht in dieser Matrix bereits die Lösung; du musst sie nur finden.
9. Finde das Minimum der Koeffizienten, die nicht gestrichen sind.
10. Ist eine Zahl durch nur eine Linie gestrichen, so übernimm sie in die neue Matrix; ist eine Zahl durch zwei Linien gestrichen, so addiere das Minimum lt. Punkt 9 zu dieser Zahl und übernimm das Ergebnis in die neue Matrix; ist eine Zahl nicht gestrichen, so subtrahiere das Minimum laut Punkt 9 von dieser Zahl und übernimm das Ergebnis in die neue Matrix. Nun ist eine neue Matrix entstanden.
11. Gehe zu Punkt 6 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 4 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 4 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.

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

Es sollen 3 Werkstücke bearbeitet werden, es stehen drei Maschinen zur Verfügung. Fraglich ist dann, welches Werkstück auf welcher Maschine bearbeitet werden soll, so dass die Kosten minimal sind. Gegeben ist dann eine Matrix A für die Bearbeitungskosten von Werkstück i auf Maschine j.

Auch zur Lösung einiger Fälle des Briefträgerproblems (chinese postman problem) kann die Ungarische Methode eingesetzt werden.

Methode mit Formeln

Gegeben ist die quadratische Matrix C = (c_ij) der Größe $n\times n$. Ohne Beschränkung der Allgemeinheit werde eine Zuordnung $j\to s_j,\ j=1,\ldots,n$ mit minimaler Gesamtsumme $\sum\limits_{j=1}^n c_{s_j,j}$ gesucht, wobei die s_j eine Permutation von $\{1,\ldots,n\}$ sind.

Soll die Summe maximiert werden, dann kann C durch − C ersetzt werden.

Die Grundlage dieses Verfahrens ist, dass sich die optimale Zuordnung unter bestimmten Änderungen der Matrix nicht ändert, sondern nur der Optimalwert. Diese Änderungen sind durch Knotenpotentiale bzw. duale Variablen $u_1,u_2,\dots,u_n$ für die Zeilen und $v_1,v_2,\dots,v_n$ für die Spalten angegeben. Die modifizierte Matrix hat dann die Komponenten $\tilde c_{i,j}=c_{ij}-u_i-v_j$. In der Summe über jede kantenmaximale Zuordnung kommt jedes Knotenpotential genau einmal vor, so dass die Änderung der Zielfunktion eine Konstante ist.

Sind die Einträge von C nichtnegativ, und sind alle Knotenpotentiale ebenfalls nichtnegativ, so nennt man die modifizierte Matrix $\tilde C$ auch eine Reduktion. Ziel ist, in der reduzierten Matrix möglichst viele Komponenten auf den Wert Null zu bringen und unter diesen die Zuordnung zu konstruieren.

Handrechnung

1. Subtrahiere von C in jeder Zeile und Spalte das Minimum.
2. Kennzeichne möglichst viele Nullen in der reduzierten Matrix mit einem Stern ($\star$), sofern weder in der Zeile noch in der Spalte bereits ein Stern steht.
3. Konnten n Sterne gesetzt werden, dann kennzeichnen diese eine optimale Zuordnung, halt.
4. Setze für jede Spalte, die einen Stern enthält, eine Randmarkierung (Pluszeichen).
5. Ermittle das Minimum h der nicht randmarkierten Elemente.
6. Bei h > 0 addiere h zu allen doppelt randmarkierten Elementen und subtrahiere h von allen nicht randmarkierten Elementen.
7. Kennzeichne eine nicht randmarkierte Null mit einem Strich.
8. Steht in der Zeile dieser Null bereits ein Stern, so lösche die Randmarkierung des Sterns, setze für diese Zeile eine Randmarkierung und gehe zum Schritt 5.
9. Kennzeichne die Null mit einem Stern.
10. Steht innerhalb dieser Spalte ein anderer Stern, etwa in einer Zeile i, so lösche diesen Stern, wähle in Zeile i die mit Strich versehene Null und gehe zu Schritt 9.
11. Lösche sämtliche Striche und Zeilenmarkierungen und gehe zu Schritt 3.

Bei jedem Sprung von Schritt 11 zu Schritt 3 ist ein Gegenstand mehr zugeordnet. Wegen der aufwendigen Matrixänderungen in Schritt 6 ist die Komplexität dieses Verfahrens ${\mathcal O}(n^4)$.

Beispiel

Gelöschte Spaltenmarkierungen werden mit $\oplus$ dargestellt. Die bereits gemäß Schritt 1 reduzierte Matrix sei

$\left[\begin{array}{*4c}0&0&0&0\\0&1&3&3\\0&5&5&9\\0&1&3&7\end{array}\right]$. Schritte 2 und 4 ergeben $\left[\begin{array}{*4c}0&\star&0&0\\\star&1&3&3\\0&5&5&9\\0&1&3&7\\+&+\end{array}\right]$. Schritte 5–8 liefern $\left[\begin{array}{*5c}0&\star&0'&0&+\\\star&1&3&3\\0&5&5&9\\0&1&3&7\\+&\oplus\end{array}\right]$. Nun wird h = 1. Schritt 6 bringt $\left[\begin{array}{*5c}1&\star&0'&0&+\\\star&0&2&2\\0&4&4&8\\0&0&2&6\\+&\oplus\end{array}\right]$. Schritte 7–11 liefern $\left[\begin{array}{*4c}1&0&\star&0\\\star&0&2&2\\0&4&4&8\\0&\star&2&6\\+\end{array}\right]$. Schritte 3–8 ergeben $\left[\begin{array}{*5c}1&0&\star&0'&+\\\star&0&2&2\\0&4&4&8\\0&\star&2&6\\+&+&\oplus\end{array}\right]$. Jetzt wird h = 2. Schritt 6 liefert $\left[\begin{array}{*5c}3&2&\star&0'&+\\\star&0&0&0\\0&4&2&6\\0&\star&0&4\\+&+&\oplus\end{array}\right]$. Mit Schritten 7 und 8 kann man $\left[\begin{array}{*5c}3&2&\star&0'&+\\\star&0&0'&0&+\\0&4&2&6\\0&\star&0&4\\\oplus&+&\oplus\end{array}\right]$ erhalten. Schritte 5–10 bringen $\left[\begin{array}{*5c}3&2&\star&0'&+\\0&0&0'&0&+\\\star&4&2&6\\0&\star&0&4\\\oplus&+&\oplus\end{array}\right]$. In $\left[\begin{array}{*5c}3&2&0&\star&+\\0&0&\star&0&+\\\star&4&2&6\\0&\star&0&4\\\oplus&+&\oplus\end{array}\right]$ sieht man das Ergebnis der weiteren Neu-Zuordnung laut Schritten 9 und 10, und dieses ist optimal.

Maschinelle Lösung

Für die Zuordnung der Sterne und das Speichern der Strich-Markierungen werden zwei Vektoren $s,z\in\N^n$ benötigt. Dabei bedeutet s_j = 0, dass in Spalte j noch kein Stern steht, während z_i = 0 heißt, dass in der i-ten Zeile keine Null mit Strich steht. Andernfalls geben s_j und z_i die Position des Sterns oder Strichs in Spalte j bzw. Zeile i an. Zeile i ist genau dann randmarkiert, wenn z_i > 0 ist. Spalte j ist genau dann randmarkiert, wenn $s_j>0\land z_{s_j}=0$ gilt.

Um die Komplexität gering zu halten und auf ${\mathcal O}(n^3)$ zu senken, werden für die maschinelle Rechnung zusätzliche Vektoren $u,v\in\R^n$ für die Knotenpotentiale benutzt. Schritt 1 wird wie folgt ersetzt:

Für $j=1,\ldots,n$ setze $v_j:=\min\limits_i c_{ij}$.

Für $i=1,\ldots,n$ setze $u_i:=\min\limits_j(c_{ij}-v_j)$.

In den Schritten 2–10 wird jeweils mit den reduzierten Gewichten $\tilde c_{ij}=c_{ij}-u_i-v_j$ gerechnet. Insbesondere reduziert sich Schritt 6 zu

Für $j=1,\ldots,n$:

a) Falls Spalte j nicht randmarkiert ist, addiere h zu v_j.

b) Falls Zeile j randmarkiert ist, subtrahiere h von u_j.

Außerdem kann die Minimumsuche in Schritt 5 mittels eines zusätzlichen Vektors $m\in\R^n$ vereinfacht werden. Dieser enthalte für jede Zeile das Minimum der nicht randmarkierten Elemente. Somit wird $h=\min\limits_i m_i$, wobei randmarkierte Zeilen auszuschließen sind. Die Initialisierung dieses Vektors m kann in Schritt 3 oder 4 erfolgen. Falls in Schritt 8 eine Spaltenmarkierung aufzuheben ist, so erfordert die Anpassung von m nur linearen Aufwand, nämlich Vergleich mit den Einträgen der betreffenden Spalte und ggf. deren Übernahme nach m.

Hilfsverfahren für komplexe Aufgabenstellungen

Beispiel 2 ist bequem in wenigen Sekunden zu lösen. Der Komplexitätsgrad des Auffindens der n unabhängigen Nullen (Rechenschritte Punkt 6) wächst mit der Dimension der n×n-Matrix allerdings rasch an. Ohne die entsprechende Software findet man mit einem händischen Verfahren bisweilen relativ lange keine Lösung. Zu einer Lösung, die in vielen Fällen bereits die Optimallösung darstellt, kommt man mit der Methode von Habr, die sich in einer Tabellenkalkulation einfacher programmieren lässt als die Ungarische Methode ab Rechenschritt 8. Die optimale Lösung andererseits durch zufällige Suche von Sets zulässiger Kombinationen zu finden, ist bei größeren Matrizen höchst unwahrscheinlich; für eine n×n-Matrix gibt es genau n! zulässiger Sets. Bereits bei einer 15×15-Matrix beträgt die Anzahl zulässiger Sets 1,3 Billionen. In der Regel sind höchstens einige, mindestens aber eine davon optimal. Je komplexer die Aufgabenstellungen sind, umso mehr muss auch der Aufwand zur Auffindung der optimalen Lösung in das Kalkül einbezogen werden. In der Praxis gibt man sich daher häufig mit suboptimalen Lösungen nahe dem vermuteten Optimum zufrieden, weil man die Gewähr hat, dass man diese viel rascher findet, was die Einbußen, die durch die Auswahl einer nicht ganz optimalen Lösung entstehen, oft mehr als wettmacht.

Die Frequenzmethode nach Habr et al.

Der Grundgedanke dieser Methode ist mit jenem der Varianzanalyse verwandt, indem jeder Wert einer Matrix nach seinen Abweichungen von den Mittelwerten beurteilt wird. Da es hier aber wichtig ist, zu wissen, ob der Wert über oder unter einem Mittelwert liegt, wird hier nicht mit Quadraten von Differenzen, sondern mit den Differenzen selbst gearbeitet. Von jedem Wert der Ausgangsmatrix X wird der Mittelwert der betreffenden Zeile und der Mittelwert der betreffenden Spalte subtrahiert und der Mittelwert der gesamten Matrix addiert, so dass man zu einer neuen Matrix Y gelangt, deren Mittelwerte über die Zeilen, die Spalten sowie über die Matrix allesamt den Wert Null haben:

y(ij) = x(ij) − μ(x(i.)) − μ(x(.j)) + μ(x(ij))

Diese Umformung relativiert den Wert einer Zelle der Matrix über seinen Rang in Zeile, Spalte und Gesamtmatrix; in der Optimierungsrechnung sind Differenzen bedeutungsvoller als absolute Werte.

Je negativer ein Wert y(ij) ist, umso mehr wird er in der Einzelbetrachtung zum Optimum gehören. Nun werden jene möglichst negativen Werte gesucht, deren Summe minimal ist oder zumindest möglichst niedrig liegt. Auch hier ist zu beachten, dass je Zeile und Spalte nur je ein Wert erlaubt ist. Es kann vorkommen, dass auch positive Werte in die Zuordnung einbezogen werden müssen.

Die Methode von Habr ist nicht wie die ungarische Methode an quadratische Matrizen gebunden. Sie löst Beispiel 1 mit nur 1 Matrixumformung:

Die minimale Summe beträgt -4.

Einzelnachweise

1. ↑ H. W. Kuhn (1955): The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, S. 83-97
2. ↑ 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

Literatur

• R.E. Burkard, M. Dell'Amico, S. Martello: Assignment Problems. SIAM, Philadelphia PA. 2009. ISBN 978-0-898716-63-4
• G. Grosche, V. Ziegler, D. Ziegler (Herausgeber): Ergänzende Kapitel zu I. N. Bronstein, K. A. Semendjajew: Taschenbuch der Mathematik. 6. Aufl., BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1990, Abschn. 9.1.
• Habr, Jaroslav: Die Frequenzmethode zur Lösung der Transportprobleme und verwandter linearer Programmierungsprobleme, in: Wissenschaftliche Zeitung der Universität Dresden 10 (1961), H. 5, S. 1069-1071.
• Habr, Jaroslav: The Use of Approximation Methods in Linear Programming, in: Proceedings of the IFIP-Congress 62. Amsterdam 1962, S. 80-82.
• E. Seiffart, K. Manteuffel: Lineare Optimierung. 4. Aufl., BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1988, Abschn. 4.2.