Ungarische Methode

Methode mit Formeln

Gegeben ist die quadratische Matrix C = (c_ij ) der Größe . Ohne Beschränkung der Allgemeinheit werde eine Zuordnung mit minimaler Gesamtsumme gesucht, wobei die s_j eine Permutation von {1, ..., 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₁ , u₂ , ..., u_n für die Zeilen und v₁ , v₂ , ..., v_n für die Spalten angegeben. Die modifizierte Matrix hat dann die Komponenten . 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 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.

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