Zuordnungsprobleme

Standardmodelltyp der —kombinatorischen Optimierung, gleichzeitig Sonderfall des —Transportmodells. Es geht darum, die Ele- mente j = 1, 2, . n jeweils einem der Plätze i = 1, 2, n zuzuordnen, so dass der Wert der —Zielfunktion maximiert (bzw. minimiert) wird und die Restriktionen der Typen Zuordnungsprobleme

eingehalten werden. Der Variablenwert x_ii = 1 kennzeichnet die Zuordnung des Elementes j auf den Platz i, x_i; = 0 die Nichtzuordnung. Die Restriktionen erzwingen, dass erstens jedes Element einen Platz und zweitens jeder Platz ein Element erhält. Dieser Modelltyp gehört zur Klasse P (kombinatorische Optimierung). Zur Lösung eignen sich Verfahren der —linearen Optimierung und davon abgeleitete Spezialverfahren der Graphentheorie.

Wenn Elemente aus verschiedenen Mengen einander im Hinblick auf die Erfüllung einer bestimmten Zielsetzung zugeordnet werden, spricht man von einem Zuordnungsproblem (ZP).

Lineares ZP: Gegeben sind n Arbeiter, n Tätigkeiten und Kosten cij für die Ausführung der Tätigkeit j durch Arbeiter i. Die Aufgabe besteht darin, jedem Arbeiter genau eine Tätigkeit so zuzuordnen, dass die Gesamtkosten minimal sind. Das lineare ZP ist ein Spezialfall des Transportproblems mit n = m, ai = 1 für i = 1, . . . , m und bj = 1 für j=1,...,n und kann somit mit den entsprechenden Verfahren gelöst werden.

Quadratisches ZP: Im Rahmen der innerbetrieblichen Standortplanung sind Maschinen in einer Werkhalle anzuordnen. Dabei sind Entfernungen zwischen den Stellplätzen und Transportmengen von Werkstücken zwischen den Maschinen zu berücksichtigen, so dass sich im binären Optimierungsmodell neben den Nebenbedingungen des linearen ZP eine quadratische Zielfunktion ergibt. Es handelt sich daher um ein nichtlineares binäres Optimierungsmodell.

Das Zuordnungsproblem ist das Standardmodell der kombinatorischen Analyse im Operations Research und zugleich ein Spezialfall des Transportproblems. Es sollen die Elemente j = 1, 2, ..., n den Plätzen i = 1, 2, ..., n nur einmal so zugeordnet werden, daß der Wert der Zielfunktion maximiert oder minimiert wird.

resultieren dadurch, dass beispielsweise Arbeitskräfte zu gegebenen Jobs, Bewerber zu offenen Stellen, Aufträge zu Maschinen, Maschinen zu entsprechenden Stellplätzen in einer Produktionshalle oder Lieferungen an Kunden zu einzelnen Fahrzeugen des Fuhrparks optimal zugeordnet werden sollen. Derartige Probleme können im Allgemeinen als lineare oder quadratische Optimierungsmodelle (Optimierung) formuliert werden, für die entsprechende Lösungsmethoden des Operation Research verfügbar sind.

Vorhergehender Fachbegriff: Zuordnungsproblem | Nächster Fachbegriff: zurückgestaute Inflation

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Einzelabschreibung | ARPA | CDG

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer