|
|
lineares Zuordnungsproblem
I. Charakterisierung: Standardproblem des Operations Research (OR), bei dem die Elemente einer Menge I und die Elemente einer Menge J einander zugeordnet werden sollen und weiterhin gilt: (1) Die Anzahl der Elemente in I und die Anzahl der Elemente in J sind gleich, d. h., jedem Element der Menge I ist genau ein Element der Menge J zuzuordnen und umgekehrt. (2) Durch Zuordnung des Elementes i (iI) zum Element j (jJ) entstehen Kosten cij. (3) Angestrebt werden möglichst geringe Gesamtkosten. (4) Gesucht ist ein Zuordnungsplan, der für jedes Element i (iI) angibt, welchem Element j(jJ) es zugeordnet werden soll. - Häufig synonym für dessen mathematische Formulierung.
II. Mathematische Formulierung:
unter den Restriktionen
(d.h. die Anzahl | I | der Elemente in I soll gleich der Anzahl | J | der Elemente in J sein), wobei x0 die Zielvariable und jedes xij eine Zuordnungsvariable mit
und I und J gewisse Indexmengen sind. Obiges Optimierungssystem wird auch als lineares Zuordnungssystem bezeichnet.
III. Eigenschaften: 1. Das Optimierungssystem läßt sich dem Bereich der ganzzahligen bzw. genauer der (vollständig) binären Optimierung zurechnen. - 2. Bei der Bestimmung einer optimalen Basislösung des Systems lassen sich die Restriktionen (4) durch Nichtnegativitätsrestriktionen
ersetzen. Das umgeformte System ist ein klassisches Transportsystem (vgl. im einzelnen klassisches Transportproblem).
IV. Lösungsverfahren: Aufgrund der Einordnung linearer Zuordnungssysteme in die binäre Optimierung lassen sich grundsätzlich deren sämtliche allgemeine Lösungsverfahren (binäres Optimierungsproblem) und -prinzipien, insbes. auch Branch-and-Bound-Verfahren, zur Bestimmung einer optimalen Lösung einsetzen. - Aufgrund der Äquivalenz von linearen Zuordnungssystemen und klassischen Transportsystemen sind grundsätzlich auch alle Verfahren zur Bestimmung optimaler Lösungen von klassischen Transportsystemen (klassisches Transportproblem) anwendbar. - Das wohl bekannteste spezielle Lösungsverfahren für lineare Zuordnungssysteme ist das Ungarische Verfahren.
V. Ökonomische Anwendungen: lineares Zuordnungsproblem Z. bilden die Grundstruktur einer Reihe ökonomischer Planungsprobleme in Industrie (wie etwa der Zuweisung von Arbeitskräften zu Arbeitsplätzen, der Zuweisung von Aufträgen zu Maschinen) und Verwaltung (Erstellung von Dienstplänen). Sie dienen v. a. als Vorbild bei der Modellierung derartiger Probleme, insbes. zur Vorbereitung des Computereinsatzes.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
