UNGARISCHE METHODE: WORAUS BESTEHT SIE ZUM BEISPIEL? - DUDAS - 2025

Die ungarische Methode ist ein Algorithmus, der bei Zuordnungsproblemen verwendet wird, wenn Sie die Kosten minimieren möchten. Das heißt, es wird verwendet, um die Mindestkosten zu ermitteln, indem mehrere Personen basierend auf den niedrigsten Kosten verschiedenen Aktivitäten zugewiesen werden. Jede Aktivität muss einer anderen Person zugeordnet sein.

Ein Zuordnungsproblem ist eine spezielle Art von linearem Programmierproblem, bei dem das Ziel darin besteht, die Kosten oder die Zeit für die Ausführung einer Reihe von Jobs durch mehrere Personen zu minimieren.

Quelle: pixabay.com

Eines der wichtigen Merkmale des Zuordnungsproblems ist, dass einer Maschine (oder einem Projekt) nur ein Job (oder Arbeiter) zugewiesen ist.

Diese Methode wurde vom ungarischen Mathematiker D. Konig entwickelt. Aus diesem Grund ist es als ungarische Methode für Zuordnungsprobleme bekannt. Es ist auch als Kuhn-Munkres-Zuordnungsalgorithmus bekannt.

Jedes Zuordnungsproblem kann leicht gelöst werden, indem diese Methode angewendet wird, die aus zwei Phasen besteht:

- In der ersten Phase werden Zeilen- und Spaltenreduzierungen durchgeführt.

- In der zweiten Phase wird die Lösung iterativ optimiert.

Was ist die ungarische Methode?

Die ungarische Methode besteht aus vier Schritten. Die ersten beiden Schritte werden nur einmal ausgeführt, während die Schritte 3 und 4 wiederholt werden, bis eine optimale Zuordnung gefunden ist.

Eine quadratische Matrix der Ordnung n mal n wird als Eingabedaten betrachtet, die nur nicht negative Elemente enthalten dürfen.

Wenn für ein bestimmtes Problem die Anzahl der Zeilen in der Matrix nicht der Anzahl der Spalten entspricht, muss je nach Fall eine Dummy-Zeile oder eine Dummy-Spalte hinzugefügt werden. Die Zuordnungskosten für diese Dummy-Zellen werden immer als Null zugewiesen.

Schritt 1: Subtrahieren Sie die Minima jeder Zeile

Für jede Zeile im Array wird das Element mit dem niedrigsten Wert ausgewählt und von jedem Element in dieser Zeile subtrahiert.

Schritt 2: Subtrahieren Sie die Minima von jeder Spalte

In ähnlicher Weise wird das Element mit dem niedrigsten Wert für jede Spalte ausgewählt und von jedem Element in dieser Spalte abgezogen.

Schritt 3: Decken Sie alle Nullen mit einer minimalen Anzahl von Zeilen ab

Alle Nullen in der Matrix, die sich aus Schritt 2 ergeben, müssen mit einer minimalen Anzahl horizontaler und vertikaler Linien entweder durch Zeilen oder Spalten abgedeckt werden.

Wenn insgesamt n Zeilen erforderlich sind, um alle Nullen abzudecken, wobei n gleich der Größe n mal n der Matrix ist, erfolgt eine optimale Zuordnung zwischen den Nullen, und daher stoppt der Algorithmus.

Andernfalls fahren Sie mit Schritt 4 fort, wenn weniger als n Zeilen erforderlich sind, um alle Nullen im Array abzudecken.

Schritt 4: Erstellen Sie zusätzliche Nullen

Das kleinste Element der Matrix (k genannt), das nicht von einer der in Schritt 3 erstellten Linien abgedeckt wird, wird ausgewählt.

Der Wert von k wird von allen Elementen abgezogen, die nicht durch Linien abgedeckt sind. Anschließend wird der Wert von ka zu allen Elementen addiert, die durch den Schnittpunkt zweier Linien abgedeckt sind.

Elemente, die durch eine einzelne Zeile abgedeckt sind, bleiben unverändert. Nachdem Sie diesen Schritt ausgeführt haben, kehren Sie zu Schritt 3 zurück.

Optimale Zuordnung

Nachdem der Algorithmus in Schritt 3 gestoppt wurde, wird ein Satz von Nullen so ausgewählt, dass für jede Zeile und jede Spalte nur eine Null ausgewählt ist.

Wenn in diesem Auswahlprozess keine einzelne Null in einer Zeile oder Spalte vorhanden ist, wird eine dieser Nullen ausgewählt. Die verbleibenden Nullen in dieser Spalte oder Zeile werden entfernt und wiederholen dies auch für die anderen Zuweisungen.

