MinSum- und MinMax-Optimierung für zwei Standorte. Darstellung, Erweiterung und Realisierung der Algorithmen von Z. Drezner als interaktive Java-Applikation

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 I ⊂ N

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

11 Die Two-Facility-Lösung beim MinMax-Problem

11.1 Eigenschaften

11.1.1 Kombinatorische Schranken für die Anzahl der Optimallösungen

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 & Themen

Das Hauptziel dieser Masterarbeit ist die Untersuchung, mathematische Herleitung und effiziente algorithmische Implementierung von Algorithmen zur Lösung des sogenannten "Twocenter-Problems". Dabei wird der Fokus auf die MinSum- und MinMax-Optimierung gelegt, um eine interaktive Java-Applikation zur Visualisierung und Lösung dieser Standortprobleme zu entwickeln.

• Mathematische Modellierung von MinSum- und MinMax-Problemen
• Algorithmen von Z. Drezner für die Zwei-Zentren-Problematik
• Methoden zur effizienten Ein-Zentren-Optimierung (Powell, Brent, Weizfeld)
• Implementierung einer grafischen Java-Benutzeroberfläche zur interaktiven Evaluation

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 Motivation: Einführung in die Problemstellung am Beispiel der Leiterplattenbohrung und Motivation für das Zwei-Zentren-Problem.

2 Aufgabenstellung: Definition der Zielsetzung der Arbeit, inklusive der Anforderung einer interaktiven Java-Implementierung.

3 Anwendungsbeispiele zu Zwei-Zentren-Problemen: Vorstellung praktischer Einsatzszenarien wie Supermärkte, Postämter und Rettungshubschrauber.

4 Formale Definitionen zu MinSum- und MinMax-Problemen: Mathematische Herleitung der Zielfunktionen für die betrachteten Optimierungsprobleme.

5 Stand der Forschung: Überblick über existierende Algorithmen und deren Komplexitätsklassen zur Lösung von Mehrzentren-Problemen.

6 Mathematische Grundlagen: Herleitung theoretischer Eigenschaften, wie der Trennbarkeit durch eine gerade Linie, sowie Analyse der Laufzeiten.

7 Die Single-Facility-Lösung beim MinSum-Problem: Diskussion von Eigenschaften und numerischen Berechnungsmethoden wie dem Powell-Algorithmus.

8 Die Two-Facility-Lösung beim MinSum-Problem: Kurze Zusammenfassung der Eigenschaften des Zwei-Zentren-Falls für das MinSum-Problem.

9 Der MinSum-Algorithmus: Detaillierte Beschreibung der algorithmischen Umsetzung inklusive der Theta-Prozedur.

10 Die Single-Facility-Lösung beim MinMax-Problem: Analyse der konvexen Optimierung für das MinMax-Ziel und Vorstellung der Parabel-Schnitt-Methoden.

11 Die Two-Facility-Lösung beim MinMax-Problem: Untersuchung der kombinatorischen Schranken und Eigenschaften optimaler Lösungen.

12 Der MinMax-Algorithmus: Beschreibung der algorithmischen Vorgehensweise zur effizienten Lösung von MinMax-Problemen.

13 Implementierung: Dokumentation der technischen Umsetzung, der verwendeten Bibliotheken und der Datenstrukturen.

14 Bedienung der Java-Applikation: Erläuterung der grafischen Benutzeroberfläche und der Interaktionsmöglichkeiten.

15 Evaluation: Durchführung und Diskussion verschiedener Testfälle zur Validierung der Implementierung.

Schlüsselwörter

Twocenter-Problem, MinSum-Optimierung, MinMax-Optimierung, Standortplanung, Algorithmus von Drezner, Java-Applikation, Partitionierung, Ein-Zentren-Problem, Geometrische Optimierung, Powell-Algorithmus, Brent-Solver, Weizfeld-Prozedur, Leiterplattenbohrung, Cluster-Analyse, Konvexität.

Häufig gestellte Fragen

Worum geht es in der Arbeit grundlegend?

Die Arbeit befasst sich mit der Lösung des sogenannten Twocenter-Problems, bei dem eine Menge von Punkten in der euklidischen Ebene optimal in zwei Teilmengen partitioniert und für jede Teilmenge ein Zentrum gefunden werden soll.

Was sind die zentralen Themenfelder?

Die zentralen Themen sind die mathematische Modellierung von Standortproblemen (MinSum und MinMax), die algorithmische Komplexitätsanalyse sowie die softwaretechnische Umsetzung in einer interaktiven Java-Anwendung.

Was ist das primäre Ziel der Arbeit?

Das primäre Ziel ist es, die Algorithmen von Z. Drezner zur Lösung der Zwei-Zentren-Probleme darzustellen, mathematisch zu beweisen und in einer Applikation zu implementieren, die es Nutzern ermöglicht, Punktmengen interaktiv zu optimieren.

Welche wissenschaftlichen Methoden werden verwendet?

Es kommen Verfahren der konvexen Optimierung zum Einsatz, darunter die Weizfeld-Prozedur, der Powell-Algorithmus für differenzierbare Funktionen, der Brent-Solver für eindimensionale Intervalle und das Simplex-Verfahren.

Was wird im Hauptteil der Arbeit behandelt?

Der Hauptteil gliedert sich in die mathematische Fundierung, die detaillierte Beschreibung der MinSum- und MinMax-Algorithmen, die Implementierungsdetails zur Partitionierungsverwaltung sowie die praktische Evaluation mittels beispielhafter Szenarien.

Welche Schlüsselwörter charakterisieren die Arbeit?

Die Arbeit lässt sich vor allem durch Begriffe wie Twocenter-Problem, MinSum-Optimierung, MinMax-Optimierung, Geometrische Optimierung und Standortplanung beschreiben.

Warum wird für die Implementierung "Apache Commons Math" genutzt?

Die Bibliothek wurde gewählt, um effiziente und robuste Standard-Optimierungsalgorithmen für die benötigten Ein-Zentren-Teilprobleme direkt nutzen zu können, statt diese grundlegend neu zu entwickeln.

Wie werden die Partitionen der Punktmengen verwaltet?

Die Partitionen werden als angeordnete Mengen (Schlangen-Struktur) verwaltet, wobei die Anordnung durch eine zyklische Verkettung der Punkte beibehalten wird, was effiziente Verschiebungen zwischen den Gruppen erlaubt.

Warum wird die Theta-Prozedur eingesetzt?

Die Theta-Prozedur wird verwendet, um systematisch alle für eine Optimalpartitionierung infrage kommenden Trenngeraden und damit die dazugehörigen Punkt-Partitionen zu generieren.