3460 lines
157 KiB
Plaintext
3460 lines
157 KiB
Plaintext
Ralf Hollstein
|
||
Optimierungsmethoden
|
||
Einführung in die klassischen, naturanalogen und neuronalen Optimierungen
|
||
|
||
Optimierungsmethoden
|
||
|
||
Ralf Hollstein
|
||
Optimierungsmethoden
|
||
Einführung in die klassischen, naturanalogen und neuronalen Optimierungen
|
||
|
||
Ralf Hollstein Linnich, Deutschland
|
||
|
||
ISBN 978-3-658-39854-5
|
||
|
||
ISBN 978-3-658-39855-2 (eBook)
|
||
|
||
https://doi.org/10.1007/978-3-658-39855-2
|
||
|
||
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
|
||
|
||
© Der/die Herausgeber bzw. der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer Nature 2023 Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags. Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von allgemein beschreibenden Bezeichnungen, Marken, Unternehmensnamen etc. in diesem Werk bedeutet nicht, dass diese frei durch jedermann benutzt werden dürfen. Die Berechtigung zur Benutzung unterliegt, auch ohne gesonderten Hinweis hierzu, den Regeln des Markenrechts. Die Rechte des jeweiligen Zeicheninhabers sind zu beachten. Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informationen in diesem Werk zum Zeitpunkt der Veröffentlichung vollständig und korrekt sind. Weder der Verlag, noch die Autoren oder die Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige Fehler oder Äußerungen. Der Verlag bleibt im Hinblick auf geografische Zuordnungen und Gebietsbezeichnungen in veröffentlichten Karten und Institutionsadressen neutral.
|
||
|
||
Planung/Lektorat: David Imgrund Springer Vieweg ist ein Imprint der eingetragenen Gesellschaft Springer Fachmedien Wiesbaden GmbH und ist ein Teil von Springer Nature. Die Anschrift der Gesellschaft ist: Abraham-Lincoln-Str. 46, 65189 Wiesbaden, Germany
|
||
|
||
Für Marita, Melanie und Leo
|
||
|
||
Vorwort
|
||
Optimierungen spielen in allen Lebensbereichen eine wichtige Rolle, sei es, um Kosten, Ressourcen, Risiken, Bearbeitungszeiten, Umweltbelastungen, Energieverbrauch, Reise- und Transportzeiten zu minimieren oder Gewinn, Motorleistung, Portfolio, Produktion, Umsatz und sportliche Leistungen zu maximieren. Die Optimierungsprobleme in der realen Welt sind vielfältig und unterscheiden sich in der Komplexität. In der Literatur gibt es eine unübersehbare Vielzahl von Optimierungsmethoden, davon wiederum Varianten und Untervarianten. Dieses Buch gibt einen Überblick zu den wichtigsten Optimierungsmethoden, wobei die Verfahren beispielhaft vorgestellt werden. Auf detaillierte Erläuterungen zur Theorie der in diesem Buch beschriebenen Verfahren wird verzichtet und auf die einschlägige Literatur verwiesen.
|
||
Zu vielen Optimierungsproblemen kann das Optimum bei größeren Eingabegrößen nicht in akzeptabler Zeit exakt bestimmt werden. Deshalb wendet man für komplexere Optimierungsprobleme sogenannte heuristische Verfahren an, die zwar nicht notwendigerweise die beste Lösung liefern, aber dafür in vertretbarer Zeit möglichst gute Lösungen finden. Beispielsweise ist in Kommunikationsnetzen beim dynamischen Routen von Datenpaketen nicht entscheidend, den kürzesten Weg zum Zielknoten zu bestimmen, sondern in möglichst kurzer Zeit einen möglichst kurzen Weg zu ermitteln. Bei vielen Optimierungsproblemen stoßen herkömmliche Großrechner an ihre Grenzen, wie zum Beispiel bei der Nutzung von Stromnetzen oder bei der optimalen Steuerung des Verkehrsflusses in einer Stadt. Hierbei muss der Verkehrsfluss dynamisch gesteuert werden, Staus müssen erkannt und Ersatzrouten bei ständig sich verändernden Optima gefunden werden. Dazu spielen effiziente Optimierungsalgorithmen eine wichtige Rolle.
|
||
Bei der Entwicklung von heuristischen Optimierungsverfahren werden gezielt Lösungen in der Biologie gesucht, analog wie in der Bionik, bei der zur Lösung von technischen Problemen Konstruktionen und Strukturen aus der Natur nachgeahmt werden. Dazu zählen beispielsweise der Klettverschluss nach dem Vorbild einer Klette, die Konstruktion von Flugzeugen nach dem Vorbild der Vögel, die selbstreinigenden Oberflächen nach dem Vorbild von Lotusblättern oder die Form
|
||
VII
|
||
|
||
VIII
|
||
|
||
Vorwort
|
||
|
||
des japanischen Shinkansen-Schnellzuges nach dem Vorbild des Eisvogelschnabels zur Lärmreduzierung.
|
||
Bei der Entwicklung von naturinspirierten Optimierungsverfahren stehen die Verfahrensweisen der Natur im Vordergrund. Zu den bekanntesten Optimierungsmethoden zählen die evolutionären Algorithmen, die sich am Vorbild der natürlichen Evolution orientieren. Die Grundprinzipien der Evolution wie Mutation, Rekombination und Selektion lassen sich algorithmisch in Optimierungsverfahren umsetzen, die breite Anwendung in vielen Gebieten finden. Bei diesen natu r-analogen Optimierungsverfahren werden Ausgangslösungen so lange verändert und kombiniert, bis eine dieser Lösungen zu den Anforderungen passt. Ebenfalls weitverbreitet sind Optimierungsmethoden, die das Verhalten von Schwärmen imitieren. Schwärme bilden eine Gruppe von vielen primitiven Lebewesen, die komplexe Fähigkeiten entwickeln können, was man als Schwarmintelligenz bezeichnet. Beobachtet man etwa Ameisen bei der Nahrungssuche, so kann man feststellen, dass die Ameisen von ihrem Nest zum Futterplatz meistens den kürzesten Weg finden. Die Optimierungsmethode, die diese Optimierungsstrategie nachahmt, konnte erfolgreich in vielen Bereichen angewendet werden, wie zum Beispiel bei der Tourenplanung. Es haben sich weitere schwarmbasierte Optimierungsmethoden etabliert, unter anderem Verfahren, die Optimierungsstrategien von Bienen und Vögeln imitieren. Ebenfalls lassen sich viele Probleme mithilfe von sogenannten künstlichen Immunsystemen lösen, die Konzepte natürlicher Immunsysteme bei der Bekämpfung von Antigenen wie Bakterien, Viren, Pilzen und Parasiten nachahmen.
|
||
Im ersten Teil werden verschiedene Optimierungsprobleme vorgestellt. Gegenstand des zweiten Teils sind klassische Methoden zur Lösung von Optimierungsproblemen. Im dritten Teil werden naturanaloge Optimierungsmethoden behandelt.
|
||
Gegenstand des letzten Teils des Buches sind Optimierungen von künstlichen neuronalen Netzen sowie Methoden des maschinellen Lernens zur Lösung von Optimierungsproblemen. Das künstliche neuronale Netz ist dem Aufbau des biologischen Gehirns nachempfunden. Es besteht aus Neuronen (Knoten), die über sogenannte Kanten mit anderen Neuronen verbunden sind und Informationen modifiziert an andere Neuronen weiterleiten.
|
||
Ein neues Forschungsgebiet sind neuronale kombinatorische Optimierungsverfahren, abgekürzt NCO. Dieser Begriff ist von Bello et al. 2015 eingeführt worden. Die NCO-Methoden stellen einen Strategie-Wechsel dar. Bei der herkömmlichen Programmierung einer Heuristik erhält der Computer Anweisungen zur Bestimmung einer brauchbaren Lösung des Optimierungsproblems. Dagegen ermittelt der Computer mit dem NCO-Verfahren selbstständig ohne menschliche Hilfe die Heuristik, wobei die Heuristik im Verborgenen bleibt. Dabei werden Verfahren aus dem Bereich des maschinellen Lernens angewendet. Dazu stehen vorprogrammierte Module aus Programmbibliotheken wie z. B. TensorFlow zur Verfügung. Der wesentliche Vorteil der NCO-Methoden besteht darin, dass diese Verfahren auf praktische Optimierungsprobleme anwendbar sind, zu denen keine guten Heuristiken existieren. Dieses Buch gibt eine Einführung in dieses neue vielversprechende Forschungsgebiet der KI-basierten, selbstlernenden Optimierungsalgorithmen.
|
||
|
||
Vorwort
|
||
|
||
IX
|
||
|
||
Das Buch dient als Einstieg in die Optimierungsverfahren und wendet sich an Anwender auf den Gebieten der praktischen Optimierung sowie an Studierende der Informatik, Mathematik, Wirtschaftswissenschaften und Ingenieurwissenschaften.
|
||
|
||
Linnich September 2022
|
||
|
||
Ralf Hollstein
|
||
|
||
Inhaltsverzeichnis
|
||
Teil I Optimierungsprobleme 1 Einführung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
|
||
1.1 Optimierungsprobleme in der realen Welt. . . . . . . . . . . . . . . . . 3 1.2 Grundbegriffe der Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . 5
|
||
1.2.1 Globales und lokales Optimum. . . . . . . . . . . . . . . . . 5 1.2.2 Umwandlung eines Maximierungsproblems
|
||
in ein Minimierungsproblem und umgekehrt. . . . . . . 5 1.2.3 Notationen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4 Supremum und Infimum . . . . . . . . . . . . . . . . . . . . . . 6 1.2.5 Kontinuierliche, diskrete und kombinatorische
|
||
Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Kontinuierliche Optimierungsprobleme. . . . . . . . . . . . . . . . . . . . . . . 9
|
||
2.1 Graph einer Funktion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Optimierungen mit Nebenbedingungen. . . . . . . . . . . . . . . . . . . 10 2.3 Anwendungsbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Unimodale und multimodale Funktionen . . . . . . . . . . . . . . . . . 14 2.5 Konvexe und konkave Funktionen. . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Extrema konvexer und konkaver Funktionen. . . . . . . . . . . . . . . 15 3 Kombinatorische Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . 17 3.1 Einführende Beispiele. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
|
||
3.1.1 Problem des Handlungsreisenden . . . . . . . . . . . . . . . 18 3.1.2 Rucksackproblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Lösungspräsentationen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2.1 Kombinatorik. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.2 Graphen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Graphenprobleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3.1 Knotenüberdeckungsproblem . . . . . . . . . . . . . . . . . . 28 3.3.2 Maximales Cliquenproblem. . . . . . . . . . . . . . . . . . . . 29 3.3.3 Stabilitätsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
|
||
XI
|
||
|
||
XII
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
3.3.4 Zusammenhang zwischen Stabilitäts-, Knotenüberdeckungs- und maximalem Cliquenproblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
|
||
3.3.5 Graphen-Färbungsproblem . . . . . . . . . . . . . . . . . . . . 33 3.3.6 Max-Cut-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Vehicle-Routing-Probleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4.1 Einführendes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4.2 Grundversion des VRP. . . . . . . . . . . . . . . . . . . . . . . . 39 3.4.3 Varianten des VRP. . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5 Scheduling-Probleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.5.1 Einführendes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.2 Grundversion des Scheduling-Problems. . . . . . . . . . 42 3.5.3 Klassifikation von Scheduling-Problemen. . . . . . . . . 44 3.5.4 Beispiele von Scheduling-Problemen . . . . . . . . . . . . 44 3.6 Zuschnittprobleme und Packungsprobleme. . . . . . . . . . . . . . . . 45 3.6.1 Dimension von Zuschnitt- und
|
||
Packungsproblemen. . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.6.2 Bin-Packing-Problem. . . . . . . . . . . . . . . . . . . . . . . . . 46 3.6.3 Eindimensionale C&P-Probleme. . . . . . . . . . . . . . . . 46 3.6.4 Zweidimensional C&P-Probleme . . . . . . . . . . . . . . . 47 3.6.5 Dreidimensionale C&P-Probleme. . . . . . . . . . . . . . . 49 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
|
||
4 Lineare Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.1 Einführungsbeispiel (Produktionsproblem). . . . . . . . . . . . . . . . 51 4.2 Standardform eines linearen Optimierungsproblems. . . . . . . . . 52 4.3 Anwendungsbeispiel (Transportproblem). . . . . . . . . . . . . . . . . 53 4.4 Ganzzahlige lineare Optimierungsprobleme. . . . . . . . . . . . . . . 54
|
||
5 Multikriterielle Optimierungsprobleme. . . . . . . . . . . . . . . . . . . . . . . 57 5.1 Definitionen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.2 Multikriterielles Optimierungsproblem in der Grundversion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.3 Einführendes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.4 Pareto-Dominanz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
|
||
|
||
Teil II Klassische Optimierungsmethoden
|
||
6 Analytische Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.1 Grundbegriffe der Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.1.1 Definitionen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.2 Der Satz vom Maximum und Minimum . . . . . . . . . . . . . . . . . . 67 6.3 Ableitung einer Funktion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.3.1 Sekanten- und Tangentensteigung. . . . . . . . . . . . . . . 68 6.3.2 Ableitung einer Funktion. . . . . . . . . . . . . . . . . . . . . . 69 6.3.3 Beispiele von Ableitungen und Ableitungsregeln . . . 69
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
XIII
|
||
|
||
6.4 Extremwertbestimmung für Funktionen mit einer Variablen. . . 70 6.5 Extremwertbestimmung für Funktionen mit zwei Variablen. . . 72
|
||
6.5.1 Partielle Ableitungen. . . . . . . . . . . . . . . . . . . . . . . . . 72 6.5.2 Notwendige Bedingung für ein Extremum . . . . . . . . 73 6.5.3 Hinreichende Bedingung für lokale Extrema. . . . . . . 76 6.6 Lagrange-Methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.6.1 Gradient einer Funktion. . . . . . . . . . . . . . . . . . . . . . . 78 6.6.2 Richtungsableitung. . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.6.3 Höhenlinie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.6.4 Eigenschaften des Gradienten. . . . . . . . . . . . . . . . . . 81 6.6.5 Lagrange-Funktion. . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.6.6 Langrange-Methode. . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.6.7 Anwendungsbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.6.8 Lagrange-Methode für Funktionen mit mehr als
|
||
zwei Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.7 Gradientenverfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
|
||
6.7.1 Ablauf des Gradientenabstiegsverfahrens. . . . . . . . . 85 6.7.2 Schrittweitenbestimmung. . . . . . . . . . . . . . . . . . . . . . 86 6.7.3 Gradientenverfahren zur Bestimmung
|
||
lokaler Maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
|
||
7 Methoden zur Lösung kombinatorischer Optimierungsprobleme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7.1 Enumerationsmethode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2 Branch-and-Bound-Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.2.1 Die Methode des Branch-and-Bound-Verfahrens . . . 91 7.2.2 Branch-and-Bound-Verfahren für das TSP . . . . . . . . 92 7.3 Dynamische Programmierung. . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.4 Greedy-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.4.1 Greedy-Algorithmus für das Münzwechsel-Problem. . . . . . . . . . . . . . . . . . . . . . . . 97 7.4.2 Greedy-Algorithmus für ein Rucksackproblem. . . . . 98 7.4.3 Dijkstra-Algorithmus. . . . . . . . . . . . . . . . . . . . . . . . . 99 7.5 Einfache lokale Suche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.5.1 Nachbarschaft einer Lösung. . . . . . . . . . . . . . . . . . . . 102 7.5.2 Methode der einfachen lokalen Suche. . . . . . . . . . . . 103 7.6 Tabu-Suche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.6.1 Einführendes Beispiel (Rucksackproblem). . . . . . . . 106 7.6.2 Grundversion der Tabu-Suche. . . . . . . . . . . . . . . . . . 108 7.6.3 Varianten der Tabu-Suche . . . . . . . . . . . . . . . . . . . . . 109 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
|
||
8 Lineare Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.1 Graphische Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.2 Simplexmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8.2.1 Standard-Maximierungsproblem. . . . . . . . . . . . . . . . 114
|
||
|
||
XIV
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
8.2.2 8.2.3 8.2.4
|
||
|
||
Schlupfvariable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Austauschverfahren. . . . . . . . . . . . . . . . . . . . . . . . . . 115 Strategie der Simplexmethode. . . . . . . . . . . . . . . . . . 117
|
||
|
||
9 Multikriterielle Optimierungsverfahren. . . . . . . . . . . . . . . . . . . . . . . 121 9.1 Methode der gewichteten Summe. . . . . . . . . . . . . . . . . . . . . . . 121 9.2 Die ε-Constraint-Methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 9.3 Pareto-Optimierung mithilfe naturanaloger Optimierungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
|
||
|
||
10 Komplexität und heuristische/metaheuristische Verfahren . . . . . . . 125 10.1 Komplexität. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 10.1.1 O-Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 10.1.2 Beispiel (Suche in einer sortierten Liste). . . . . . . . . . 126 10.1.3 Komplexität von Problemen. . . . . . . . . . . . . . . . . . . . 127 10.1.4 Polynomielle Algorithmen. . . . . . . . . . . . . . . . . . . . . 128 10.1.5 Entscheidungsprobleme. . . . . . . . . . . . . . . . . . . . . . . 128 10.1.6 Komplexitätsklassen P und NP . . . . . . . . . . . . . . . . . 129 10.1.7 Polynomielle Reduzierbarkeit. . . . . . . . . . . . . . . . . . 129 10.1.8 Komplexitätsklasse NP-vollständig. . . . . . . . . . . . . . 131 10.1.9 NP-schwere Optimierungsprobleme . . . . . . . . . . . . . 131 10.2 Heuristisches Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 10.3 Metaheuristische Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 10.4 Exploitation und Exploration. . . . . . . . . . . . . . . . . . . . . . . . . . . 133 10.5 No Free Lunch Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
|
||
|
||
Teil III Naturanaloge Optimierungen
|
||
11 Physikbasierende Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 11.1 Simulated Annealing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 11.1.1 Abkühlungsprozess beim Erhärten einer Metallschmelze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 11.1.2 Simulated-Annealing-Algorithmus. . . . . . . . . . . . . . 139 11.2 Threshold-Accepting-Algorithmus . . . . . . . . . . . . . . . . . . . . . . 142 11.3 Sintflut-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 11.4 Populationbasierende Algorithmen. . . . . . . . . . . . . . . . . . . . . . 145 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
|
||
12 Evolutionäre Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 12.1 Biologische Evolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 12.2 Genetische Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 12.2.1 Grundversion der genetischen Algorithmen . . . . . . . 149 12.3 Varianten der genetischen Algorithmen. . . . . . . . . . . . . . . . . . . 155 12.3.1 Varianten von Selektionsverfahren . . . . . . . . . . . . . . 155 12.3.2 Varianten von Rekombinationen . . . . . . . . . . . . . . . . 158 12.3.3 Varianten von Mutationen. . . . . . . . . . . . . . . . . . . . . 159
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
XV
|
||
|
||
12.3.4 Varianten der Ersetzung (Replacement). . . . . . . . . . . 160 12.4 Permutationscodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
|
||
12.4.1 Rekombination für Permutationen. . . . . . . . . . . . . . . 162 12.4.2 Mutationen für Permutationen. . . . . . . . . . . . . . . . . . 164 12.4.3 Beispiel: n-Damen-Problem. . . . . . . . . . . . . . . . . . . . 165 12.5 Anwendungen genetischer Algorithmen. . . . . . . . . . . . . . . . . . 166 12.5.1 Optimierung kontinuierlicher Funktionen
|
||
mit GA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 12.5.2 Multikriterielle Optimierung mit GA. . . . . . . . . . . . . 170 12.6 Evolutionsstrategien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 12.6.1 Der Grundalgorithmus der Evolutionsstrategie. . . . . 174 12.6.2 Initialisierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 12.6.3 Rekombination. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 12.6.4 Mutationen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 12.6.5 Selektion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 12.6.6 Abbruch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
|
||
13 Partikelschwarmalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 13.1 Schwarmverhalten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 13.2 Boids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 13.3 Grundversion des Partikelschwarmalgorithmus . . . . . . . . . . . . 187 13.3.1 Einführendes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . 188 13.3.2 Grundversion des PSO-Algorithmus. . . . . . . . . . . . . 188 13.3.3 Ablauf der Grundversion des PSO. . . . . . . . . . . . . . . 190 13.4 Varianten des PSO-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . 191 13.4.1 Maßnahmen beim Verlassen des Suchraumes. . . . . . 191 13.4.2 Nachbarschafts-Topologien. . . . . . . . . . . . . . . . . . . . 192 13.4.3 Trägheitsparameter. . . . . . . . . . . . . . . . . . . . . . . . . . . 194 13.4.4 Kontraktionsfaktor. . . . . . . . . . . . . . . . . . . . . . . . . . . 195 13.4.5 Tabelle der wichtigsten Parameter des PSO-Verfahrens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 13.5 Anwendungsbeispiel (Diagnostik). . . . . . . . . . . . . . . . . . . . . . . 196 13.6 Diskrete Partikelschwarmoptimierungen. . . . . . . . . . . . . . . . . . 196 13.6.1 Binäres PSO-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 197 13.6.2 DPSO-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 13.7 Multikriterielle Partikelschwarmoptimierung. . . . . . . . . . . . . . 201 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
|
||
14 Ameisenalgorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 14.1 Ameisen in der Natur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 14.2 Grundprinzip des Ameisenalgorithmus. . . . . . . . . . . . . . . . . . . 210 14.3 Die Grundversion des Ameisenalgorithmus . . . . . . . . . . . . . . . 213 14.4 Der Algorithmus AS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 14.5 Unterschied zwischen realen und künstlichen Ameisen . . . . . . 216 14.6 Varianten des Ameisenalgorithmus AS. . . . . . . . . . . . . . . . . . . 217
|
||
|
||
XVI
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
14.6.1 Elitist AS (EAS). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 14.6.2 Rank based AS (ASrank). . . . . . . . . . . . . . . . . . . . . . 218 14.6.3 MAX–MIN Ant-System (MMAS). . . . . . . . . . . . . . . 218 14.6.4 Ant Colony System (ACS). . . . . . . . . . . . . . . . . . . . . 219 14.7 Parameterwerte für ACO-Algorithmen . . . . . . . . . . . . . . . . . . . 220 14.8 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 14.8.1 Rucksackproblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 14.8.2 Generalised Assignment Problem . . . . . . . . . . . . . . . 221 14.8.3 Routing in Netzwerken . . . . . . . . . . . . . . . . . . . . . . . 223 14.8.4 Shortest Common Supersequence Problem. . . . . . . . 225 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
|
||
15 Bienenalgorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 15.1 Bienen in der Natur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 15.1.1 Bienenvolk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 15.1.2 Futtersuche der Bienen. . . . . . . . . . . . . . . . . . . . . . . . 232 15.2 Der BA-Algorithmus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 15.2.1 Die Grundversion des BA-Algorithmus. . . . . . . . . . . 234 15.2.2 Analogie zwischen natürlichen und künstlichen Bienen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 15.2.3 Lokale und globale Suche . . . . . . . . . . . . . . . . . . . . . 236 15.2.4 Anwendungsbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . 237 15.3 Der ABC-Algorithmus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
|
||
16 Fledermausalgorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 16.1 Fledermäuse in der Natur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 16.2 Grundversion des BAT-Algorithmus. . . . . . . . . . . . . . . . . . . . . 244 16.2.1 Parameter des BAT-Algorithmus. . . . . . . . . . . . . . . . 244 16.2.2 BAT-Algorithmus in der Grundversion. . . . . . . . . . . 245 16.2.3 Analogie zwischen natürlichen und künstlichen Fledermäusen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 16.2.4 BAT-Algorithmus für das Problem des Handlungsreisenden. . . . . . . . . . . . . . . . . . . . . . . . . . 248 16.3 Binärer BAT-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 16.4 Multikriterieller BAT-Algorthmus. . . . . . . . . . . . . . . . . . . . . . . 251 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
|
||
17 Künstliche Immunsysteme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 17.1 Natürliches Immunsystem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 17.1.1 Angeborenes und erworbenes Immunsystem . . . . . . 254 17.1.2 Affinität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 17.2 Positive und negative Selektion. . . . . . . . . . . . . . . . . . . . . . . . . 256 17.2.1 Thymusmodell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 17.2.2 Künstliche positive und negative Selektion. . . . . . . . 257
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
XVII
|
||
|
||
17.3 Klonaler Selektions-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 260 17.3.1 Klonale Selektionstheorie . . . . . . . . . . . . . . . . . . . . . 260 17.3.2 CLONALG für Mustererkennung. . . . . . . . . . . . . . . 262 17.3.3 CLONALG für Optimierung. . . . . . . . . . . . . . . . . . . 266
|
||
17.4 Immuner-Netzwerk-Algorithmus. . . . . . . . . . . . . . . . . . . . . . . . 270 17.4.1 Die Jernesche Netzwerktheorie. . . . . . . . . . . . . . . . . 270 17.4.2 Der aiNet-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 271 17.4.3 Anwendung (Clusteranalyse). . . . . . . . . . . . . . . . . . . 273 17.4.4 Der opt-aiNet -Algorithmus. . . . . . . . . . . . . . . . . . . . 274
|
||
Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
|
||
18 Übersicht: Naturanaloge Optimierungen. . . . . . . . . . . . . . . . . . . . . . 279 18.1 Naturanaloge Optimierungen in diesem Buch. . . . . . . . . . . . . . 279 18.2 Übersicht weiterer naturanaloger Optimierungsmethoden . . . . 280 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
|
||
|
||
Teil IV Neuronale kombinatorische Optimierung
|
||
19 Neuronale Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 19.1 Natürliches neuronales Netz . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 19.2 Das künstliche Neuron. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 19.3 Typen von Aktivierungsfunktionen. . . . . . . . . . . . . . . . . . . . . . 288 19.4 Das Perzeptron. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 19.5 Deltaregel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 19.6 Das mehrschichtige Perzeptron. . . . . . . . . . . . . . . . . . . . . . . . . 291 19.7 Klassifikation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 19.8 Deep Learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 19.9 Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 19.10 Varianten der Gradientenverfahren . . . . . . . . . . . . . . . . . . . . . . 298 19.11 Ablauf des Backpropagation-Lernalgorithmus. . . . . . . . . . . . . 298 19.12 Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 19.13 Under- und Overfittung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 19.14 Funktionsapproximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 19.15 Optimierung von KNN mit naturanalogen Optimierungsmethoden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 19.16 Netztopologien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 19.17 Lernen mit künstlichen neuronalen Netzen. . . . . . . . . . . . . . . . 307 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
|
||
20 Selbstorganisierende Karten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 20.1 Kohonen-Karte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 20.2 Einführendes Beispiel (SOM-Algorithmus) . . . . . . . . . . . . . . . 310 20.3 SOM-Lernalgorithmus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 20.4 Klassifizierung von Daten mit SOM. . . . . . . . . . . . . . . . . . . . . 314 20.5 Lösung des TSP mit der SOM-Methode. . . . . . . . . . . . . . . . . . 315 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
|
||
|
||
XVIII
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
21 Hopfield-Netze. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 21.1 Definition eines Hopfield-Netzes. . . . . . . . . . . . . . . . . . . . . . . . 317 21.2 Aktualisierung in Hopfield-Netzen . . . . . . . . . . . . . . . . . . . . . . 318 21.3 Energiefunktion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 21.4 Speichern von Mustern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 21.5 Wiederherstellung eines Musters. . . . . . . . . . . . . . . . . . . . . . . . 322 21.6 Hopfield-Algorithmus mit dem SimulatedAnnealing-Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 21.7 Anwendungen auf Optimierungsprobleme . . . . . . . . . . . . . . . . 324 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
|
||
22 Reinforcement Learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 22.1 Einführung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 22.2 Menace. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 22.3 Formale Beschreibung von RL . . . . . . . . . . . . . . . . . . . . . . . . . 333 22.4 Markovsche Entscheidungprozesse. . . . . . . . . . . . . . . . . . . . . . 335 22.5 Return. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 22.6 Policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 22.7 State-Value-Funktion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 22.7.1 Definition der State-Value-Funktion . . . . . . . . . . . . . 338 22.7.2 Beispiel der State-Value-Funktion. . . . . . . . . . . . . . . 338 22.8 Action-Value-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 22.9 Optimale Policies und optimale Value-Funktionen. . . . . . . . . . 340 22.10 Q-Learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 22.11 DQN-Algorithmus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 22.12 REINFORCE-Algorithmus. . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 22.12.1 Policy Gradient Theorem. . . . . . . . . . . . . . . . . . . . . . 346 22.12.2 REINFORCE Algorithmus . . . . . . . . . . . . . . . . . . . . 347 22.12.3 Beispiel (Vier Gewinnt). . . . . . . . . . . . . . . . . . . . . . . 348 22.12.4 REINFORCE mit Baseline . . . . . . . . . . . . . . . . . . . . 349 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
|
||
23 Optimierungsmethoden in Deep Learning. . . . . . . . . . . . . . . . . . . . . 351 23.1 Problem der verschwindenden und explodierenden Gradienten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 23.2 Gradient Clipping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 23.3 Momentum-Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 23.4 Exponentiell gleitender Durchschnitt . . . . . . . . . . . . . . . . . . . . 354 23.5 RMSProp-Optimierung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 23.6 Adam-Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
|
||
24 Neuronale Optimierung mit dem Pointer-Netzwerk. . . . . . . . . . . . . 357 24.1 Rekurrente neuronale Netze. . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 24.2 Einführende Beispiele von RNN. . . . . . . . . . . . . . . . . . . . . . . . 358 24.3 Mathematische Beschreibung des RNN . . . . . . . . . . . . . . . . . . 359
|
||
|
||
Inhaltsverzeichnis
|
||
|
||
XIX
|
||
|
||
24.4 Backpropagation Through Time . . . . . . . . . . . . . . . . . . . . . . . . 360 24.5 LSTM-Zellen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 24.6 Seq2seq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 24.7 Softmax-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 24.8 Attention-Mechanismus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 24.9 Stochastische Policy für das TSP. . . . . . . . . . . . . . . . . . . . . . . . 365 24.10 Pointer-Netzwerk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 24.11 Trainierbare Zielfunktion für das TSP. . . . . . . . . . . . . . . . . . . . 367 24.12 Baseline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 24.13 REINFORCE-Algorithmus für das TSP . . . . . . . . . . . . . . . . . . 369 24.14 Varianten der REINFORCE-Methode für
|
||
Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
|
||
25 Neuronale Optimierung mit Transformer . . . . . . . . . . . . . . . . . . . . . 373 25.1 Transformer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 25.1.1 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 25.1.2 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 25.2 Greedy Rollout Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 25.3 REINFORCE mit Greedy Rollout Baseline . . . . . . . . . . . . . . . 383 25.4 Testphase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
|
||
26 Optimierung mit graphischen neuronalen Netzen. . . . . . . . . . . . . . . 385 26.1 Graphische neuronale Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 26.2 Grapheneinbettung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 26.3 S2V-Einbettung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 26.4 TSP als Markovscher Entscheidungsprozess. . . . . . . . . . . . . . . 388 26.5 Parametrisierung der Action-Value-Funktion . . . . . . . . . . . . . . 389 26.6 S2V-DQN-Algorithmus für TSP. . . . . . . . . . . . . . . . . . . . . . . . 390 26.7 Testphase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 26.8 Weitere Optimierungsverfahren mit GNN. . . . . . . . . . . . . . . . . 392 Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
|
||
27 Programmbibliotheken für Machine Learning. . . . . . . . . . . . . . . . . 393 27.1 Programmbibliothek TensorFlow. . . . . . . . . . . . . . . . . . . . . . . . 393 27.2 Weitere Programmbibliotheken. . . . . . . . . . . . . . . . . . . . . . . . . 394
|
||
|
||
Literatur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
|
||
|
||
Stichwortverzeichnis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
|
||
|
||
Abkürzungsverzeichnis
|
||
|
||
ABC ACS Adam aiNet AIS AS ASrank AS-SCSP BA BAT BFD BinBA BN BPTT C&P CLONALG CVRP DPSO EAS ERX ES FFD GA GAP GNN HopSA KNN LSTM MDVVRP MMAS MOBA
|
||
|
||
Artificial Bee Colony Algorithm Ant Colony System Adaptive Moment Estimation Künstlicher Immunnetzwerk-Algorithmus Künstliches Immunsystem Ameisenalgorithmus Ranked-Based Ant System Ant System-Shortest Common Supersequence Problem Bienenalgorithmus Fledermausalgorithmus Best Fit decreasing Binärer Fledermausalgorithmus Batch-Normalisierung Backpropagation through Time Cutting and Packing Problem Klonaler Selektions-Algorithmus Capacitated Vehicle Routing Problem Diskreter Partikelschwarmalgorithmus Elitist Ant System Edge Recombination Crossover Evolutionsstrategien First Fit decreasing Genetischer Algorithmus Generalised Assignment Problem Graphische Neuronale Netze Hopfield-Simulated-Annealing-Algorithmus Künstliche neuronale Netze Long Short-Term Memory Multi-Depot Vehicle Routing Problem MAX-MIN Ant System Multikriterieller Fledermausalgorithmus
|
||
|
||
XXI
|
||
|
||
XXII
|
||
|
||
Abkürzungsverzeichnis
|
||
|
||
MOPSO NCO NFD NSA NSGAII OX PMX PSA PSO RL RMSProp RNN S2V SA SCSP SGD SI SUS TA TSP VPR VRPTW
|
||
|
||
Multikriterielle Partikelschwarmoptimierung Neuronale kombinatorische Optimierung Next Fit decreasing Negativer-Selektions-Algorithmus Nondominated Sorting Genetic Algorithm II Order Crossover Partially Matched Crossover Positiver-Selektions-Algorithmus Partikelschwarmalgorithmus Reinforcement Learning Root Mean Square Propogation Rekurrente Neuronale Netze Structure2Vec Simulated Annealing Shortest Common Supersequence Problem stochastisches Gradientenverfahren Sinflut-Algorithmus Stochastic Universal Sampling Threshhold-Accepting-Algorithmus Traveling Salesman Problem Vehicle Routing Problem Vehicle Routing Problem with Time Windows
|
||
|
||
Teil I
|
||
Optimierungsprobleme
|
||
|
||
Kapitel 1
|
||
Einführung
|
||
|
||
Es gibt eine unübersehbare Vielzahl verschiedener Optimierungsprobleme in der realen Welt, wie zum Beispiel Optimierungsaufgaben aus den Bereichen Logistik, Technik, Finanzwirtschaft, Medizin, Telekommunikation oder Verkehrsplanung. Im ersten Kapitel werden verschiedene Optimierungsprobleme aus diesen Bereichen aufgelistet. Weiterhin werden Grundbegriffe der Optimierung eingeführt.
|
||
|
||
1.1 Optimierungsprobleme in der realen Welt
|
||
Im Folgenden werden stellvertretend einige Optimierungsprobleme aus unterschiedlichen Bereichen aufgeführt:
|
||
Produktionsplanung
|
||
• Minimierung des Verschnitts beim Zuschneiden von Rohren, Holzplatten oder Stoffen und beim Stanzen von Blechen
|
||
• Minimierung des Laderaums beim Beladen von LKWs, Containern oder Schiffen
|
||
• Optimierung der Lagerhaltung einer Firma • Kostengünstige Mischung aus einem Vorrat (z. B. Futtermischungen)
|
||
Tourenplanung
|
||
• Minimierung der Wegstrecke zwischen zwei Orten • Bestimmung der kürzesten Rundreise • Optimierung der Routen für Müllabfuhr, Wartungsfahrten, Paketlieferung oder
|
||
Entleerung von Briefkästen • Optimierung der Laufwege von Bohrautomaten • Optimierung der Auslastung von Fahrzeugen
|
||
Städte- und Verkehrsplanung
|
||
• Optimale Steuerung des Verkehrsflusses • Optimierung bei der Auslegung von Strom- und Wasserleitungen
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH,
|
||
|
||
3
|
||
|
||
ein Teil von Springer Nature 2023
|
||
|
||
R. Hollstein, Optimierungsmethoden, https://doi.org/10.1007/978-3-658-39855-2_1
|
||
|
||
4
|
||
|
||
1 Einführung
|
||
|
||
• Optimierung bei der Standortbestimmung wie zum Beispiel von Feuerwehrstationen und Windrädern
|
||
• Optimale Platzierung von Parkplätzen
|
||
Telekommunikation
|
||
• Optimale Ausrichtung von Antennen • Optimierung der Auslegung von Telefonleitungen • Suche nach der besten Standortverteilung für Mobilfunkmasten • Optimale Steuerung von Datenströmen in Kommunikationsnetzwerken während
|
||
des Betriebs
|
||
Ablaufplanung
|
||
• Optimierung von Arbeitsabläufen • Optimale Ausnutzung von Maschinen • Maximierung der Kapazitätsauslastung • Minimierung der Terminabweichung • Optimierung bei der Erstellung von Stunden-, Bahn-, Bus- und Flugplänen
|
||
Medizin
|
||
• Maximierung der Wirkung eines Medikaments bei gleichzeitiger Minimierung der Nebenwirkungen
|
||
• Optimierung bei der medizinischen Bildverarbeitung in der Radiologie • Erstellung eines optimalen Diätplans
|
||
Technik
|
||
• Optimierung der Oberfläche eines PKWs zur Reduzierung des Luftwiderstandsbeiwertes
|
||
• Optimale Kalibrierung eines Motors zur Minimierung des Kraftstoffverbrauchs und des Schadstoffausstoßes bei möglichst hoher Motorleistung
|
||
• Optimierung von PKW-Reifen • Minimierung der Laufwege von Schweißrobotern beim Punktschweißen von
|
||
Karosserieteilen • Optimierung von Flugzeugflügeln • Optimierung von Brillengläsern
|
||
Finanzwirtschaft
|
||
• Portfolio-Optimierung • Risikominimierung von Finanzprodukten • Optimierung von Geschäftsabläufen • Optimierung von Investitionen • Preisoptimierung • Kostenminimierung
|
||
|
||
1.2 Grundbegriffe der Optimierung
|
||
|
||
5
|
||
|
||
1.2 Grundbegriffe der Optimierung
|
||
|
||
Bei einer Optimierung geht es darum, zu einer Bewertungsfunktion f : S → R unter allen Elementen aus einer Menge S ein Element mit der besten Bewertung zu ermitteln. Die zu optimierende Funktion f wird Zielfunktion und im Zusammenhang mit evolutionären Algorithmen (Kap. 12) auch Fitnessfunktion genannt. Der Definitionsbereich S von f wird mit Suchraum bezeichnet, die Elemente aus dem Suchraum nennt man Lösungen.
|
||
|
||
1.2.1 Globales und lokales Optimum
|
||
Definitionen • Eine Zielfunktion f : S → R besitzt in x∗ ∈ S ein globales Maximum bzw.
|
||
globales Minimum, wenn für alle x ∈ S gilt: f (x) ≤ f (x∗) bzw. f (x∗) ≤ f (x). • Eine Zielfunktion f : S → R besitzt in x∗ ∈ S ein lokales Maximum bzw.
|
||
lokales Minimum, wenn es eine (kleine) Umgebung U von x∗ gibt, sodass für alle x ∈ U ∩ S gilt: f (x) ≤ f (x∗) bzw. f (x∗) ≤ f (x) (s. Abb. 1.1).
|
||
|
||
1.2.2 Umwandlung eines Maximierungsproblems in ein Minimierungsproblem und umgekehrt
|
||
Durch Multiplikation einer Zielfunktion f (x) mit −1 kann ein Maximierungsproblem (Minimierungsproblem) in ein Minimierungsproblem (Maximierungsproblem) umgewandelt werden. Die Extremstellen beider Funktionen sind identisch (s. Abb. 1.2).
|
||
|
||
()
|
||
|
||
globales Maximum
|
||
|
||
flaches Gebiet lokaler Maxima
|
||
|
||
globales Minimum
|
||
|
||
lokales Minimum
|
||
|
||
lokales Minimum
|
||
|
||
Abb. 1.1 Globale und lokale Extremwerte der Zielfunktion f : [a, b] → R mit den Randextremwerten in aund b. In dem Bereich zwischen x1 und x2 ist jeder Punkt eine Maximalstelle.
|
||
|
||
6
|
||
|
||
Abb. 1.2 Graphisch bewirkt die Multiplikation der
|
||
|
||
y
|
||
|
||
Zielfunktion f (x) mit −1 eine
|
||
|
||
Spiegelung an der x-Achse.
|
||
|
||
Die Lage der Extremstellen
|
||
|
||
bleibt unberührt.
|
||
|
||
1 Einführung
|
||
()
|
||
x
|
||
|
||
1.2.3 Notationen
|
||
Für die Bestimmung eines Maximums bzw. Minimums der Funktion f (x) ist folgende Schreibweise üblich:
|
||
f (x) → max bzw. f (x) → min. Besitzt die Funktion f : S → R in x∗ ein globales Maximum bzw. Minimum, so schreibt man
|
||
|
||
f x∗ = max f (x) bzw. f x∗ = min f (x)
|
||
|
||
x∈S
|
||
|
||
x∈S
|
||
|
||
und
|
||
|
||
x∗ = argmax f (x) bzw. x∗ = arg min f (x).
|
||
|
||
x∈S
|
||
|
||
x∈S
|
||
|
||
1.2.4 Supremum und Infimum
|
||
|
||
Supremum Ist die Funktion f : S → R nach oben beschränkt, so existiert die kleinste obere Schranke M mit f (x) ≤ M für alle x ∈ S. M heißt Supremum von f (x) und man schreibt
|
||
M = sup f (x).
|
||
x∈S
|
||
Infimum Ist die Funktion f : S → R nach unten beschränkt, so existiert die größte untere Schranke N. N heißt Infimum von f (x) und man schreibt
|
||
N = inf f (x).
|
||
x∈S
|
||
|
||
1.2 Grundbegriffe der Optimierung
|
||
|
||
7
|
||
|
||
Beispiel: Gegeben sei die Funktion
|
||
|
||
: [ , ] → ℝ, ( ) =
|
||
|
||
wenn ∈ [ , ) wenn ∈ [ , ]
|
||
|
||
y 2
|
||
()
|
||
1
|
||
|
||
0
|
||
|
||
1
|
||
|
||
2
|
||
|
||
3x
|
||
|
||
Die Funktion f (x) besitzt im Intervall [0,3] in 0 ein globales Minimum und kein Maximum. Es gilt
|
||
|
||
f (0) = min f (x) = inf f (x) = 0
|
||
|
||
x∈[0,3]
|
||
|
||
x∈[0,3]
|
||
|
||
und
|
||
|
||
sup f (x) = 2.
|
||
x∈[0,3]
|
||
Die Funktion f (x) nimmt im Intervall [0,3] ihr Supremum nicht an.
|
||
|
||
1.2.5 Kontinuierliche, diskrete und kombinatorische Optimierung
|
||
Ein Optimierungsproblem mit der Zielfunktion f : S → R heißt
|
||
• kontinuierlich, wenn der Suchraum S überabzählbar unendlich ist (z. B. S = [a,b] ⊂ R).
|
||
• diskret, wenn S endlich oder abzählbar unendlich ist (z. B. S = Menge Z der ganzen Zahlen).
|
||
• kombinatorisch, wenn S endlich ist (z. B. S = Menge der Zahlen 1, . . . , 10).
|
||
|
||
Kapitel 2
|
||
Kontinuierliche Optimierungsprobleme
|
||
|
||
In diesem Kapitel werden Beispiele von kontinuierlichen Optimierungsproblemen vorgestellt. Weiterhin wird der Begriff Regression eingeführt. Bei der Regression wird eine Funktion vom bestimmten Typ an eine Datenwolke von Punkten angepasst, wobei man von linearer, quadratischer und exponentieller Regression spricht, wenn die anzupassende Funktion linear, quadratisch bzw. exponentiell ist. Weiterhin werden Extremwerteigenschaften von konkaven und konvexen Funktionen beschrieben.
|
||
|
||
2.1 Graph einer Funktion
|
||
Im Folgenden sei f : S → R eine zu optimierende kontinuierliche Funktion, wobei S eine Teilmenge von Rn ist.
|
||
• Für eine Funktion f : S → R mit S ⊂ R heißt die Menge (x, f (x)) ∈ R2 : x ∈ S Graph von f und stellt eine ebene Kurve dar.
|
||
• Für S ⊂ R2 beschreibt der Graph (x, y, f (x)) ∈ R3 : (x,y) ∈ S ein Gebirge, in dem die Talsohlen die lokalen Minima und die Berggipfel die lokalen Maxima darstellen. Der höchste Berg ist dann das globale Maximum und das tiefste Tal das globale Minimum.
|
||
Beispiele Im Folgenden sind die Funktionsgebirge von vier (Benchmark)-Funktionen dargestellt, die oft für Performance-Tests von Optimierungsalgorithmen verwendet werden (s. Abb. 2.1). Rastrigin-Funktion Diese Funktion ist definiert durch
|
||
f (x,y) = 20 + x2 − 10 cos (2π x) + y2 − 10 cos (2π y) .
|
||
Sie stellt ein schweres Optimierungsproblem dar, da die Wertelandschaft sehr viele lokale Minima und ein globales Minimum im Punkt (0,0) besitzt.
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH,
|
||
|
||
9
|
||
|
||
ein Teil von Springer Nature 2023
|
||
|
||
R. Hollstein, Optimierungsmethoden, https://doi.org/10.1007/978-3-658-39855-2_2
|
||
|
||
10 Rastrigin-Funktion
|
||
Egg Crate Funktion
|
||
|
||
2 Kontinuierliche Optimierungsprobleme Cross-Tray-Funktion
|
||
Easom’s Funktion
|
||
|
||
Abb. 2.1 Die Graphen der vier Benchmark-Funktionen
|
||
|
||
Cross-Tray-Funktion Diese Funktion ist definiert durch
|
||
|
||
f (x, y) = −0.0001| sin (x) sin (y) exp
|
||
|
||
1 100 −
|
||
|
||
x2 + y2
|
||
|
||
| + 1)0.1.
|
||
|
||
π
|
||
|
||
Die vier globalen Minima dieser Funktion sind gegeben (x0, y0) = (±1.349407, ∓1.349407) mit f (x0, y0) = −2.0626122. Egg-Crate-Funktion Diese Funktion ist definiert durch
|
||
f (x,y) = x2 + y2 + 25(sin2 x + sin2 y).
|
||
Das globale Minimum liegt in (0,0), wobei f (0,0) = 0. Easom’s Funktion Diese Funktion ist definiert durch
|
||
|
||
durch
|
||
|
||
f (x,y) = − cos (x) cos (y) exp −(x − π )2 − (y − π )2 .
|
||
|
||
Sie besitzt in (π , π ) ein globales Minimum mit f (π , π ) = −1.
|
||
|
||
2.2 Optimierungen mit Nebenbedingungen
|
||
In vielen Anwendungen sucht man Extremstellen einer Funktion f : S → R, S ⊂ Rn, wobei die Lösungen x zusätzlich die Nebenbedingung x ∈ M erfüllen sollen. Die Menge M ∩ S heißt dann zulässiger Bereich und x ∈ M ∩ S zulässige
|
||
|
||
2.3 Anwendungsbeispiele
|
||
|
||
11
|
||
|
||
Lösung. Die Nebenbedingungen können in Form von Ungleichungen g(x) ≥ 0 oder Gleichungen der Form h(x) = 0 gegeben sein.
|
||
|
||
Optimierungsproblem mit Nebenbedingungen Ein Optimierungsproblem ist gegeben durch
|
||
Zielfunktion: f (x) → min(max) Nebenbedingungen: gi(x) ≥ 0, i = 1, . . . , m
|
||
hk(x) = 0, k = 1, . . . n x∈S
|
||
Ungleichungen der Form g(x) ≤ 0 können durch Vorzeichenwechsel in eine Ungleichung ≥ 0 übergeführt werden.
|
||
|
||
2.3 Anwendungsbeispiele
|
||
• Optimierungsproblem aus der Wirtschaft Zu bestimmen sind die Maße einer zylindrischen Dose mit einem Volumeninhalt von V, sodass die Dose mit minimalem Material hergestellt werden kann.
|
||
Die zu minimierende Oberfläche O ist gegeben durch die Summe des Flächeninhalts der Mantelfläche 2π rh und des doppelten Flächeninhalts der Deckelfläche π r2. Das Volumen der zylindrischen Dose ergibt sich aus V = π r2h.
|
||
r
|
||
h
|
||
|
||
Das Optimierungsproblem lautet demzufolge:
|
||
Zielfunktion: f (h, r) = 2π r2 + 2π rh → min πr2h = V
|
||
Nebenbedingungen: r ≥ 0 h≥0
|
||
Die Lösung des Optimierungsproblems kann mit den in Kap. 6 beschriebenen analytischen Methoden leicht berechnet werden. Die optimale Lösung lautet (vgl. Abschn. 6.6.7)
|
||
|
||
r0 =
|
||
|
||
3
|
||
|
||
V ,
|
||
2π
|
||
|
||
h0 = 2 3
|
||
|
||
V .
|
||
2π
|
||
|
||
12
|
||
|
||
2 Kontinuierliche Optimierungsprobleme
|
||
|
||
• Optimierungsproblem aus der Geometrie
|
||
In einem Quadrat mit einer gegebenen Seitenlänge a soll ein Quadrat so einbeschrieben werden, dass dessen Flächeninhalt minimal ist.
|
||
|
||
Einbeschriebenes Quadrat in einem Quadrat
|
||
|
||
Der Flächeninhalt des eingeschriebenen Quadrats ist gleich x2 + y2. Man erhält damit folgendes Optimierungsproblem:
|
||
|
||
Zielfunktion: f (x, y) = x2 + y2 → min x+y=a
|
||
Nebenbedingungen: a − x ≥ 0 a−y≥0 x, y ≥ 0
|
||
Mittels analytischer Methoden (vgl. Kap. 6) erhält man als optimale Lösung:
|
||
a x=y= .
|
||
2
|
||
|
||
• Regression
|
||
|
||
Einführendes Beispiel Eine Feder wird durch Anhängen eines Gewichts gedehnt. Nach dem Hookschen Gesetz besteht der lineare Zusammenhang F = D · x zwischen der Auslenkung x und der Gewichtskraft F, wobei D die Federkonstante ist. Das Hooksche Gesetz ist zum Beispiel auch auf die Ausdehnung eines Gummiseils beim Bungee-Springen anwendbar, wobei die Ausdehnung von der Gummihärte D und vom Gewicht des Bungee-Springers abhängt. Für die Bestimmung der Federkonstante D einer Feder seien die fünf Messdaten wie in Abb. 2.2 ermittelt worden. Es ist das Ziel, die Gerade F = D · x bestmöglich an die Messdaten anzupassen. Diese Gerade nennt man Ausgleichsgerade. Hierzu wird die Summe der Quadrate der Fehler Fi − Dxi (senkrechte Abweichung zur Geraden) minimiert:
|
||
|
||
f (D) =
|
||
|
||
5 i=1
|
||
|
||
(Fi
|
||
|
||
−
|
||
|
||
Dxi )2
|
||
|
||
→
|
||
|
||
min.
|
||
|
||
Das Quadrieren ist erforderlich, da bei der einfachen Summierung die negativen und positiven Fehler sich gegenseitig aufheben können. Die Verwendung von Beträgen ist nicht sinnvoll, da das Rechnen mit Beträgen aufwendig ist.
|
||
|
||
2.3 Anwendungsbeispiele
|
||
|
||
13
|
||
|
||
Messwerte
|
||
|
||
in cm
|
||
|
||
in
|
||
|
||
0,5
|
||
|
||
1,8
|
||
|
||
2
|
||
|
||
5,3
|
||
|
||
3
|
||
|
||
5,9
|
||
|
||
4
|
||
|
||
9,8
|
||
|
||
5
|
||
|
||
6
|
||
Messpunkt
|
||
4
|
||
2
|
||
|
||
Fehler =∙
|
||
|
||
0
|
||
|
||
2
|
||
|
||
4
|
||
|
||
6
|
||
|
||
8
|
||
|
||
10 x
|
||
|
||
Abb. 2.2 Bestimmung einer Federkonstante D durch eine Ausgleichsgerade F = D · x, die optimal an die Messdaten anzupassen ist
|
||
|
||
Arten von Regressionen Bei der Regression wird eine Funktion g(x) vom bestimmten Typ optimal an eine Datenwolke von Punkten (xi, yi), i = 1, . . . , n, angepasst (s. Abb. 2.3). Je nach Funktionstyp g(x) unterscheidet man folgende Arten von Regressionen:
|
||
|
||
Lineare Regression (g(x) = ax + b):
|
||
|
||
f (a, b) =
|
||
|
||
n i=1
|
||
|
||
(yi
|
||
|
||
−
|
||
|
||
(axi
|
||
|
||
+
|
||
|
||
b))2
|
||
|
||
→
|
||
|
||
min
|
||
|
||
Quadratische Regression g(x) = ax2 + bx + c :
|
||
|
||
f (a,b,c) =
|
||
|
||
n i=1
|
||
|
||
yi −
|
||
|
||
axi2 + bxi + c
|
||
|
||
2 → min
|
||
|
||
Exponentielle Regression g(x) = a · ekx :
|
||
|
||
f (a,k) =
|
||
|
||
n i=1
|
||
|
||
yi − aekx
|
||
|
||
2 → min
|
||
|
||
y
|
||
|
||
y
|
||
|
||
y
|
||
|
||
6
|
||
|
||
6
|
||
|
||
6
|
||
|
||
5
|
||
|
||
5
|
||
|
||
5
|
||
|
||
4
|
||
|
||
4
|
||
|
||
4
|
||
|
||
3
|
||
|
||
3
|
||
|
||
3
|
||
|
||
2
|
||
|
||
2
|
||
|
||
2
|
||
|
||
1
|
||
|
||
1
|
||
|
||
1
|
||
|
||
x 1 2 3 4 5 6 7 8 9 10
|
||
|
||
x 1 2 3 4 5 6 7 8 9 10
|
||
|
||
x 1 2 3 4 5 6 7 8 9 10
|
||
|
||
Abb. 2.3 ① Lineare Regression: Anpassung durch eine Gerade ② Quadratische Regression: Anpassung durch eine Parabel ③ Exponentielle Regression: Anpassung durch eine Exponentialfunktion
|
||
|
||
14
|
||
|
||
2 Kontinuierliche Optimierungsprobleme
|
||
|
||
2.4 Unimodale und multimodale Funktionen
|
||
|
||
Eine Funktion f : S → R heißt unimodal, wenn sie nur ein lokales Optimum in S besitzt, das damit auch gleichzeitig globales Optimum ist. Dagegen werden Funktionen mit mehreren lokalen Optima multimodal genannt. Unimodale Funktionen können im Allgemeinen einfach optimiert werden.
|
||
Im Folgenden betrachten wir Klassen von Funktionen, die unimodal sind.
|
||
|
||
2.5 Konvexe und konkave Funktionen
|
||
Konvexe Menge Eine Menge C ⊆ Rn heißt konvex, wenn für alle x, y ∈ C und alle α ∈ [0,1] gilt:
|
||
αx + (1 − α)y ∈ C. Bemerkung: Die Menge
|
||
|
||
stellt die Verbindungsstrecke zwischen den Punkten x und y dar. Somit ist die Menge C genau dann konvex, wenn für je zwei beliebige Punkte x, y ∈ C auch stets deren Verbindungsstrecke in C liegt (s. Abb. 2.4).
|
||
Definition Eine Funktion f : C → R, die auf einer konvexen Menge C ⊆ Rn definiert ist, heißt
|
||
• konvex, wenn gilt f (α x + (1 − α)y) ≤ αf (x) + (1 − α)f (y) • streng konvex, wenn gilt f (αx + (1 − α)y) < αf (x) + (1 − α)f (y) • konkav, wenn gilt f (αx + (1 − α)y) ≥ αf (x) + (1 − α)f (y) • streng konkav, wenn gilt f (αx + (1 − α)y) > αf (x) + (1 − α)f (y)
|
||
für alle x, y ∈ C mit x = y und 0 < α < 1 (s. Abb. 2.5).
|
||
|
||
a
|
||
|
||
b
|
||
|
||
Abb. 2.4 (a) konvexe Menge (b) Mengen mit Einbuchtungen sind nicht konvex
|
||
|
||
2.6 Extrema konvexer und konkaver Funktionen
|
||
|
||
Abb. 2.5 Illustration der konvexen Funktion
|
||
|
||
() ( ) + (1 − ) ( )
|
||
( + (1 − ) ) ()
|
||
|
||
15 + (1 − )
|
||
|
||
Konvexe und konkave Funktionen besitzen folgende geometrische Eigenschaft:
|
||
Satz Eine auf einer konvexen Menge C ⊆ Rn definierte Funktion f : C → R ist genau dann konvex (konkav), wenn für alle x, y ∈ C der Graph von f unterhalb (oberhalb) der Verbindungsstrecke der beiden Punkte (x, f (x)) und (y, f (y)) liegt (s. Abb. 2.6).
|
||
|
||
2.6 Extrema konvexer und konkaver Funktionen
|
||
Satz a) Nimmt eine konvexe (konkave) f (x) in einem Punkt x0 ein lokales Minimum
|
||
(Maximum) an, so besitzt sie in x0 auch ihr globales Minimum (Maximum). b) Eine streng konvexe (streng konkave) Funktion f (x) ist unimodal, wenn sie ein
|
||
lokales Minimum (Maximum) besitzt.
|
||
Bemerkungen
|
||
1) Die konstante Funktion f (x) = 1 ist sowohl konkav als auch konvex und nimmt in jedem Punkt x ein globales Minimum und Maximum an.
|
||
2) Die Funktion f (x) = ex ist in R streng konvex, besitzt aber kein globales Maximum.
|
||
3) Die Funktion f (x,y) = x2 ist konvex und besitzt in jedem Punkt (0,y), y ∈ R, ein globales Minimum (s. Abb. 2.7).
|
||
|
||
a
|
||
|
||
b
|
||
|
||
()
|
||
|
||
()
|
||
|
||
Abb. 2.6 (a) Konvexe Funktion: Graph von f liegt unterhalb der Verbindungsstrecke. (b) Konkave Funktion: Graph von f liegt oberhalb der Verbindungsstrecke
|
||
|
||
16
|
||
a ( , )= 2
|
||
|
||
2 Kontinuierliche Optimierungsprobleme
|
||
|
||
b
|
||
|
||
( , )=1− 2− 2
|
||
|
||
Abb. 2.7 (a) f (x,y) = x2 ist konvex (aber nicht streng konvex) und besitzt in jedem Punkt der Geraden G = {(0,y) : y ∈ R} ein globales Minimum (b) f (x,y) = 1 − x2 − y2 ist streng konkav
|
||
und besitzt nur in (0,0) ein globales Maximum
|
||
|
||
Kapitel 3
|
||
Kombinatorische Optimierungsprobleme
|
||
|
||
Viele kombinatorische Optimierungsprobleme können eingeordnet werden in die Optimierungsgebiete Vehicle-Routing-Probleme, Graphenprobleme, SchedulingProbleme, Zuschnittprobleme und Packungsprobleme, die in diesem Kapitel beschrieben werden.
|
||
Unter einem Vehicle-Routing-Problem versteht man allgemein die Optimier ungsaufgabe, mit einer Anzahl von Fahrzeugen von Depots aus mehrere Standorte anzufahren, sodass die Gesamtstrecke minimal ist.
|
||
Es gibt eine Vielzahl von Optimierungsproblemen, die in ein Graphenproblem umformuliert werden können. Auf diese Weise lassen sich diese Probleme einfach beschreiben und können mit graphentheoretischen Methoden gelöst werden.
|
||
Man bezeichnet allgemein als Scheduling-Problem die Optimierungsaufgabe, Arbeitsabläufe zu optimieren sowie Maschinen, Personal und Arbeitszeit effizient auszunutzen. Je nach Art der Maschinenreihenfolge werden die SchedulingProbleme unterschiedlich klassifiziert.
|
||
Zuschnittoptimierungen werden in der textil-, metall-, papier- oder holzverarbeitenden Industrie angewendet. Packungsprobleme treten zum Beispiel bei der Beladung von Lastkraftwagen oder Containern auf. Zuschnitt- und Packungsprobleme werden zu einem Optimierungsgebiet zusammengefasst, da die Optimierungskriterien äquivalent sind. Bei einem Packungsproblem werden kleinere Teile in größere Objekte gepackt, während bei einem Zuschnittproblem größere Objekte in kleinere Teile zerlegt werden.
|
||
3.1 Einführende Beispiele
|
||
Im Folgenden werden das Problem des Handlungsreisenden und das Rucksackproblem vorgestellt, die zu den am intensivsten untersuchten kombinatorischen Optimierungsproblemen gehören. Wir werden die in diesem Buch vorgestellten Optimierungsmethoden oft wegen der einfachen und leicht verständlichen Formulierung mit diesen Optimierungsproblemen illustrieren.
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH,
|
||
|
||
17
|
||
|
||
ein Teil von Springer Nature 2023
|
||
|
||
R. Hollstein, Optimierungsmethoden, https://doi.org/10.1007/978-3-658-39855-2_3
|
||
|
||
18
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
3.1.1 Problem des Handlungsreisenden
|
||
|
||
Viele Optimierungsmethoden wurden am Beispiel des Problems des Handlungsreisenden (engl. Traveling Salesman Problem, abgekürzt TSP) entwickelt und oft für die Bestimmung der Performance eines Optimierungsverfahrens verwendet. Es ist einfach zu beschreiben, sehr praxisrelevant und erscheint auf den ersten Blick leicht lösbar. Tatsächlich gehört das TSP zu den komplizierten Optimierungsproblemen, da der Suchraum bei einer größeren Anzahl von Städten eine astronomische Größe annimmt.
|
||
Unter dem Problem des Handlungsreisenden versteht man die folgende Optimierungsaufgabe:
|
||
|
||
Problem des Handlungsreisenden (TSP) Gesucht ist die kürzeste Rundreise durch n verschiedene Städte, wobei bis auf den Startort jede Stadt nur einmal besucht werden soll.
|
||
|
||
Das Problem des Handlungsreisenden tritt bei vielen Anwendungen auf, wie z. B. in der Logistik bei der Tourenplanung für Kundenlieferungen. In der Automobilindustrie werden verschiedene Karosserieteile mithilfe von Schweißrobotern durch Punktschweißen aneinandergefügt, wobei der Gesamtweg zwischen Tausenden Schweißpunkten minimiert werden soll. Bei der Herstellung von Leiterplatten werden Löcher gebohrt, in denen Leiterbahnen auf der Oberseite mit Leiterbahnen auf der Unterseite verbunden oder in denen Bauteile eingesteckt werden. Auch hier liegt ein Problem des Handlungsreisenden vor, wobei die Herstellungszeit einer Platine mit oftmals mehreren Hundert Bohrstellen durch Minimierung des Laufweges des Bohrers reduziert werden soll.
|
||
Als Beispiel betrachten wir eine Rundreise durch die folgenden fünf größten Städte Deutschlands: Berlin (B), Hamburg (HH), München (M), Köln (K) und Frankfurt a. M. (F). Der Startort sei K.
|
||
Der Suchraum S ist die Menge aller möglichen Rundreisen und die zu minimierende Zielfunktion f : S → R ist die gesamte Reisestrecke.
|
||
Für die Rundreise x : K → HH → M → B → F → K ergibt sich nach der Entfernungstabelle von Abb. 3.1 die Länge f (x) = 2387(km).
|
||
|
||
Abb. 3.1 Entfernungstabelle für die fünf größten Städte Deutschlands
|
||
|
||
B HH M K F B
|
||
HH M
|
||
K
|
||
F
|
||
|
||
3.1 Einführende Beispiele
|
||
|
||
19
|
||
|
||
Das Minimierungsproblem kann gelöst werden, indem man die Reisestrecken aller möglichen Rundreisen berechnet und die Tour mit der kürzesten Weglänge auswählt. In unserem Beispiel sind es insgesamt 12 verschiedene Rundreisen. Dieses Lösungsverfahren ist jedoch nur praktikabel für eine kleine Anzahl von Städten.
|
||
Bei n Städten gibt es insgesamt
|
||
1 (n − 1)!
|
||
2
|
||
verschiedene Rundreisen (vgl. Abschn. 3.2.1). Unter der Annahme, dass ein Computer für die Lösung für 11 Städte mit 10!/2 = 1,8 · 106 verschiedenen Rundreisen eine Sekunde benötigt, ergeben sich die in Abb. 3.2 angegebenen Laufzeiten, die bei steigender Anzahl der zu besuchenden Städte überexponentionell rasant anwachsen. Die Enumerationsmethode, bei der die Gesamtstrecken aller möglichen Rundreisen berechnet werden, ist somit nur für wenige Städte anwendbar. Für längere Touren sind Näherungsverfahren notwendig, die in akzeptabler Zeit brauchbare Lösungen liefern. Verschiedene Näherungsmethoden für das Problem des Handlungsreisenden werden in späteren Kapiteln beschrieben.
|
||
|
||
3.1.2 Rucksackproblem
|
||
Unter dem Rucksackproblem (Knapsack-Problem) versteht man die Optimierungsaufgabe, aus einer Menge von Gegenständen möglichst die wertvollsten auszuwählen, die in einen Rucksack mit gegebener Kapazität eingepackt werden können.
|
||
|
||
Rucksackproblem Zu einer Menge von Gegenständen mit gegebener Größe und Nutzwert sollen die Gegenstände ausgewählt werden, die in einen Rucksack mit gegebener Größe eingepackt werden können, sodass der Gesamtnutzwert der eingepackten Gegenstände maximal ist.
|
||
|
||
Anwendungsbeispiel ist Beladung eines LKWs, der verschiedene Güter mit jeweils unterschiedlichem Gewinn transportieren soll, wobei aufgrund der
|
||
|
||
Abb. 3.2 Laufzeiten bei Anwendung der Enumerationsmethode
|
||
|
||
Orte Anzahl 11 1,8 ∙ 106 15 4,3 ∙ 1010 19 3,2 ∙ 1015 23 5,6 ∙ 1020 27 2,0 ∙ 1026
|
||
|
||
Laufzeit
|
||
sec
|
||
6,7 h
|
||
55,9 h 9,8 ∙ 106 Jahre 3,5 ∙ 1012 Jahre
|
||
|
||
20
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
beschränkten Ladekapazität nicht alle Güter berücksichtigt werden können. Es soll eine Auswahl mit maximalem Gesamtgewinn bestimmt werden.
|
||
Als Beispiel betrachten wir einen Rucksack mit einer Maximallast von 20 kg und fünf Gegenstände 1, . . . , 5, deren Gewichte ci und Nutzwert wi in Abb. 3.3 angegeben sind. Es soll die Menge der Gegenstände mit maximalem Gesamtnutzwert bestimmt werden, dessen Gesamtgewicht 20 kg nicht überschreitet.
|
||
Der Suchraum S ist die Menge aller Teilmengen M von {1, . . . , 5}. Die zu maximierende Funktion f : S → R gegeben durch
|
||
|
||
Gesamtnutzwert: ( ) = ∑5=1
|
||
|
||
,
|
||
|
||
={
|
||
|
||
1 0
|
||
|
||
wenn wenn
|
||
|
||
∈ ∉
|
||
|
||
Gegenstand i wird eingepackt
|
||
|
||
Der zulässige Bereich besteht aus allen Lösungen M ∈ S mit
|
||
|
||
Gewichtsbedingung g(M) =
|
||
|
||
5 i=1
|
||
|
||
ci xi
|
||
|
||
≤
|
||
|
||
20
|
||
|
||
Der Suchraum S besteht aus insgesamt 32 verschiedenen Teilmengen. Mithilfe der Enumerationsmethode, bei der für jede mögliche Auswahl der Gesamtnutzwert berechnet wird, erhält man die optimale Lösung M = {1,3,5} mit einem Gesamtnutzwert f (M) = 56 und einem Gesamtgewicht von g(M) = 18.
|
||
Allgemein gibt es bei n Objekten 2n verschiedene Auswahlmöglichkeiten (vgl. Abschn. 3.2.1), sodass bei steigender Anzahl n die Zahl der verschiedenen Teilmengen exponentiell anwächst. Die Enumerationsmethode ist damit nur für kleinere Eingangsgrößen n anwendbar. Für das Rucksackproblem für größeres n sind daher Näherungsverfahren erforderlich, die in akzeptabler Zeit brauchbare Lösungen liefern.
|
||
|
||
3.2 Lösungspräsentationen
|
||
Um ein Optimierungsproblem mathematisch modellieren zu können, muss die mathematische Darstellung der Lösungen festgelegt werden. Dabei kann die Wahl der Darstellung für die Effizienz eines Algorithmus von Bedeutung sein. In diesem Abschnitt werden verschiedene Darstellungsarten vorgestellt.
|
||
|
||
Abb. 3.3 Von den fünf Gegenständen sollen die Objekte ausgewählt werden, die in den Rucksack passen und den größten Gesamtnutzwert haben
|
||
|
||
13 € 6 kg
|
||
2
|
||
|
||
12 € 3 kg
|
||
1
|
||
|
||
24 €
|
||
5 8 kg
|
||
|
||
20 € 7 kg
|
||
3
|
||
9 €
|
||
4 5 kg
|
||
|
||
3.2 Lösungspräsentationen
|
||
|
||
21
|
||
|
||
3.2.1 Kombinatorik
|
||
|
||
Die Kombinatorik beschäftigt sich mit der Berechnung der Anzahl aller möglichen Anordnungen einer bestimmten Menge von Objekten, wobei unterschieden wird, ob die Reihenfolge der Objekte berücksichtigt wird und ob die Objekte wiederholt auftreten können.
|
||
Eine n-Menge ist eine Menge mit n Elementen. Für die Auswahl von k Elementen aus einer n-Menge ergeben sich, abhängig vom Auswahlverfahren, folgende Anzahl von Anordnungen:
|
||
|
||
Den Ausdruck
|
||
|
||
n k
|
||
|
||
nennt man Binomialkoeffizient und ist definiert durch
|
||
|
||
n k
|
||
|
||
=
|
||
|
||
n! k!(n−k)!
|
||
|
||
fu¨r 0 ≤ k
|
||
|
||
≤n
|
||
|
||
0
|
||
|
||
fu¨r 0 ≤ n < k.
|
||
|
||
Zur Illustration betrachten wir die Auswahl von k = 2 Elementen aus der 3-Menge {1,2,3}:
|
||
|
||
Beispiele
|
||
|
||
Lotto „6 aus 49“ Das Ergebnis einer Ziehung beim Lotto „6 aus 49“ kann
|
||
|
||
als 6-Menge aus der Menge {1, . . . , 49} dargestellt werden (Reihenfolge
|
||
|
||
unwesentlich, Wiederholung nicht erlaubt). Demnach gibt es insgesamt
|
||
|
||
49 6
|
||
|
||
=
|
||
|
||
49! 6!(49−6)!
|
||
|
||
=
|
||
|
||
13 983 816
|
||
|
||
verschiedene
|
||
|
||
Ergebnisse.
|
||
|
||
22
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Rucksackproblem Die Lösungen beim Rucksackproblem mit n Objekten können
|
||
|
||
dargestellt werden als k-Mengen (k ≤ n). Nach der obigen Formel gibt es ins-
|
||
|
||
gesamt
|
||
|
||
n k
|
||
|
||
verschiedene Möglichkeiten k Objekte in den Rucksack einzupacken.
|
||
|
||
Die Anzahl aller Auswahlmöglichkeiten ergibt sich dann aus der Gesamtsumme,
|
||
|
||
die sich mithilfe des binomischen Satzes wie folgt berechnen lässt:
|
||
|
||
nn =
|
||
k=0 k
|
||
|
||
n k=0
|
||
|
||
n k
|
||
|
||
1n−k · 1k = (1 + 1)n = 2n.
|
||
|
||
Problem des Handlungsreisenden Beim TSP kann eine Rundreise durch n Städte, die von 1 bis n durchnummeriert seien, dargestellt werden als eine (n − 1)Permutation der (n − 1)-Menge {2, . . . , n}, wobei die Stadt 1 der Startort ist (Reihenfolge wesentlich, Wiederholung nicht erlaubt). Beispielsweise kann die Route 1 → 4 → 2 → 5 → 3 → 1 als 4-Permutation (4,2,5,3) dargestellt werden. Nach der obigen Formel gibt es
|
||
|
||
(n − 1)!
|
||
|
||
(n − 1)!
|
||
|
||
=
|
||
|
||
= (n − 1)!
|
||
|
||
((n − 1) − (n − 1))!
|
||
|
||
0!
|
||
|
||
verschiedene (n − 1)−Permutationen. Da die Richtung der Rundreise nicht
|
||
|
||
relevant ist, halbiert sich die Anzahl der möglichen Routen. Somit erhält man ins-
|
||
|
||
gesamt
|
||
|
||
1 2
|
||
|
||
(n
|
||
|
||
−
|
||
|
||
1)!
|
||
|
||
verschiedene
|
||
|
||
Rundreisen.
|
||
|
||
Toto Bei der Elferwette wird auf elf Spielpaarungen getippt, indem auf dem Tippschein bei jeder Spielpaarung entweder die 1 (Heimmannschaft gewinnt), die 0 (unentschieden) oder die 2 (Auswärtsmannschaft gewinnt) angekreuzt wird. Eine Auswahl kann als 11-Tupel aus der 3-Menge {0, 1, 2} dargestellt werden (Reihenfolge wesentlich und Wiederholung erlaubt). Damit gibt es insgesamt
|
||
311 = 177.147
|
||
verschiedene Auswahlmöglichkeiten.
|
||
|
||
Beispiel (k-Kombination) Vier Freikarten sollen auf fünf Personen (durchnummeriert von 1 bis 5) verteilt werden, wobei jede Person auch mehrere Freikarten erhalten kann. Eine Auswahl kann als 4-Kombination über der 5-Menge {1, . . . , 5} dargestellt werden (Reihenfolge unwesentlich, Wiederholung erlaubt). Insgesamt gibt es
|
||
|
||
5+4−1 4
|
||
|
||
=
|
||
|
||
8 4
|
||
|
||
= 70
|
||
|
||
verschiedene Auswahlmöglichkeiten.
|
||
|
||
3.2 Lösungspräsentationen
|
||
|
||
23
|
||
|
||
3.2.2 Graphen
|
||
|
||
3.2.2.1 Definitionen
|
||
|
||
Netzartige Strukturen wie zum Beispiel Straßennetze, U-Bahnnetze, Gasleitungsnetze, Stromleitungen, Telekommunikationsnetze, Computernetze, elektrische Schaltungen, Ablaufpläne usw. können mittels Graphen modelliert werden. In den Netzstrukturen werden Objekte miteinander verbunden, wie z. B. in Straßennetzen Orte durch Straßen. In der Graphentheorie werden die Objekte als Knoten und die Verbindungen als Kanten bezeichnet.
|
||
|
||
Definition (Graph) Ein Graph G = (V , E) besteht aus einer Menge V von Knoten (engl. vertex) und einer Menge E von Kanten (engl. edge), wobei jeder Kante e ∈ E zwei Knoten a, b ∈ V , a <20>= b zugeordnet werden. Man schreibt dann e = {a, b} und nennt a und b benachbarte Knoten (adjazent).
|
||
Graphen werden graphisch veranschaulicht, indem Knoten als kleine Kreise und Kanten als Linien zwischen zwei Knoten dargestellt werden.
|
||
Beispiel Sei G = ({1,2,3,4,5}, {a, b, c, d}) ein Graph, wobei die Kanten wie folgt definiert sind:
|
||
|
||
Der Graph G lässt sich wie unten abgebildet als Diagramm darstellen.
|
||
|
||
1
|
||
|
||
5
|
||
|
||
2
|
||
|
||
4
|
||
|
||
3
|
||
|
||
Definitionen Sei G(V , E) ein Graph.
|
||
• Ein Kantenzug ist eine Folge von n Knoten v1, v2, v3, . . . ., v(n−1), vn aus V und n − 1 Kanten {v1, v2}, {v2, v3}, . . . ., v(n−1), vn aus E.
|
||
• Ein Kantenzug heißt geschlossen, wenn der Anfangspunkt v1 mit dem Endpunkt vn zusammenfällt.
|
||
• Ein Kantenzug heißt Weg, wenn alle vorkommenden Knoten verschieden sind. • Ein geschlossener Kantenzug heißt Kreis, wenn bis auf den Anfangs- und End-
|
||
punkt alle vorkommenden Knoten verschieden sind.
|
||
|
||
24
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
• Ein Kreis, der jeden Knoten (bis auf Anfangs- und Endpunkt) genau einmal enthält, heißt Hamilton-Kreis.
|
||
Die folgenden Graphen zeigen beispielhaft die verschiedenen Arten von Kantenzügen.
|
||
|
||
3.2.2.2 Klassifizierung von Graphen
|
||
|
||
Vollständiger Graph Ein Graph heißt vollständig, wenn zwischen je zwei seiner Knoten genau eine Kante existiert.
|
||
|
||
A
|
||
|
||
B
|
||
|
||
vollständiger
|
||
|
||
Graph
|
||
|
||
C
|
||
|
||
D
|
||
|
||
A
|
||
|
||
B
|
||
|
||
unvollständiger
|
||
|
||
Graph
|
||
|
||
C
|
||
|
||
D
|
||
|
||
Gerichteter Graph In vielen Netzwerken spielt die Wegrichtung eine Rolle, wie zum Beispiel Straßennetze mit Einbahnstraßen, Wasserleitungen, Ölpipelines oder Datenströme in digitalen Netzwerken. Solche Netzwerke können mittels Graphen modelliert werden, indem die Kanten mit Richtungen versehen werden.
|
||
|
||
ungerichteter Graph
|
||
|
||
C
|
||
|
||
E
|
||
|
||
B D
|
||
A
|
||
|
||
C
|
||
|
||
E
|
||
|
||
B D
|
||
A
|
||
|
||
gerichteter Graph
|
||
|
||
Ein Graph, in dem jede Kante eine Richtung besitzt, heißt gerichteter Graph. Zur Unterscheidung von ungerichteten Kanten {u, v} werden gerichtete Kanten
|
||
als 2-Tupel (u, v) gekennzeichnet.
|
||
|
||
Gewichteter Graph In einem Graphen können die Kanten mit einem Wert versehen werden. Diese Werte können zum Beispiel in Straßennetzen die Entfernungen oder die Transportkosten sein.
|
||
Ein Graph heißt gewichteter Graph, wenn jede Kante {u, v} mit einem Gewicht (Kostenwert) c ≥ 0 bewertet wird. Die in Abb. 3.4 abgebildete Grafik stellt einen gewichteten Graphen dar, dessen Kantengewichte die Flugzeiten in Minuten
|
||
|
||
3.2 Lösungspräsentationen
|
||
Abb. 3.4 Gewichteter Graph mit den Flugzeiten als Kostenwert
|
||
|
||
25
|
||
|
||
D 75 B
|
||
|
||
70 50
|
||
|
||
70 70
|
||
|
||
F 55 M
|
||
|
||
zwischen den in Deutschland vier größten Flughäfen Frankfurt (F), Düsseldorf (D), München (M) und Berlin (B) angeben. Zusammenhängender Graph Ein Graph G = (V , E) heißt zusammenhängend, wenn zwischen je zwei Knoten u, v ∈ V ein Weg existiert.
|
||
|
||
nicht zusammenhängend
|
||
|
||
zusammenhängend
|
||
|
||
3.2.2.3 Bäume
|
||
Bäume sind Graphen von besonderem Typ, die sehr gut geeignet sind, um Abläufe darzustellen.
|
||
Ein Baum ist ein zusammenhängender Graph, der keine Kreise enthält.
|
||
|
||
Baum
|
||
|
||
kein Baum, da unzusammenhängend
|
||
|
||
kein Baum, da nicht kreisfrei
|
||
|
||
Baum
|
||
|
||
Wurzelbaum Sei T = G(V , E) ein Baum und w ∈ V ein Knoten. Das Paar (T , w) heißt Wurzelbaum und w Wurzel. Sei a ein Knoten.
|
||
• Die Knoten auf dem Weg von w nach a heißen Vorgänger von a. Der zu a benachbarte Vorgänger heißt Vater oder unmittelbarer Vorgänger von a.
|
||
• Die Knoten b heißen Nachfolger von a, wenn a auf dem Weg von w zu b liegt. Ein mit a durch eine Kante verbundener Nachfolger heißt Kind oder unmittelbarer Nachfolger von a.
|
||
|
||
26
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Vorgänger von Vater von Kind von
|
||
|
||
c
|
||
|
||
a
|
||
|
||
b
|
||
|
||
d
|
||
|
||
w
|
||
|
||
Wurzel
|
||
|
||
Nachfolger von c
|
||
|
||
Beispiel (Problem des Handlungsreisenden) Eine Lösung des Problems des Handlungsreisenden kann als Hamilton-Kreis in einem Graphen dargestellt werden, dessen Knoten die Orte repräsentieren. Eine Lösung kann auch als Weg in einem Wurzelbaum dargestellt werden, wobei als Wurzel der Startort gewählt wird. Als Kinder eines Knotens a werden alle Orte festgelegt, die auf dem Weg von der Wurzel bis a noch nicht besucht sind (s. Abb. 3.5).
|
||
Binärbaum Ein Binärbaum ist ein Wurzelbaum, in dem jeder Knoten höchstens zwei Kinder hat.
|
||
|
||
kein Binärbaum
|
||
|
||
Binärbaum
|
||
|
||
Beispiel (Rucksackproblem) Als Beispiel betrachten wir das Rucksackproblem mit den drei Objekten A, B und C. Eine Lösung ist ein Weg in einem Binärbaum. Für den linken unmittelbaren Nachfolger wird ein Objekt eingepackt, für den rechten wird das Objekt nicht berücksichtigt (s. Abb. 3.6).
|
||
Adjazenzmatrix Graphen können in einem Computerprogramm verarbeitet werden, indem man eine mathematische Darstellung in Form einer Matrix verwendet. Adjazenzmatrix für ungerichtete und gerichtete Graphen Gegeben sei ein ungerichteter (bzw. gerichteter) Graph G = G(V , E), wobei V = {1, . . . , n} durchnummeriert ist. Dann ist die Adjazenzmatrix A = (aik) von G definiert durch
|
||
|
||
A
|
||
D
|
||
Hamilton-Kreis
|
||
|
||
Route
|
||
B
|
||
C
|
||
|
||
B
|
||
|
||
C
|
||
|
||
D
|
||
|
||
D
|
||
|
||
C
|
||
|
||
A
|
||
|
||
C
|
||
|
||
B
|
||
|
||
D
|
||
|
||
D
|
||
|
||
B
|
||
|
||
Wurzel
|
||
|
||
D
|
||
|
||
B
|
||
|
||
C
|
||
|
||
C
|
||
|
||
B
|
||
|
||
Abb. 3.5 Linke Grafik: Lösung des Problems des Handlungsreisenden mit den vier Orten A, B, C und D als Hamilton-Kreis. Rechte Grafik: Lösung als Weg in einem Baum von dem Startort (Wurzel) bis zum Endknoten
|
||
|
||
3.3 Graphenprobleme
|
||
|
||
27
|
||
|
||
A
|
||
|
||
B
|
||
|
||
A und B werden eingepackt
|
||
|
||
A
|
||
|
||
A
|
||
|
||
B
|
||
|
||
B
|
||
|
||
B
|
||
|
||
B
|
||
|
||
C
|
||
|
||
C
|
||
|
||
CC
|
||
|
||
CC
|
||
|
||
CC
|
||
|
||
C
|
||
|
||
Abb. 3.6 Darstellung einer Lösung des Rucksackproblems als Weg in einem Binärbaum mit den drei Objekten A, B und C
|
||
|
||
G ungerichtet : aik =
|
||
|
||
1 wenn {i, k} ∈ E 0 sonst
|
||
|
||
G gerichtet : aik =
|
||
|
||
1 wenn (i, k) ∈ E 0 sonst
|
||
|
||
Die Matrixelemente werden somit gleich 1 gesetzt, wenn eine Kante bzw. gerichtete Kante vorhanden ist und 0 im anderen Fall (s. Abb. 3.7). Adjazenzmatrix für gewichtete Graphen Ist G(V , E) ein gewichteter Graph, so können in der Adjazenzmatrix anstelle der Einsen die Kantengewichte eingetragen werden (s. Abb. 3.8).
|
||
|
||
3.3 Graphenprobleme
|
||
Viele Optimierungsprobleme in der Praxis können zu einem Graphenproblem umformuliert werden. Diese lassen sich damit visualisieren und können mit graphentheoretischen Methoden gelöst werden.
|
||
|
||
Knoten
|
||
|
||
Knoten
|
||
|
||
ungerichtet
|
||
|
||
Adjazenzmatrix
|
||
|
||
gerichtet
|
||
|
||
Adjazenzmatrix
|
||
|
||
Abb. 3.7 Beispiel einer Adjazenzmatrix für einen ungerichteten und einen gerichteten Graphen
|
||
|
||
Abb. 3.8 Adjazenzmatrix des gewichteten Graphen
|
||
|
||
4 97
|
||
5
|
||
|
||
28
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
3.3.1 Knotenüberdeckungsproblem
|
||
|
||
Knotenüberdeckung Zu einem ungerichteten Graphen G = (V , E) heißt eine Teilmenge U von V Knotenüberdeckung (englisch vertex cover) von G, wenn jede Kante aus E wenigstens einen Knoten aus U enthält. Die Anzahl der Knoten einer kleinsten Knotenüberdeckung β(G) heißt Knotenüberdeckungszahl.
|
||
Knotenüberdeckungsproblem Die Bestimmung der kleinsten Überdeckung U nennt man Knotenüberdeckungsproblem (englisch Minimum Vertex Cover Problem).
|
||
|
||
Knotenüberdeckungsproblem Unter dem Knotenüberdeckungsproblem versteht man die Optimierungsaufgabe, zu einem ungerichteten Graphen G = (V , E) die kleinste Teilmenge U von V zu bestimmen, die eine Knotenüberdeckung ist.
|
||
|
||
Die Abb. 3.9 a bis c illustrieren die Knotenüberdeckung an Beispielen.
|
||
Anwendungsbeispiel Der Verkehr in einem Überwachungsbereich einer Stadt soll mithilfe von Kameras gesteuert werden. Dabei sollen die Kameras in Straßenkreuzungen platziert werden und Einsicht in alle Straßenzügen von einer Kreuzung zur anderen Kreuzung haben, wobei aus Kostengründen möglichst wenige Installationsstellen zu bestimmen sind. Betrachtet man das zu beobachtende Straßennetz als Graph, wobei die Knoten des Graphen die Kreuzungspunkte repräsentieren und die Kanten die Straßen, so liegt hier ein Knotenüberdeckungsproblem vor (s. Abb. 3.10a und b).
|
||
Matrixproblem Das Knotenüberdeckungsproblem zu dem Graphen G = (V , E) kann in ein Matrixproblem übergeführt werden, indem die Adjazenzmatrix zu G zu Grunde gelegt wird.
|
||
|
||
a
|
||
|
||
b
|
||
|
||
c
|
||
|
||
ist die Menge aller schwarz markierten Knoten
|
||
Abb. 3.9 (a) U ist keine Knotenüberdeckung. (b) U ist eine Knotenüberdeckung. (c) U ist kleinste Knotenüberdeckung
|
||
|
||
3.3 Graphenprobleme
|
||
|
||
29
|
||
|
||
a
|
||
|
||
b
|
||
|
||
Abb. 3.10 (a) Darstellung des abgebildeten Straßennetzes (b) als Graph. Die optimale Lösung des Knotenüberdeckungsproblems liefert die kleinste Anzahl von Straßenknoten, in denen Kameras installiert werden müssen, um alle Straßenzüge im Überwachungsbereich zu beobachten
|
||
Das Knotenüberdeckungsproblem kann gelöst werden, indem die kleinste Anzahl von Indizes bestimmt wird, für die die zugehörigen Spalten und Zeilen alle Einsen der Adjazenzmatrix enthalten (s. Abb. 3.11a und b).
|
||
|
||
3.3.2 Maximales Cliquenproblem
|
||
Clique Zu einem ungerichteten Graphen G = (V , E) heißt eine Teilmenge C ⊆ V Clique, wenn C einen vollständigen Teilgraphen bildet, d. h. wenn in C alle Knoten direkt miteinander verbunden sind. C heißt größte Clique, wenn es in G keine Clique gibt, die mehr Knoten als C enthält. Die Anzahl der Elemente der größten Clique ω(G) heißt Cliquenzahl.
|
||
Maximales Cliquenproblem Die Bestimmung der größten Clique nennt man maximales Cliquenproblem (englisch Maximum Clique Problem).
|
||
|
||
a
|
||
|
||
b
|
||
|
||
1234567
|
||
|
||
10100000
|
||
|
||
21010110
|
||
|
||
30101000
|
||
|
||
40010101
|
||
|
||
50101000
|
||
|
||
60100000
|
||
|
||
70001000
|
||
|
||
Abb. 3.11 Der Graph (a) besitzt die Adjazenzmatrix (b). Die Matrix ist symmetrisch, da nach Voraussetzung der Graph ungerichtet ist. Eine 1 wird im Matrixelement (i, j) bzw. (j, i) gesetzt, wenn eine Kante zwischen i und j existiert und 0 im anderen Fall. Die Menge U = {2,4} ist eine Knotenüberdeckung, da die Spalten und Zeilen zu den Indizes 2 und 4 alle Einsen enthalten. Denn alle Kanten von allen anderen Knoten ausgehend weisen auf die Knoten 2 oder 4
|
||
|
||
30
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Maximales Cliquenproblem Unter einem maximalen Cliquenproblem versteht man die Optimierungsaufgabe, zu einem ungerichteten Graphen G = (V , E) eine Clique mit der größten Anzahl von Knoten zu bestimmen.
|
||
|
||
Anwendungen Maximale Cliquenprobleme treten in verschiedenen Anwendungsbereichen auf, wie Schaltungsdesign, Codierungstheorie, DNA-Sequenzierung oder NetzwerkCodierung. Soziale Netzwerke wie z. B. Facebook können als Graph modelliert werden, wobei die Knoten die Benutzer und die Kanten die Beziehungen zwischen den Benutzern wie gemeinsame Aktivitäten oder Bekanntschaften repräsentieren. Von Interesse sind die Cliquen innerhalb des Netzwerkes (s. Abb. 3.12a bis c).
|
||
Bestimmung der größten Clique Eine nicht effiziente Methode zur Bestimmung der größten Clique in einem ungerichteten Graphen G = (V , E) mit n Knoten besteht darin, alle Teilmengen von V daraufhin zu überprüfen, ob sie eine Clique bilden. Nach den Formeln der Kombinatorik 3.2.1 gibt es insgesamt 2n verschiedene Teilmengen in V. Durch Hinzufügen eines weiteren Knotens erhöht sich die Anzahl um den Faktor 2. Innerhalb der Teilmengen muss noch geprüft werden, ob alle Knotenpaare miteinander verbunden sind.
|
||
|
||
3.3.3 Stabilitätsproblem
|
||
Definitionen Sei G = (V , E) ein ungerichteter Graph. • Eine Teilmenge U von V heißt stabil oder unabhängig, wenn keine zwei Knoten
|
||
in U benachbart sind.
|
||
|
||
a
|
||
|
||
C
|
||
|
||
b
|
||
|
||
C
|
||
|
||
cC
|
||
|
||
Abb. 3.12 Cliquenbildung in einem sozialen Netzwerk, wobei die Kanten die Bekanntschaftsbeziehungen zwischen den Benutzern repräsentieren (a) C ist keine Clique, da zu einem Knotenpaar in C keine Kante existiert. (b) C ist eine Clique mit drei Knoten (c) C ist die größte Clique mit vier Knoten
|
||
|
||
3.3 Graphenprobleme
|
||
|
||
31
|
||
|
||
• Eine stabile Menge U heißt maximal, wenn es keine unabhängige Menge in G gibt, die U echt enthält.
|
||
• Gibt es zu einer stabilen Menge U in G keine stabile Menge, die mehr Elemente als U enthält, so nennt man U die größte stabile Menge.
|
||
Stabilitätszahl Die Anzahl α(G) der Elemente der größten stabilen Menge in G heißt Stabilitätszahl.
|
||
Abb. 3.13 illustriert beispielhaft die Stabilität einer Menge.
|
||
Stabilitätsproblem Die Bestimmung der Stabilitätszahl nennt man Stabilitätsproblem (englisch Maximal Independent Set Problem).
|
||
|
||
Stabilitätsproblem Unter dem Stabilitätsproblem versteht man die Optimierungsaufgabe, zu einem ungerichteten Graphen G = (V , E) die größte stabile Teilmenge in V zu bestimmen.
|
||
Anwendungsbeispiel Es sollen fünf Aufträge J1, . . . , J5 ausgeführt werden, wobei für die Durchführung drei Maschinen M1, M2, M3 zur Verfügung stehen. Die für jeden Auftrag erforderlichen Maschinen sind in der folgenden Tabelle aufgeführt. Es soll ein Plan so erstellt werden, dass möglichst viele Aufträge gleichzeitig ausgeführt werden können. Diese Optimierungsaufgabe kann in ein Stabilitätsproblem übergeführt werden, indem die Knoten die Aufträge J1, . . . , J5 repräsentieren. Eine Kante zwischen zwei Knoten wird gebildet, wenn unter den Maschinen, die für die Ausführung der beiden entsprechenden Aufträge erforderlich sind, mindestens eine Maschine ist, die für beide Aufträge benötigt wird. Als optimale Lösung des Stabilitätsproblems ergeben sich die Knoten, die die Aufträge J1, J4 und J5 repräsentieren. Damit können diese drei Aufträge gleichzeitig ausgeführt werden (s. Abb. 3.14).
|
||
|
||
a
|
||
|
||
b
|
||
|
||
c
|
||
|
||
d
|
||
|
||
( )=3
|
||
|
||
nicht stabil
|
||
|
||
maximal stabil
|
||
|
||
stabil nicht maximal
|
||
|
||
größte stabile Menge
|
||
|
||
Abb. 3.13 Stabilität der Menge U, bestehend aus den schwarz markierten Knoten
|
||
|
||
32
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
1
|
||
|
||
12345
|
||
|
||
1
|
||
|
||
×
|
||
|
||
×
|
||
|
||
2
|
||
|
||
×
|
||
|
||
×
|
||
|
||
3×××
|
||
|
||
5 4
|
||
|
||
2 3
|
||
|
||
Abb. 3.14 Darstellung des Maschinenbelegungsplans als Graph. Die größte stabile Menge des Modellgraphen besteht aus den schwarz markierten Knoten zu den Aufträgen J1, J4 und J5.
|
||
|
||
3.3.4 Zusammenhang zwischen Stabilitäts-, Knotenüberdeckungs- und maximalem Cliquenproblem
|
||
Komplementärgraph Zu einem ungerichteten Graphen G = (V , E) ist der Komplementärgraph G = V , E zu G der Graph, der die gleiche Knotenmenge V wie G besitzt und in dem zwei Knoten genau dann benachbart sind, wenn sie in G nicht benachbart sind.
|
||
|
||
=( , )
|
||
|
||
=( , )
|
||
|
||
= Komplementärgraph zu
|
||
|
||
Sei G = (V , E) ein ungerichteter Graph. Es gilt:
|
||
• Eine Knotenmenge U in G = (V , E) ist genau dann stabil, wenn U eine Clique im Komplementärgraph G = V , E ist. Es gilt dann ω(G) = α(G).
|
||
|
||
• Eine Knotenmenge U in G = (V , E) ist genau dann stabil, wenn das Komplement V \U eine Knotenüberdeckung in G = (V , E) ist. Es gilt
|
||
α(G) = n − β(G),
|
||
|
||
wobei die n die Anzahl der Knoten von V ist.
|
||
Die Abb. 3.15 illustriert den Zusammenhang zwischen Knotenüberdeckungs- und maximalem Cliquenproblem.
|
||
|
||
Stabilitäts-,
|
||
|
||
3.3 Graphenprobleme Knotenüberdeckungsproblem
|
||
=( , )
|
||
|
||
Stabilitätsproblem =( , )
|
||
|
||
33
|
||
maximales Cliquenproblem =( , )
|
||
|
||
\
|
||
|
||
kleinste Knotenüberdeckung
|
||
|
||
größte stabile Menge
|
||
|
||
schwarz markierte Knoten
|
||
|
||
größte Clique in = ( , )
|
||
|
||
Abb. 3.15 Zusammenhang zwischen Stabilitäts-, Knotenüberdeckungs- und maximalem Cliquenproblem
|
||
|
||
3.3.5 Graphen-Färbungsproblem
|
||
Färben von Graphen Gegeben sei ein ungerichteter Graph G = (V , E).
|
||
• Eine Abbildung f : V → {1, . . . , n} von der Knotenmenge V auf die Menge der natürlichen Zahlen C = {1, . . . , n} nennt man Knotenfärbung. Die Zahlen aus C nennt man Farben. Jedem Knoten kann damit eine Farbe zugeordnet werden, wobei alle n Farben unterschiedlich sind.
|
||
• Die Abbildung f : V → {1, . . . , n} heißt zulässig, wenn für alle benachbarten Knoten v, w ∈ V gilt: f (v) = f (w). In diesem Fall nennt man den Graphen nknotenfärbbar (s. Abb. 3.16a und b).
|
||
|
||
Abb. 3.16 (a) keine
|
||
|
||
a
|
||
|
||
b
|
||
|
||
zulässige Färbung (b)
|
||
|
||
4-knotenfärbbarer Graph
|
||
|
||
34
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Chromatische Zahl Die chromatische Zahl χ(G) eines Graphen G ist definiert als die kleinste natürliche Zahl n, für die der Graph G n-färbbar ist (s. Abb. 3.17). Die Bestimmung von χ(G) nennt man Graphen-Färbungsproblem.
|
||
|
||
Graphen-Färbungsproblem Unter dem Graphen-Färbungsproblem versteht man die Optimierungsaufgabe, zu einem Graphen G = (V , E) die kleinste natürliche Zahl k zu bestimmen, für die G k-färbbar ist.
|
||
|
||
Anwendungen des Graphen-Färbungsproblems
|
||
Frequenzplanung in Funknetzen Bei der Frequenzplanung in Mobilfunknetzen sind Kanäle (Frequenzen) auf die Sendemaste so zu verteilen, dass der Betrieb störungsfrei ist, wobei aus Kostengründen die Anzahl der erforderlichen Frequenzen zu minimieren ist. Zwischen zwei Sendemasten, die mit der gleichen Frequenz senden, können bei Überschneidung der Sendebereiche Interferenzen auftreten, die die Gesprächsqualität beeinträchtigen. Das Interferenzproblem kann als Graphen-Färbungsproblem aufgefasst werden, indem die Knoten die Sendemasten darstellen und zwei Knoten mit einer Kante verbunden werden, wenn in den zugehörigen Sendebereichen Interferenzen auftreten. Die Bestimmung der chromatischen Zahl liefert eine optimale Lösung des Frequenzplanungsproblems (s. Abb. 3.18).
|
||
Ein Graph heißt planar, wenn er ohne Überkreuzung der Kanten in einer Ebene gezeichnet werden kann. Es gilt der folgende Satz:
|
||
Vierfarbensatz Jeder planare Graph ist 4-färbbar.
|
||
Beweis des Vierfarbensatzes: Lange Zeit war der Vierfarbensatz ein offenes Problem (Vierfarbenproblem) und wurde 1976 von K. Appel und W. Haken mithilfe eines Computers bewiesen. Sie konnten den Beweis auf 1936 Fälle
|
||
|
||
a
|
||
|
||
b
|
||
|
||
c
|
||
|
||
Abb. 3.17 (a) Die chromatische Zahl eines gitterartigen Graphen ist unabhängig von der Anzahl der Knoten stets gleich 2. (b) Die chromatische Zahl eines vollständigen Graphen ist gleich der Anzahl der Knoten. (c) Die chromatische Zahl eines Hamiltonkreises mit n Knoten ist 2, wenn n gerade ist und 3, wenn n ungerade ist
|
||
|
||
3.3 Graphenprobleme
|
||
|
||
35
|
||
|
||
Abb. 3.18 Das Frequenzplanungsproblem für das Beispielfunknetz kann in ein Graphen Färbungsproblem übergeführt werden, indem die Knoten die Sendemasten repräsentieren und die Kanten die Verbindung der Sendemasten mit überlappenden Sendebereichen darstellen. Da der Modellgraph 3-knotenfärbbar ist, sind drei verschiedene Frequenzen für den störungsfreien Betrieb ausreichend
|
||
reduzieren, die sie einzeln mittels eines Computers überprüften. Bislang ist ein analytischer Beweis noch nicht gefunden worden.
|
||
Anwendung des Vierfarbensatzes: Jede Landkarte kann auch als Graph dargestellt werden, indem die Knoten die Länder repräsentieren und jeweils zwischen den Knoten zweier angrenzenden Länder eine Kante gelegt wird. Damit kann nach dem Vierfarbensatz jede Landkarte mit nur vier Farben so eingefärbt werden, dass keine Nachbarländer die gleiche Farbe haben (s. Abb. 3.19a und b).
|
||
|
||
3.3.6 Max-Cut-Problem
|
||
|
||
Max-Cut-Probleme treten in vielen Anwendungsbereichen auf, wie zum Beispielin der Bioinformatik, statistischen Physik, VLSI-Design oder Portfolio-Optimierung.
|
||
Schnitt in Graphen Sei G = (V , E) ein ungerichteter Graph. Zu einer Teilmenge S von V ist der Schnitt definiert als die Menge aller Kanten in G, die einen Knoten in S mit einem Knoten im Komplement V \S verbinden. Der Schnitt wird mit S
|
||
|
||
a
|
||
|
||
b
|
||
|
||
Abb. 3.19 Die Landkarte (a) wird mit dem planaren Graphen (b) modelliert, indem zu jeder Fläche ein gleichfarbiger Knoten zugeordnet wird und die Knoten von Nachbarländern durch eine Kante miteinander verbunden werden. Jede Landkarte kann nach dem Vierfarbensatz mit vier Farben so gefärbt werden, dass benachbarte Länder verschiedene Farben haben
|
||
|
||
36
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
identifiziert. Die Anzahl der Kanten des Schnittes S wird mit w(S) bezeichnet (s. Abb. 3.20).
|
||
Max-Cut-Problem Bei dem Max-Cut-Problem wird ein größtmöglicher Kantenschnitt S gesucht.
|
||
|
||
Max-Cut-Problem Unter einem Max-Cut-Problem versteht man die Optimierungsaufgabe, zu einem ungerichteten Graphen G = (V , E) einen Schnitt S mit maximaler Kantenzahl w(S) zu bestimmen.
|
||
|
||
Gewichtetes Max-Cut-Problem Sei G = (V , E) ein gewichteter ungerichteter Graph mit den Kantengewichten wij > 0, wii = 0 und wij = wji. Bei dem gewichteten Max-Cut-Problem wird ein Schnitt S ⊂ V gesucht, sodass das Gesamtgewicht
|
||
|
||
maximal ist (s. Abb. 3.21).
|
||
|
||
wij
|
||
i∈S,j∈V \S
|
||
|
||
( )=3
|
||
|
||
( )=5
|
||
|
||
Abb. 3.20 Illustration des Schnittes S in einem Graphen
|
||
|
||
a
|
||
|
||
①
|
||
|
||
12
|
||
|
||
②
|
||
|
||
14
|
||
|
||
23
|
||
|
||
13
|
||
|
||
④
|
||
|
||
34
|
||
|
||
③
|
||
|
||
b
|
||
|
||
-1 ①
|
||
|
||
12
|
||
|
||
②+1
|
||
|
||
14
|
||
|
||
23
|
||
|
||
13
|
||
|
||
-1 ④
|
||
|
||
34
|
||
|
||
③+1
|
||
|
||
Abb. 3.21 (a) Schnitt in einem gewichteten Graphen (b) Vorzeichen der Knoten bei dem Schnitt S
|
||
|
||
3.4 Vehicle-Routing-Probleme
|
||
|
||
37
|
||
|
||
Mathematische Formulierung des gewichteten Max-Cut-Problems Die Knoten des gewichteten ungerichteten Graphen G = (V , E) seien durchnummeriert von 1 bis n. Jedem Knoten i ∈ V werde eine Zahl xi ∈ {−1,1} zugeordnet (s. Abb. 3.21a und b). Wählt man die Vorzeichen von xi für die Knoten aus S und V \S unterschiedlich, so gilt
|
||
|
||
1 2 1 − xixj =
|
||
|
||
0 wenn {i, j} in S oder in V \S liegt 1 sonst
|
||
|
||
Eine optimale Lösung des gewichteten Max-Cut-Problems kann damit bestimmt werden durch die Maximierung von
|
||
|
||
1
|
||
|
||
f (x) = max x2
|
||
|
||
wij 1 − xixj ,
|
||
|
||
i<j
|
||
|
||
wobei x = (x1, . . . , xn) mit xi ∈ {−1, 1}, i = 1, . . . , n. Die Einschränkung i < j ist erforderlich, damit die Gewichte nicht doppelt addiert werden.
|
||
|
||
3.4 Vehicle-Routing-Probleme
|
||
Unter dem Vehicle Routing-Problem (VRP) versteht man die logistische Aufgabe, mit einer Flotte von Fahrzeugen von einem Depot aus mehrere Kunden an verschiedenen Standorten mit Waren zu beliefern, sodass die Gesamttransportstrecke minimal ist. Hierbei sind unterschiedliche Restriktionen zu berücksichtigen, wie z. B. Kapazitäten der Fahrzeuge, Anzahl der Fahrzeuge oder Zeitrestriktionen. Eine zulässige Lösung des VPR nennt man Tourenplan. Das TSP ist ein Spezialfall des VRP, bei dem zur Lösung nur eine Route erforderlich ist.
|
||
Das Vehicle-Routing-Problem ist nicht nur auf die Auslieferung von Waren beschränkt. Die Anwendungsgebiete des VPR sind vielfältig, wie z. B. Routenplanung für Straßenreinigung, Müllabfuhr, Schulbusfahrten, Wartungsfahrten, Pflegedienste oder Entleerung von Briefkästen.
|
||
|
||
3.4.1 Einführendes Beispiel
|
||
Im Folgenden betrachten wir ein vereinfachtes Beispiel. Von einem Depot aus sollen sechs Kunden an verschiedenen Standorten mit Waren beliefert werden. Die Kundenstandorte werden von 1 bis 6 durchnummeriert, das Depot bekommt die null zugewiesen. In der Entfernungstabelle der Abb. 3.22 sind die kürzesten Wege zwischen den Kundenstandorten und dem Depot zusammengefasst. Ein Fahrzeug kann aufgrund der Volumenbeschränkung maximal drei Kunden beliefern.
|
||
|
||
38
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Entfernungstabelle
|
||
|
||
Abb. 3.22 Eine zulässige Lösung des gegebenen Vehicle-Routing-Problems
|
||
Die Fahrzeuge sollen nach der Warenlieferung wieder zum Depot zurückfahren. Gesucht ist ein Tourenplan mit minimaler Gesamttransportstrecke.
|
||
Wir betrachten zwei verschiedene Lösungsmethoden.
|
||
Methode 1: Eine zulässige Lösung erhält man, indem man mit der ersten Belieferung bei Kunde 1 beginnt. Von dort aus werden nacheinander die zwei nächstgelegenen Kundenstandorte aufgesucht. Dies ergibt für Fahrzeug 1 die Route 0 → 1 → 4 → 3 → 0. Für Fahrzeug 2 erhält man für die restlichen drei Orte die Route 0 → 2 → 6 → 5 → 0, wobei auch hier stets der nächstgelegene Ort angefahren wird. Damit ergibt sich für die Gesamtstrecke dieses Tourenplans der folgende Wert:
|
||
|
||
Man erhält insgesamt sechs verschiedene Tourenpläne, wenn man jeweils einen anderen Kundenort als ersten Lieferort wählt. Ausgewählt wird der Tourenplan mit der kürzesten Gesamtstrecke.
|
||
|
||
Methode 2: Eine weitere Lösungsmethode besteht darin, Cluster von jeweils drei Kundenorten zu bilden, z. B. die Gruppen {2,3,6} und {1,4,5}. In jedem Cluster wird unter Einbeziehung des Depots das Problem des Handlungsreisenden gelöst und die Summe der Weglängen der beiden Touren gebildet. Wendet man das Verfahren für jede mögliche Clusterbildung mit drei Orten an, so gibt es nach 3.2.1
|
||
|
||
insgesamt
|
||
|
||
6 3
|
||
|
||
= 20 verschiedene Tourenpläne, von denen der Tourenplan mit
|
||
|
||
der niedrigsten Gesamtstrecke als beste gefundene Lösung ausgewählt wird.
|
||
|
||
3.4 Vehicle-Routing-Probleme
|
||
|
||
39
|
||
|
||
3.4.2 Grundversion des VRP
|
||
|
||
Unter dem VRP in der Grundversion versteht man die folgende Optimierungsaufgabe:
|
||
|
||
Vehicle-Routing-Problem (VRP) Gegeben seien ein Depot, N Kunden und M Fahrzeuge. Gesucht sind M Touren, um alle Kunden zu bedienen, sodass die zurückgelegte Gesamtstrecke minimal ist. Dabei dürfen alle Kunden nur einmal besucht werden. Die Fahrzeuge starten am Depot und fahren dorthin zurück.
|
||
|
||
Mathematische Formulierung des VRP Das Vehicle-Routing-Problem kann wie folgt mathematisch modelliert werden:
|
||
|
||
Gegeben:
|
||
• Ein Depot, das mit Null gekennzeichnet wird • N Kunden, die von 1 bis N durchnummeriert werden • Die Entfernung cij zwischen Kunde i und Kunde j • M Fahrzeuge, die durchnummeriert werden von 1 bis M
|
||
|
||
Suchraum: Die folgende binäre Entscheidungsvariable xij gibt an, ob ein Fahrzeug von Kunde i zu Kunde j fährt:
|
||
|
||
xij =
|
||
|
||
1 wenn ein Fahrzeug von i nach j, i <20>= j, fa¨hrt 0 sonst
|
||
|
||
,
|
||
|
||
Der Suchraum S besteht aus der Menge aller (N + 1)2−Tupel
|
||
|
||
i, j = 0, . . . , N.
|
||
|
||
x = xij i,j=0,...,N .
|
||
Zielfunktion: Die zu minimierende Zielfunktion (Gesamtstrecke) ist definiert durch:
|
||
|
||
N
|
||
|
||
N
|
||
|
||
f : S → R, f (x) = i=0 j=0 cijxij → min.
|
||
|
||
Da die Komponenten xij nur die Werte 0 oder 1 annehmen, werden nur die Entfernungen cij der Kanten (i, j) summiert, die in dem Tourenplan enthalten sind.
|
||
|
||
Nebenbedingungen:
|
||
|
||
(a)
|
||
|
||
N i=0
|
||
|
||
xij
|
||
|
||
=
|
||
|
||
1
|
||
|
||
fu¨ r
|
||
|
||
alle
|
||
|
||
j
|
||
|
||
=
|
||
|
||
1,
|
||
|
||
.
|
||
|
||
.
|
||
|
||
.
|
||
|
||
,
|
||
|
||
N
|
||
|
||
(b)
|
||
|
||
N j=1
|
||
|
||
x0j
|
||
|
||
=
|
||
|
||
M
|
||
|
||
40
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
(c) (d)
|
||
|
||
N iN=1 i=0
|
||
|
||
xi0 xik
|
||
|
||
= =
|
||
|
||
N
|
||
|
||
N j=0
|
||
|
||
xkj
|
||
|
||
fu¨r alle k = 1, . . . , M
|
||
|
||
(e) i,j∈U xij ≤ |U| − 1 für alle nichtleeren Teilmengen U ⊂ {1, . . . , N}
|
||
|
||
Erläuterungen
|
||
|
||
(a) Die Nebenbedingung (a) gewährleistet, dass es für jeden Knoten j genau
|
||
|
||
einen Knoten i und ein Fahrzeug gibt, das von i nach j fährt. Damit wird jeder
|
||
|
||
Kunde genau einmal besucht.
|
||
|
||
(b) Mit der Bedingung (b) wird festgelegt, dass jedes Fahrzeug das Depot ver-
|
||
|
||
lässt.
|
||
|
||
(c) Bedingung (c) impliziert, dass jedes Fahrzeug wieder zum Depot zurückfährt.
|
||
|
||
(d) Bedingung (d) stellt sicher, dass ein Fahrzeug, das einen Kunden k bedient,
|
||
|
||
diesen auch wieder verlässt.
|
||
|
||
(e) Der Betrag |U|. gibt die Anzahl der Elemente von U an. Bedingung (e) wird
|
||
|
||
auch als „Subtour-Eliminations-Bedingung“ bezeichnet. Sie gewährleistet,
|
||
|
||
dass in den Tourengraphen keine Kreise vorliegen. Setzt man nämlich zum
|
||
|
||
Beispiel voraus, dass für die Menge U = {2,4,5} die Bedingung (e) nicht erfüllt
|
||
|
||
ist, so gilt i,j∈U xij > |U| − 1 = 2. Der Teilgraph mit den Knoten 2, 4 und 5 enthält demnach mehr als zwei Kanten und bildet somit einen Kreis, wie unten
|
||
|
||
abgebildet.
|
||
|
||
2
|
||
|
||
4
|
||
|
||
5
|
||
|
||
Das VRP lässt sich in zwei Teilprobleme zerlegen: die Zuordnung der Kunden zu den einzelnen Touren und die Bestimmung der Reihenfolge der Kunden innerhalb einer Tour (Problem des Handlungsreisenden).
|
||
|
||
Vehicle Routing Problem
|
||
|
||
Zuordnungsproblem Reihenfolgenproblem
|
||
|
||
3.4.3 Varianten des VRP
|
||
Das VRP ist erweiterbar durch eine Vielzahl unterschiedlicher Nebenbedingungen, wie zum Beispiel die Berücksichtigung von Kapazitäts- und Tourenlängenbeschränkungen, von Arbeitszeitregelungen, der maximalen Fahrdauer, der Fahrkosten, der Anzahl der Depots, der Auswahl von Fahrzeugtypen oder des Mehrfacheinsatzes von Fahrzeugen. Wir betrachten hierzu stellvertretend einige Varianten:
|
||
|
||
3.5 Scheduling-Probleme
|
||
|
||
41
|
||
|
||
• Capacitated Vehicle Routing Problem (CVRP) Bei dem CVRP werden zusätzlich Kapazitätsbeschränkungen der Fahrzeuge betrachtet. Jedem Kunden wird eine Bedarfsmenge zugeordnet. Es gilt, für jedes Fahrzeug die Rundreise vom Depot so zu bestimmen, dass die Gesamtmenge der auszuliefernden Waren die Kapazität des Fahrzeugs nicht übersteigt.
|
||
• Vehicle Routing Problem with Time Windows (VRPTW) Bei diesem Tourenplanungsproblem wird gefordert, dass jeder Kunde nur in einem Zeitfenster angefahren werden darf. Anwendungsbeispiele des VRPTW sind Routenplanungen für Schulbusse, Besuchszeiten von Pflegekräften, Postzustellung, Zeitungszustellung oder Belieferung von Waren an Supermärkte zu bestimmten Öffnungszeiten.
|
||
• Multi-Depot Vehicle Routing Problem (MDVRP) Bei diesem Tourenplanungs-Problem geht man von mehreren Depots aus, wobei jedes Fahrzeug fest einem Depot zugeordnet wird und jedes Fahrzeug auch dorthin wieder zurückkehrt.
|
||
• Vehicle Routing Problem with Pickup and Delivery Bei diesem Problem werden Waren an Kunden nicht nur geliefert (Delivery), sondern es werden auch auszuliefernde Waren vorher bei einem anderen Kunden abgeholt (Pickup).
|
||
Die Abb. 3.23a bis c illustrieren Varianten der Vehicle Routing-Probleme.
|
||
|
||
3.5 Scheduling-Probleme
|
||
Unter Scheduling versteht man die Erstellung eines Ablaufplans mit dem Ziel, Arbeitsabläufe zu optimieren und Arbeitsmittel wie Maschinen, Personal, Arbeitszeit oder Kapital effizient auszunutzen.
|
||
|
||
a
|
||
|
||
CVRP
|
||
|
||
4 t
|
||
|
||
3 t
|
||
|
||
200 kg
|
||
|
||
b VRPTW
|
||
19 — 20:00 7 — 9:00
|
||
|
||
c MDVRP
|
||
|
||
t 300 kg
|
||
|
||
2 t 600 kg
|
||
|
||
8 — 10:00 7 — 16:00
|
||
|
||
14 — 16:00 13 — 17:00
|
||
|
||
D
|
||
|
||
D
|
||
|
||
7,5 t 7,5 t
|
||
Fuhrpark:
|
||
|
||
Fuhrpark:
|
||
|
||
Fuhrpark D : Fuhrpark D2:
|
||
|
||
Abb. 3.23 (a) VRP mit Kapazitätsbeschränkung (b) VRP mit Zeitfenster (c) VRP mit zwei Depots D1 und D2
|
||
|
||
42
|
||
3.5.1 Einführendes Beispiel
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Es soll ein Maschinenbelegungsplan für drei Aufträge Job 1, Job 2 und Job 3 erstellt werden, die auf drei Maschinen M1, M2 und M3 bearbeitet werden sollen. Jeder Job besteht aus Vorgängen (Tasks), die in einer vorgegebenen festen Reihenfolge auf den Maschinen ausgeführt werden müssen, wobei jede Maschine nur einen Vorgang gleichzeitig bearbeiten kann. Es ist die Optimierungsaufgabe zu lösen, die Maschinenbelegung so festzulegen, dass die Gesamtbearbeitungszeit (engl. Makespan) minimiert wird. Dieses Optimierungsproblem nennt man JobShop-Problem. Die Maschinenreihenfolge für jeden Job und die Bearbeitungszeit für jede Maschine und jeden Job ist in der folgenden Tabelle angegeben.
|
||
|
||
Eine Lösung des Job-Shop-Problems kann visuell als sogenanntes GanttDiagramm in Form von überschneidungsfreien Balken auf einer Zeitachse dargestellt werden. Jeder Job bzw. jede Maschine wird innerhalb des Balkens durch ein eigenes Feld gekennzeichnet. Die Länge der Balken gibt die Bearbeitungszeit an (s. Abb. 3.24a und b). Bei diesem vereinfachten Job-Shop-Problem wird unterstellt, dass die Maschinen rund um die Uhr verfügbar sind. In realen Produktionsumgebungen sind zusätzlich Stillstandszeiten wie zum Beispiel Schichtzeiten oder Ausfallzeiten für Wartungsarbeiten zu berücksichtigen.
|
||
3.5.2 Grundversion des Scheduling-Problems
|
||
Unter einem Scheduling-Problem versteht man allgemein die folgende Optimierungsaufgabe:
|
||
Scheduling-Problem Gesucht ist ein Maschinenbelegungsplan, der m Jobs auf n Maschinen unter Berücksichtigung vorgegebener Bearbeitungsreihenfolgen zuordnet, sodass eine vorgegebene Zielfunktion minimiert wird.
|
||
|
||
3.5 Scheduling-Probleme
|
||
|
||
43
|
||
|
||
a
|
||
Job 1 Job 2 Job 3
|
||
|
||
Maschine 1 Maschine 2 Maschine 3
|
||
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Zeit
|
||
|
||
b
|
||
Maschine 1 Maschine 2 Maschine 3
|
||
|
||
Job 1 Job 2 Job 3
|
||
1 2 3 4 5 6 7 8 9 10 11 12 13 14 Zeit
|
||
|
||
Abb. 3.24 (a) Darstellung einer Lösung des Job-Shop-Problems als joborientiertes GanttDiagramm. Die Gesamtbearbeitungszeit beträgt bei dieser Lösung 13 Zeiteinheiten. (b) Darstellung einer Lösung des Job-Shop-Problems als maschinenorientiertes Gantt-Diagramm. Die Gesamtbearbeitungszeit beträgt bei dieser Lösung insgesamt 14 Zeiteinheiten.
|
||
|
||
Mathematische Modellierung des Scheduling-Problems
|
||
|
||
Gegeben • m Jobs: J1, . . . , Jm • n Maschinen: M1, . . . , Mn • Reihenfolge für jeden Job Ji : Mk1 → Mk2 → · · · → Mkl, darstellbar als Per-
|
||
mutation pi = (k1, k2, . . . , kl) für i = 1, . . . , m • Bearbeitungszeit cij von Job Ji auf Maschine Mj
|
||
Notation Ci = Zeitpunkt der Fertigstellung von Job Ji
|
||
Zielfunktion Häufig wird eine der folgenden Zielfunktionen zur Minimierung eines Maschinebelegungsplans verwendet:
|
||
|
||
1. Gesamtbearbeitungszeit: Cmax = max Ci → min
|
||
i=1,...,m
|
||
|
||
2. Summe der Fertigstellzeitpunkte:
|
||
|
||
m i=1
|
||
|
||
Ci
|
||
|
||
→
|
||
|
||
min
|
||
|
||
3. Gewichtete Summe der Fertigstellzeitpunkte mit Gewichtsfaktoren wi :
|
||
|
||
m i=1
|
||
|
||
wi Ci
|
||
|
||
→
|
||
|
||
min
|
||
|
||
44
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
3.5.3 Klassifikation von Scheduling-Problemen
|
||
|
||
Scheduling-Probleme werden je nach Art der Maschinenreihenfolge wie folgt klassifiziert:
|
||
• Job Shop Für jeden Job ist eine jobspezifische Reihenfolge der Maschinen festgelegt.
|
||
• Flow Shop Ein Flow Shop ist ein spezieller Job Shop, bei dem alle Jobs die gleichen Maschinen in der gleichen Reihenfolge durchlaufen.
|
||
• Open Shop Die Reihenfolge der Jobs und die Maschinenreihenfolge sind frei wählbar.
|
||
• Parallel Shop Jeder Job besteht nur aus einem Vorgang, der auf Maschinen vom gleichen Typ auszuführen ist.
|
||
Abb. 3.25 illustriert die Varianten der Scheduling-Probleme.
|
||
|
||
3.5.4 Beispiele von Scheduling-Problemen
|
||
Scheduling-Probleme treten in vielen Anwendungsfeldern auf, wie zum Beispiel bei der Erstellung eines Stundenplans an Schulen und Universitäten, bei der Personaleinsatzplanung, bei der Erstellung eines Bahn-Fahrplans, bei der Scheduling von Prozessen auf Computern oder bei der Planung von Sportveranstaltungen. Dabei sind je nach Problemstellung die Maschinen und Jobs unterschiedlich zu interpretieren. Hierzu exemplarisch folgende Anwendungen:
|
||
|
||
Job Shop
|
||
|
||
Job
|
||
|
||
3 12
|
||
|
||
Job
|
||
|
||
231
|
||
|
||
Flow Shop
|
||
|
||
Job
|
||
|
||
1 23
|
||
|
||
Job
|
||
|
||
Open Shop
|
||
|
||
Job
|
||
|
||
1 23
|
||
|
||
Job
|
||
|
||
1 23
|
||
|
||
Parallel Shop Job
|
||
Maschine Job
|
||
|
||
Maschine
|
||
|
||
Job
|
||
|
||
Maschine
|
||
|
||
Job
|
||
|
||
Job
|
||
|
||
Abb. 3.25 Job Shop: Job spezifische Maschinenreihenfolge. Flow Shop: gleiche Maschinenreihenfolge für jeden Job. Open Shop: Maschinenreihenfolge frei wählbar. Parallel Shop: Die Jobs werden auf identischen Maschinen ausgeführt.
|
||
|
||
3.6 Zuschnittprobleme und Packungsprobleme
|
||
|
||
Anwendung Stundenplan
|
||
Krankenhaus Computer
|
||
Bahn-Fahrplan Flughafen
|
||
|
||
Maschinen Lehrer
|
||
Wartezimmer, Arztraum, Röntgenraum,... Prozessor Zugstrecken
|
||
Start- und Landebahnen
|
||
|
||
45
|
||
Jobs Unterrichtsstunden
|
||
Patienten Prozesse
|
||
Züge Start und Landungen
|
||
von Flugzeugen
|
||
|
||
3.6 Zuschnittprobleme und Packungsprobleme
|
||
Zuschnitt- und Packungsprobleme (engl. Cutting&Packing problem, abgekürzt C&P-Problem) treten in vielen Anwendungsbereichen auf, wie zum Beispiel bei der Zuschnittoptimierung in der holz-, metall-, papier- und textilverarbeitenden Industrie oder bei der Stauraumoptimierung zur Beladung von Lastkraftwagen und Containern. Zuschnitt- und Packungsprobleme sind dual zueinander und werden zu einem Optimierungsgebiet zusammengefasst. Bei den Zuschnittproblemen werden größere Objekte in kleinere Teile zerlegt, während bei den Packungsproblemen kleinere Teile in größere Objekte gepackt werden (s. Abb. 3.26).
|
||
|
||
3.6.1 Dimension von Zuschnitt- und Packungsproblemen
|
||
Ein wichtiges Klassifizierungsmerkmal von C&P-Problemen ist die Dimension. Die Objekte sind meistens dreidimensional, werden aber je nach Relevanz auch als ein- oder zweidimensionale Objekte betrachtet. Für ein- und zweidimensionale C&P-Probleme haben die Zuschnittoptimierungen die größere Praxisrelevanz,
|
||
|
||
Abb. 3.26 Äquivalente Optimierungskriterien bei Zuschnitt- und Packungsproblemen
|
||
|
||
Zuschnitt Verschnitt
|
||
|
||
Beladung Leeraum
|
||
|
||
46 eindimensional
|
||
a
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
zweidimensional b
|
||
|
||
dreidimensional c
|
||
|
||
Abb. 3.27 (a) Zuschnitt von Wasserleitungen mit möglichst geringem Verschnitt (b) Zuschnitt von Holzplatten mit minimalem Verschnitt (c) Beladung von Quadern in möglichst wenigen Kisten
|
||
während für dreidimensionale C&P-Probleme die Packungsoptimierungen vorrangig Anwendungen finden (s. Abb. 3.27).
|
||
3.6.2 Bin-Packing-Problem
|
||
Bin-Packing-Problem (Behälterproblem) Unter einem Bin-Packing-Problem versteht man die Optimierungsaufgabe, eine Anzahl von Objekten unterschiedlicher Größen in möglichst wenige Behälter (engl. Bins) von gleicher Größe zu packen.
|
||
On- und Offline Zuordnung Man unterscheidet zwischen der Online-Zuordnung und der Offline-Zuordnung. Bei der Online-Variante muss sofort entschieden werden, in welchen Behälter das Objekt gepackt wird. Bei dem Offline-Verfahren sind alle Objekte im Vorhinein bekannt, sodass eine Sortierung möglich ist.
|
||
3.6.3 Eindimensionale C&P-Probleme
|
||
Online-Bin-Packing-Probleme Die einfachsten Verfahren zur Lösung von Online Bin Packing-Problemen sind die folgenden Methoden: • Next Fit (NF): Die Objekte werden der Reihe nach in den letzten offenen
|
||
Behälter gepackt, sofern sie reinpassen. Ansonsten wird der Behälter geschlossen und das aktuelle Objekt in den nächsten leeren Behälter gepackt.
|
||
|
||
3.6 Zuschnittprobleme und Packungsprobleme
|
||
|
||
47
|
||
|
||
• First Fit (FF): Die Objekte werden der Reihe nach in den ersten nichtleeren Behälter eingepackt, in dem noch Platz ist. Ansonsten wird das aktuelle Objekt in den nächsten leeren Behälter gepackt.
|
||
• Best Fit (BF): Die Objekte werden der Reihe nach in den Behälter mit dem kleinsten Restraum eingepackt. Falls das aktuelle Objekt in keinen Restraum passt, so wird es in den nächsten leeren Behälter gepackt.
|
||
Offline-Bin-Packing-Probleme Bei der Offline-Variante sind alle Objekte bekannt und werden absteigend sortiert. Auf diese sortierten Objekte werden die Verfahren der OnlineVariante angewendet. Diese Methoden werden entsprechend mit NFD (Next Fit decreasing), FFD (First Fit decreasing) und BFD (Best Fit decreasing) bezeichnet.
|
||
Beispiel 1 (Zuschneiden von Rohren) Aus Rohren der Länge 10 Längeneinheiten (LE) sollen Rohrteile der Länge 5, 6, 3, 4 und 2 LE mit minimalem Verschnitt herausgeschnitten werden. Dieses Zuschnittproblem soll mit dem Online-Bin-Packing-Verfahren gelöst werden. Die Behälter entsprechen den Rohlingen und die Objekte den Rohrteilen. Die Ergebnisse sind in der Abb. 3.28 angegeben.
|
||
Beispiel 2 (Backup auf Datenträger) Das Problem, mehrere Dateien auf möglichst wenigen USB-Sticks zu sichern, kann als eindimensionales Bin-Packing-Problem aufgefasst werden.
|
||
|
||
3.6.4 Zweidimensional C&P-Probleme
|
||
Bei den zweidimensionalen Zuschnittproblemen spielen die sogenannten Guillotine-Schnitte in der industriellen Praxis sowie bei der Lösung von Zuschnittoptimierungen eine wichtige Rolle.
|
||
|
||
Rohling
|
||
|
||
Objekte 10 5 6 3 4 2
|
||
|
||
Next Fit
|
||
3 2
|
||
564
|
||
|
||
First Fit 24 3
|
||
56
|
||
|
||
Best Fit
|
||
43
|
||
56 2
|
||
|
||
Abb. 3.28 Lösungen des Online-Bin-Packing-Problems nach der NF-, FF- und BF-Methode. Die Lösung der FF-Methode ist zufällig optimal.
|
||
|
||
48
|
||
|
||
3 Kombinatorische Optimierungsprobleme
|
||
|
||
Guillotine-Schnitte Guillotine-Schnitte finden in vielen Herstellungsprozessen Anwendung, wie zum Beispiel in der Holz-, Glas-, Metall- oder Möbelindustrie. Durch einen GuillotineSchnitt wird ein Rechteck in zwei kleinere Rechtecke geteilt, wobei der Schnitt von Kante zu Kante erfolgt. Die Rechtecke können mit Guillotinen-Schnitten weiter unterteilt werden, bis man die Rechtecke in der gewünschten Größe erhält. Bei feststehender Säge sind orthogonale Drehungen der Rechteckteile erforderlich. Die Anzahl der notwendigen Richtungsänderungen wird Stufen genannt (s. Abb. 3.29).
|
||
|
||
Strip-Packing-Problem Gegeben sei ein Streifen (engl. strip) der Breite W mit einer unendlichen Höhe sowie eine Menge von kantenparallelen Rechtecken mit einer maximalen Breite W. Die Optimierungsaufgabe besteht darin, die Rechtecke in den Streifen so zu packen, dass die Gesamthöhe minimal ist. Dabei dürfen die Rechtecke nicht überlappen und nicht gedreht werden.
|
||
|
||
Strip-Packing-Optimierungen finden unter anderem Anwendung in der industriellen Fertigung, bei der passende Rechtecke aus Stoff- oder Papierbahnen herausgeschnitten werden.
|
||
Level-Algorithmus Strip-Packing-Probleme können mithilfe von sogenannten Level-Algorithmen gelöst werden, bei denen so viele Rechtecke wie möglich nebeneinander gepackt werden. Die größte Höhe eines dieser Rechtecke legt das Level fest, ab dem die nächsten Rechtecke eingepackt werden.
|
||
Ein einfacher Level-Algorithmus ist die folgende Online-Methode:
|
||
Next Level (NL): Die Rechtecke werden der Reihe nach eingepackt. Passt ein Rechteck nicht mehr in ein Level, so wird dieses Level geschlossen und ein neues Level wird eröffnet.
|
||
|
||
einstufig 1
|
||
|
||
Guillotine-Schnitte
|
||
|
||
zweistufig
|
||
|
||
dreistufig
|
||
|
||
1
|
||
|
||
1
|
||
|
||
2
|
||
|
||
2
|
||
|
||
kein GuillotineSchnitt
|
||
|
||
Abb. 3.29 Beispiele von Guillotine-Schnitten
|
||
|
||
3.6 Zuschnittprobleme und Packungsprobleme
|
||
|
||
49
|
||
|
||
Rechteck Breite Höhe
|
||
|
||
10
|
||
|
||
9
|
||
|
||
8
|
||
76
|
||
|
||
6
|
||
|
||
5
|
||
|
||
4
|
||
|
||
3
|
||
|
||
3
|
||
|
||
2
|
||
11
|
||
|
||
7
|
||
|
||
Level 3
|
||
|
||
4 5 Level 2
|
||
|
||
2
|
||
|
||
Level 1
|
||
|
||
1 2 3 4 5 6 7 8 9 10
|
||
|
||
Abb. 3.30 Ergebnis der NL-Methode. Die Gesamthöhe beträgt 9.
|
||
|
||
Beispiel Sieben Rechtecke sollen in einen Streifen der Breite 10 mithilfe der NL-Methode gepackt werden. Die Größen der Rechtecke und die Ergebnisse sind in der Abb. 3.30 angegeben.
|
||
Nesting-Probleme Als Nesting (Einschachtelung) wird die verschnittminimale Anordnung beim Ausschneiden bezeichnet. Unter einem Nesting-Problem versteht man die Aufgabe, eine Menge von irregulär geformten ebenen Objekten (genannt Schablonen) auf eine Unterlage zu platzieren (bezeichnet als Schnittbild), sodass der Verschnitt minimal ist. Nesting-Optimierungen finden zum Beispiel Anwendungen in der textil- und metallverarbeitenden Industrie (s. Abb. 3.31).
|
||
|
||
3.6.5 Dreidimensionale C&P-Probleme
|
||
Unter einem dreidimensionalen Packungsproblem versteht man die Aufgabe, kleinere Objekte (Kisten) in eine größere Einheit (Container, Palette, Ladungsraum, Behälter) so zu packen, dass ein vorgegebenes Ziel erreicht wird. Dreidimensionale Packungsoptimierungen finden in der Logistik Anwendung bei der Beladung von Lastkraftwagen, Schiffen oder Flugzeugen. In der Praxis kommen vorwiegend Beladungen mit quaderförmigen Objekten vor. Dabei können u. a.
|
||
|
||
Abb. 3.31 Anwendung der Nesting-Optimierung auf textile Schnittmuster
|
||
|
||
50 Knapsackbeladung
|
||
|
||
3 Kombinatorische Optimierungsprobleme Strip Packing-Beladung Bin Packing-Beladung
|
||
|
||
300 € 350 € 200 €
|
||
700 € 500 €
|
||
|
||
50 € 100 €
|
||
|
||
Abb. 3.32 Knapsackbeladung: Maximierung des Gesamtwertes. Strip-Packing-Beladung: Minimierung der Ladungstiefe. Bin-Packing-Beladung: Minimierung der erforderlichen Container
|
||
|
||
folgende Optimierungskriterien zugrunde gelegt werden: Minimierung der Anzahl der größeren Einheiten, Minimierung des Ladevolumens, Maximierung des Gesamtwertes der eingepackten Güter. Entsprechend der Zielsetzung können die Beladungsprobleme wie folgt klassifiziert werden:
|
||
• Knapsackbeladungsproblem Bei der Knapsackbeladung besitzt jede Kiste einen Wert. Das Knapsackproblem (Rucksackproblem) besteht darin, eine Teilmenge der Kisten, die in einen einzelnen Container passt, so zu wählen, dass der Gesamtwert maximal ist. Ist der Wert der Kisten die Volumengröße, so ist die Auswahl so zu treffen, dass der Leerraum minimal ist.
|
||
• Strip Packing-Beladungsproblem Bei dieser Beladung sollen alle Kisten in einen Container mit unendlicher Länge gepackt werden. Das Optimierungsproblem besteht darin, die Tiefe der Ladung zu minimieren.
|
||
• Bin Packing-Beladungsproblem Bei dieser Beladungsvariante sollen alle Kisten in möglichst wenige identische Container verladen werden.
|
||
Abb. 3.32 illustriert die unterschiedlichen Beladungsprobleme.
|
||
Eine differenzierte Typisierung der Beladungsproblemen, die sich in der Fachliteratur etabliert hat, findet sich bei Dyckhoff [1].
|
||
|
||
Literatur
|
||
1. Dykhoff H (1990) A topology of cutting and packing problem. Eur J Oper Res 44:145–159
|
||
|
||
Kapitel 4
|
||
Lineare Optimierungsprobleme
|
||
|
||
Die lineare Optimierung wird in vielen verschiedenen Bereichen eingesetzt. Sie wird dort angewendet, wo eine lineare Funktion zu minimieren bzw. maximieren ist unter Einhaltung von Nebenbedingungen. In der Fachliteratur wird die lineare Optimierung oft auch unter dem Begriff lineare Programmierung oder Operations Research geführt. Methoden zur Lösung von linearen Optimierungsproblemen wurden erstmalig im Zweiten Weltkrieg entwickelt und von den Alliierten auf Transportprobleme angewendet. Mit der Simplexmethode, die von G. B. Dantzig 1947 entwickelt wurde, finden lineare Optimierungen breite Anwendung in vielen Bereichen von Industrie und Wirtschaft. In diesem Kapitel wird das lineare Optimierungsproblem mathematisch formuliert, wobei je nach Suchraum zwischen ganzzahligem, gemischt-ganzzahligem, binärem und gemischtbinärem linearem Optimierungsproblem unterschieden wird. Als Beispiel eines binären linearen Optimierungsproblems wird das Mengenüberdeckungsproblem betrachtet. Weiterhin werden Beispiele aus dem Bereich Produktions- und Transportplanung angegeben.
|
||
Methoden zur Lösung von linearen Optimierungsproblemen, insbesondere die Simplexmethode, werden im Kap. 8 beschrieben.
|
||
|
||
4.1 Einführungsbeispiel (Produktionsproblem)
|
||
|
||
Ein Futtermittelhersteller produziert Hunde- und Katzenfutter, die aus einer Mischung von Huhn, Lamm und Rind bestehen. Die Mischungsverhältnisse und die Verfügbarkeit der Zutaten sind in der folgenden Tabelle angegeben:
|
||
|
||
Huhn [kg] Rind [kg] Lamm [kg]
|
||
|
||
Verfügbarkeit Hundefutter Katzenfutter
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH,
|
||
|
||
51
|
||
|
||
ein Teil von Springer Nature 2023
|
||
|
||
R. Hollstein, Optimierungsmethoden, https://doi.org/10.1007/978-3-658-39855-2_4
|
||
|
||
52
|
||
|
||
4 Lineare Optimierungsprobleme
|
||
|
||
Der Gewinn für die Hundefutter-Packung beträgt 10 € und für die KatzenfutterPackung 7 €. Zu bestimmen ist die Anzahl der Hundefutter-Packungen x und die Anzahl der Katzenfutter-Packungen y, sodass der Gewinn maximal ist.
|
||
Der Produktionsplan kann wie folgt mathematisch formuliert werden:
|
||
Zielfunktion: f (x, y) = 10x + 7y → max
|
||
4x + 6y ≤ 1200 Nebenbedingungen: 7 x + 4y ≤ 2000
|
||
3x + 4y ≤ 800
|
||
|
||
4.2 Standardform eines linearen Optimierungsproblems
|
||
Bei einem linearen Optimierungsproblem sind die Zielfunktion und die Nebenbedingungen linear.
|
||
Eine Funktion f (x1, . . . , xn) heißt linear, wenn sie von der folgenden Form ist: f (x1, . . . , xn) = c1x1 + c2x2 + · · · + cnxn,
|
||
wobei c1, . . . , cn ∈ R Konstanten sind.
|
||
|
||
Graph der linearen Funktion ( , )=4 +2
|
||
|
||
Lineares Optimierungsproblem Unter einem linearen Optimierungsproblem versteht man die Aufgabe, eine lineare Zielfunktion
|
||
f (x1, . . . , xn) = c1x1 + · · · + cnxn
|
||
|
||
zu maximieren bzw. minimieren unter den Nebenbedingungen
|
||
|
||
ai1x1 + · · · + ainxn ≥ bi, i = 1, . . . , k
|
||
|
||
bj1x1 + · · · + bjnxn = dj, j = 1, . . . , l
|
||
|
||
xm ≥ 0,
|
||
|
||
m = 1, . . . , n
|
||
|
||
Ungleichungen ≤ können durch Vorzeichenwechsel in eine Ungleichung ≥ übergeführt werden.
|
||
|
||
4.3 Anwendungsbeispiel (Transportproblem)
|
||
|
||
53
|
||
|
||
4.3 Anwendungsbeispiel (Transportproblem)
|
||
|
||
Ein Produzent einer Ware mit den Produktionsstätten A1 und A2 erhält den Auftrag, Waren an drei Warenhäuser B1, B2 und B3 zu liefern. In der Fabrik A1 liegen 15 LKW-Ladungen und in A2 insgesamt 13 LKW-Ladungen der auszuliefernden Ware auf Lager. Die Nachfrage beträgt für das Warenhaus B1 12, für B2 7 und für B3 9 LKW-Ladungen. Die Kosten in Geldeinheiten (GE) pro LKW-Ladung für den Transport der Waren von den Produktionsstätten zu den Warenhäusern sind in der Abb. 4.1 angegeben.
|
||
Zu bestimmen ist ein Transportplan, für den die gesamten Transportkosten minimal sind.
|
||
Mit xik wird die Menge bezeichnet, die von Ai nach Bk transportiert werden soll. Das Transportproblem kann als lineares Optimierungsproblem wie folgt dargestellt werden:
|
||
Lineares Optimierungsproblem
|
||
Zielfunktion: f (x11, x12, x13, x21, x22, x23) = 5x11 + 3x12 + 4x13 + 2x21 + 4x22 + 6x23 → min
|
||
|
||
Nebenbedingungen:
|
||
|
||
x11
|
||
|
||
+
|
||
|
||
x21
|
||
|
||
=
|
||
|
||
12
|
||
|
||
|
||
|
||
x12 + x22 = 7 Nachfrage
|
||
|
||
x13 + x23 = 9
|
||
|
||
x11
|
||
|
||
+
|
||
|
||
x12
|
||
|
||
+
|
||
|
||
x13
|
||
|
||
≤
|
||
|
||
15
|
||
|
||
|
||
|
||
x12 + x22 + x23 ≤ 13 Angebot
|
||
|
||
xij ≥ 0
|
||
|
||
|
||
|
||
Angebot 1 2 3 [LKW]
|
||
|
||
1 [GE]
|
||
|
||
1
|
||
|
||
2 [GE]
|
||
Nachfrage [LKW]
|
||
|
||
1
|
||
5
|
||
2
|
||
4
|
||
|
||
4
|
||
3
|
||
6
|
||
|
||
Abb. 4.1 Darstellung des Transportproblems als gerichteten Graphen, deren Kantengewichte die Transportkosten in Geldeinheiten (GE) sind
|
||
|
||
54
|
||
|
||
4 Lineare Optimierungsprobleme
|
||
|
||
4.4 Ganzzahlige lineare Optimierungsprobleme
|
||
|
||
In vielen Anwendungen können die Variablen nur ganzzahlige Werte annehmen. Es macht zum Beispiel keinen Sinn, bei einer Einsatzplanung 9, 2 LKWs einzusetzen.
|
||
Ein lineares Optimierungsproblem mit der linearen Zielfunktion f (x1, . . . , xn) heißt ganzzahlig, gemischt-ganzzahlig, binär bzw. gemischt-binär, wenn für die Variablen x1, . . . , xn zusätzlich gilt:
|
||
|
||
Lineares Optimierungsproblem ganzzahlig
|
||
gemischt-ganzzahlig binär
|
||
gemischt-binär
|
||
|
||
Nebenbedingungen ,… ∈ ℤ ,… ∈ ℤ , ,…, ∈ ℝ , … ∈ {0,1} , … ∈ {0,1}, , … , ∈ ℝ
|
||
|
||
= Menge der nichtnegativen ganzen Zahlen = Menge der nichtnegativen reellen Zahlen
|
||
|
||
Beispiele von binären linearen Optimierungsproblemen
|
||
• Vehicle-Routing-Problem (VRP) Nach der mathematischen Beschreibung 3.4.2 des VRP ist die zu minimierende Zielfunktion (Gesamtstrecke) sowie die Nebenbedingungen in den Binärvariablen linear. Das VRP kann somit als binäres lineares Optimierungsproblem aufgefasst werden.
|
||
• Mengenüberdeckungsproblem Unter einem Mengenüberdeckungsproblem (Set Cover Problem) versteht man folgende Optimierungsaufgabe:
|
||
|
||
Mengenüberdeckungsproblem Zu einer Menge S und n Teilmengen Mi von S ist eine Überdeckung von S mit einer möglichst kleinen Anzahl der Teilmengen Mi zu bestimmen.
|
||
Beispiel Als Anwendung betrachten wir folgendes Beispiel:
|
||
In einem Bezirk, in dem sechs größere Orte sich befinden, sollen Polizeistationen errichtet werden, sodass von jedem Ort aus die Entfernung zu einer Station kleiner ist als 10 km. Zu bestimmen ist die kleinste Anzahl der erforderlichen Polizeistationen. Die Entfernungen der Orte untereinander sind in Abb. 4.2 angegeben.
|
||
Sei Mi für jedes i = 1, . . . , 6 die Menge aller Orte k, für die die Entfernung von dem Ort i zu dem Ort k kleiner ist als 10 km. Diese Mengen sind gegeben durch:
|
||
M1 = {1,3}, M2 = {2,4}, M3 = {1,3,6}, M4 = {2,4,5}, M5 = {4,5,6}, M6 = {3,5,6}
|
||
|
||
4.4 Ganzzahlige lineare Optimierungsprobleme
|
||
|
||
55
|
||
|
||
Abb. 4.2 Links: Entfernungstabelle, wobei die Entfernungen zwischen den Orten unter 10 grau markiert sind. Rechts: Eine zulässige Lösung mit drei Polizeistationen in den Orten 1, 2 und 6
|
||
|
||
Zu bestimmen ist die kleinste Anzahl dieser Mengen, die M = {1, . . . , 6} überdecken. Dieses Mengenüberdeckungsproblem kann als binäres lineares Optimierungsproblem interpretiert werden, indem man die folgenden Binärvariablen xi einführt:
|
||
|
||
xi =
|
||
|
||
1 Polizeistation wird im Ort i gebaut 0 sonst
|
||
|
||
Die Mengen Mi können als Ungleichungen in den Binärvariablen modelliert werden. Beispielsweise kann die Menge M4 = {2,4,5} durch die Ungleichung x2 + x4 + x5 ≥ 1 beschrieben werden. Ist die Ungleichung erfüllt, so ist xi = 1 für mindestens ein i ∈ M4 erfüllt, d. h. eine Polizeistation wird im Ort i gebaut. Damit liegen auch die restlichen Orte von M4 in der 10 km-Zone.
|
||
|
||
Das entsprechende binäre lineare Optimierungsproblem ist gegeben durch: Binäres lineares Optimierungsproblem
|
||
|
||
Zielfunktion: f (x1, . . . , x6) = x1 + x2 + x3 + x4 + x5 + x6 → min
|
||
|
||
Nebenbedingungen:
|
||
|
||
M1 : x1 + x3 ≥ 1 M2 : x2 + x4 ≥ 1 M3 : x1 + x3 + x6 ≥ 1 M4 : x2 + x4 + x5 ≥ 1 M5 : x4 + x5 + x6 ≥ 1 M6 : x3 + x5 + x6 ≥ 1
|
||
|
||
Eine minimale Lösung ist gegeben durch
|
||
|
||
x1∗, x2∗, x3∗, x4∗, x5∗, x6∗ = (0,0,1,1,0,0). Demnach sind nur Polizeistationen im Ort 3 und 4 erforderlich.
|
||
|
||
Kapitel 5
|
||
Multikriterielle Optimierungsprobleme
|
||
|
||
Man spricht von einem multikriteriellen Optimierungsproblem, wenn mehrere Zielfunktionen zu optimieren sind, wobei sie zueinander konkurrierend sein können.
|
||
Beispiel eines multikriteriellen Optimierungsproblems aus dem Bereich Produktionsplanung ist die Gewinnmaximierung bei gleichzeitiger Minimierung der Kosten. In diesem Kapitel wird das multikriterielle Optimierungsproblem an einem Beispiel aus dem Anwendungsbereich Transportplanung eingeführt.
|
||
Bei einem multikriteriellen Optimierungsproblem existiert im Allgemeinen keine eindeutig beste Lösung, deren Werte für alle zu optimierenden Funktionen optimal sind. Gesucht wird eine sogenannte Pareto-Menge aus dem Suchraum, deren Lösungen im gewissen Sinne gleich gut sind. Eine Lösung gehört zur Pareto-Menge und wird Pareto-optimal genannt, wenn es zu dieser Lösung keine Lösung gibt, die bessere Funktionswerte für alle Zielfunktionen besitzt. Das Konzept der Pareto-optimalen Lösungen wurde von dem italienischen Ingenieur Vilfredo Pareto Anfang des letzten Jahrhunderts eingeführt.
|
||
Die Bestimmung der Pareto-Menge mit klassischen Methoden werden im neunten Kapitel und mit naturanalogen Optimierungsmethoden im dritten Teil des Buches beschrieben.
|
||
|
||
5.1 Definitionen
|
||
Optimierungsprobleme, bei denen eine Zielfunktion optimiert werden soll, nennt man einkriteriell. Es gibt jedoch auch viele Probleme, in denen mehrere Zielfunktionen gleichzeitig zu optimieren sind. Solche Optimierungsaufgaben nennt man multikriterielles Optimierungsproblem (oder Mehrziel-Optimierungsproblem).
|
||
Ein Anwendungsbeispiel ist die optimale Motoreinstellung eines Verbrennungsmotors mit dem Ziel, den Kraftstoffverbrauch und Schadstoffausstoß zu minimieren sowie die Leistung zu maximieren. Diese Zielgrößen stehen in einer konkurrierenden Wechselbeziehung miteinander. Eine Steigerung des Drehmoments erhöht den Kraftstoffverbrauch und den Schadstoffausstoß, ein niedriger
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH,
|
||
|
||
57
|
||
|
||
ein Teil von Springer Nature 2023
|
||
|
||
R. Hollstein, Optimierungsmethoden, https://doi.org/10.1007/978-3-658-39855-2_5
|
||
|
||
58
|
||
|
||
5 Multikriterielle Optimierungsprobleme
|
||
|
||
Stellgrößen
|
||
Zündzeitpunkt Eingespritzte Treibstoffmenge
|
||
Einspritzzeitpunkt
|
||
|
||
Zielgrößen
|
||
|
||
1
|
||
|
||
Kraftstoffverbrauch
|
||
|
||
2
|
||
|
||
Drehmoment
|
||
|
||
3
|
||
|
||
Schadstoffausstoß
|
||
|
||
Abb. 5.1 Optimierung der Motoreinstellung, modelliert als multikriterielles Optimierungsproblem (Auswahl von Stell- und Zielgrößen)
|
||
|
||
Kraftstoffverbrauch wiederum verringert das Drehmoment. Die Optimierung erfolgt dynamisch in Abhängigkeit vom Betriebszustand des Motors (s. Abb. 5.1).
|
||
|
||
5.2 Multikriterielles Optimierungsproblem in der Grundversion
|
||
Ein multikriterielles Optimierungsproblem kann allgemein wie folgt formuliert werden (s. Abb. 5.2):
|
||
Multikriterielles Optimierungsproblem Sei S ⊂ Rn eine nichtleere Teilmenge und fi : S → R, i = 1, . . . , m, gegebene Zielfunktionen. Ein multikriterielles Optimierungsproblem ist gegeben durch:
|
||
Minimiere/Maximiere: fi(x), i = 1, . . . , m, unter der Nebenbedingung x ∈ M
|
||
Der zulässige Bereich M kann beschrieben werden durch Ungleichungsrestriktionen g(x) ≥ 0 und Gleichheitsrestriktionen h(x) = 0.
|
||
|
||
Suchraum
|
||
0
|
||
|
||
2( )
|
||
|
||
Zielfunktionsraum
|
||
|
||
( 1( 0), 2( 0))
|
||
|
||
Abb. 5.2 Multikriterielles Optimierungsproblem mit den zwei Zielfunktionen f1, f2 im Suchraum S
|
||
|
||
5.3 Einführendes Beispiel
|
||
|
||
59
|
||
|
||
5.3 Einführendes Beispiel
|
||
|
||
Ein Mitarbeiter einer Reederei hat die logistische Aufgabe, den Seetransport von Frachtgütern mittels eines Containerschiffs zu einem bestimmten Zeitpunkt zu organisieren. Das zur Verfügung stehende Containerschiff hat eine maximale Frachtkapazität von 1000 TEU. (Unter einem TEU versteht man einen StandardContainer von einer Länge von 20 Fuß.) Dem Mitarbeiter liegen 8 Angebote vor. In der folgenden Tabelle sind in der 2. Zeile für jedes Angebot die erforderlichen Kapazitäten und darunter der Gewinn in Währungseinheiten (WE) eingetragen. Aufgrund der beschränkten Kapazität von 1000 TEU können nicht alle Angebote angenommen werden. Weiterhin soll die Anzahl der Container minimiert werden, um Lade- und Löschzeiten, Löschkosten und Treibstoffverbrauch niedrig zu halten oder um Restkapazitäten für den Transport anderer Waren zu schaffen. Es stellt sich das Optimierungsproblem, die Angebote auszuwählen, die einen maximalen Gewinn bei minimaler Anzahl von Containern erzielen.
|
||
|
||
Angebot Nr. Anzahl Container Gewinn (WE)
|
||
|
||
12345678 202 142 89 105 222 78 129 256 344 183 125 201 151 136 78 46
|
||
|
||
Eine Auswahl der Angebote 1, . . . , 8 wird codiert durch den Binärvektor x = (x1, x2, . . . , x8), wobei xi gleich 1 gesetzt wird, wenn das Angebot i ausgewählt wird und 0 im anderen Fall. Mit Gi wird der Gewinn und mit Ci die Anzahl der erforderlichen Container für den Auftrag i bezeichnet. Es liegt folgendes multikriterielles Optimierungsproblem vor, wobei die Containeranzahl f1(x) zu minimieren und der Gewinn f2(x) zu maximieren ist.
|
||
|
||
Suchraum: M = {x = (x1, x2, . . . , x8) : xi ∈ {0, 1}, i = 1, . . . , 8}
|
||
|
||
Minimiere: f1(x) =
|
||
|
||
8 i=1
|
||
|
||
xi
|
||
|
||
·
|
||
|
||
Ci
|
||
|
||
Maximiere: f2(x) =
|
||
|
||
8 i=1
|
||
|
||
xi
|
||
|
||
·
|
||
|
||
Gi
|
||
|
||
Nebenbedingung: g (x) = f1(x) ≤ 1.000
|
||
|
||
Die zu minimierende Zielfunktion „Containeranzahl“ und die zu maximierende Zielfunktion „Gewinn“ stehen in einer konkurrierenden Wechselbeziehung. Vermindert man die Anzahl der Container, so vermindert sich der Gewinn, umgekehrt bei höherem Gewinn erhöht sich die Anzahl der Container. Für die in der unteren Tabelle ausgewählten Kombinationen können die Funktionswerte graphisch in einem Gewinn-Container-Diagramm dargestellt werden.
|
||
|
||
60
|
||
|
||
5 Multikriterielle Optimierungsprobleme
|
||
|
||
Gewinn (max) Gewinn (max)
|
||
|
||
800
|
||
|
||
nicht-dominiert
|
||
|
||
600 400 200
|
||
0 200
|
||
|
||
1 2 3
|
||
|
||
4
|
||
|
||
6
|
||
|
||
5
|
||
|
||
400
|
||
|
||
600
|
||
|
||
Container (min)
|
||
|
||
dominierter Bereich von
|
||
|
||
800 600 400 200
|
||
0 200
|
||
|
||
nicht-dominiert
|
||
|
||
7
|
||
|
||
1
|
||
|
||
4
|
||
|
||
6
|
||
|
||
2 5
|
||
3
|
||
|
||
400
|
||
|
||
600
|
||
|
||
Container (min)
|
||
|
||
dominierter Bereich von
|
||
|
||
Abb. 5.3 Punkte innerhalb der Rechtecke werden von a1 bzw. a7 dominiert
|
||
|
||
Für jede Teilmenge x(i) von Angeboten kann man entsprechend der Containerzahl und des Gewinns den Punkt
|
||
ai = f1 x(i) , f2 x(i)
|
||
in dieses Gewinn-Container-Diagramm einzeichnen. Im linken Diagramm der Abb. 5.3 sind die Datenpunkte a1, . . . , a6 eingetragen. Optimal ist der weit oben und weit links liegende Punkt a1, da er im Vergleich zu den restlichen Punkten den größten Gewinn und die kleinste Containeranzahl aufweist. Alle restlichen Datenpunkte, die rechts unterhalb von a1 bzw. in dem Rechteck mit dem linken oberen Eckpunkt a1 liegen, sind schlechter als a1. Dieses Rechteck nennt man dominierter Bereich von a1 und die im dominierten Bereich liegenden Punkte werden von a1 dominiert genannt. Fügt man den Datenpunkt a7 hinzu, der außerhalb des dominierten Bereichs zu a1 liegt, so dominiert a7 die Punkte, die innerhalb des Rechtecks liegen, das a7 als linken oberen Eckpunkt besitzt. Die Punkte a1 und a7 nennt man nicht-dominiert. Beide Punkte sind nicht vergleichbar, da jeder der beiden Lösungen in jeweils einem Funktionswert der anderen überlegen ist.
|
||
Betrachtet man alle Datenpunkte, so ergibt sich eine Datenwolke, die in der Abb. 5.4 dargestellt ist. Zu den schwarz berandeten Punkten gibt es keine anderen Punkte, die links oberhalb dieser Punkte liegen. Die restlichen Punkte können dagegen nicht optimal sein, da man einen besseren Punkt finden kann, der weiter oben und weiter links im Diagramm liegt. Die Menge der nicht-dominierten Punkte nennt man Pareto-Front und wird von den schwarz berandeten Punkten in Abb. 5.4 dargestellt.
|
||
|
||
5.4 Pareto-Dominanz
|
||
Im Folgenden betrachten wir multikriterielle Optimierungsprobleme mit zu minimierenden Zielfunktionen fi : M → R, i = 1, . . . , n, wobei M der Suchraum ist. Mit f (x) wird die Vektorfunktion f (x) = (f1(x), . . . , fn(x)) bezeichnet. Wir verwenden die abgekürzte Schreibweise
|
||
min {f1(x), . . . , fn(x)}.
|
||
x∈M
|
||
|
||
Gewinn (max)
|
||
|
||
5.4 Pareto-Dominanz
|
||
|
||
Pareto-Front
|
||
|
||
61 unzulässiger
|
||
Bereich
|
||
|
||
Container (min)
|
||
Abb. 5.4 Die Pareto-Front setzt sich aus den schwarz berandeten Punkten zusammen, die die Randpunkte dieser Datenwolke bilden. Datenpunkte mit einer Containeranzahl über 1000 sind nach Voraussetzung nicht zulässig.
|
||
Skalarfunktionen, die zu maximieren sind, können durch Multiplikation mit −1 ohne Änderung der Optimalpunkte in eine zu minimierende Funktion übergeführt werden.
|
||
Definitionen
|
||
• Pareto-optimal Eine zulässige Lösung x0 im Suchraum M heißt Paretooptimal, wenn es kein x ∈ M existiert mit f (x) ≤ f (x0), d. h. fi(x) ≤ fi(x0) für alle i = 1, . . . , n.
|
||
• Pareto-Menge Die Menge aller Pareto-optimalen Lösungen aus M heißt Pareto-Menge.
|
||
• Nicht-dominierter Punkt Für einen Pareto-optimalen Punkt x0 ∈ M heißt der Funktionsvektor f (x0) nicht-dominiert.
|
||
• Pareto-Front Für die Pareto-Menge P ⊂ M heißt die Menge
|
||
{f (x) = (f1(x), . . . , fn(x)) : x ∈ P}
|
||
Pareto-Front. • Dominierter Punkt Gilt f x′ ≤ f x′′ für zwei Punkte x′, x′′ ∈ M, so sagt
|
||
man, dass x′ den Punkt x′′ im Suchraum und f x′ den Funktionswert f x′′ im Zielraum dominiert.
|
||
Eine Pareto-Menge besteht aus Lösungen, die in gewissem Sinne gleich gut sind, sodass der Optimierer aufgrund weiterer Überlegungen sich für einen Paretooptimalen Punkt entscheiden muss.
|
||
Das Konzept der Pareto-Dominanz geht auf den italienischen Ingenieur und Ökonomen Vilfredo Pareto (1848–1923) zurück.
|
||
Abb. 5.5 zeigt, dass die Lage der Pareto-Front davon abhängt, ob die Zielfunktionen minimiert oder maximiert werden.
|
||
Beispiel Gegeben sei
|
||
M = x = (x1, x2) ∈ R2 : (x1 − 1)2 + (x2 − 1)2 ≤ 1, 0 ≤ x1, x2 ≤ 1
|
||
|
||
62
|
||
|
||
5 Multikriterielle Optimierungsprobleme
|
||
|
||
P
|
||
|
||
P
|
||
|
||
2 (min) 2 (max) 2 (min) 2 (max)
|
||
|
||
P
|
||
1 (min)
|
||
Pareto-Front
|
||
|
||
1 (min)
|
||
dominierter Bereich von P
|
||
|
||
P
|
||
1 (max)
|
||
|
||
1 (max)
|
||
Wertebereich
|
||
|
||
Abb. 5.5 Die Lage der Pareto-Front hängt davon ab, ob die Funktionen maximiert oder minimiert werden.
|
||
|
||
2( )(min)
|
||
|
||
Suchraum
|
||
2
|
||
|
||
1.5
|
||
|
||
1
|
||
|
||
′M
|
||
|
||
Pareto-Menge
|
||
|
||
Pareto-Front ( ′)
|
||
|
||
dominierter Bereich von ( ′ )
|
||
Bildmenge ()
|
||
|
||
Abb. 5.6 Die Pareto-Menge und die Pareto-Front der Vektorfunktion f ist gegeben durch den Viertelkreis. Die Punkte, die von f x′ dominiert werden, liegen in dem Rechteck, dessen linker unterer Eckpunkt f x′ ist
|
||
eine Viertelkreisscheibe im R2 und f (x) = (f1(x), f2(x)) eine Vektorfunktion, definiert durch
|
||
f1(x1, x2) = x1 + 1 und f2(x1, x2) = x2 + 0.5, x = (x1, x2) ∈ M. Die Vektorfunktion f bewirkt eine Verschiebung des Suchraumes M in Richtung des Vektors (1, 0.5). Die Pareto-Menge und die Pareto-Front zu f ist in Abb. 5.6 dargestellt.
|
||
|
||
Teil II
|
||
Klassische Optimierungsmethoden
|
||
|
||
Kapitel 6
|
||
Analytische Methoden
|
||
In diesem Kapitel werden Verfahren zur Optimierung von kontinuierlichen Funktionen mit den Methoden der Analysis vorgestellt. Die klassische Methode für die Extremwertbestimmung einer differenzierbaren Funktion mit einer Variablen ist die Berechnung der Nullstellen der Ableitungsfunktion. Weiterhin wird eine analytische Methode für Funktionen mit zwei Variablen beschrieben. Für die Optimierung von Funktionen mit mehreren Variablen unter Nebenbedingungen findet die Lagrange-Methode breite Anwendung. Mithilfe des Gradienten, angewendet auf die Lagrange Funktion, erhält man ein Gleichungssystem, dessen Lösungen Kandidaten für Extremstellen der zu optimierenden Funktion sind. Der Gradient ist ein Vektor, dessen Komponenten aus den partiellen Ableitungen einer Funktion besteht. Numerisch können die Extremstellen von Funktionen mit dem Gradientenverfahren bestimmt werden, indem man in der Nähe einer lokalen Extremstelle startet und in Richtung des positiven bzw. negativen Gradienten fortschreitet, bis keine Verbesserung des Zielwertes erzielt wird. Bei der Suche nach einem lokalen Maximum ist die Fortschreitungsrichtung der positive Gradient und im Fall des Minimums der negative Gradient. Das Gradientenverfahren kommt in vielen Verfahren des maschinellen Lernens zur Anwendung, die im letzten Teil des Buches näher beschrieben werden.
|
||
|
||
© Der/die Autor(en), exklusiv lizenziert an Springer Fachmedien Wiesbaden GmbH,
|
||
|
||
65
|
||
|
||
ein Teil von Springer Nature 2023
|
||
|
||
R. Hollstein, Optimierungsmethoden, https://doi.org/10.1007/978-3-658-39855-2_6
|
||
|
||
66
|
||
6.1 Grundbegriffe der Analysis
|
||
|
||
6 Analytische Methoden
|
||
|
||
6.1.1 Definitionen
|
||
• Norm in Rn Die Norm (Euklidische Norm) x von x = (x1, . . . , xn) ∈ Rn ist definiert durch
|
||
<EFBFBD>x<EFBFBD> = x12 + · · · + xn2. • δ-Umgebung Für eine Zahl δ > 0 heißt die Menge Uδ aller x ∈ Rn mit
|
||
<EFBFBD>x − a<> < δ δ-Umgebung von a.
|
||
2
|
||
-Umgebung von
|
||
|
||
1
|
||
|
||
• Konvergenz einer Folge
|
||
Eine Folge (xn) in Rn konvergiert gegen a ∈ Rn, wenn zu jedem ε > 0 ein n0 ∈ N existiert mit
|
||
|
||
<EFBFBD>xn − a<> < ε fur alle n ≥ n0.
|
||
|
||
Schreibweise: lim
|
||
n→∞
|
||
|
||
xn
|
||
|
||
=
|
||
|
||
a.
|
||
|
||
Beispiel: Es gilt für die Folge xn =
|
||
|
||
1,
|
||
|
||
1 n
|
||
|
||
in R2: lim
|
||
n→∞
|
||
|
||
xn
|
||
|
||
=
|
||
|
||
(1,0).
|
||
|
||
Denn zu einem ε
|
||
|
||
> 0 gibt es ein n0
|
||
|
||
∈
|
||
|
||
N
|
||
|
||
mit
|
||
|
||
1 n0
|
||
|
||
< ε, sodass für alle n ≥ n0 gilt:
|
||
|
||
1
|
||
|
||
111
|
||
|
||
<EFBFBD>xn − (1, 0)<29> =
|
||
|
||
0, n
|
||
|
||
= n2 = n ≤ n0 < ε.
|
||
|
||
• Stetigkeit einer Funktion
|
||
|
||
Eine auf S ⊆ Rn definierte Funktion f : S → R heißt stetig in x0, wenn für jede (!) Folge (xn) in S mit lim xn = x0 gilt
|
||
n→∞
|
||
|
||
lim f (xn) = f (x0).
|
||
n→∞
|
||
|
||
6.2 Der Satz vom Maximum und Minimum
|
||
|
||
67
|
||
|
||
Eine Funktion heißt stetig in S, wenn sie in jedem Punkt x ∈ S stetig ist.
|
||
Eine Funktion f :[a,b] → R ist stetig, wenn f im Intervall [a,b] keine Sprungstellen besitzt, d. h. der Graph von f kann mit einem Stift ohne Absetzen gezeichnet werden.
|
||
• Kompakte Teilmenge in Rn
|
||
– Eine Teilmenge S ⊂ Rn heißt beschränkt, wenn es für jedes 1 ≤ i ≤ n untere und obere Schranken mi und Mi existieren mit mi ≤ xi ≤ Mi für alle x = (x1, . . . , xn) ∈ S.
|
||
– Eine Teilmenge S ⊂ Rn heißt abgeschlossen, wenn alle Randpunkte von S zu S gehören. Ein Punkt x0 ∈ Rn heißt Randpunkt von S, wenn in jeder δ -Umgebung von x0 Punkte in S und im Komplement Rn\S liegen.
|
||
– Eine abgeschlossene und beschränkte Teilmenge S ⊂ Rn heißt kompakt.
|
||
|
||
6.2 Der Satz vom Maximum und Minimum
|
||
Die Frage, wann eine kontinuierliche Funktion f : S → R in S ⊂ Rn ein Maximum und Minimum besitzt, beantwortet der folgende Hauptsatz der Mathematik:
|
||
Der Satz vom Maximum und Minimum (Satz von Weierstraß) Jede Funktion f : S → R, die stetig auf einer kompakten Menge S ⊂ Rn ist, ist in S beschränkt und nimmt dort ein Maximum und ein Minimum an.
|
||
Dieser Satz ist eine Existenzaussage und liefert nicht die Extremstellen. Die folgenden Funktionen, die jeweils eine der drei Voraussetzungen des Satzes
|
||
vom Maximum nicht erfüllen, besitzen kein Maximum in ihren Definitionsbereichen (s. Abb. 6.1).
|
||
|
||
y
|
||
|
||
y
|
||
|
||
2
|
||
|
||
ℎ( )
|
||
|
||
()
|
||
|
||
()
|
||
|
||
1
|
||
|
||
x
|
||
|
||
0
|
||
|
||
1
|
||
|
||
2
|
||
|
||
3x
|
||
|
||
Abb. 6.1 ① f (x) ist im beschränkten, aber nicht abgeschlossenen Intervall (0,1] stetig, besitzt jedoch dort kein Maximum. ② Die in dem abgeschlossenen unbeschränkten Intervall [0,∞) stetige Funktion g(x) besitzt ebenfalls kein Maximum. ③ Die im Punkt 2 unstetige Funktion h(x) hat im abgeschlossenen, beschränkten Intervall [0,3] kein Maximum, da es zu jedem x ∈ [0,3] ein x′ ∈ [0,3] gibt mit h(x) < h x′ .
|
||
|
||
68
|
||
|
||
•
|
||
|
||
f
|
||
|
||
:
|
||
|
||
(0,1]
|
||
|
||
→
|
||
|
||
R, f (x)
|
||
|
||
=
|
||
|
||
1 x
|
||
|
||
• g : [0,∞) → R, g(x) = x2
|
||
|
||
• h : [0,3] → R, h(x) =
|
||
|
||
x, x ∈ [0,2) 1, x ∈ [2,3]
|
||
|
||
6 Analytische Methoden
|
||
|
||
6.3 Ableitung einer Funktion 6.3.1 Sekanten- und Tangentensteigung
|
||
Gegeben sei die Funktion f (x) = x2.
|
||
|
||
() ( )= 2
|
||
|
||
Sekante Tangente
|
||
|
||
Sekantendreieck ( ) − ( 0)
|
||
|
||
( 0)
|
||
|
||
0
|
||
−0
|
||
|
||
Sekantensteigung Die Steigung mS(x0) der Sekante zwischen den Kurvenpunkten (x0, f (x0)) und (x, f (x)) ist gegeben durch den sogenannten Differenzenquotienten
|
||
|
||
mS (x0 )
|
||
|
||
=
|
||
|
||
f (x) − x−
|
||
|
||
f (x0) . x0
|
||
|
||
Tangentensteigung Lässt man x gegen x0 gehen, so geht die Sekante über in die Tangente und man erhält die Tangentensteigung mT (x0) im Kurvenpunkt (x0, f (x0)) durch
|
||
|
||
mT (x0)
|
||
|
||
=
|
||
|
||
lim
|
||
x→xo
|
||
|
||
f
|
||
|
||
(x) x
|
||
|
||
− −
|
||
|
||
f (x0) . x0
|
||
|
||
Für die Funktion f (x) = x2 ergibt sich folgende Tangentensteigung:
|
||
|
||
mT (x0)
|
||
|
||
=
|
||
|
||
lim
|
||
x→xo
|
||
|
||
f
|
||
|
||
(x) x
|
||
|
||
− −
|
||
|
||
f (x0) x0
|
||
|
||
= lim
|
||
x→xo
|
||
|
||
x2 − x02 x − x0
|
||
|
||
= lim
|
||
x→xo
|
||
|
||
(x − x0) · (x + x0) x − x0
|
||
|
||
= lim (x + x0)
|
||
x→xo
|
||
|
||
= 2x0.
|
||
|
||
6.3 Ableitung einer Funktion
|
||
|
||
69
|
||
|
||
Ist beispielsweise x0 = 3, so ist die Steigung der Tangente im Kurvenpunkt (3,9) gleich 6.
|
||
|
||
6.3.2 Ableitung einer Funktion
|
||
|
||
Die Ableitung einer Funktion f (x) im Punkt x0 gibt die Steigung der Funktionskurve im Kurvenpunkt (x0, f (x0)) an. Sie ist als Steigung der Tangente an die Kurve in diesem Punkt definiert.
|
||
|
||
Eine Funktion f (x) heißt an einer Stelle x0 differenzierbar, wenn der Grenzwert
|
||
|
||
lim
|
||
x→xo
|
||
|
||
f (x) − f (x0) x − x0
|
||
|
||
=
|
||
|
||
f ′(x0)
|
||
|
||
existiert. Dieser Grenzwert f ′(x0) heißt die Ableitung von f an der Stelle x0.
|
||
|
||
Eine Funktion f (x) heißt in D differenzierbar, wenn f in jedem Punkt x ∈ D differenzierbar ist. Die Funktion f ′(x) mit x ∈ D heißt die Ableitung von f (x).
|
||
|
||
f (x) heißt in D stetig differenzierbar, wenn f (x) in D differenzierbar ist und die Ableitung f ′(x) in D stetig ist.
|
||
Ableitung höherer Ordnung Ist f ′ in D ebenfalls differenzierbar, so kann die Ableitung von f ′ gebildet werden und man erhält die zweite Ableitung f ′′(x) von f (x). Entsprechend sind Ableitungen höherer Ordnung bildbar.
|
||
|
||
6.3.3 Beispiele von Ableitungen und Ableitungsregeln
|
||
|
||
Ableitungen einiger elementarer Funktionen in ihren Definitionsbereichen
|
||
|
||
( ) , ∈ℝ
|
||
|
||
′( )
|
||
|
||
( −1)
|
||
|
||
ln( ) sin( ) cos 1 cos( ) − sin( )
|
||
|
||
Die Ableitung weiterer elementarer Funktionen, sowie Funktionen, die sich aus elementaren Funktionen zusammensetzen, können mithilfe der folgenden Ableitungsregeln hergeleitet werden.
|
||
|
||
70
|
||
Ableitungsregeln
|
||
Summenregel: Faktorregel: Produktregel: Quotientenregel: Kettenregel:
|
||
|
||
() () ()
|
||
=
|
||
()
|
||
|
||
6 Analytische Methoden
|
||
()
|
||
|
||
Beispiel:
|
||
|
||
x5ex
|
||
|
||
′
|
||
=
|
||
|
||
x5 ′ex + x5(ex)′ = 5x4ex + x5ex.
|
||
|
||
6.4 Extremwertbestimmung für Funktionen mit einer Variablen
|
||
Kandidaten für lokale Extremwerte sind solche Punkte x0, in denen die Ableitung gleich null ist. An einem Extremum verläuft die Tangente waagrecht. Diese Bedingung ist notwendig, aber nicht hinreichend, da in Sattelpunkten die Tangenten ebenfalls waagrecht verlaufen. Eine Funktion f (x) hat in x0 einen Sattelpunkt, wenn die Ableitung f ′(x) in x0 ein lokales Extremum besitzt mit f ′(x0) = 0 (s. Abb. 6.2).
|
||
Es gelten die folgenden Kriterien für Extrema von differenzierbaren Funktionen mit einer Variablen.
|
||
|
||
Notwendige Bedingung für ein Extremum von f : [a, b] → R in x0 ∈ (a, b) : f ′(x0) = 0
|
||
Hinreichende Bedingung für ein Extremum von f : [a, b] → R in x0 ∈ (a, b)
|
||
|
||
′ ( 0) = 0 und ′′ ( 0) ≠ 0
|
||
|
||
′′ ( 0) > 0
|
||
|
||
′′ ( 0) < 0
|
||
|
||
besitzt in 0 ein lokales Minimum
|
||
|
||
besitzt in 0 ein lokales Maximum
|
||
|
||
Gilt f ′(x0) = f ′′(x0) = 0, so müssen höhere Ableitungen untersucht werden, bis erstmals für eine Ableitung f (n)(x0) = 0 gilt. Ist f (n)(x0) < 0 (bzw. f (n)(x0) > 0),
|
||
so liegt an der Stelle x0 ein lokales Maximum (bzw. lokales Minimum) vor, wenn
|
||
|
||
6.4 Extremwertbestimmung für Funktionen mit einer Variablen
|
||
|
||
71
|
||
|
||
( ) Maximalstelle ′( 1) = 0
|
||
|
||
Minimalstelle
|
||
|
||
′( 2) = 0
|
||
|
||
Sattelpunkt ′( 3) = 0
|
||
|
||
′( ) 1
|
||
|
||
2
|
||
|
||
3
|
||
|
||
′′ ( 1) < 0
|
||
|
||
′′ ( 2) > 0
|
||
|
||
Minimalstelle
|
||
|
||
Abb. 6.2 Maximalstelle: Ein virtueller Wanderer auf der Wertelandschaft geht zunächst bergauf, d. h. die Steigung f ′(x) ist positiv. Am Ende des Aufstiegs erreicht er die Maximalstelle in
|
||
x1, an der die Steigung null ist und die Tangente waagrecht verläuft. Beim Weiterlaufen geht er bergab und die Ableitung f ′ wird negativ. Da f ′ monoton fallend ist, ist die Steigung von f ′ bzw. die zweite Ableitung f ′′ in der Umgebung von x1 negativ. Minimalstelle: Umgekehrt ist f ′ in der Umgebung der Minimalstelle x2 monoton steigend, d. h. f ′′ ist dort positiv. Sattelpunkt: In einem Sattelpunkt hat die Ableitung f ′ in x3 eine Extremstelle (hier Minimalstelle)
|
||
|
||
n gerade ist. Ist f (n)(x0) = 0 für ein ungerades n, so besitzt f (x) in x0 einen Sattelpunkt.
|
||
Bei der analytischen Methode wird das Optimierungsproblem in ein Nullstellenproblem übergeführt:
|
||
|
||
Optimierungsproblem
|
||
|
||
Nullstellenproblem
|
||
|
||
Zur Bestimmung der Nullstellen von f ′ existieren verschiedene numerische Verfahren wie zum Beispiel das Newton-, Regula Falsi- oder das Sekantenverfahren, mit denen man iterativ die Nullstellen mit beliebiger Genauigkeit berechnen kann, sofern Konvergenz vorliegt. In manchen Fällen können die Nullstellen auch direkt berechnet werden.
|
||
|
||
Beispiel: Aus f ′(x) = e3x − 2 = 0 folgt e3x = 2, 3x = ln e3x = ln 2 und damit
|
||
|
||
x
|
||
|
||
=
|
||
|
||
1 3
|
||
|
||
ln 2.
|
||
|
||
Anwendungsbeispiel Ein Händler verkauft in einem Zeitraum 200 Artikel eines Produkts X mit einem Gewinn von 30 € je Artikel bei einem Verkaufspreis von 300 €. Nach Marktanalysen können bei einer Preisreduktion von einem Euro insgesamt 10 Artikel X mehr verkauft werden. Gesucht ist der optimale Verkaufspreis.
|
||
|
||
72
|
||
|
||
6 Analytische Methoden
|
||
|
||
Lösung: Der zu maximierende Gesamtgewinn f (x) bei einer Preisreduzierung x ist gegeben durch.
|
||
Anzahl Artikel X Gewinn
|
||
f (x) = (200 + 10x) · (30 − x) = 6.000 − 200x + 300x − 10x2 = −10x2 + 100x + 6.000.
|
||
Durch Nullsetzen der ersten Ableitung erhält man
|
||
f ′(x) = −20x + 100 = 0. Hieraus ergibt sich die Lösung x0 = 5. Wegen f ′′ = −20 < 0 ist x0 eine Maximalstelle. Der optimale Verkaufspreis des Artikels X ist somit 295 €.
|
||
|
||
6.5 Extremwertbestimmung für Funktionen mit zwei Variablen
|
||
|
||
6.5.1 Partielle Ableitungen
|
||
|
||
Sei f (x,y) eine Funktion von x und y.
|
||
|
||
Partielle Ableitung von f nach x: f (x,y) heißt in (x0,y0) partiell nach x differenzierbar, wenn der folgende Grenzwert existiert:
|
||
|
||
fx(x0, y0)
|
||
|
||
=
|
||
|
||
lim
|
||
x→x0
|
||
|
||
f
|
||
|
||
(x, y0) x
|
||
|
||
− −
|
||
|
||
f (x0, x0
|
||
|
||
y0)
|
||
|
||
Partielle Ableitung von f nach y: f (x, y) heißt in (x0, y0) partiell nach y differenzierbar, wenn der folgende Grenzwert existiert:
|
||
|
||
fy(x0,
|
||
|
||
y0)
|
||
|
||
=
|
||
|
||
lim
|
||
y→y0
|
||
|
||
f
|
||
|
||
(x0, y) y
|
||
|
||
− −
|
||
|
||
f (x0, y0) . y0
|
||
|
||
Bildet man die partiellen Ableitungen in den variablen Punkten (x,y), so erhält man die Funktionen fx(x, y) und fy(x,y).
|
||
|
||
Alternative
|
||
|
||
Schreibweise:
|
||
|
||
fx
|
||
|
||
=
|
||
|
||
∂f ∂x
|
||
|
||
und
|
||
|
||
fy
|
||
|
||
=
|
||
|
||
∂f ∂y
|
||
|
||
.
|
||
|
||
Partielle Ableitungen höherer Ordnung Die Funktionen fx(x,y) und fy(x,y) können nochmals nach x und y abgeleitet werden, sofern sie partiell differenzierbar sind. Man erhält die partiellen Ableitungen zweiter Ordnung: fxx(x,y), fxy(x,y), fyx(x,y) und fyy(x,y).
|
||
|
||
6.5 Extremwertbestimmung für Funktionen mit zwei Variablen
|
||
|
||
73
|
||
|
||
Beispiel Bei der Berechnung der partiellen Ableitung nach einer Variablen kann die andere Variable als Konstante aufgefasst werden.
|
||
Für f (x,y) = 1 − x2 − y2 gilt:
|
||
fx(x,y) = −2x, fy(x,y) = −2y,
|
||
fxx(x,y) = −2, fxy(x,y) = 0, fyx(x,y) = 0 und fyy(x,y) = −2.
|
||
Geometrische Deutung Die Funktion z = f (x,y) beschreibt eine Fläche im Raum. P sei der Flächenpunkt (x0, y0, f (x0, y0)) (s. Abb. 6.3).
|
||
• Hält man y0 fest, so entsteht eine Funktion f (x,y0) mit der einzigen Variablen x. Der Graph dieser Funktion ist eine Flächenkurve, die man erhält, wenn man die Fläche mit der zur xz-Ebene parallelen Ebene y = y0 schneidet. Die partielle Ableitung fx(x0, y0) ist die Steigung der Tangente an dieser Schnittkurve im Punkt P.
|
||
• Bei festgehaltenem x0 beschreibt die Funktion f (x0,y) die Schnittkurve, die entsteht, wenn man die Fläche mit der zur yz−Ebene parallelen Ebene x = x0 schneidet. Die Steigung der Tangente an dieser Schnittkurve in P ist fy(x0,y0).
|
||
|
||
6.5.2 Notwendige Bedingung für ein Extremum
|
||
Eine Fläche, die durch eine Funktion f (x,y) beschrieben wird, besitzt im Maximum- bzw. Minimumpunkt P = P(x0, y0, f (x0, y0)) eine waagrechte Tangentialebene. Jede in der Fläche liegende und durch P gehende Kurve hat dort ebenfalls ein Maximum- bzw. Minimumpunkt und somit eine waagrechte
|
||
|
||
Tangentensteigung ( 0, 0) Schnittkurve ( , 0)
|
||
|
||
Tangentensteigung ( 0, 0) Schnittkurve ( 0, )
|
||
|
||
Abb. 6.3 Geometrische Deutung der partiellen Ableitungen in (x0,y0)
|
||
|
||
74
|
||
|
||
6 Analytische Methoden
|
||
|
||
Tangente. Dies gilt insbesondere für die Flächenkurven in Richtung der x- bzw. yAchse. Somit sind die partiellen Ableitungen fx(x0, y0) und fy(x0, y0) gleich null. Damit gelten die folgenden notwendigen Bedingungen für das Vorhandensein eines Maximums bzw. Minimums in (x0, y0).
|
||
|
||
Notwendige Bedingung für ein Extremum von f (x, y) in (x0, y0) : fx(x0, y0) = 0 und fy(x0, y0) = 0
|
||
|
||
Ein Punkt (x0, y0) heißt stationärer Punkt von f (x,y), wenn die partiellen Ableitungen erster Ordnung in (x0, y0) null sind. Stationäre Punkte können Extremstellen, aber auch Sattelpunkte sein. Betrachtet man zum Beispiel die Funktion h(x,y) = y2 − x2, so sind die partiellen Ableitungen
|
||
hx(x,y) = −2x und hy(x,y) = 2y
|
||
im Nullpunkt null, d. h. (0,0) ist ein stationärer Punkt von h(x,y). Ein im Nullpunkt befindlicher Bergsteiger auf der Wertelandschaft von h(x,y) würde in Richtung der x-Achse bergab und in Richtung der y-Achse bergauf gehen. Somit liegt im Nullpunkt kein Extremalpunkt, sondern ein Sattelpunkt vor (s. Abb. 6.4).
|
||
Zur Bestimmung von hinreichenden Bedingungen für das Vorhandensein von Extremstellen betrachten wir zunächst folgendes Beispiel.
|
||
Beispiel Gegeben sei die Funktion
|
||
f (x,y) = x2 + y2 − 3xy .
|
||
|
||
( , )=− 2− 2
|
||
|
||
( , )= 2+ 2
|
||
|
||
ℎ( , = 2 − 2
|
||
Abb. 6.4 Horizontale Tangentialebene in einem Maximalpunkt, Minimalpunkt und in einem Sattelpunkt
|
||
|
||
6.5 Extremwertbestimmung für Funktionen mit zwei Variablen
|
||
|
||
75
|
||
|
||
Der Graph dieser Funktion ist unten abgebildet. Wir betrachten die drei Flächenkurven.
|
||
① f (x,0) = x2 ② f (0,y) = y2 und ③ f (x,x) = 2x2 − 3x2 = −x2,
|
||
|
||
die sich im Nullpunkt schneiden. Ein im Nullpunkt befindlicher virtueller Wanderer würde in Richtung der x- und y-Richtung bergauf und in Richtung der Winkelhalbierenden y = x bergab laufen. Somit liegt im Nullpunkt kein Extremum vor.
|
||
|
||
Für die partiellen Ableitungen 1. Ordnung im Nullpunkt gilt: fx(x, y) = 2x − 3y, fx(0, 0) = 0
|
||
fy(x, y) = 2y − 3x, fy(0, 0) = 0 Demnach ist der Nullpunkt ein stationärer Punkt von f . Aus
|
||
|
||
fxx(x,y) = 2 und fyy(x,y) = 2
|
||
folgt, dass fxx(0,0) und fyy(0,0) positiv sind. Offenbar genügt es nicht, zum Nachweis eines Extremums die Vorzeichen der partiellen Ableitungen fxx und fyy zu überprüfen.
|
||
Bei der Formulierung der hinreichenden Bedingungen muss auch das Verhalten der Funktion zwischen den Hauptachsen berücksichtigt werden. Dies führt zum Begriff der Hesse-Matrix, in der die gemischten Ableitungen fxy = fyx einbezogen werden.
|
||
Hesse-Matrix Die Hesse-Matrix ist definiert durch:
|
||
|
||
Hf (x0, y0) =
|
||
|
||
fxx(x0, y0) fxy(x0, y0) fxy(x0, y0) fyy(x0, y0)
|
||
|
||
Mit <20>(x0, y0) wird die Determinante von Hf (x0, y0) bezeichnet: <20>(x0, y0) = fxx(x0, y0) · fyy(x0, y0) − fx2y(x0, y0)
|
||
|
||
76
|
||
|
||
6 Analytische Methoden
|
||
|
||
6.5.3 Hinreichende Bedingung für lokale Extrema
|
||
|
||
Die Funktion f (x,y) habe in (x0, y0) stetige zweite partielle Ableitungen und (x0, y0) sei stationärer Punkt von f (x,y), d. h.
|
||
fx(x0, y0) = fy(x0, y0) = 0.
|
||
Dann gilt:
|
||
|
||
Δ( 0, 0) < 0
|
||
Sattelpunkt in ( 0, 0)
|
||
|
||
Δ( 0, 0) > 0
|
||
Extremum in ( 0, 0)
|
||
|
||
Δ( 0, 0) = 0 Keine allgemeine Aussage möglich
|
||
|
||
( 0, 0) < 0 ( 0, 0) ist Maximalstelle
|
||
|
||
( 0, 0) > 0 ( 0, 0) ist Minimalstelle
|
||
|
||
Aus <20>(x0, y0) = fxx(x0, y0) · fyy(x0, y0) − fx2y(x0, y0) > 0 und fxx(x0, y0) > 0 folgt auch fyy(x0, y0) > 0. Ebenso ist fyy(x0, y0) < 0, wenn <20>(x0, y0) > 0 und fxx(x0, y0) < 0 gilt.
|
||
Im Fall <20>(x0, y0) = 0 versagt das Kriterium und es müssen andere Verfahren zur Extremwertbestimmung verwendet werden. Stationäre Punkte (x0, y0) einer Funktion f (x, y) mit <20>(x0, y0) = 0 können Maximalstellen, Minimalstellen oder Sattelpunkte sein (Beispiele hierzu in Abb. 6.5).
|
||
Beispiel Gesucht sind die Abmessungen einer Schachtel ohne Deckel mit vorgegebenem Volumen V , sodass die Herstellungskosten (d. h. Oberfläche) minimal sind.
|
||
Lösung: Die zu minimierende Oberfläche ist gegeben durch die Funktion
|
||
O(x,y,z) = xy + 2xz + 2yz
|
||
mit der Nebenbedingung V = xyz.
|
||
|
||
( , )= 4+ 4
|
||
|
||
( , )=− 4− 4
|
||
|
||
ℎ( , ) = 3 − 3
|
||
|
||
Abb. 6.5: Funktionen, für die <20>(0,0) = 0 gilt
|
||
|
||
6.5 Extremwertbestimmung für Funktionen mit zwei Variablen
|
||
|
||
77
|
||
|
||
Ersetzt man in der Funktion O(x,y,z) die Variable z durch z = V /xy, so erhält man die folgende zu minimierende Funktion:
|
||
|
||
V
|
||
|
||
V
|
||
|
||
f (x, y)= xy + 2x · + 2y ·
|
||
|
||
xy
|
||
|
||
xy
|
||
|
||
2V 2V = xy + + .
|
||
yx
|
||
|
||
Nullsetzen der partiellen Ableitungen erster Ordnung ergibt
|
||
|
||
2V
|
||
|
||
2V
|
||
|
||
fx(x,y) = y − x2 = 0, fy(x,y) = x − y2 = 0.
|
||
|
||
Erweitert man die erste Gleichung mit x2 und die zweite Gleichung mit y2, so erhält man die Gleichungen
|
||
|
||
yx2 = 2V , xy2 = 2V , √
|
||
woraus yx2 = xy2 und damit x = y folgt. Wegen x3 = 2V ist x = y = 3√2V . √ Die Funktion f (x,y) kann höchstens im Punkt (x0, y0) = 3 2V , 3 2V
|
||
eine Minimalstelle besitzen. Zur Bestimmung von <20>(x0, y0) sind die partiellen
|
||
Ableitungen zweiter Ordnung von f (x,y) zu berechnen:
|
||
|
||
4V
|
||
|
||
4V
|
||
|
||
fxx = x3 , fyy = y3 , fxy = 1.
|
||
|
||
Hieraus folgt
|
||
|
||
<EFBFBD>(x0, y0)= fxx(x0, y0) · fyy(x0, y0) − fx2y(x0, y0) 4V 4V
|
||
= · − 1 = 3 > 0. 2V 2V
|
||
|
||
√√ Wegen fxx(x0, y0) = 2 > 0 ist (x0, y0) = 3 2V , 3 2V Minimalstelle von f (x, y). Die zugehörige Höhe z0 ergibt sich aus
|
||
|
||
V z0 = x0 · y0 =
|
||
|
||
V
|
||
|
||
1
|
||
|
||
=·
|
||
|
||
3 (2V )2 2
|
||
|
||
3 3
|
||
|
||
(2V )3 (2V )2
|
||
|
||
=
|
||
|
||
1 2
|
||
|
||
√ · 3 2V
|
||
|
||
=
|
||
|
||
1 2 x0
|
||
|
||
=
|
||
|
||
1 2 y0.
|
||
|
||
Resultat: Eine Schachtel ohne Deckel mit minimaler Oberfläche ist ein Quader, dessen Grundfläche ein Quadrat und dessen Höhe die halbe Grundseite ist (s. Abb. 6.6).
|
||
|
||
Die hier beschriebenen analytischen Methoden sind erweiterbar auf Funktionen mit mehr als zwei Variablen. Die Methode ist jedoch für eine größere Anzahl von Variablen nicht sehr effizient.
|
||
|
||
78
|
||
Abb. 6.6 Schachtel ohne Deckel mit minimaler Oberfläche bei gegebenem Volumen V
|
||
|
||
6 Analytische Methoden
|
||
|
||
6.6 Lagrange-Methode
|
||
Die Lagrange-Methode ist ein Verfahren zur Optimierung von Funktionen mit mehreren Variablen unter Nebenbedingungen. Bei diesem Verfahren spielt der sogenannte Gradient einer Funktion eine zentrale Rolle.
|
||
|
||
6.6.1 Gradient einer Funktion
|
||
|
||
Zu einer Funktion f (x1, . . . , xn) mit stetigen partiellen Ableitungen erster Ordnung heißt der Vektor
|
||
|
||
(
|
||
|
||
)
|
||
|
||
) ⋮
|
||
)
|
||
|
||
Gradient von f an der Stelle x1, . . . , xn . Der Operator ∇, der die Skalarfunktion f (x1, . . . , xn) auf die Vektorfunktion
|
||
∇f (x1, . . . , xn) abbildet, wird Nabla-Operator genannt.
|
||
|
||
Beispiel: Sei f (x, y) = x2 + y2. Der Gradient von f an der Stelle (1, 2) ist gegeben durch
|
||
|
||
∇f (x, y) =
|
||
|
||
fx(x, y) fy(x, y)
|
||
|
||
=
|
||
|
||
2x 2y
|
||
|
||
, ∇f (1, 2) =
|
||
|
||
2 4
|
||
|
||
.
|
||
|
||
6.6 Langrange-Methode
|
||
|
||
79
|
||
|
||
6.6.2 Richtungsableitung
|
||
|
||
Sei n = (n1, . . . , nk) ein normierter Vektor (Richtungsvektor) mit
|
||
<EFBFBD>n<EFBFBD> = n12 + · · · + nk2 = 1. Dann heißt für eine Funktion f (x1, . . . , xk) der Grenzwert
|
||
|
||
∂f
|
||
|
||
f = lim
|
||
|
||
x1 + h · n1, . . . , xk + h · nk
|
||
|
||
∂n h→0
|
||
|
||
h
|
||
|
||
Richtungsableitung von f an der Stelle x1, . . . , xk , sofern der Grenzwert existiert (s. Abb. 6.7).
|
||
Die Richtungsableitung kann bestimmt werden mithilfe des Gradienten. Es gilt:
|
||
|
||
∂f ∂n (x1, . . . , xk) = n · ∇f (x1, . . . , xk) (Skalarprodukt)
|
||
= n1 · fx1 (x1, . . . , xk) + · · · + nk · fxk (x1, . . . , xk).
|
||
Für die kanonischen Einheitsvektoren ei = (0, . . . , 1, . . . , 0), deren Komponenten bis auf die i-te Komponente 0 sind und in der i-ten Komponente den Wert 1 annimmt, gilt damit
|
||
|
||
∂f ∂f =.
|
||
∂ei ∂xi
|
||
|
||
Beispiel: Sei f (x, y) = x2 + x · y und n =
|
||
|
||
√1 , √1 . Es gilt
|
||
22
|
||
|
||
∂f
|
||
|
||
1
|
||
|
||
1
|
||
|
||
1
|
||
|
||
1
|
||
|
||
(x, y) ∂n
|
||
|
||
=
|
||
|
||
√ 2
|
||
|
||
· fx(x, y) +
|
||
|
||
√ 2
|
||
|
||
· fy(x, y)
|
||
|
||
=
|
||
|
||
√ (2x 2
|
||
|
||
+
|
||
|
||
y)
|
||
|
||
+
|
||
|
||
√ x. 2
|
||
|
||
(, )
|
||
|
||
Tangentensteigung = ( 0, 0)
|
||
|
||
0
|
||
|
||
Abb. 6.7 Durch den vertikalen Schnitt in Richtung des normierten Vektors n entsteht auf
|
||
|
||
der Fläche z = f (x,y) eine Schnittkurve. Die Steigung der Tangente an diese Flächenkurve im
|
||
|
||
Flächenpunkt
|
||
|
||
P(x0
|
||
|
||
,
|
||
|
||
y0
|
||
|
||
,
|
||
|
||
f
|
||
|
||
(x0
|
||
|
||
,
|
||
|
||
y0))
|
||
|
||
ist
|
||
|
||
dann
|
||
|
||
gegeben
|
||
|
||
durch
|
||
|
||
die
|
||
|
||
Richtungsableitung
|
||
|
||
∂f ∂n
|
||
|
||
(x0
|
||
|
||
,
|
||
|
||
y0
|
||
|
||
).
|
||
|
||
80
|
||
|
||
6 Analytische Methoden
|
||
|
||
( , ) = ∙ sin( ) ∙ −( 2+ 2)
|
||
|
||
−∇ ( 0, 0)
|
||
|
||
Höhenlinien ∇ ( 1, 1)
|
||
|
||
Abb. 6.8 Die Höhenlinien stellen eine 2D-Landkarte der 3D-Wertelandschaft von z = f (x, y) dar. Die Gradienten von f (x, y) stehen senkrecht in der xy-Ebene auf den Höhenlinien
|
||
|
||
Die Richtungsableitung im Punkt (1,2) ist gegeben durch
|
||
|
||
∂f
|
||
|
||
41 5
|
||
|
||
(1, 2) = √ + √ = √ .
|
||
|
||
∂n
|
||
|
||
22 2
|
||
|
||
6.6.3 Höhenlinie
|
||
|
||
Zu einer Funktion z = f (x, y) nennt man Schnittkurven mit den Ebenen z = konstant (Ebenen parallel zur xy-Ebene) Höhenlinien (s. Abb. 6.8).
|
||
|
||
a
|
||
|
||
2
|
||
|
||
(, )
|
||
|
||
b
|
||
|
||
∇ ( 0, 0, 0)
|
||
|
||
0
|
||
|
||
0
|
||
|
||
∇ ( 0, 0)
|
||
|
||
0
|
||
|
||
0
|
||
|
||
0
|
||
|
||
Abb. 6.9 (a) Ein virtueller Bergsteiger auf der Wertelandschaft von f (x, y), der auf dem Weg zum Berggipfel den stärksten Anstieg wählt, muss stets in Richtung des Gradienten laufen. (b) In einem Temperaturfeld t(x, y, z) zeigt der Gradient (Temperaturgradient) im Punkt P(x0, y0, z0) in Richtung des größten Temperaturanstiegs
|
||
|
||
6.6 Langrange-Methode
|
||
|
||
81
|
||
|
||
Es gilt: Für eine Funktion f (x, y) steht der Gradient ∇f (x0, y0) senkrecht auf der Höhenlinie mit der Höhe c = f (x0, y0).
|
||
|
||
6.6.4 Eigenschaften des Gradienten
|
||
|
||
Satz: Der Gradient ∇f x1, . . . , xk zeigt im Punkt x1, . . . , xk in Richtung des stärksten Anstiegs (s. Abb. 6.9).
|
||
|
||
Dies folgt aus
|
||
|
||
∂f ∂n x1, . . . , xk = n · ∇f x1, . . . , xk
|
||
= <20>n<EFBFBD> · ∇f x1, . . . , xk
|
||
|
||
cos α
|
||
|
||
1
|
||
= ∇f x1, . . . , xk · cos α
|
||
|
||
und der Eigenschaft cos α < cos 0 = 1 fu¨r alle α ∈ (0, π ], wobei α der Winkel zwischen ∇f x1, . . . , xk und n ist.
|
||
Der Maximalanstieg ist damit gegeben durch ∇f x1, . . . , xk .
|
||
|
||
Satz: In der Gegenrichtung besitzt der negative Gradient −∇f im Punkt x1, . . . , xk die Richtung des stärksten Abstiegs.
|
||
|
||
6.6.5 Lagrange-Funktion
|
||
Mit der Lagrange-Funktion kann folgendes Optimierungsproblem gelöst werden:
|
||
Optimierungsaufgabe: Gesucht sind die Extremstellen einer Funktion z = f (x, y) unter der Nebenbedingung g(x, y) = 0.
|
||
Geometrisch beschreibt die Funktion z = f (x, y) eine Fläche im Raum und die Gleichung g(x, y) = 0 stellt eine Kurve in der xy-Ebene dar. Die Extremwerte liegen dann auf der Fläche senkrecht über der Kurve g(x, y) = 0. Ist (x0, y0) eine lokale Extremstelle, so berührt die Höhenlinie f (x, y) = d mit d = f (x0, y0) die Kurve g(x, y) = 0 im Punkt (x0, y0) (s. Abb. 6.10). Daraus folgt, dass die Gradienten ∇f (x0, y0) und ∇g(x0, y0) parallel oder antiparallel sind, d. h. es gibt ein ∈ R mit
|
||
∇f (x0, y0) = − ∇g(x0, y0), sofern ∇g(x0, y0) <20>= 0.
|
||
|
||
82
|
||
a = (, )
|
||
|
||
b Höhenlinie ( , ) =
|
||
|
||
6 Analytische Methoden
|
||
Tangente ∇ ( 0, 0)
|
||
|
||
0
|
||
|
||
2 ( , )=0
|
||
|
||
( 0, 0) ( , )=0
|
||
|
||
0
|
||
∇ ( 0, 0)
|
||
|
||
Abb. 6.10 Illustration der Lagrange-Methode. (a) Ein virtueller Wanderer kann auf der Wertelandschaft z = f (x, y) das Maximum unter der Bedingung g(x, y) = 0 erreichen, indem er längs der Schnittkurve senkrecht über der in der xy-Ebene liegenden Kurve g(x, y) = 0 bis zum höchsten Punkt P läuft. (b) Die Höhenlinie f (x, y) = d in Höhe von P berührt die Kurve g(x, y) = 0 in der xy-Ebene im Punkt (x0, y0), d. h. beide Kurven haben im Kurvenpunkt (x0, y0) eine gemeinsame Tangente, ansonsten würden sich die Kurven in (x0, y0) schneiden. Da die Gradienten von f (x, y) und g(x, y) senkrecht auf ihren Höhenlinien bzw. den Tangenten stehen, sind die Vektoren ∇f (x0, y0) und ∇g(x0, y0) kollinear, d. h. es gilt ∇f (x0, y0) = − ∇g(x0, y0) für eine reelle Zahl = 0.
|
||
|
||
Definition Die Funktion
|
||
|
||
L(x,y, ) = f (x,y) + g(x,y), ∈ R
|
||
|
||
heißt Lagrange-Funktion und die Variable Lagrange-Multiplikator.
|
||
|
||
Wendet man den Gradienten auf die Lagrange-Funktion an, so erhält man
|
||
∇L(x,y, ) = ∇f (x,y) + ∇g(x,y).
|
||
Ist (x0, y0) ein lokale Extremstelle von f (x,y), so gilt dann wegen ∇f (x0, y0) = − ∇g(x0, y0)
|
||
∇L(x0, y0, ) = 0
|
||
für ein ∈ R. Alle lokale Extremstellen von f (x,y) sind somit unter der Bedingung g(x,y) = 0 Lösungen der Gleichung ∇L(x,y, ) = 0. Die Variable ist eine Hilfsgröße, wobei die Lösungen (x,y) nicht von abhängen.
|
||
|
||
6.6 Langrange-Methode
|
||
|
||
83
|
||
|
||
6.6.6 Lagrange-Methode
|
||
|
||
Zur Bestimmung der lokalen Extremstellen einer Funktion f (x,y) unter der Nebenbedingung g(x,y) = 0 führe man folgende Schritte aus: 1. Setze L(x,y, ) = f (x,y) + g(x,y), ∈ R 2. Bestimme alle Lösungen der Gleichung ∇L(x,y, ) = 0 bzw. löse das
|
||
Gleichungssystem Lx(x,y, ) = fx(x,y) + gx(x,y) = 0
|
||
Ly(x,y, ) = fy(x,y) + gy(x,y) = 0
|
||
L (x,y, ) = g(x,y) = 0.
|
||
Alle lokale Extremstellen sind Lösungen des Gleichungssystems. Es muss noch überprüft werden, ob bei diesen Lösungen tatsächlich lokale Extremstellen vorliegen.
|
||
|
||
6.6.7 Anwendungsbeispiel
|
||
Im Folgenden wenden wir die Lagrange-Methode auf die Optimierungsaufgabe 2.3 an, bei der die Höhe h und der Radius r einer zylindrischen Dose zu bestimmen sind, sodass bei gegebenem Volumen V die Oberfläche minimal ist.
|
||
ℎ
|
||
Die mathematische Formulierung lautet nach 2.3: Zielfunktion: f (h, r) = 2π r2 + 2π rh Nebenbedingung: g (h, r) = π r2h − V = 0 Lagrange-Methode 1. Setze L(h, r, ) = 2π r2 + 2π rh + π r2h − V 2. Aus ∇L = 0 ergibt sich das Gleichungssystem
|
||
(i) Lh = 2π r + π r2 = 0 (ii) Lr = 4π r + 2π h + 2 π rh = 0 (iii) L = π r2h − V = 0
|
||
Berechnung der Lösungen: Aus (i) folgt = − 2r.
|
||
|
||
84
|
||
Abb. 6.11 Zylindrische Dose mit minimaler Oberfläche bei gegebenem Volumen V
|
||
|
||
6 Analytische Methoden
|
||
|
||
Eingesetzt in (ii) ergibt
|
||
|
||
4πr + 2πh − 4πh = 4πr − 2πh = 0
|
||
|
||
und damit
|
||
|
||
h = 2r.
|
||
|
||
Aus (iii) folgt 2π r3 = V und demnach r =
|
||
|
||
3
|
||
|
||
V 2π
|
||
|
||
.
|
||
|
||
Es
|
||
|
||
gilt
|
||
|
||
dann
|
||
|
||
h = 2r = 2 3
|
||
|
||
V
|
||
|
||
=
|
||
|
||
3
|
||
|
||
4V .
|
||
|
||
2π
|
||
|
||
π
|
||
|
||
Als einzige Lösung liegt hier ein absolutes Minimum vor.
|
||
|
||
Resultat: Eine zylindrische Dose mit quadratischem Aufriss besitzt minimale Oberfläche bei gegebenem Volumeninhalt V (s. Abb. 6.11).
|
||
|
||
6.6.8 Lagrange-Methode für Funktionen mit mehr als zwei Variablen
|
||
Sinngemäß kann die Lagrange-Methode auch auf Funktionen f (x1, . . . , xn) unter der Nebenbedingung g(x1, . . . , xn) = 0 angewendet werden. Hierzu führe man folgende Schritte aus: 1. Setze L(x1, . . . , xn, ) = f (x1, . . . , xn) + g(x1, . . . , xn), ∈ R 2. Bestimme alle x = (x1, . . . , xn) mit ∇L(x, ) = 0.
|
||
6.7 Gradientenverfahren
|
||
Das Gradientenverfahren ist ein numerisches Verfahren zur Bestimmung eines nächstgelegenen lokalen Minimums bzw. Maximums. Dabei schreitet man von einem Startpunkt ausgehend in Richtung des negativen bzw. positiven Gradienten
|
||
|
||
6.7 Gradientenverfahren
|
||
|
||
85
|
||
|
||
fort, bis keine Verbesserung des Zielwertes erzielt wird. Das Gradientenverfahren spielt eine zentrale Rolle bei der Optimierung von neuronalen Netzen (vgl. Teil IV).
|
||
Im Folgenden wird das Gradientenabstiegsverfahren mit vereinfachter Schrittweitenberechnung beschrieben.
|
||
|
||
6.7.1 Ablauf des Gradientenabstiegsverfahrens
|
||
Eingabe: Eine Funktion f (x1, . . . , xn) mit stetigen partiellen Ableitungen erster Ordnung und eine Schrittweite 0 < α < 1
|
||
Gesucht: Lokales Minimum von f (x1, . . . , xn)
|
||
0. Wähle Anfangspunkt x = (x1, . . . , xn) in der Nähe der zu bestimmenden lokalen Minimalstelle.
|
||
1. Setze x′ = x − α · ∇f (x) 2. Setze x = x′
|
||
Wiederhole die Schritte 1 und 2, bis eine Abbruchbedingung erfüllt ist.
|
||
Ausgabe: Beste gefundene Lösung x′
|
||
Mögliche Abbruchbedingung
|
||
• Es gilt f x′ − f (x) < ε für eine Schranke ε. • Es gilt ∇f x′ = 0. • Das Erreichen einer vorgegebenen Anzahl von Iterationsschritten.
|
||
Abb. 6.12 zeigt graphisch den Ablauf des Gradientenabstiegsverfahrens mit vereinfachter Schrittweitenberechnung.
|
||
Mit dem Gradientenabstiegsverfahren kann zwar das globale Minimum nicht gefunden werden. Aber man kann mit verschiedenen Startwerten lokale Minima ermitteln und sich mit dem besten Wert der ermittelten lokalen Minima zufriedengeben.
|
||
Abb. 6.13 illustriert beispielhaft das Gradientenabstiegsverfahren.
|
||
|
||
Eingabe: Anfangspunkt
|
||
|
||
′ = − ∙∇ ( ) =′
|
||
|
||
Ausgabe: ′ bei Abbruch
|
||
|
||
Abb. 6.12 Ablauf des Gradientenabstiegsverfahrens mit vereinfachter Schrittweitenberechnung
|
||
|