Ungarische Methode

Ü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.

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 ${\displaystyle -\infty }$ in der Matrix dargestellt.

Es gibt aber auch Fälle, in welchen das Ausgangsproblem keine quadratische Form besitzt: ${\displaystyle n}$ Mitarbeiter machen ${\displaystyle k}$ Eignungstests für ${\displaystyle k}$ zu besetzende Positionen (${\displaystyle k<n}$). 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 ${\displaystyle n-k}$ Dummy-Positionen („keine Position“) eingeführt werden. Dummy-Positionen werden üblicherweise mit der größten vorhandenen Zahl aus der Matrix besetzt.[3]

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 ${\displaystyle n}$×${\displaystyle n}$-Matrix genau so viele Möglichkeiten gibt, die Zeilen- bzw. Spaltenvektoren zu ordnen, wie es Permutationen von n Elementen gibt, also ${\displaystyle n!}$. 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.

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.

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.

Es sollen drei Werkstücke auf jeweils einer von drei zur Verfügung stehenden Maschinen bearbeitet werden. Gesucht ist die optimale (gesamtkostenminimale) Zuordnung der Werkstücke zu den Maschinen. Gegeben ist dann eine Matrix ${\displaystyle A}$ für die Bearbeitungskosten von Werkstück ${\displaystyle i}$ auf Maschine ${\displaystyle j}$.

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

