Springer-Lehrbuch Springer-Verlag Berlin Heidelberg GmbH Wolfgang Domschke · Andreas Drexl Einführung in Operations Research Vierte, verbesserte Auflage Mit 80 Abbildungen und 58 Tabellen i Springer Professor Dr. Wolfgang Domschke Technische Universităt Darmstadt Institut fiir Betriebswirtschaftslehre Fachgebiet Operations Research Hochschulstrafie 1 D-64289 Darmstadt Professor Dr. Andreas Drexl Christian-Albrechts-Universităt zu Kiel Lehrstuhl fiir Produktion und Logistik OlshausenstraBe 40 D-24118 Kiel ISBN 978-3-540-64587-0 ISBN 978-3-662-06910-3 (eBook) DOI 10.1007/978-3-662-06910-3 Die Deutsche Bibliothek-CIP-Einheitsaufnahme Domschke, Wolfgang: Einfiihrung in Operations-Research 1 Wolfgang Domschke; Andreas Drexl. - 4., verb. Aufl. - Berlin; Heidelberg; New York; Barcelona; Budapest; Hong Kong; · London; Mailand, Paris; Tokyo: Springer, 1998 (Springer-Lehrbuch) Dieses Werk ist urheberrechtlich geschiitzt. Die dadurch begriindeten Rechte, insbesondere die der Obersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Ta bellen, der Funksendung, der Mikroverfilmung oder der Vervielfăltigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Ver wertung, vorbehalten. Eine Vervieltliltigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsge setzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fas sung zuliissig. Sie ist grundsiitzlich vergiitungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. C Springer-Verlag Berlin Heidelberg 1990, 1991, 1995, 1998 Urspriinglich erschienen bei Springer-Verlag Berlin Heidelberg New York 1998. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dafi solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wiiren und daher von jedermann benutzt werden diirften. SPIN 10682812 42/2202-5 4 3 2 1 O - Gedruckt auf saurefreiem Papier Vorwort (zur 4. Auflage) Langjähriger Einsatz des Buches in Lehrveranstaltungen hat uns in der Absicht bestärkt, auch bei der vierten Auflage dessen Grundkonzeption beizubehalten. Gegenüber der dritten Auflage wurden erneut einige Passagen des Manuskriptes mit dem Ziel der Verbesserung der Ver ständlichkeit umgeschrieben. Am intensivsten überarbeitet wurden die Kapitel 6 und 8. In Kapitel 6 wird die Bedeutung, die insbesondere die Metaheuristiken Tabu Search und Simulated Annealing erlangt haben, stärker hervorgehoben. Darüber hinaus sind nunmehr bei fast allen Kapiteln ausführlichere Hinweise auf Softwarepakete enthalten. Erneut gilt ein herzliches Dankeschön für die tatkräftige Unterstützung bei der Neuauflage Frau DipI .-Math. Gabriela Krispin sowie den Herren DipI .-Wirtsch.-Inf. Robert Klein und Dr. Armin Scholl. Darmstadt /Kiel, im März 1998 Wolfgang Domschke A ndreas Drexl Vorwort (zur 1. Auflage) Das vorliegende Buch ist aus Vorlesungen zur Eintührung in Operations Research entstanden, die wir für Studenten der Betriebswirtschaftslehre, der Volkswirtschaftslehre, des Wirtschafts ingenieurwesens, der (Wirtschafts-) Informatik und der Mathematik an der Technischen Hochschule Darmstadt und an der Christian-Albrechts-Universität zu Kiel gehalten haben. Das Operations Research hat sich in den letzten 20 Jahren stürmisch entwickelt. In allen grundlegenden Bereichen des Operations Research, mit denen wir uns in den Kapiteln 2 bis 10 dieses Buches näher auseinandersetzen, wurde eine Vielzahl unterschiedlicher Modelle und leistungsfähiger Verfahren konzipiert. Dasselbe gilt für diejenigen Bereiche, die sich mit primär anwendungsorientierten Problemen beschäftigen. Ein Ende dieser Entwicklung ist nicht in Sicht. Die Ergebnisse dieser Forschungsbemühungen werden in einer Fülle von Fachzeitschriften und Monographien dokumentiert. Für die meisten dieser Publikationen gilt, daß sie von Fach leuten für Fachleute verfaßt werden. Für Anfänger ist der Zugang teilweise recht schwierig. VI Vorwort Dieses Buch ist angesichts der oben bereits genannten heterogenen studentischen Zielgruppe ein einführendes Studienskript mit grundlegenden Modellen und Verfahren des Operations Research. Im Vordergrund steht damit nicht die Darstellung neuester Forschungsergebnisse, sondern eine didaktisch günstige Aufbereitung und Vermittlung von Grundlagen dieser jungen Wissenschaft. Die Ausführungen sind so gehalten, daß sie weitgehend auch zum Selbststudium geeignet sind. Alle Verfahren werden daher, soweit erforderlich und mit vertretbarem Auf wand möglich, algorithmisch beschrieben und an Beispielen verdeutlicht. Ein über die in den Text gestreuten Beispiele hinausgehender Aufgaben- und Lösungsteil befindet sich in Vorbereitung. Wir danken unseren Mitarbeitern, insbesondere Frau Dipl.-Math. Birgit Schildt sowie den Herren Dipl.-Wirtsch.-Inf. Annin Scholl und Dipl.-Math. Arno· Sprecher für die kritische Durchsicht des Manuskripts sowie wertvolle Anregungen und Verbesserungsvorschläge. Herrn Dr. Werner Müller vom Springer-Verlag danken wir für die Aufnahme dieses Buches in die Reihe der Springer-Lehrbücher. Wir widmen dieses Buch Barbara und Ulrike. Ihnen sollte ein OR-Preis verliehen werden: Während der Wochen und Monate, die wir mit dem Schreiben dieses Buches zugebracht haben und damit unseren Familien nicht zur Verfügung standen, ist es ihnen gelungen, unsere Kinder davon zu überzeugen, daß die Beschäftigung mit Operations Research die schönste und wichtigste Sache im Leben ist. Wir hoffen, daß unsere Studenten und Kollegen nach der Lektüre des Buches diese Auffassung teilen. Darmstadt I Kiel, im August 1990 Wolfgang Domschke Andreas Drexl Inhaltsverzeichnis Vorwort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V Symbolverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XIII Kapitell: Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Begriff des Operations Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Modelle im Operations Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Charakterisierung verschiedener Modelltypen . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 Optimierungsmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2.1 Formulierung eines allgemeinen Optimierungsmodells . . . . . . . . . . . . 3 1.2.2.2 Beispiele für Optimierungsmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2.3 Klassifikation von Optimierungsmodellen . . . . . . . . . . . . . . . . . . . . . 5 1.3 Teilgebiete des Operations Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Arten der Planung und Anwendungsmöglichkeiten des OR .... ·. . . . . . . . . . . . . . . 8 1.5 Ergänzende Hinweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Literaturhinweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Kapitel2: Lineare Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 21 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 22 Graphische Lösung von linearen Optimierungsproblemen . . . . . . . . . . . . . . . . . . . . 12 23 Formen und Analyse von linearen Optimierungsproblemen . . . . . . . . . . . . . . . . . . 14 2.3.1 Optimierungsprobleme mit Ungleichungen als Nebenbedingungen . . . . . . . . . 14 2.3.2 Die Normalform eines linearen Optimierungsproblems . . . . . . . . . . . . . . . . . 15 2.3.3 Analyse von linearen Optimierungsproblemen . . . . . . . . . . . . . . . . . . . . . . . 16 24 I>er Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Der Simplex-Algorithmus bei bekannter zulässiger Basislösung........... 20 2.4.1.1 Darstellung des Lösungsprinzips anband eines Beispiels . . . . . . . . . . 20 2.4.1.2 Derprimale Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 Verfahren zur Bestimmung einer zulässigen Basislösung . . . . . . . . . . . . . . . . 25 2.4.2.1 Der duale Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.2.2 Die M-Methode................................... . . . . 27 VIII Inhaltsverzeichnis 2.4.3 Der revidierte Simplex-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4.4 Sonderfälle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 25 Dualität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 26 Untere und obere Schranken für Variablen .............................. · 40 2 7 Sensitivitätsanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 28 Optimierung bei mehrfacher Zielsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.8.1 Lexikographische Ordnung von Zielen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.8.2 Zieldominanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.8.3 Zielgewichtung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.8.4 Berücksichtigung von Abstandsfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . 51 29 Spieltheorie und lineare Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Software-und Literaturhinweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Kapitel 3: Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.1.1 Begriffe der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.1.2 Speicherung von Knotenmengen und Graphen . . . . . . . . . . . . . . . . . . . . . . . 63 • 3.2 Kü~zeste Wege in Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2.1 Baumalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.2.2 Der Tripel-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3 Minimale spannende Bäume und minimale 1-Bäume . . . . . . . . . . . . . . . . . . . . . . 72 3.3.1 Bestimmung eines minimalen spannenden Baumes . . . . . . . . . . . . . . . . . . . . 72 3.3.2 Bestimmung eines minimalen 1-Baumes . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Software-und Literaturhinweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Kapitel4: Lineare Optimierungsprobleme mit spezieller Struktur . . 75 4.1 Das klassische Transportproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.1.1 Problemstellung und Verfahrensüberblick . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.1.2 Eröffnungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.1.3 Die MODI-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 Das lineare Zuordnungsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3 Umladeprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Software-und Literaturhinweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Inhaltsverzeichnis IX KapitelS: Netzplantechnik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.1 Einführung und Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.2 Struktur-und Zeitplanung mit Vorgangsknotennetzplänen . . . . . . . . . . . . . . . . . . . 91 5.2.1 Strukturplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.2.1.1 Grundregeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.2.1.2 Transformation von Vorgangsfolgen . . . . . . . . . . . . . . . . . . . . . . . . 93 5.2.1.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.2.2 Zeitplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.2.2.1 Ermittlung frühester und spätester Zeitpunkte . . . . . . . . . . . . . . . . 96 5.2.2.2 Pufferzeiten, kritische Vorgänge und Wege . . . . . . . . . . . . . . . . . . . 99 5.2.2.3 Zeitplanung mit linearer Optimierung . . . . . . . . . . . . . . . . . . . . . . 101 5.2.3 Gantt-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.3 Struktur-und Zeitplanung mit Vorgangspfeilnetzplänen . . . . . . . . . . . . . . . . . . . . 103 5.3.1 Strukturplanung . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.3.1.1 Grundregeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.3.1.2 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.3.2 Zeitplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.3.2.1 Ermittlung frühester und spätester Zeitpunkte . . . . . . . . . . . . . . . . 105 5.3.2.2 Pufferzeiten, kritische Vorgänge und Wege . . . . . . . . . . . . . . . . . . . 107 5.4 Kostenplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.5 Kapazitätsplanung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Software-und Literaturhinweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Kapitel6: Ganzzahlige und kombinatorische Optimierung . . . . . . . . 113 6.1 Klassifikation und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.2 Komplexität und Lösungsprinzipien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 6.2.1 Komplexität von Algorithmen und Optimierungsproblemen . . . . . . . . . . . . 118 6.2.2 Lösungsprinzipien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.3 Grundprinzipien heuristischer Lösungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.4 Branch-and-Bound-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.4.1 Das Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 125 6.4.2 Erläuterung anband eines Beispiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.4.3 Komponenten von B&B-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.5 Traveling Salesman-Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.5.1 Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.5.1.1 Deterministische Eröffnungsverfahren . . . . . . . . . . . . . . . . . . . . . . 131