Aufgabe ist die Lösung des sog. „Twocenter-Problems”, welches exakt durch den sog. „MinSum-
Algorithmus” bzw. „MinMax-Algorithmus” für die MinMax-Probleme lösbar ist. Das Twocenter- Problem lässt sich auf viele konkrete Sachverhalte anwenden. Speziell auch auf die eingangs aufgeworfene Fragestellung bei der Durchbohrung von Leiterplatten. Allerdings sind einige praktische Formulierungen des Twocenter-Problems griffiger. Diese sollen im Anschluss als „Informelle Problemstellung” erörtert werden. Danach werde ich zu einer exakten mathematischen Fassung dieser Problemstellung kommen.
Der von [Drezner(1984a)] vorgeschlagene MinSum-Algorithmus soll vorgestellt, hergeleitet und bewiesen werden. Alle notwendigen mathematischen Hilfsmittel sollen ausgebreitet werden.
Ebenfalls soll diese Erörterung für den von [Drezner(1984a)] ebenfalls vorgeschlagenen MinMax-Algorithmus erfolgen.
Außerdem soll es eine Implementierung als Java-Applikation mit grafischer Benutzeroberfläche geben. Punkte sollen anklickbar, löschbar und verschiebbar sein, sowie das Ergebnis automatisch aktualisiert werden. Einige Ein- und Ausgaben der Implementierung werden am Ende der Erörterung beispielhaft gegeben.
Inhaltsverzeichnis
- 1 Motivation
- 1.1 Darstellung der Lösung als affine Abbildung
- 2 Aufgabenstellung
- 3 Anwendungsbeispiele zu Zwei-Zentren-Problemen
- 3.1 Supermarkt-Zentrallager
- 3.2 Postkästen-Postamt
- 3.3 MinMax-kritische Probleme
- 3.4 Drohnenflug
- 3.5 Problemstellung
- 4 Formale Definitionen zu MinSum- und MinMax-Problemen
- 5 Stand der Forschung
- 5.1 Sonderfall k-Means
- 6 Mathematische Grundlagen
- 6.1 Eigenschaften von Ein-Zentren-Problemen
- 6.2 Bestimmung der Trenngeraden
- 6.3 Laufzeitanalyse
- 7 Die Single-Facility-Lösung beim MinSum-Problem
- 7.1 Eigenschaften
- 7.2 Berechnung
- 7.2.1 Berechnung mittels Weizfeld-Prozedur
- 7.2.2 Berechnung mittels Powell-Algorithmus
- 7.2.3 Berechnung mittels Brent-Algorithmus
- 8 Die Two-Facility-Lösung beim MinSum-Problem
- 8.1 Eigenschaften
- 9 Der MinSum-Algorithmus
- 9.1 Idee des MinSum-Algorithmus
- 9.2 Der MinSum-Algorithmus 2
- 9.3 Abwandlung des MinSum-Algorithmus für gleichgroße Partitionen
- 10 Die Single-Facility-Lösung beim MinMax-Problem
- 10.1 Eigenschaften
- 10.1.1 Existenz der Single-Facility-Lösung für eine Teilmenge der konvexen Funktionen ICN
- 10.1.2 Stationäre Punkte der Zielfunktion bei nichtkonvexen Funktionen
- 10.2 Berechnung
- 10.2.1 Berechnung mittels eindimensionalen Parabel-Schnitten
- 10.2.2 Berechnung mittels geometrischer Kreis-Methode
- 10.2.3 Berechnung mittels Simplex-Verfahren
- 10.1 Eigenschaften
- 11 Die Two-Facility-Lösung beim MinMax-Problem
- 11.1 Eigenschaften
- 11.1.1 Kombinatorische Schranken für die Anzahl der Optimallösungen
- 11.1 Eigenschaften
- 12 Der MinMax-Algorithmus
- 12.1 Idee des MinMax-Algorithmus
- 12.2 Der MinMax-Algorithmus 2
- 12.3 Abwandlung des MinMax-Algorithmus für gleichgroße Partitionen
- 13 Implementierung
- 13.1 Verwaltung der Partitionen
- 13.2 Verwendete Optimierungsalgorithmen, verwendete Startpunkte
- 13.3 Erweiterung zur Speicherung der Lösung
- 13.4 Überprüfung der Lemmata auf Änderung der MinMax-Lösungen
- 14 Bedienung der Java-Applikation
- 15 Evaluation
- 15.1 zufälliges Twocenter
- 15.2 vier kollineare Punkte
- 15.3 ein rechter Winkel
- 15.4 zwei rechte Winkel
- 15.5 zwei Quadrate
- 15.6 ein Quadrat
- 15.7 zwei optimale Disks 1
- 15.8 zwei optimale Disks 2
Zielsetzung und Themenschwerpunkte
Die Masterarbeit beschäftigt sich mit der Optimierung von zwei Standorten (,,Two-Facility-Problem") für die Minimierung der Summe (,,MinSum") oder des Maximums (,,MinMax") der Abstände zu gegebenen Punkten. Diese Problemstellung ist relevant in verschiedenen Anwendungsbereichen, beispielsweise bei der Planung von Zentrallagern, Postämtern oder der Optimierung von Drohnenflügen.
- Formale Definition und mathematische Grundlagen von MinSum- und MinMax-Problemen
- Entwicklung und Analyse von Algorithmen zur Lösung von Two-Facility-Problemen
- Implementierung der Algorithmen in einer interaktiven Java-Applikation
- Evaluation der Algorithmen anhand verschiedener Testfälle
- Darstellung der Ergebnisse und Diskussion der Ergebnisse im Kontext der Anwendungsszenarien
Zusammenfassung der Kapitel
Die Masterarbeit beginnt mit einer Motivation des Themas, indem sie das Problem der Bohrung von Leiterplatten als Beispiel für ein Two-Facility-Problem darstellt. Anschließend werden formale Definitionen und mathematische Grundlagen für MinSum- und MinMax-Probleme erläutert. Die Arbeit untersucht den Stand der Forschung und präsentiert verschiedene Algorithmen zur Lösung von Single-Facility- und Two-Facility-Problemen. Die Algorithmen werden in einer interaktiven Java-Applikation implementiert und anhand von verschiedenen Testfällen evaluiert.
Schlüsselwörter
MinSum-Optimierung, MinMax-Optimierung, Two-Facility-Problem, Standortplanung, Zentrallager, Postamt, Drohnenflug, Algorithmen, Java-Applikation, Evaluation
- Citation du texte
- Thomas Plehn (Auteur), 2017, MinSum- und MinMax-Optimierung für zwei Standorte. Darstellung, Erweiterung und Realisierung der Algorithmen von Z. Drezner als interaktive Java-Applikation, Munich, GRIN Verlag, https://www.grin.com/document/367545
