ZU DEN KURSEN!

Operations Research - Ungarische Methode

Kursangebot | Operations Research | Ungarische Methode

Operations Research

Ungarische Methode

Die Ungarische Methode ist dazu gedacht lineare Zurodnungsprobleme zu lösen. 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.

Anwendungsbeispiel: Ungarische Methode

Ungarische Methode Beispiel

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.

Ungarische Methode Reduktion der Kostenmatrix


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.

Ungarische Methode Zuordnung


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.

Ungarische Methode Zuordnung

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. 
Ungarische Methode, markieren Zeilen und 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.

Ungarische Methode


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

Ungarische Methode, streichen von Nullen


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.

Ungarische Methode, streichen von Nullen


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:

Ungarische Methode Zuordnung

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$.