Diese Arbeit beschäftigt sich im Rahmen eines Seminarvortrags mit dem median line Problem, einem Teilgebiet der Standortoptimierung. Speziell wird dieses Optimierungsproblem hier im dreidimensionalen reellen Vektorraum, versehen mit der Euklidischen Norm, behandelt.
Zu gegebenen Punkten des R3 wird eine Gerade gesucht, so dass die Summe der Abstände der gegebenen Punkte zu dieser Geraden minimal wird. Zur Lösung dieses Problem wird eine geometrische Variante des Branch and Bound Algorithmus vorgestellt (vgl. Kapitel 3). Im Vorfeld wird das median line Problem in Kapitel 2 eingehend betrachtet. Dabei spielt besonders eine Parametrisierung des gegebenen Problems eine große Rolle. Der vierte Abschnitt beschäftigt sich mit der Berechnung von unteren Schranken der optimalen Lösung des Problems. Abschließend werden kurz praktische Ergebnisse diskutiert.
Inhaltsverzeichnis
1 Einleitung
2 Das 'median line' Problem
2.1 Die Gerade im R^3
2.2 Problemformulierung
2.3 Eigenschaften
2.4 Parametrisierung des Problems
3 Der geometrische Branch-and-Bound Algorithmus
4 Berechnung unterer Schranken
4.1 Die natürliche Intervallerweiterung
4.2 Allgemeine Bounding-Verfahren
4.3 Untere Schranken des median line Problems
Zielsetzung & Themen
Die Arbeit befasst sich mit dem sogenannten 'median line' Problem, einer speziellen Aufgabenstellung der Standortoptimierung. Ziel ist es, für eine Menge gegebener Punkte im dreidimensionalen euklidischen Raum eine Gerade zu finden, welche die Summe der Abstände zu diesen Punkten minimiert, wofür ein geometrischer Branch-and-Bound Algorithmus angewendet wird.
- Mathematische Modellierung der Geraden im R^3
- Formulierung des Optimierungsproblems und dessen Parametrisierung
- Anwendung des geometrischen Branch-and-Bound Algorithmus
- Berechnung und Analyse effizienter unterer Schranken
Auszug aus dem Buch
2.1 Die Gerade im R^3
Ausgehend von der Punkt-Richtungs-Gleichung hat eine Gerade r im R^3 die Form
r = r(x, d) = {x + td : t ∈ R},
wobei d ∈ R^3\{0} die Richtung von r darstellt und x ∈ R^3 ein Punkt auf der Gerade ist. Für eine Gerade gibt es keine eindeutige Darstellung. Man sieht leicht, dass für beliebige λ, μ ∈ R, μ ≠ 0 gilt
r(x + λd, d) = r(x, d) = r(x, μd).
Diese Variabilität in der mathematischen Darstellung einer Geraden wird im weiteren Verlauf für die Parametrisierung der median line Problems genutzt.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in das median line Problem als Teilgebiet der Standortoptimierung ein und skizziert den Aufbau der Arbeit sowie die Verwendung des Branch-and-Bound Algorithmus.
2 Das 'median line' Problem: Dieses Kapitel definiert die mathematischen Grundlagen der Geraden im R^3, formuliert das Optimierungsproblem präzise und leitet dessen Eigenschaften sowie eine effiziente Parametrisierung her.
3 Der geometrische Branch-and-Bound Algorithmus: Hier wird das allgemeine Vorgehen des Branch-and-Bound Algorithmus zur globalen Optimierung vorgestellt und auf das median line Problem zugeschnitten.
4 Berechnung unterer Schranken: Dieses Kapitel befasst sich mit der Bestimmung von unteren Schranken mittels Intervallarithmetik und spezieller Bounding-Verfahren, um die Effizienz des Optimierungsalgorithmus zu steigern.
Schlüsselwörter
Standortoptimierung, median line Problem, euklidischer Raum, Branch-and-Bound Algorithmus, Intervallarithmetik, mathematische Optimierung, untere Schranken, Geradengleichung, Zielfunktion, Konvexität, Bounding-Verfahren, Standortproblem, dreidimensionaler Raum.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der mathematischen Optimierung zur Bestimmung einer optimalen Geraden im dreidimensionalen Raum, die den Abstand zu einer gegebenen Punktemenge minimiert.
Welche zentralen Themenfelder werden behandelt?
Die zentralen Themen umfassen die geometrische Standortoptimierung, die algorithmische Lösung mittels Branch-and-Bound sowie die Berechnung von unteren Schranken durch Intervallmethoden.
Was ist das primäre Ziel oder die Forschungsfrage?
Das primäre Ziel ist die effiziente Lösung des median line Problems im dreidimensionalen Raum durch die Herleitung einer geeigneten Parametrisierung und deren Optimierung.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine geometrische Variante des Branch-and-Bound Algorithmus unter Nutzung der Intervallarithmetik zur Berechnung unterer Schranken verwendet.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil behandelt die mathematische Modellierung, die Parametrisierung des Optimierungsproblems und die algorithmische Implementierung zur effizienten Suche nach dem globalen Minimum.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit ist durch Begriffe wie Standortoptimierung, median line Problem, Branch-and-Bound Algorithmus und Intervallarithmetik geprägt.
Warum ist die Darstellung der Geraden in Kapitel 2 nicht eindeutig?
Da eine Gerade durch einen Punkt und einen Richtungsvektor definiert ist, können verschiedene Punkte auf der Gerade sowie skalierte Richtungsvektoren dieselbe Gerade repräsentieren.
Wie unterscheidet sich die Effizienz der unteren Schranken LB1 und LB2 in der Praxis?
Die in Kapitel 4 hergeleitete Schranke LB2 erweist sich laut der vergleichenden Tabelle in der Praxis als deutlich effizienter hinsichtlich Rechenzeit und Iterationsanzahl als LB1.
- Arbeit zitieren
- Sarah Lehnhardt (Autor:in), 2014, Das 'median line'-Standortproblem im dreidimensionalen euklidischen Raum, München, GRIN Verlag, https://www.grin.com/document/336381
