Zuordnungsproblem-Löser
Zuordnungsprobleme mit dem ungarischen Algorithmus lösen. Implementiert den ungarischen Algorithmus (Kuhn-Munkres) zur optimalen 1:1-Zuordnung zwischen…
Implementiert den ungarischen Algorithmus (Kuhn-Munkres) zur optimalen 1:1-Zuordnung zwischen Arbeitern und Aufgaben, minimiert oder maximiert die Gesamtkosten in O(n3) Zeitkomplexität.
Was ist das Zuordnungsproblem?
Das Zuordnungsproblem ist ein grundlegendes kombinatorisches Optimierungsproblem: Gegeben n Agenten und n Aufgaben mit einer Kostenmatrix C, finde eine Eins-zu-Eins-Zuordnung, die die Gesamtkosten minimiert.
Der ungarische Algorithmus (Kuhn-Munkres-Methode, 1955) löst das Problem in O(n³). Er reduziert die Kostenmatrix iterativ durch Zeilen- und Spaltensubtraktion und findet dann die optimale Zuordnung über augmentierende Pfade.
Für rechteckige Matrizen werden Dummy-Zeilen oder -Spalten mit Kosten 0 hinzugefügt. Nicht zugeordnete Agenten oder Aufgaben werden separat gemeldet.
Formula: Minimiere Σ C[i][σ(i)] für alle i unter der Bedingung, dass σ eine Permutation ist (Eins-zu-eins-Zuordnung) Schritte der Ungarischen Methode: 1. Zeilenminima subtrahieren 2. Spaltenminima subtrahieren 3. Nullen mit minimaler Linienzahl abdecken 4. Matrix anpassen, wiederholen bis optimal
Berechnungsbeispiel
Kostenmatrix: [[9,2,7],[6,4,3],[5,8,1]]. Zeilenreduktion → [[7,0,5],[3,1,0],[4,7,0]]. Spaltenreduktion → [[4,0,5],[0,1,0],[1,7,0]]. Die Nullen erlauben je Agent eine Aufgabe: Agent 1→Aufgabe 2 (Kosten 2), Agent 2→Aufgabe 1 (Kosten 6), Agent 3→Aufgabe 3 (Kosten 1). Gesamtkosten = 9 — weniger als die naheliegende Paarung Agent 2→Aufgabe 3, Agent 3→Aufgabe 1 (10).
Wann diesen Rechner verwenden
- Ein Produktionsleiter, der Mitarbeiter Maschinen zuordnet, um die Gesamtbearbeitungszeit oder -kosten zu minimieren
- Ein Projektmanager, der Teammitglieder auf Basis von Qualifikationsübereinstimmung und Aufwandsschätzungen Aufgaben zuweist
- Ein Logistikkoordinator, der Lieferfahrzeuge Routen zuordnet, um die Gesamtfahrstrecke zu minimieren
- Ein Universitätsverwalter, der Prüfungsräume Kursen zuteilt, um Konflikte oder Laufwege zu minimieren
Häufige Fehler vermeiden
- Inkonsistente Kosteneingabe — alle Werte in der Kostenmatrix müssen dieselbe Einheit verwenden (Geldbetrag, Stunden, Entfernung); das Mischen von Einheiten erzeugt bedeutungslose Zuordnungen
- Vergessen, zwischen Minimierungs- und Maximierungsmodus umzuschalten — bei Zuordnung nach Gewinn oder Präferenz (höher ist besser) Maximieren wählen; bei Kosten oder Zeit (niedriger ist besser) Minimieren wählen
- Verwendung der Zuordnung für Probleme mit mehreren Zuweisungen pro Agent — der Ungarische Algorithmus weist jeden Agenten genau einer Aufgabe zu; wenn Agenten mehrere Aufgaben übernehmen können, ist ein anderes Modell zu verwenden
- Unzulässige Paarungen nicht behandeln — wenn bestimmte Agent-Aufgabe-Kombinationen unmöglich sind, deren Kosten auf eine sehr große Zahl setzen, statt sie bei null zu belassen
Ergebnisse interpretieren
- Die Gesamtkosten stellen das globale Optimum dar — keine andere Eins-zu-eins-Zuordnung kann eine niedrigere (bzw. bei Maximierung höhere) Gesamtsumme erreichen
- Wenn einige Zeilen oder Spalten als nicht zugeordnet aufgeführt sind, gibt es mehr Agenten als Aufgaben (oder umgekehrt) — diese Agenten/Aufgaben bleiben frei
- Vergleichen Sie die optimale Gesamtsumme mit der naiven Zuordnung (z. B. Zeile 1 zu Spalte 1), um zu sehen, wie viel Verbesserung der Algorithmus liefert
Verwandte Normen und Referenzen
- Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — Originalveröffentlichung des Algorithmus
- Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — die Verfeinerung, die die polynomielle Laufzeit etablierte
- Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — umfassendes modernes Referenzwerk zu Zuordnungsmodellen und -algorithmen
Häufig gestellte Fragen
Kann das Zuordnungsproblem maximieren?
Ja. Alle Kosten negieren oder vom Maximum subtrahieren, dann das Minimierungsproblem lösen. Die optimale Zuordnung ist identisch.
Was bei ungleicher Anzahl von Arbeitern und Aufgaben?
Der Algorithmus füllt die kleinere Dimension mit Dummy-Einträgen (Kosten 0) auf. Zuordnungen zu Dummy-Einträgen zeigen nicht zugeordnete Arbeiter/Aufgaben an.
Kann das Zuordnungsproblem reale Nebenbedingungen wie Mitarbeiterqualifikationen oder Verfügbarkeit berücksichtigen?
Nicht direkt in der Grundformulierung. Sie können jedoch unzulässige Zuordnungen codieren, indem Sie deren Kosten auf eine sehr große Zahl setzen (z. B. 999999), wodurch der Algorithmus effektiv daran gehindert wird, sie auszuwählen. Für komplexe Nebenbedingungen sollten Sie Solver für ganzzahlige lineare Programmierung in Betracht ziehen.