Das Zuordnungsproblem ist ein Problem der innerbetrieblichen Standortplanung, in dem es um die (kosten-)optimale Zuordnung von Organisationseinheiten zu Standorten geht. Ein vereinfachtes Problem ist das quadratische Zuordnungsproblem mit gleicher Anzahl von Organisationseinheiten und Standorten. Aufgrund der Nichtlinearität gehört es zur Klasse np-schwerer Probleme, deren Rechenaufwand bei steigender Variablenanzahl exponentiell ansteigt. Exakte Lösungen sind nur im begrenzten Umfang möglich. Approximationen der Optimallösung umfangreicherer Probleme ergeben sich durch Eingrenzung in obere und untere Schranken. Einen Approximationsversuch durch graphentheoretische Ansätze zur Linearisierung des Problems unternehmen Ball et al. in dem dieser Arbeit zugrunde liegenden Artikel ,,Networked-based formulation of the quadratic assignment problem."1
Diese anwendungsorientierte Seminararbeit verdeutlicht anhand eines Beispiels die Problematik des quadratischen Zuordnungsproblems, gibt eine Übersicht über die Grundmodelle und beschäftigt sich intensiv mit der Formulierung des netzwerkbasierten Ansatzes.
1 Ball et al. (1995)
Inhaltsverzeichnis
1. Einführung
2. Beispiel
3. Grundmodelle des quadratischen Zuordnungsproblems
3.1. Das Koopmans-Beckmann-Modell
3.1.1. Die Annahmen des Koopmans-Beckmann-Modells
3.1.2. Mathematische Formulierung
3.2. Varianten des Grundmodells
3.2.1. Explizite Berücksichtigung der Zuordnungskosten
3.2.2. Symmetrie
3.2.3. Überzahl an Standorten
3.3 Beispiel
4. Netzwerkbasierte Ansätze
4.1. Charakteristika und Arten netzwerkbasierter Ansätze
4.2. Der „große“ netzwerkbasierte Ansatz
4.2.1. Aufbau der Linearisierung
4.2.2. Modellierung
4.2.3. Validität der Formulierung
4.2.4. Beispiel
4.3. Der „kleine“ netzwerkbasierte Ansatz
4.3.1. Aufbau der Linearisierung
4.3.2. Modellierung
4.3.3. Validität der Formulierung
4.3.4. Beispiel
4.3.5. Ergänzende Bemerkungen zur Bestimmung unterer Schranken
4.4. Beurteilung und Leistungsfähigkeit der Ansätze
5. Zusammenfassung und Ausblick
6. Literaturverzeichnis
Zielsetzung & Themen
Das Hauptziel dieser Arbeit ist die Untersuchung des quadratischen Zuordnungsproblems (QAP) im Kontext der innerbetrieblichen Standortplanung. Es wird analysiert, wie das komplexe, NP-schwere Problem durch netzwerkbasierte Ansätze linearisiert werden kann, um bessere Möglichkeiten zur Bestimmung unterer Schranken zu erhalten.
- Grundlagen des quadratischen Zuordnungsproblems und des Koopmans-Beckmann-Modells
- Methoden der Linearisierung komplexer Zuordnungsprobleme
- Vergleich zwischen "großen" und "kleinen" netzwerkbasierten Formulierungen
- Anwendung mathematischer Optimierungsansätze und Beweisführung zur Validität
- Leistungsfähigkeit und Grenzen verschiedener Lösungsansätze
Auszug aus dem Buch
4.2.2. Modellierung
Die mathematische Darstellung des linearisierten Problems erfolgt mit folgend definierten Variablen.
xij = Transportmenge von Knoten i zu Knoten j
dij = Entfernung zwischen Standorten i und j
Fi+ = Gesamttransportmenge von Organisationseinheit i
Fi- = Gesamttransportmenge zu Organisationseinheit i
Die Zielfunktion summiert die Länge (Produkt aus Transportmenge und Entfernung) aller Pfeile aus Spalte 3-4, also alle möglichen Transportkombinationen bewertet mit deren Kosten. N Nebenbedingungen aus Gleichung (10) sichern, dass das Angebot der Organisationseinheiten transportiert wird. Die Nebenbedingungen aus (11) sichern, dass die Summe der individuellen Transportmengen aus Spalte 2-3 der gesamten Angebotsmenge einer Organisationseinheit gleicht.
Zusammenfassung der Kapitel
1. Einführung: Definition des quadratischen Zuordnungsproblems als NP-schwere Aufgabe der Standortplanung und Vorstellung der netzwerkbasierten Forschungsansätze.
2. Beispiel: Illustrative Darstellung der Zielsetzung des QAP anhand einer kleinen Instanz mit drei Standorten und drei Organisationseinheiten.
3. Grundmodelle des quadratischen Zuordnungsproblems: Erläuterung der Annahmen und mathematischen Formulierungen des Koopmans-Beckmann-Modells sowie gängiger Modellvarianten.
4. Netzwerkbasierte Ansätze: Detaillierte Analyse der Linearisierungsmethoden, unterteilt in einen "großen" und einen "kleinen" Ansatz, inklusive Validitätsbeweisen und Leistungsbeurteilung.
5. Zusammenfassung und Ausblick: Resümee über die Anwendbarkeit der vorgestellten Methoden und den Stand der Forschung zur exakten Lösung größerer Problemstellungen.
6. Literaturverzeichnis: Auflistung der verwendeten Quellen und wissenschaftlichen Publikationen.
Schlüsselwörter
Quadratisches Zuordnungsproblem, QAP, innerbetriebliche Standortplanung, Netzwerkformulierung, Linearisierung, Koopmans-Beckmann-Modell, NP-schwere Probleme, Transportkosten, Optimierung, untere Schranken, Constraint-Generating-Approach, mathematische Modellierung, Standortträger, Transportintensität, Standortplanung.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundlegend?
Die Arbeit befasst sich mit der mathematischen Modellierung und Optimierung des quadratischen Zuordnungsproblems (QAP) im Kontext der innerbetrieblichen Standortplanung.
Welche zentralen Themenfelder werden behandelt?
Zentral sind die theoretischen Grundlagen des QAP, die mathematische Formulierung durch Koopmans-Beckmann sowie die spezielle Methodik der Linearisierung durch netzwerkbasierte Ansätze.
Was ist das primäre Ziel der Forschungsarbeit?
Ziel ist es, zu zeigen, wie durch netzwerkbasierte Formulierungen (große und kleine Netzwerke) eine Linearisierung des Problems erreicht werden kann, um effizientere untere Schranken zu bestimmen.
Welche wissenschaftliche Methode wird verwendet?
Es werden mathematische Modellierungstechniken, graphentheoretische Ansätze zur Linearisierung sowie formale Beweise zur Validität der Modellformulierungen angewandt.
Was wird im Hauptteil detailliert behandelt?
Im Hauptteil werden das Koopmans-Beckmann-Modell sowie zwei spezifische netzwerkbasierte Formulierungen ("groß" und "klein") inklusive ihrer mathematischen Nebenbedingungen und Validitätsbeweise erläutert.
Welche Schlüsselwörter charakterisieren die Arbeit?
Zu den wichtigsten Begriffen zählen das quadratische Zuordnungsproblem, Linearisierung, Netzwerkformulierung, Standortplanung, Optimierung und untere Schranken.
Warum wird das "große" Netzwerk in der Praxis kritisch gesehen?
Das "große" Netzwerk bietet keine Verringerung der Komplexität, da diese bei O(n^4) verbleibt, und erbringt bei realen Problemgrößen keine konkurrenzfähige Performance.
Welchen Vorteil bietet der "kleine" netzwerkbasierte Ansatz?
Dieser Ansatz zeichnet sich durch eine überschaubare Knotenzahl von O(n^2) aus und ist insbesondere für die Berechnung unterer Schranken gegenüber klassischen Verfahren wie Gilmore-Lawler überlegen.
- Quote paper
- Christian Mechnik (Author), 2002, Modellierung des quadratischen Zuordnungsproblems, Munich, GRIN Verlag, https://www.grin.com/document/10092
