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

Inhaltsverzeichnis

1 Motivation.. 5

1.1 Darstellung der Lösung als affine Abbildung.. 5

2 Aufgabenstellung.. 6

3 Anwendungsbeispiele zu Zwei-Zentren-Problemen.. 6

3.1 Supermarkt-Zentrallager.. 6

3.2 Postkästen-Postamt.. 7

3.3 MinMax-kritische Probleme.. 7

3.4 Drohnenflug.. 7

3.5 Problemstellung.. 8

4 Formale Definitionen zu MinSum- und MinMax-Problemen.. 9

5 Stand der Forschung.. 10

5.1 Sonderfall k-Means.. 11

6 Mathematische Grundlagen.. 12

6.1 Eigenschaften von Ein-Zentren-Problemen.. 12

6.2 Bestimmung der Trenngeraden.. 13

6.3 Laufzeitanalyse.. 15

7 Die Single-Facility-Lösung beim MinSum-Problem.. 16

7.1 Eigenschaften.. 16

7.2 Berechnung.. 17

7.2.1 Berechnung mittels Weizfeld-Prozedur.. 17

7.2.2 Berechnung mittels Powell-Algorithmus.. 19

7.2.3 Berechnung mittels Brent-Algorithmus.. 19

8 Die Two-Facility-Lösung beim MinSum-Problem.. 23

8.1 Eigenschaften.. 23

9 Der MinSum-Algorithmus.. 23

9.1 Idee des MinSum-Algorithmus.. 23

9.2 Der MinSum-Algorithmus 2.. 24

9.3 Abwandlung des MinSum-Algorithmus für gleichgroße Partitionen.. 26

10 Die Single-Facility-Lösung beim MinMax-Problem.. 28

10.1 Eigenschaften.. 28

10.1.1 Existenz der Single-Facility-Lösung für eine Teilmenge der konvexen Funktionen I in N.. 28

10.1.2 Stationäre Punkte der Zielfunktion bei nichtkonvexen Funktionen . . 29

10.2 Berechnung.. 30

10.2.1 Berechnung mittels eindimensionalen Parabel-Schnitten.. 30

10.2.2 Berechnung mittels geometrischer Kreis-Methode.. 30

10.2.3 Berechnung mittels Simplex-Verfahren.. 33

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

11.1 Eigenschaften.. 34

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

12 Der MinMax-Algorithmus.. 37

12.1 Idee des MinMax-Algorithmus.. 37

12.2 Der MinMax-Algorithmus 2.. 37

12.3 Abwandlung des MinMax-Algorithmus für gleichgroße Partitionen.. 39

13 Implementierung.. 40

13.1 Verwaltung der Partitionen.. 40

13.2 Verwendete Optimierungsalgorithmen, verwendete Startpunkte.. 40

13.3 Erweiterung zur Speicherung der Lösung.. 42

13.4 Überprüfung der Lemmata auf Änderung der MinMax-Lösungen.. 42

14 Bedienung der Java-Applikation.. 43

15 Evaluation.. 44

15.1 zufälliges Twocenter.. 44

15.2 vier kollineare Punkte.. 44

15.3 ein rechter Winkel.. 46

15.4 zwei rechte Winkel.. 46

15.5 zwei Quadrate.. 46

15.6 ein Quadrat.. 48

15.7 zwei optimale Disks 1.. 48

15.8 zwei optimale Disks 2.. 48

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, be- finden 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 weni- gen 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 Partitio- nierung der Leiterplattenmenge und deren Zuordnung zu verschiedenen Bohrzentren. Dies ist sogar ein „Multicenter-Problem”.

Zum Abschluss hat eine solche Leiterplatte natürlich an vielen Nominalpositionen Stapel mit Lötaugen auf den verschiedenen Lagen. Dies führt zunächst zu n Instanzen des Problems. Hier soll ein vereinfachtes Problem diskutiert werden, bei dem jedes Board nur eine Lage mit Lötaugen hat (keine mehrlagigen Aufbauten). Außerdem werden auch nur zwei Stapel aus der Menge der Leiterplatten gebildet. Es handelt sich um nur eine Instanz des Problems.

[...]