Was ist das Zuordnungsproblem?

Das Zuordnungsproblem ist ein klassisches kombinatorisches Optimierungsproblem: Gegeben eine Menge von Arbeitern und Aufgaben, jeweils mit zugeordneten Kosten, finde die Eins-zu-Eins-Zuordnung, die die Gesamtkosten minimiert. Es tritt natürlicherweise in Planung, Logistik, Ressourcenallokation und Operations Research auf – in jeder Situation, in der Sie zwei Gruppen auf die effizienteste Weise abgleichen müssen.

Das Problem wird mit dem Ungarischen Algorithmus (auch Munkres-Algorithmus genannt) gelöst, einer effizienten Methode aus den 1950er Jahren. Im Gegensatz zu Brute-Force-Ansätzen, die jede Permutation auswerten müssen, findet der Ungarische Algorithmus die optimale Lösung in Polynomialzeit, was ihn auch für mäßig große Matrizen praktisch macht.

Werkzeugbeschreibung

Geben Sie eine Kostenmatrix ein, die darstellt, wie viel es kostet, jeden Arbeiter jeder Aufgabe zuzuordnen, und klicken Sie dann auf Lösen, um sofort die optimale Zuordnung zu finden. Das Werkzeug hebt hervor, welche Arbeiter-Aufgaben-Paare die Gesamtkosten minimieren, und zeigt das Ergebnis in einer übersichtlichen Tabelle zusammen mit den optimalen Gesamtkosten an.

Beispiele

Eingabematrix (3 Arbeiter × 3 Aufgaben):

Aufgabe 1 Aufgabe 2 Aufgabe 3
Arbeiter 1 400 150 400
Arbeiter 2 400 450 600
Arbeiter 3 300 225 300

Optimale Zuordnungen:

Arbeiter Aufgabe Kosten
Arbeiter 1 Aufgabe 2 150
Arbeiter 2 Aufgabe 1 400
Arbeiter 3 Aufgabe 3 300

Gesamtkosten: 850

Funktionen

  • Bearbeitbare Matrix – klicken Sie auf eine beliebige Zelle oder einen Spaltenkopf, um Arbeiter, Aufgaben und Kosten direkt in der Tabelle umzubenennen
  • Konfigurierbare Größe – unterstützt Matrizen von 2×2 bis 8×8
  • Sofortige Ergebnisse – der Ungarische Algorithmus läuft im Browser ohne Server-Roundtrip

Wie es funktioniert

Das Werkzeug verwendet den Munkres (Ungarischen) Algorithmus, um das Zuordnungsproblem optimal zu lösen. Es erstellt eine Kostenmatrix aus Ihren Eingaben, wendet eine Reihe von Zeilen- und Spaltenreduktionsschritten an und findet iterativ ein maximales Matching von Nullen, bis eine vollständige optimale Zuordnung identifiziert ist. Die Zeitkomplexität beträgt $O(n^3)$, wobei $n$ die Matrixdimension ist.

Für nicht-quadratische Matrizen (mehr Arbeiter als Aufgaben oder umgekehrt) füllt der Algorithmus die Matrix mit Nullen auf, sodass jeder Arbeiter und jede Aufgabe zugeordnet wird.

Optionen erklärt

  • Anzahl der Arbeiter / Zeilen – steuert, wie viele Zeilen in der Kostenmatrix angezeigt werden (2–8)
  • Anzahl der Aufgaben / Spalten – steuert, wie viele Spalten in der Kostenmatrix angezeigt werden (2–8)
  • Kostenmatrix-Zellen – geben Sie die Kosten für die Zuordnung eines bestimmten Arbeiters zu einer bestimmten Aufgabe ein; jeder numerische Wert wird akzeptiert

Einschränkungen

  • Die Matrixgröße ist auf 8×8 (64 Zellen) begrenzt
  • Der Algorithmus minimiert die Gesamtkosten; um zu maximieren (z. B. für Gewinnmatrizen), negieren Sie die Werte, bevor Sie sie eingeben
  • Nicht-numerische Zellwerte werden als Null behandelt