Ungarische Methode

Definition der Ungarischen Methode

Die Ungarische Methode ist dazu gedacht lineare Zurodnungsprobleme zu lösen.

Vorgehen bei der Ungarischen Methode

Für die Anwendung der Ungarischen Methode wird zunächst eine Spalten- und Zeilenweise Reduktion der Kostenmatrix durchgeführt. 

Die Vorgehensweise bei der Ungarischen Methode soll anhand des nachfolgenden Beispiel aufgezeigt werden.

Beispiel zur Ungarischen Methode

Es wird die Ungarische Methode angewandt um das Zurodnungsproblem zu lösen. 

1. Es wird zunächst eine Reduktion der Ausgangsmatrix vorgenommen, indem zunächst die Zeilen betrachtet werden und hier das kleinste Element einer Zeile von den anderen Elemente der Zeile abgezogen werden. Danach wird die Spalte betrachtet und das kleinste Element der Spalte von den anderen Elementen der Spalte abgezogen.

2. Es wird mit derjenigen Spalte und Zeile begonnen, welche nur eine Null enthält. Diesem Feld wird dann zugeordnet, indem die Null umrandet wird.

Danach werden die weiteren Nullen in der Matrix betrachtet. Dabei werden weitere Zuordnungen so vorgenommen, dass am Ende jede Spalte und jede Zeile nur eine Zuordnung aufweist.

Da und nur 4 Zuordnungen gefunden worden sind, geht es weiter mit Schritt 3.

Bei 3. Schritt wird nun wie folgt vorgegangen. Es werden nun alle Nullen (auch die zugeordneten) versucht mit so wenig Strichen wie möglich zu streichen. Dabei wird wie folgt vorgegangen:

• a) Markiere alle Zeilen, die keine Zuordnung (Umrandung) aufweisen: Unterste Zeile 5 (*1)
  
  
• (b) Markiere alle Spalten, welche Null-Elemente in den bereits bei a) markierten Zeilen aufweisen: Nullelement in unterster Zeile 5 bei Spalte 1 (*2)
  
  
• (c) Markiere alle nicht-markierten Zeilen, welche Zuordnungen in den markierten Spalten aufweisen: Spalte 1 weist 1 Zuordnung in Zeile 4 auf (*3). 
  
  
• Wiederhole b - c solange bis keine Markierungen mehr erfolgen.
• Zeichne eine Linie durch alle nicht-markierten Zeilen und durch alle markierten Spalten. 

4. Die Matrixelemente müssen nun wie folgt angepasst werden. Das kleinste nicht mit einer Linie überdeckte Element (hier: 1) wird von den anderen nicht von einer Linie überdeckten Elementen abgezogen und zu den doppelt überdeckten Elementen (dort wo sich Linien schneiden) addiert. Die einfach überdeckten Elemente bleiben unverändert.

Es wird wieder bei Schritt 2 begonnen. Die Schritte 2-3 ergeben die folgende Matrix:

Danach wird Schritt 4 durchgeführt. Die Matrixelemente müssen nun wie folgt angepasst werden. Das kleinste nicht mit einer Linie überdeckte Element (hier: 2) wird von den anderen nicht von einer Linie überdeckten Elementen abgezogen und zu den doppelt überdeckten Elementen (dort wo sich Linien schneiden) addiert. Die einfach überdeckten Elemente bleiben unverändert.

Es wird wieder mit Schritt 2 begonnen. Nach Schritt 2, also Zuordnung der Nullen, ergibt sich eine eine optimale Lösung, da Zuordnungen gefunden werden:

Die optimale Lösung sieht also wie folgt aus:

Ein Wagen von Ort 1 nach Ort 4.

Ein Wagen von Ort 2 nach Ort 2.

Ein Wagen von Ort 3 nach Ort 3.

Ein Wagen von Ort 4 nach Ort 5.

Ein Wagen von Ort 5 nach Ort 1.

Die Kilometeranzahl beträgt demnach:

.