Inhaltsverzeichnis
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.
Methode
Ungarische Methode
1. Reduktion der Ausgangsmatrix. Spalten-und zeilenweise Reduktion der Ausgangsmatrix.
2. Es wird mit derjenigen Spalte und Zeile begonnen, welche nur eine Null enthält. Diesem Feld wird dann $x_{ij} = 1$ 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.
Sind $n$ Zurodnungen gefunden, so ist die Lösung optimal. Sind weniger als $n$ Zuordnungen gefunden, geht es weiter mit Schritt 3.
3. Es wird nun wie folgt vorgegangen:
- (a) Markiere alle Zeilen, die keine Zuordnung (Umrandung) aufweisen.
- (b) Markiere alle Spalten, welche Null-Elemente in den bereits markierten Zeilen aufweisen.
- (c) Markiere alle nicht-markierten Zeilen, welche Zuordnungen in den markierten Spalten aufweisen.
- 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 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.
5. Es wird wieder bei Schritt 2 begonnen.
Die Vorgehensweise bei der Ungarischen Methode soll anhand des nachfolgenden Beispiel aufgezeigt werden.
Beispiel zur Ungarischen Methode
Beispiel
Ein Logistikunternehmen benötigt an 5 Orten $j$ je einen Lastwagen. Diese sollen von den Ausgangsorten $i$ auf diese 5 Orten so verteilt werden, dass die Fahrtkosten minimal werden. In der Tabelle sind die Kilometer von dem Ort $i$ zum Ort $j$ angegeben. Die Zuordnung soll so stattfinden, dass die Kilometerzahl minimiert wird.
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 $x_{ij} = 1$ 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 $n = 5$ 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 $n = 5$ 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:
$2 + 3 + 4 + 7 + 5 = 21 km$.
Weitere interessante Inhalte zum Thema
-
Gauß Eliminationsverfahren
Vielleicht ist für Sie auch das Thema Gauß Eliminationsverfahren (Matrizen) aus unserem Online-Kurs Analysis und Lineare Algebra interessant.
-
Dualität - Primalproblem als Maximierungsproblem
Vielleicht ist für Sie auch das Thema Dualität - Primalproblem als Maximierungsproblem (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.
