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 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
• 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 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