Zuordnungsproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 wie folgt verbal formuliert werden:

Einer Anzahl (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 Aufgabe zu Aufgabe unterscheiden.

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


Mit der 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 Ausführungskosten c_{ij} ergibt sich das folgende mathematische Modell:

Minimiere

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,…,n
\sum_{i=1}^n x_{ij}=1 für j=1,…,n


Dies Problem ist mittels der Ungarischen Methode lösbar. Beispiele für das lineare Zuordnungsproblem sind die Zuordnung von Schülern zu Schulen oder die Zuordnung von Studenten auf Seminarplätze. Das quadratische Zuordnungsproblem hat mit dem linearen Problem identische Nebenbedingungen, allerdings ist die Zielfunktion quadratisch. Es kann beispielsweise in der Werkstattfertigung zu einer Zuordnung von Maschinen auf Stellplätze genutzt werden, bei der die Summe der Produkte aus Transportmengen und Entfernungen minimal wird. Diese Problemklasse ist np-schwer und daher nicht mit einfachen Algorithmen lösbar.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]