Stefan Nickel · Claudius Steinhardt Hans Schlenker · Wolfgang Burkart Melanie Reuter-Oppermann Angewandte Optimierung mit IBM ILOG CPLEX Optimization Studio Modellierung von Planungs- und Entscheidungsproblemen des Operations Research mit OPL 2. Auflage Angewandte Optimierung mit IBM ILOG CPLEX Optimization Studio Stefan Nickel · Claudius Steinhardt · Hans Schlenker · Wolfgang Burkart · Melanie Reuter-Oppermann Angewandte Optimierung mit IBM ILOG CPLEX Optimization Studio Modellierung von Planungs- und Entscheidungsproblemen des Operations Research mit OPL 2. Auflage Stefan Nickel Claudius Steinhardt Institut für Operations Research Business Analytics und Management Science Karlsruher Institut für Technologie Universität der Bundeswehr München Karlsruhe, Deutschland Neubiberg, Deutschland Hans Schlenker Wolfgang Burkart München, Deutschland Analytics & Optimization Universität Augsburg Melanie Reuter-Oppermann Augsburg, Deutschland Wirtschaftsinformatik Technische Universität Darmstadt Darmstadt, Deutschland ISBN 978-3-662-62184-4 ISBN 978-3-662-62185-1 (eBook) https://doi.org/10.1007/978-3-662-62185-1 Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detail- lierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. © Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2020, 2021 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. Springer Gabler ist ein Imprint der eingetragenen Gesellschaft Springer-Verlag GmbH, DE und ist ein Teil von Springer Nature. Die Anschrift der Gesellschaft ist: Heidelberger Platz 3, 14197 Berlin, Germany Vorwort Das vorliegende Buch ist aus einem Kurs entstanden, den wir seit dem Jahr 2012 im fortgeschrittenen Bachelorstudium für Studierende der Betriebswirtschaftslehre, der (Wirtschafts-)Mathematik, der (Wirtschafts-)Informatik und des Wirtschaftsingenieur- wesens am Karlsruher Institut für Technologie, an der Universität Augsburg sowie an der Universität der Bundeswehr München gehalten und kontinuierlich weiterentwickelt haben. Das Buch liefert einen fundierten Einstieg in die Arbeit mit dem IBM ILOG CPLEX Optimization Studio und insbesondere in den Umgang mit der Modellierungssprache OPL zur Modellierung linearer und ganzzahliger linearer Optimierungsprobleme. Es richtet sich sowohl an Praktiker, die mit der Modellierung und Optimierung von Pla- nungs- und Entscheidungsproblemen befasst sind, als auch an Lehrende und Studieren- de an Universitäten und Hochschulen zur Verwendung in entsprechenden Vorlesungs- und Kursangeboten. Dabei werden keine Vorkenntnisse der mathematischen Grundla- gen der Optimierung vorausgesetzt, wenngleich ein auf dem Buch basierender Kurs gut als Ergänzung oder Bestandteil einer einführenden Veranstaltung in das Operations Research gehalten werden kann. Teil 1 des Buchs gliedert sich in zehn aufeinander aufbauende Lerneinheiten, ergänzt um eine Auswahl kleinerer Aufgaben jeweils am Kapitelende zur Einübung der erlernten Inhalte. Teil 2 enthält eine Reihe von zusätzlichen, größeren Anwendungsstudien, bei deren Darstellung ein besonderes Augenmerk auf umfassende, didaktisch aufbereitete Lösungsvorschläge gelegt wurde. Ausführliche Hinweise zum Aufbau des Buchs finden sich in Kapitel 1.4. Über die buchbegleitende Website www.opl-buch.de sind ergänzende Materialien – etwa Aufgabenlösungen und sämtliche Programm-Codes – abrufbar. VI Vorwort Der Kurs wurde in enger Abstimmung mit IBM Deutschland entwickelt. Stellvertre- tend möchten wir an dieser Stelle Herrn Dr. Martin Mähler und Herrn Michael Neuffer für die wohlwollende Unterstützung des Buchprojekts ausdrücklich danken. Ferner möchten wir uns bei Herrn Michael Bursik sowie Frau Dr. Isabella Hanser vom Verlag Springer Gabler für die sehr gute Zusammenarbeit bedanken. Für die Unterstützung im Rahmen der Erstellung des Manuskripts und insbesondere das Korrekturlesen danken wir zudem herzlich den wissenschaftlichen Mitarbeitern und Hilfskräften der drei betei- ligten Lehrstühle. Für das Buch sind eine englische Übersetzung und regelmäßige Aktualisierungen ge- plant. Karlsruhe, München, Augsburg, im Januar 2020 Stefan Nickel Claudius Steinhardt Hans Schlenker Wolfgang Burkart Melanie Reuter-Oppermann Vorwort VII Prof. Dr. Stefan Nickel Karlsruher Institut für Technologie (KIT) Institut für Operations Research (IOR) Lehrstuhl für Diskrete Optimierung und Logistik Direktor FZI – Forschungszentrum Informatik Direktor KSRI – Karlsruhe Service Research Institute Kaiserstraße 89 76133 Karlsruhe [email protected] Prof. Dr. Claudius Steinhardt Universität der Bundeswehr München Lehrstuhl für Allgemeine Betriebswirtschaftslehre, insbesondere Business Analytics & Management Science Werner-Heisenberg-Weg 39 85577 Neubiberg [email protected] Dr. Hans Schlenker Wallbergstraße 28 81539 München [email protected] Dr. Wolfgang Burkart Universität Augsburg Institut für Statistik und mathematische Wirtschaftstheorie Lehrstuhl für Analytics & Optimization Universitätsstraße 16 86159 Augsburg [email protected] Dr. Melanie Reuter-Oppermann Technische Universität Darmstadt Fachgebiet Wirtschaftsinformatik | Software & Digital Business Hochschulstraße 1 64289 Darmstadt [email protected] Inhaltsverzeichnis Vorwort ............................................................................................................................ V Abkürzungsverzeichnis .............................................................................................. XIII Teil 1 Lektionen Kapitel 1: Einleitung .........................................................................................................3 1.1 Modellierung und Optimierung von Planungs- und Entscheidungsproblemen .................................................................................................... 4 1.2 Softwareeinsatz und IBM ILOG CPLEX Optimization Studio ..................................... 4 1.3 Einleitendes Beispiel ............................................................................................................ 5 1.4 Inhalt des Buchs ................................................................................................................... 7 Kapitel 2: IBM ILOG CPLEX Optimization Studio ........................................................9 2.1 Technischer Rahmen und Installation .............................................................................. 9 2.2 Programmstart .................................................................................................................... 10 2.3 Erste Schritte ....................................................................................................................... 12 2.4 Hilfesystem und weitere Ressourcen ............................................................................... 22 Kapitel 3: Der Aufbau einer Modell-Datei ....................................................................25 3.1 Deklaration und Initialisierung der Modellparameter ................................................. 27 3.2 Deklaration der Entscheidungsvariablen ........................................................................ 31 3.3 Zielfunktion ........................................................................................................................ 32 3.4 Nebenbedingungen ............................................................................................................ 34 3.5 Lösung Fallbeispiel 1 .......................................................................................................... 36 3.6 Aufgaben ............................................................................................................................. 40 X Inhaltsverzeichnis Kapitel 4: Zusammengesetzte Datentypen und zugehörige Sprachelemente ..............43 4.1 Zahlenbereiche (Ranges) ................................................................................................... 44 4.2 Felder (Arrays) .................................................................................................................... 45 4.3 Mengen (Sets) ..................................................................................................................... 51 4.4 Aggregatoperatoren ........................................................................................................... 56 4.5 Der forall-Quantor ............................................................................................................. 59 4.6 Lösung Fallbeispiel 2 .......................................................................................................... 61 4.7 Aufgaben ............................................................................................................................. 63 Kapitel 5: Einführung in ILOG Script ...........................................................................67 5.1 Aufbau und grundlegende Sprachelemente von ILOG Script ..................................... 68 5.2 OPL-Datenelemente und ILOG-Script-Variablen ........................................................ 70 5.3 Weitere Sprachelemente .................................................................................................... 72 5.4 Lösung Fallbeispiel 3 .......................................................................................................... 81 5.5 Aufgaben ............................................................................................................................. 82 Kapitel 6: Modellierung mit Tupeln ..............................................................................85 6.1 Der Datentyp Tupel ........................................................................................................... 86 6.2 Tupelmengen ...................................................................................................................... 92 6.3 Effiziente Modellierung mit Tupelmengen .................................................................. 102 6.4 Lösung Fallbeispiel 4: Effiziente Modellierung dünn besetzter Matrizen durch Tupelmengen ............................................................. 110 6.5 Aufgaben ........................................................................................................................... 117 Kapitel 7: Trennung von Modell und Daten ............................................................... 121 7.1 Interne und externe Daten-Initialisierung ................................................................... 123 7.2 Explizite Initialisierung in Daten-Dateien .................................................................... 127 7.3 Anbindung von Tabellenkalkulations-Dateien ............................................................ 131 7.4 Lösung Fallbeispiel 5 ........................................................................................................ 135 7.5 Aufgaben ........................................................................................................................... 140 Kapitel 8: Ausgewählte Funktionalitäten von OPL und CPLEX Optimization Studio ....................................................................... 143 8.1 Modellierung mit logischen Verknüpfungen ............................................................... 145 8.2 Abschnittsweise lineare Funktionen .............................................................................. 156 8.3 Konflikte und Relaxationen ............................................................................................ 169 8.4 Lösung Fallbeispiel 6 ........................................................................................................ 175 8.5 Aufgaben ........................................................................................................................... 178 Kapitel 9: Ausgewählte Funktionalitäten von ILOG Script ........................................ 183 9.1 Ein- und Ausgabe mit ILOG Script ............................................................................... 184 9.2 Pre- und Postprocessing mit ILOG Script .................................................................... 191 9.3 Zeitmessung und CPLEX-Einstellungen ...................................................................... 193 Inhaltsverzeichnis XI 9.4 Lösung Fallbeispiel 7 ........................................................................................................ 197 9.5 Aufgaben ........................................................................................................................... 200 Kapitel 10: Ablaufsteuerung mit ILOG Script ............................................................ 205 10.1 Funktionsweise und Einsatzfelder ................................................................................. 207 10.2 Zugriff auf Modell- und Daten-Dateien ....................................................................... 209 10.3 Lösung Fallbeispiel 8 ........................................................................................................ 213 10.4 Verweis auf weiterführende Problemstellungen .......................................................... 217 10.5 Aufgaben ........................................................................................................................... 218 Teil 2 Anwendungsstudien Kapitel 11: Versorgungsplanung ................................................................................. 223 Kapitel 12: Fuhrparkplanung ....................................................................................... 231 Kapitel 13: Standortplanung ........................................................................................ 239 Kapitel 14: Transportplanung ...................................................................................... 249 Kapitel 15: Kapazitätssteuerung .................................................................................. 259 Kapitel 16: Losgrößenplanung ..................................................................................... 271 Literaturverzeichnis ...................................................................................................... 287 Stichwortverzeichnis..................................................................................................... 289