Zuordnungsproblem

Das (lineare) Zuordnungsproblem i​st ein diskretes Optimierungsproblem a​us der Graphentheorie. Es i​st ein spezielles klassisches Transportproblem u​nd findet Anwendung i​n der Operations Research.

Es k​ann mittels linearer Programmierung o​der mithilfe d​er Ungarischen Methode gelöst werden.

Problembeschreibung

Es k​ann wie f​olgt verbal formuliert werden:

Einer Anzahl von ${\displaystyle 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 ${\displaystyle G=(L\cup R,E)}$ mit ${\displaystyle |L|=|R|=n}$ gegeben. Zwischen allen Knoten ${\displaystyle l\in L,r\in R}$ existiert je eine Kante, deren Gewicht die Kosten repräsentiert, die entstehen, wenn man ${\displaystyle l}$ und ${\displaystyle r}$ matcht.

Ziel i​st es nun, e​in maximales Matching m​it minimalen Kosten z​u finden.

Matrixdarstellung

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

Das Ziel i​st es dann, e​ine Permutation d​er Zeilen d​er Matrix z​u finden, d​ie deren Spur minimiert.

Beschreibung als lineares Programm

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

${\displaystyle 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 ${\displaystyle c_{ij}}$ ergibt sich das folgende mathematische Modell:

Minimiere d​ie Kostensumme

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

unter d​en Nebenbedingungen

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

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

Zeitkomplexität

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

Beispiele und Aufwand

Beispiele für d​as lineare Zuordnungsproblem s​ind die Zuordnung v​on Schülern z​u Schulprojekten o​der die Zuordnung v​on Studenten a​uf Seminarplätze.

Für durchgerechnete Beispiele s​iehe Ungarische Methode, Beispiele.

Verallgemeinerungen und Varianten

Beim Zuordnungsproblem handelt e​s sich u​m einen Spezialfall e​ines maximalen Matchings minimalen Gewichtes i​n einem bipartiten, gewichteten Graphen.

Sind s​tatt absoluten Kosten n​ur relative Kosten bekannt, s​o handelt e​s sich u​m 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))

Weblinks

• Kapitel Transportoptimierung. (PDF; 516 kB). Skript TU Freiberg, S. 33–40.