Zuordnungsproblem-Löser (ungarischer Algorithmus)

Zuordnungsproblem-Löser (ungarischer Algorithmus) | Kostenloses Online-Tool | Elysia Tools

Leitfaden zur Tool-Nutzung

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Kategorie: Math & Numbers
Eingabetypen: textarea, select, number
Ausgabetyp: text
Sample-Abdeckung: 4
API bereit: Ja

Überblick

Dieser Zuordnungsproblem-Löser berechnet die optimale Paarung von Arbeitskräften und Aufgaben mittels des ungarischen Algorithmus (Kuhn-Munkres). Das Tool verarbeitet Kosten- oder Nutzenmatrizen der Dimension 2×2 bis 8×8, füllt rechteckige Eingaben automatisch mit Nullkosten-Dummys auf und liefert ein schrittweises Protokoll der Zeilen- und Spaltenreduktionen sowie der König-Linienüberdeckungen.

Wann verwenden

Wenn Aufgaben, Schichten oder Maschinen eindeutig Personen oder Aufträgen zugewiesen werden müssen, um Gesamtkosten oder Bearbeitungszeiten zu minimieren.
Wenn Effizienz- oder Ertragsmatrizen vorliegen und eine 1:1-Zuordnung den maximalen Gesamtnutzen erzielen soll.
Zur Verifikation und Schritt-für-Schritt-Nachverfolgung von Übungsaufgaben im Operations Research und in der kombinatorischen Optimierung.

So funktioniert es

1Geben Sie die Matrix zeilenweise mit kommagetrennten Werten (2–8 Zeilen und Spalten) ein und wählen Sie das Optimierungsziel (Kosten minimieren oder Nutzen maximieren).
2Das System führt Zeilen- und Spaltenreduktionen durch; Maximierungsprobleme werden intern über die negierte Matrix vorbereitet und rechteckige Matrizen mit Dummy-Zeilen oder -Spalten ausgeglichen.
3Nullen werden über alternierende Wege gematcht; reicht das Matching nicht aus, bestimmt der Algorithmus die minimale Linienüberdeckung nach König und passt ungedeckte Werte sowie Schnittpunkte iterativ an.
4Das Werkzeug gibt die einzelnen Reduktions- und Überdeckungsrunden, die finale 1:1-Zuordnung und den verifizierten Gesamtwert aus.

Anwendungsfälle

Minimierung von Arbeits- oder Rüstzeiten bei der Zuordnung von Aufträgen an spezialisierte Maschinen.
Optimierung der Personaldisposition durch Zuweisung von Mitarbeitenden zu Projekten anhand ihrer Qualifikations- oder Kostensätze.
Maximierung von Teamerlösen oder Vertriebszielen bei der Zuweisung von Verkaufsgebieten an Außendienstmitarbeiter.

Beispiele

1. Minimierung von Betriebskosten bei 3 Aufgaben

Produktionsleiter

Hintergrund

Drei Maschinenbetreiber müssen drei unterschiedlichen Fertigungsstationen mit unterschiedlichen Stückkosten zugewiesen werden.

Aufgabe

Die Gesamtkosten für den Einsatz aller drei Betreiber sollen auf ein Minimum reduziert werden.

Verwendung

Tragen Sie die Kostenmatrix in das Textfeld ein, wählen Sie 'Gesamtkosten minimieren' und starten Sie die Berechnung.

matrix = 9, 2, 7
6, 4, 3
5, 8, 1
goal = min
decimalPlaces = 4

Ergebnis

Optimale Zuordnung: Arbeiter 1 → Aufgabe 2 (Kosten 2), Arbeiter 2 → Aufgabe 1 (Kosten 6), Arbeiter 3 → Aufgabe 3 (Kosten 1) bei minimalen Gesamtkosten von 9.

2. Maximierung des Ertrags bei Vertriebsgebieten

Vertriebsleiter

Hintergrund

Drei Vertriebsbeauftragte erzielen je nach Region unterschiedliche prognostizierte Umsatzzahlen in Tausend Euro.

Aufgabe

Jedem Mitarbeiter soll genau ein Gebiet so zugeordnet werden, dass der Gesamtumsatz maximal ausfällt.

Verwendung

Geben Sie die Umsatzmatrix ein, wählen Sie die Option 'Gesamtnutzen maximieren' und prüfen Sie die Auswertung.

FAQ

Welche Matrixgrößen werden unterstützt?

Das Tool verarbeitet Matrizen von minimal 2×2 bis maximal 8×8 Elementen.

Können ungleiche Anzahlen von Arbeitskräften und Aufgaben eingegeben werden?

Ja, rechteckige Matrizen werden automatisch durch Dummy-Zeilen oder Dummy-Spalten mit Kosten von 0 zu einer quadratischen Matrix ergänzt.

Wie wird die Nutzenmaximierung berechnet?

Das Werkzeug negiert die eingegebenen Nutzenwerte intern, wendet den ungarischen Minimierungsalgorithmus an und gibt das Ergebnis mit den ursprünglichen Nutzenwerten aus.

Wie müssen die Eingabewerte formatiert sein?

Geben Sie jede Zeile der Matrix auf einer neuen Zeile ein, wobei die Spaltenwerte durch Kommas oder Leerzeichen getrennt werden.

Wie kann die Genauigkeit bei Dezimalwerten eingestellt werden?

Über das Feld Dezimalstellen lässt sich die Rundungsgenauigkeit für Zwischenschritte und Endergebnisse zwischen 0 und 8 Nachkommastellen festlegen.

matrix = 7, 3, 5
2, 9, 4
6, 8, 1
goal = max
decimalPlaces = 4

Dieses Tool ausführen

Beispiele zu diesem Tool

Mit verwandten Tools und Themen fortfahren

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Überblick

Wann verwenden

So funktioniert es

Anwendungsfälle

Beispiele

1. Minimierung von Betriebskosten bei 3 Aufgaben

2. Maximierung des Ertrags bei Vertriebsgebieten

FAQ

ELK Stack Log-Analyse Beispiele

MP3 Audio-Beispiele ohne Urheberrechte

Benannte Capture-Gruppen von Regex

Umgebungsvariablen (.env) Beispiele

Kürzester-Wege-Rechner (Dijkstra Schritt für Schritt)

Kopfüber-Text

Podcast-Kapitelmarken-Generator (ID3 / Podcasting 2.0)

STEM-Physik: Tutor für Geschwindigkeits-Zeit-Diagramm