Zuordnungsproblem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das (lineare) Zuordnungsproblem ist ein diskretes Optimierungsproblem aus der Graphentheorie. Es ist ein spezielles klassisches Transportproblem und findet Anwendung in der Operations Research.

Es kann mittels ganzzahliger linearer Optimierung oder mithilfe der Ungarischen Methode gelöst werden.

Problembeschreibung

[Bearbeiten | Quelltext bearbeiten]

Es kann wie folgt verbal formuliert werden:

Einer Anzahl von Arbeitern soll die gleiche Anzahl Tätigkeiten bei bekannten (Ausführungs-)Kosten zugeordnet werden, wobei sich die Ausführungskosten von Arbeiter zu Arbeiter und von Aufgabe zu Aufgabe unterscheiden.

  • Jedem Arbeiter wird genau eine Tätigkeit zugeordnet und jede Tätigkeit wird von genau einem Arbeiter ausgeführt.
  • Anschließend wird unter allen zulässigen Plänen der kostenminimale Arbeitsplan gewählt.

Mathematisches Modell

[Bearbeiten | Quelltext bearbeiten]

Graphentheoretische Beschreibung

[Bearbeiten | Quelltext bearbeiten]

Es sei ein bipartiter, gewichteter Graph mit gegeben. Zwischen allen Knoten existiert je eine Kante, deren Gewicht die Kosten repräsentiert, die entstehen, wenn man und matcht.

Ziel ist es nun, ein maximales Matching mit minimalen Kosten zu finden.

Matrixdarstellung

[Bearbeiten | Quelltext bearbeiten]

Anlehnend an die Problembeschreibung können wir eine Matrix erzeugen, indem wir in die Zelle die Kosten eintragen, die entstehen, wenn wir dem Arbeiter die Aufgabe zuordnen.

Das Ziel ist es dann, eine Permutation der Zeilen der Matrix zu finden, die deren Spur minimiert.

Beschreibung als lineares Programm

[Bearbeiten | Quelltext bearbeiten]

Mit den (zu bestimmenden) Variablen

und den (gegebenen) Ausführungskosten ergibt sich das folgende mathematische Modell:

Minimiere die Kostensumme

unter den Nebenbedingungen

für ,
für .

Zeitkomplexität

[Bearbeiten | Quelltext bearbeiten]

Das Problem ist mithilfe der Ungarischen Methode in lösbar.

Beispiele und Aufwand

[Bearbeiten | Quelltext bearbeiten]

Beispiele für das lineare Zuordnungsproblem sind die Zuordnung von Schülern zu Schulprojekten oder die Zuordnung von Studenten auf Seminarplätze.

Für durchgerechnete Beispiele siehe Ungarische Methode, Beispiele.

Verallgemeinerungen und Varianten

[Bearbeiten | Quelltext bearbeiten]

Beim Zuordnungsproblem handelt es sich um einen Spezialfall eines maximalen Matchings minimalen Gewichtes in einem bipartiten, gewichteten Graphen.

Sind statt absoluten Kosten nur relative Kosten bekannt, so handelt es sich um ein Stable Marriage Problem.