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 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
1 Motivation
Die Software „PanelGrouping”, welche sich mit der Bohrung von Leiterplatten beschäftigt, wirft folgendes Problem auf: Auf mehreren Lagen, aus denen eine Leiterplatte besteht, befinden sich Kupferkreise. Die Kupferkreise sind idealerweise untereinander, so dass durch eine einzige Bohrung ein ganzer Stapel von Kupferkreisen durchkontaktiert werden kann. Die Kupferkreise fungieren später als Lötaugen, wenn sie durchbohrt sind.
Um Zeit zu sparen, bohrt man oft einen ganzen Stapel gleichartiger Platten zusammen, indem man sie aufeinanderlegt und als Ganzes durchbohrt. Dies ist auch kein Problem, denn die Kupferkreise haben die gleiche Nominalposition. Leider haben aber die Kupferpads der einzelnen Platten infinitestimale Verrückungen, so dass sie beim Bohren nicht genau getroffen werden. Gesucht ist nun eine ebenfalls infinitestimale Verrückung der Bohrposition, so dass alle Kupferkreise möglichst mittig durchbohrt werden.
Die Summe der Center-Abweichungen (Bohrkoordinate zu den Pad-Koordinaten - jeweils die Mittelpunkte) soll minimal werden. Dies beschreibt sich zunächst als „Onecenter-Problem”. Nun will man aber bei der Verarbeitung einer Menge von Leiterplatten mit möglichst wenigen Bohrvorgängen auskommen. (D.h. für einen zu durchbohrenden Stapel Leiterplatten ist das Bohrzentrum gleich). Daher ordnet man eine Menge Leiterplatten zu möglichst wenigen Leiterplatten-Stapeln zu, die man als Ganzes durchbohren will. Dies induziert eine Partitionierung der Leiterplattenmenge und deren Zuordnung zu verschiedenen Bohrzentren. Dies ist sogar ein „Multicenter-Problem”.
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.
- Arbeit zitieren
- Thomas Plehn (Autor:in), 2017, MinSum- und MinMax-Optimierung für zwei Standorte. Darstellung, Erweiterung und Realisierung der Algorithmen von Z. Drezner als interaktive Java-Applikation, München, GRIN Verlag, https://www.grin.com/document/367545