Wenn es keine einzelne Nullzuweisung gibt, gibt es mehrere Lösungen. Die Kosten bleiben jedoch für verschiedene Zuweisungssätze gleich.

Alle hinzugefügten Dummy-Zeilen oder -Spalten werden entfernt. Die in dieser endgültigen Matrix gewählten Nullen entsprechen somit der idealen Zuordnung, die in der ursprünglichen Matrix erforderlich ist.

Beispiel

Betrachten wir ein Unternehmen, in dem vier Aktivitäten (A1, A2, A3, A4) von vier Arbeitern (T1, T2, T3, T4) ausgeführt werden müssen. Pro Arbeiter muss eine Aktivität zugewiesen werden.

Die folgende Matrix zeigt die Kosten für die Zuordnung eines bestimmten Arbeitnehmers zu einer bestimmten Aktivität. Ziel ist es, die Gesamtkosten der aus diesen vier Aktivitäten bestehenden Aufgabe zu minimieren.

Schritt 1: Subtrahieren Sie die Minima jeder Zeile

Sie subtrahieren zunächst das Element mit dem Mindestwert in jeder Zeile von den anderen Elementen in dieser Zeile. Zum Beispiel ist das kleinste Element in der ersten Zeile 69. Daher wird 69 von jedem Element in der ersten Zeile subtrahiert. Die resultierende Matrix lautet:

Schritt 2: Subtrahieren Sie die Minima von jeder Spalte

Auf die gleiche Weise wird das Element mit dem Mindestwert jeder Spalte von den anderen Elementen dieser Spalte subtrahiert, wodurch die folgende Matrix erhalten wird:

Schritt 3: Decken Sie alle Nullen mit einer minimalen Anzahl von Zeilen ab

Nun bestimmen wir die Mindestanzahl von Linien (horizontal oder vertikal), die erforderlich sind, um alle Nullen in der Matrix abzudecken. Alle Nullen können mit 3 Zeilen abgedeckt werden:

Da die Anzahl der erforderlichen Zeilen drei beträgt und weniger als die Größe der Matrix (n = 4) beträgt, fahren wir mit Schritt 4 fort.

Schritt 4: Erstellen Sie zusätzliche Nullen

Es wird das kleinste Element ausgewählt, das nicht von den Linien abgedeckt wird und dessen Wert 6 beträgt. Dieser Wert wird von allen nicht abgedeckten Elementen abgezogen, und derselbe Wert wird zu allen Elementen addiert, die durch den Schnittpunkt zweier Linien abgedeckt werden. Daraus ergibt sich folgende Matrix:

Wie in der ungarischen Methode angegeben, muss Schritt drei erneut durchgeführt werden.

Schritt 3 (wiederholen)

Wiederum wird die minimale Anzahl von Zeilen bestimmt, die erforderlich sind, um alle Nullen in der Matrix abzudecken. Diesmal sind vier Zeilen erforderlich:

Da die Anzahl der erforderlichen Zeilen 4 beträgt, was der Größe der Matrix entspricht (n = 4), haben wir eine optimale Zuordnung zwischen den Nullen in der Matrix. Daher stoppt der Algorithmus.

Optimale Zuordnung

Wie die Methode angibt, entspricht die Auswahl der folgenden Nullen einer optimalen Zuordnung:

Diese Auswahl von Nullen entspricht der folgenden optimalen Zuordnung in der ursprünglichen Kostenmatrix:

Daher muss Arbeiter 1 Aktivität 3 ausführen, Arbeiter 2, Aktivität 2, Arbeiter 3, Aktivität 1 und Arbeiter 4 müssen Aktivität 4 ausführen. Die Gesamtkosten dieser optimalen Aufgabe betragen 69 + 37 + 11 + 23 = 140.

Verweise

1. Ungarischer Algorithmus (2019). Der ungarische Algorithmus. Entnommen aus: hungarianalgorithm.com.
2. Studie (2019). Verwenden des ungarischen Algorithmus zum Lösen von Zuweisungsproblemen. Entnommen aus: study.com.
3. Weisheitsjobs (2018). Ungarische Methode zur Lösung von Zuweisungsproblemen - Quantitative Techniken für das Management. Entnommen aus: Weisheitsjobs.
4. Geeks for Geeks (2019). Ungarischer Algorithmus für Zuweisungsproblem. Entnommen aus: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Ungarischer Maximum-Matching-Algorithmus. Brillant. Entnommen aus: brillant.org.