Ungarische Methode

Die Ungarische Methode ist ein Spezialfall der Linearen Optimierung, für den sehr schnelle (Größenordnung O(n3)O(n^3)) Algorithmen existieren.

Aufgabenstellung

Typische Zuordnungsprobleme

Die Ungarische Methode eignet sich besonders für Zuordnungsprobleme, da die Lösungen dieser Problemklasse binär und damit insbesondere ganzzahlig sind. Ausgangsinformation zur Lösung des Problems ist in den überwiegenden Fällen eine quadratische Matrix, in der Koeffizienten stehen. Es gibt aber auch Fälle, in welchen das Ausgangsproblem nicht in Form einer quadratischen Matrix vorliegt: nn Mitarbeiter machen kk Eignungstests für kk intern zu besetzende Positionen (k<nk < n). In solchen Fällen wird die Matrix künstlich quadratisch gemacht, indem n−kn-k Dummy-Positionen ("keine Position") eingeführt werden. Dummy-Positionen werden üblicherweise mit Nullen besetzt.
In jeder Zeile/Spalte der Matrix steht genau ein Element, das zur optimalen Lösung gehört. Deshalb kann die Problemstellung auch anders formuliert werden: Ordne die Zeilen-/Spaltenvektoren so, dass die Summe der Elemente in der Hauptdiagonale ein Minimum wird. Hieraus wird sofort ersichtlich, dass es in einer n×nn \cross n - Matrix genau n!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 x 10 - Matrix gibt es an die 3,63 Millionen zulässiger Lösungen.
 
 

10 Rechenschritte ohne Formeln

  1. Bilde die Spaltenminima (s. Beispiel 1 Matrix 1).
  2. Subtrahiere von jedem Element einer Spalte das jeweilige Spaltenminimum (s. Beispiel 1 Matrix 2).
  3. Bilde die neuen Zeilenminima.
  4. Subtrahiere von jedem Element einer Zeile das jeweilige Zeilenminimum (s. Beispiel 1 Matrix 3).
  5. 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.
  6. 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).
  7. Gibt es keine solche Kombination von Nullen, weil in bestimmten Zeilen oder Spalten keine Nullen gefunden werden können, die die Bedingung des Punktes 5 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 x 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.
  8. Finde das Minimum der Koeffizienten, die nicht gestrichen sind.
  9. 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 8 zu dieser Zahl und übernimm das Ergebnis in die neue Matrix; ist eine Zahl nicht gestrichen, so subtrahiere das Minimum laut Punkt 8 von dieser Zahl und übernimm das Ergebnis in die neue Matrix. Nun ist eine neue Matrix entstanden.
  10. Gehe zu Punkt 5 und versuche erneut, eine zulässige Kombination von Nullen in der neuen Matrix zu finden.
Bemerkung: Aus Symmetriegründen sind in den Punkten 1 bis 4 die Begriffe "Zeilen" und "Spalten" gegeneinander austauschbar.

Beispiel 1

Ungmeth1.JPG
Ungarische Methode
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 x 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.

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 5) wächst mit der Dimension der n x 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 7. 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 x n - Matrix gibt es genau n! zulässiger Sets. Bereits bei einer 15 x 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 des vermuteten Optimums 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.

Methode_Habr.JPG
Methode von Habr
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))y(ij) = x(ij) - \my (x(i\, )) - \my (x(\, j)) + \my (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 an quadratische Matrizen gebunden. Sie löst Beispiel 1 mit nur 1 Matrixumformung:
Die minimale Summe beträgt -4,1.

Quellen

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

Alle Pädagogen sind sich darin einig: man muß vor allem tüchtig Mathematik treiben, weil ihre Kenntnis fürs Leben größten direkten Nutzen gewährt.

Felix Klein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Ungarische Methode aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Optimierung