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 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

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

Minimiere

unter den Nebenbedingungen

für
für

Dies Problem ist mittels der Ungarischen Methode lösbar. Beispiele für das lineare Zuordnungsproblem sind die Zuordnung von Schülern zu Schulprojekten 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 nur bei geringer Anzahl mit einfachen Algorithmen lösbar. Bei größeren Problemen kommen Heuristiken zum Einsatz.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]