Zuordnungsproblem

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

Es kann wie folgt verbal formuliert werden:

Einer Anzahl von $n$ 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

Graphentheoretische Beschreibung

Es sei ein bipartiter, gewichteter Graph $G=(L\cup R,E)$ mit $|L|=|R|=n$ gegeben. Zwischen allen Knoten $l\in L,r\in R$ existiert je eine Kante, deren Gewicht die Kosten repräsentiert, die entstehen, wenn man $l$ und $r$ matcht.

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

Matrixdarstellung

Anlehnend an die Problembeschreibung können wir eine $n\times n$ Matrix $A\in \mathbb {R} ^{n,n}$ erzeugen, indem wir in die Zelle $a_{i,j}$ die Kosten eintragen, die entstehen, wenn wir dem Arbeiter $i$ die Aufgabe $j$ zuordnen.

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

Beschreibung als lineares Programm

Mit den (zu bestimmenden) Variablen $x_{ij}$

$x_{ij}={\begin{cases}1,&{\text{falls Arbeiter i die Tätigkeit j ausführen soll}}\\0,&{\text{sonst}}\end{cases}}$

und den (gegebenen) Ausführungskosten $c_{ij}$ ergibt sich das folgende mathematische Modell:

Minimiere die Kostensumme

$F=\sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij}x_{ij}$

unter den Nebenbedingungen

$\sum _{j=1}^{n}x_{ij}=1$ für $i=1,\cdots ,n$ ,

$\sum _{i=1}^{n}x_{ij}=1$ für $j=1,\cdots ,n$ .

Zeitkomplexität

Das Problem ist mithilfe der Ungarischen Methode in ${\mathcal {O}}(n^{3})$ lösbar.

Beispiele und Aufwand

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

Verallgemeinerungen und Varianten

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

A. Bogatzki: Fabrikplanung: Verfahren zur Optimierung von Maschinenaufstellung. Diss. Universität Wuppertal 1998. Roderer, 1998, ISBN 3-89073-234-8.
Wolfgang Domschke, Andreas Drexl: Einführung in Operations Research. Springer, 2011, ISBN 978-3-642-18111-5, S. 188ff. ( Auszug (Google))

Basierend auf einem Artikel in:

Wikipedia.de