Ungarische Methode

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 findet man 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 (horizontalen und vertikalen) Linien, mit welchen sämtliche Nullen der Matrix gestrichen werden können. Wenn dabei in einer n×n-Matrix wenigstens n Striche erforderlich sind, um alle Nullen zu streichen, dann steht in dieser Matrix bereits die optimale Lösung.
9. Finde das Minimum der Koeffizienten, die nicht gestrichen sind.
10. Nun wird eine neue n×n-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.
11. Gehe zu Punkt 2, 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.

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