|
|
quadratisches 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 ist gleich der Anzahl der Elemente in J; jedem Element aus I soll genau ein Element aus J zugeordnet werden und umgekehrt. (2) Zwischen je zwei Elementen i und r aus der Menge I bestehen gewisse richtungsorientierte Kontakte von der Intensität dir bzw. dri. (3) Zwischen je zwei Elementen j und s der Menge J bestehen gewisse richtungsorientierte Entfernungen ejs und esj. (4) Durch die Zuordnung eines Elementes i aus I entstehen zum einen Kosten kij, die ausschl. davon abhängen, welchem Element j aus J dieses Element zugeordnet wird (Kosten der absoluten Zuordnung). Daneben entstehen durch die Zuordnung von i aus I noch weitere Kosten, deren Höhe davon abhängt, welchen Elementen aus J die übrigen Elemente aus I zugeordnet werden (Kosten der relativen Zuordnung). Für jedes Paar (i, r) von Elementen i und r aus I verhalten sich die Kosten der relativen Zuordnung, die im Zusammenhang mit der jeweiligen Kontaktintensität dir anfallen, proportional zur Entfernung ejs zwischen den Elementen j und s aus J, denen i und r zugeordnet sind. Weitere Kosten der relativen Zuordnung entstehen nicht. (5) Gesucht ist ein Zuordnungsplan, der für jedes Element aus I angibt, welchem Element aus J es zugeordnet werden soll bei möglichst geringen Gesamtkosten. Häufig auch synonym für dessen mathematische Formulierung.
II. Mathematische Formulierung: Minimiere:
unter den Restriktionen:
(x0 = Gesamtkosten der Zuordnung; cir = Kosten (der relativen Zuordnung), die bei der Kontaktintensität dir zwischen i und r (i, r I) pro Entfernungseinheit anfallen; xij = Zuordnungsvariable mit
In Verbindung mit (4) und (5) fordern die Restriktionen (2) und (3), daß jedem Element i I genau ein Element j J zugeordnet wird, und umgekehrt. (5) besagt, daß die Anzahl I der Elemente in I gleich der Anzahl J der Elemente in J sein muß.
III. Varianten: 1. Die mathematische Formulierung eines quadratischen Zuordnungsproblems bezeichnet man als ein Koopmans-Beckmann-Problem, wenn die Zielfunktion (1) speziell die Gestalt
hat. - Gilt außerdem für jedes Paar (i, r) von Elementen i und r der Menge Icir = cri (i, r I) und/oder jedes Paar (j, s) von Elementen j, s der Menge Jejs = esj, so spricht man von einem symmetrischen Koopmans-Beckmann-Problem; gilt dagegen circri (i, r I) für mindestens ein Paar (i, r) von Elementen i, r der Menge I und ejsesj (i, s J) für mindestens ein Paar (j, s) von Elementen j und s der Menge J, so liegt ein asymmetrisches Koopmans-Beckmann-Problem vor. - 2. Anstelle der Zielfunktion (1) verwendet man auch die Zielfunktion
spricht dann von einem allgemeinen quadratischen Optimierungssystem. (1) läßt sich dabei in (1´´) durch die Transformation:
überführen.
IV. Lösungsverfahren: 1. Für q. Z. stehen verschiedene exakte Lösungsverfahren zur Verfügung, denen die Branch-and-Bound-Methode zugrunde liegt. Diese Verfahren sind aber sehr rechenaufwendig und damit kaum zur Untersuchung von Praxisproblemen geeignet. - 2. Entsprechendes gilt für die theoretisch ebenfalls zu optimalen Lösungen führenden Schnittebenenverfahren, die auf entsprechende gemischt-binäre Optimierungssysteme mit linearer Zielfunktion, in die sich etwa Systeme des Typs ((1´), (2), (3), (4), (5)) transformieren lassen, anwendbar sind. - 3. Die meisten (heuristischen) Eröffnungsverfahren bestehen aus n = I Teilschritten, wobei in jedem Schritt genau ein noch nicht zugeordnetes Element i (i I) ausgewählt und einem noch freien Element s (s J) zugeordnet wird. - 4. Verbesserungsverfahren gehen von einer zulässigen Lösung aus und versuchen i. d. R. zu besseren Lösungen zu gelangen, indem zwei oder mehrere Elemente der Menge I gegen die ihnen zugeordneten Elemente der Menge J ausgetauscht werden.
V. Anwendung: quadratisches Zuordnungsproblem Z. spielen bei der Untersuchung von Problemen der Layoutplanung (innerbetriebliche Standortplanung) eine gewisse Rolle. Weitere Anwendungen sind von der Planung der Tastaturbelegung bei Schreibmaschinen bekannt.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
