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.

Definition[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Mit der (zu bestimmenden) Variablen

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

Minimiere die Kostensumme

unter den Nebenbedingungen

für
für

Methoden[Bearbeiten | Quelltext bearbeiten]

Dies Problem ist mittels der Ungarischen Methode lösbar.

Beispiele und Aufwand[Bearbeiten | Quelltext bearbeiten]

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]