Zuordnungsproblem

Optimierungsproblem aus der Graphentheorie

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

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

Graphentheoretische Beschreibung

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

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

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

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

Beispiele und Aufwand

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

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.

Literatur

Bearbeiten
Bearbeiten