1. Subtrahiere von ${\displaystyle C}$ in jeder Zeile und Spalte das Minimum.
2. Kennzeichne möglichst viele Nullen in der reduzierten Matrix mit einem Stern (${\displaystyle \star }$), sofern weder in der Zeile noch in der Spalte bereits ein Stern steht.
3. Konnten ${\displaystyle n}$ Sterne gesetzt werden, dann kennzeichnen diese eine optimale Zuordnung. Die Berechnung ist damit abgeschlossen.
4. Setze für jede Spalte, die einen Stern enthält, eine Randmarkierung (Pluszeichen).
5. Ermittle das Minimum ${\displaystyle h}$ der nicht randmarkierten Elemente.
6. Bei ${\displaystyle h>0}$ addiere ${\displaystyle h}$ zu allen doppelt randmarkierten Elementen und subtrahiere ${\displaystyle 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 ${\displaystyle i}$, so lösche diesen Stern, wähle in Zeile ${\displaystyle 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 Minimumsuche in Schritt 5 und der Matrixänderungen in Schritt 6 ist die Komplexität dieses Verfahrens ${\displaystyle {\mathcal {O}}(n^{4})}$.

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

${\displaystyle \left[{\begin{array}{*{4}c}0&0&0&0\\0&1&3&3\\0&5&5&9\\0&1&3&7\end{array}}\right]}$. Schritte 2 und 4 ergeben ${\displaystyle \left[{\begin{array}{*{4}c}0&\star &0&0\\\star &1&3&3\\0&5&5&9\\0&1&3&7\\+&+\end{array}}\right]}$. Schritte 5–8 liefern ${\displaystyle \left[{\begin{array}{*{5}c}0&\star &0'&0&+\\\star &1&3&3\\0&5&5&9\\0&1&3&7\\+&\oplus \end{array}}\right]}$. Nun wird ${\displaystyle h=1}$. Schritt 6 bringt ${\displaystyle \left[{\begin{array}{*{5}c}1&\star &0'&0&+\\\star &0&2&2\\0&4&4&8\\0&0&2&6\\+&\oplus \end{array}}\right]}$. Schritte 7–11 liefern ${\displaystyle \left[{\begin{array}{*{4}c}1&0&\star &0\\\star &0&2&2\\0&4&4&8\\0&\star &2&6\\+\end{array}}\right]}$. Schritte 3–8 ergeben ${\displaystyle \left[{\begin{array}{*{5}c}1&0&\star &0'&+\\\star &0&2&2\\0&4&4&8\\0&\star &2&6\\+&+&\oplus \end{array}}\right]}$. Jetzt wird ${\displaystyle h=2}$. Schritt 6 liefert ${\displaystyle \left[{\begin{array}{*{5}c}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 ${\displaystyle \left[{\begin{array}{*{5}c}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 ${\displaystyle \left[{\begin{array}{*{5}c}3&2&\star &0'&+\\0&0&0'&0&+\\\star &4&2&6\\0&\star &0&4\\\oplus &+&\oplus \end{array}}\right]}$. In ${\displaystyle \left[{\begin{array}{*{5}c}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.

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

Um die Komplexität gering zu halten und auf ${\displaystyle {\mathcal {O}}(n^{3})}$ zu senken, werden für die maschinelle Rechnung zusätzliche Vektoren ${\displaystyle u,v\in \mathbb {R} ^{n}}$ für die Knotenpotentiale sowie ein Vektor ${\displaystyle m\in \mathbb {R} ^{n}}$ zur schnelleren Minimumsuche in Schritt 5 benutzt. ${\displaystyle m}$ enthalte für jede Zeile das Minimum der nicht randmarkierten Elemente. Somit wird ${\displaystyle h=\min \limits _{i}m_{i}}$, wobei randmarkierte Zeilen auszuschließen sind. Die Initialisierung dieses Vektors ${\displaystyle m}$ kann in Schritt 3 oder 4 erfolgen. Schritt 1 wird wie folgt ersetzt:

Für ${\displaystyle j=1,\ldots ,n}$ setze ${\displaystyle v_{j}:=\min \limits _{i}c_{ij}}$.

Für ${\displaystyle i=1,\ldots ,n}$ setze ${\displaystyle u_{i}:=\min \limits _{j}(c_{ij}-v_{j})}$.

In den Schritten 2–10 wird jeweils mit den reduzierten Gewichten ${\displaystyle {\tilde {c}}_{ij}=c_{ij}-u_{i}-v_{j}}$ gerechnet. Insbesondere reduziert sich Schritt 6 bei ${\displaystyle h>0}$ zu

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

a) Falls Spalte ${\displaystyle j}$ nicht randmarkiert ist, addiere ${\displaystyle h}$ zu ${\displaystyle v_{j}}$.

b) Falls Zeile ${\displaystyle j}$ randmarkiert ist, subtrahiere ${\displaystyle h}$ von ${\displaystyle u_{j}}$.

c) Subtrahiere ${\displaystyle h}$ von ${\displaystyle m_{j}}$ (zumindest in unmarkierten Zeilen).

Falls in Schritt 8 eine Spaltenmarkierung aufzuheben ist, so erfordert die Anpassung von ${\displaystyle m}$ nur linearen Aufwand, nämlich Vergleich mit den Einträgen der betreffenden Spalte und ggf. deren Übernahme nach ${\displaystyle m}$.

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 ${\displaystyle 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 ${\displaystyle Y}$ gelangt, deren Mittelwerte über die Zeilen, die Spalten sowie über die Matrix allesamt den Wert Null haben:

${\displaystyle y(ij)=x(ij)-\mu (x(i.))-\mu (x(.j))+\mu (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 ${\displaystyle 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:

Methode von Habr

Rangordnung der Präferenzen
Matrix x

	A	B	C	D	${\displaystyle \mu }$
E	1	1	1	2	1,25
K	3	2	4	1	2,50
P	4	4	2	4	3,50
Z	2	3	3	3	2,75
${\displaystyle \mu }$	2,5	2,5	2,5	2,5	2,5

Matrix y

	A	B	C	D	${\displaystyle \mu }$
E	−0,25	−0,25	−0,25	0,75	0,00
K	0,5	−0,5	1,5	−1,5	0,00
P	0,5	0,5	−1,5	0,5	0,00
Z	−0,75	0,25	0,25	0,25	0,00
${\displaystyle \mu }$	0	0	0	0	0,00

Die minimale Summe beträgt −4.