Ungarische Methode

Methode mit Formeln

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 .

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