Lecture Notes in Economics and Mathematical Systems Operations Research, Computer Science, Social Science Edited by M. Beckmann, Previdence, G. Gees, Karlsruhe, and H. P. Künzi, Zürich 4 Sranch and Sound: Eine Einführung Zweite, geänderte Auflage Herausgegeben von F. Weinberg Unterlagen für einen Kurs des Instituts für Operations Research der ETH Zürich Spri nger-Verlag Berlin . Heidelberg . NewYork 1973 Advisory Board H. Albach . A. V. Balakrishnan . F. Ferschl . R. E. KaIman· W. Krelle . G. Seegmüller N. Wirth Prof. Dr. Franz Weinberg Institut für Operations Research der ETH Zürich 8006 Zürich, Clausiusstr. 55 AMS Subject Classifications (1970): 90-B-99, 90-02 ISBN-13: 978-3-540-06112-0 e-ISBN -13: 978-3-642-80724-4 DO!: 10.1007/978-3-642-80724-4 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is pavable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin . Heidelberg 1973. Library of Congress Catalog Card Number 72-95677. Offsetdruck: Julius Beltz, HemsbachfBergstr. VORWORT Es gibt eine grosse Menge von betriebswirtschaftlichen Entscheidungsfragen, die sich mit den nunmehr bereits als herkömmlich geltenden Optimierungs methoden des Operations Research nicht behandeln la§sen, sei es beispiels weise, dass die Zielfunktion und auch einzelne Restriktionen nicht konvex sind, sei es, dass nur ganzzahlige Lösungen toleriert werqen, sei es, dass die von einzelnen Variablen angenommenen Zahlenwerte Einfluss auf die Gültigkeit ganzer Restriktionengruppen nehmen. So wachsen z. B. die Kosten der Lagerhaltung als Sprungfunktion mit der Er richtung jedes zusätzlichen Warenhauses und sie nehmen für jedes bestehende Warenhaus meist konkav mit der Quantität der gelagerten Güter zu. Dieser nicht-konvexe Charakter kann sich in einer Zielfunktion (Kosten-Minimierung) oder in einer Restriktion äussern (Nicht-Ueberschreitung einer Kostenlimite). Die Anzahl von Warenhäusern ist offenbar eine ganze Zahl, deren Optimum unter Angabe der zugehörigen geographischen Standorte gesucht werden mag. Die Notwendigkeit der Berücksichtigung ortsgebundener Restriktionen für einzelne Warenhäuser (z.B. Provenienzvorschriften betreffend deren eigene Güterversorgung) ist vom Werte der logischen Variablen" abhängig, der angibt, ob ein bestimmtes Warenhaus errichtet werden soll oder nicht. Es würde nicht schwer fallen, eine lange Liste von derartigen Problemen auf zuzählen, die alle sehr erhebliche finanzielle Bedeutung für eine Unternehmung annehmen. Diese Probleme haben schon immer bestanden; es ist interessant, dass sie in letzter Zeit immer häufiger genannt werden und der Ruf nach ihrer Lösung mit immer grösserer Dringlichkeit ertönt. Diese Erscheinung ist allerdings erklärbar. Zunächst darf man feststellen, dass das Operations Research sich nach und nach als Disziplin etabliert hat. Die Führungsspitzen von Unternehmungen beginnen sich langsam mit diesem Werk zeug zu befreunden und wünschen mit seiner Hilfe Antwort auf Fragen von hoher Wichtigkeit zu erhalten, die sie bisher nur mühevoll und mit dem unbehaglichen Gefühl von grosser Unsicherheit behandeln konnten. Dies betrifft häufig Politik Variantenprobleme . Während Mischungsprobleme, wie sie beispielsweise ins Gebiet der gewöhnli chen linearen Programmierung fallen (z.B. optimale Produktionsmengen zusammensetzung) mit den klassischen Methoden des Operations Research meist lösbar sind, stellen Politik-Variantenprobleme normalerweise Aufgaben des eingangs erwähnten Typus dar. Nun sind Mischungsprobleme aber naturgemäss meist nicht so kritischer Natur, weil intuitiv gewählte Lösungen oft schon optimumnah ausfallen und sich schlimmstenfalls zu gegebener Zeit korrigieren lassen. Eine bestehende Fabrik kann ohne allzu schwerwiegende Eingriffe ihren Produktionsplan leicht abändern, und die damit verbundenen Kosten sind takti scher GrÖssenordnung. - IV - Politik-Varianten sind im allgemeinen nicht stetig modifizierbar. Eine Firma, die 10 Fabriken und 20 Warenhäuser betreibt, kann die einzelnen gewählten Standorte nicht adaptiv verschieben. Die Unternehmungsleitung muss sich an lässlich von Reorganisationsmassnahmen oder bei Erweiterungsabsichten für eine bestimmte Verteil-Organisation entscheiden, jegliche Aenderungen sind einschneidender Natur und finanziell von strategischer Dimension. Im Zuge der immer stärker sich abzeichnenden Kontaktnahme zwischen Management und Operations Research-Fachleuten ist es daher verständlich, dass gerade derartige, vom unternehmerischen Standpunkt aus besonders brennende Probleme in den Vordergrund gerückt werden. Gleichzeitig - und dies ist kein Zufall, denn angewandte Wissenschaft und Praxis stehen seit jeher und auf allen Gebieten in gegenseitiger, anspornender Wechselwirkung, - wur den neue Verfahren entwickelt, die auf Probleme dieser Art zugeschnitten sind. Diese Verfahren sind noch keineswegs vollkommen und sie führen auch nicht immer zum Ziel; denn je nach der angewandten Methodik ist entweder die Konvergenz oft schlecht oder der Rechenaufwand wächst mit der Dimension des Problems häufig explosionsartig . Das letztere Charakteristikum trifft für kombinatorische Vorgehensweise zu. Das im folgenden zur Sprache gelangende Branch and Bound-Verfahren kann zu den kombinatorischen Methoden gezählt werden. Im wesentlichen liegt sein Bestreben darin, durch ausgeklügelte Systematik von der normalerweise un übersehbaren Anzahl erlaubter Lösungen so rasch wie möglich ganze Familien zweige als nicht in Frage kommend abzuspalten und auf diese Weise mit oft einfacher Probiertechnik das gesuchte Optimum aufzuspüren. Branch and Bound ist gegenwärtig in Mode. Es ist nie schlecht, eine vernünfti ge Mode mitzumachen, denn so bleibt man in lebendigem Kontakt mit der Ent wicklung. Ob die hier vorliegende Moderichtung sich als dauerhaft erweisen wird, muss die Zukunft zeigen. Sicherlich darf man baldige Erarbeitung neuer verbesserter Methoden erwarten, sowohl auf dem Gebiete des Branch and Bound als auch auf jenem anderer Techniken, die sich mit den gleichen Auf gabenstellungen befassen. Einstweilen aber reicht der gegenwärtige Stand des Branch and Bound schon aus, um recht viele bedeutsame Aufgaben des Operations Research zu lösen und wertvolle Anregungen für eine weitere Be reicherung des mathematischen Instrumentariums dieser Disziplin zu bieten. Prof. Dr. Franz Weinberg Direktor des Instituts für Operations Research der ETH INHA LTSVERZEIC HNIS 1 Branch and Bound: Eine Einführung GIANCORRADO ESCHER 1 2 Das Handelsreisenden-Problem GIANCORRADO ESCHER 20 3 Ein Branch and Bound-Algorithmus zur Bestimmung einer exakten Lösung des Maschinenbelegungsplan problems für 3 Maschinen ULRICH WEISNER 33 4 Vertreter-Touren mit zeitlich variabler Dringlichkeit OTTO MUELLER 45 5 Das verallgemeinerte Knapsack-Problem NILS KYED 64 6 Zusammenhang zwischen Dynamischer Programmierung und Branch and Bound PETER KALL 75 7 Diskussion der Modellwahl am Beispiel des Travelling-Salesman Problems PIA PFLUGER 90 8 Ganzzahlige, Null-Eins- und Gemischt-Ganzzahlige Programmierung im Zusammenhang mit der Branch and Bound-Technik WOLF GANG RUNGGALDIER 107 9 Optimales Rangieren PETER SCHALTEGGER 127 10 Optimale Bildung von Nahgüterzügen JOSEF ACHERMANN 143 11 Gemeinsame Losgrössenrechnung für Teilevarianten bei deterministischem Bedarf KLAUS RUTZ 155 VERZEICHNIS DER AUTOREN Dr. Josef Achermann Wander AG., Bern Giancorrado Escher, dipl. Phys. ETH Institut für Operations Research der ETH Zürich Prof. Dr. Peter Kall Institut für Operations Research der Universität Zürich Dr. Pia Korevaar-Pfluger Math. Dept. San Diego State College Nils Kyed Institut für Elektronische Datenverarbeitung der Universität Zürich Dr. Otto Müller Werkzeugmaschinenfabrik Oerlikon-Bührle AG. Prof. Dr. Wolfgang Runggaldier Universita degli Studi di Padova Dr. Klaus Rutz Heberlein & Co. AG., Wattwil Peter Schaltegger, lic. Math. FIDES Treuhand-Vereinigung, Zürich Ulrich Weisner, dipl. Phys. ETH Institut für Operations Research der ETH Zürich HERSTELLUNG DES MANUSKRIPTS Frau Maria Daniel, Institut für Operations Research der ETH Zürich VORBEMERKUNG Bei dieser Veröffentlichung handelt es sich um eine Zusammen stellung von Unterlagen für einen vom Institut für Operations Research der ETH Zürich gehaltenen Kurs. Gegenüber der 1. Auflage wurden einige wesentliche Aenderungen vorgenommen, die der Ergänzung und der besseren Verständlich.,. keit dienen. Einige der Beiträge folgen ziemlich genau den Gedankengängen bereits publizierter Abhandlungen. Die entsprechenden Literatur angaben gehen aus dem Text hervor. BRANCH AND BOUND: EINE EINFUEHRUNG Giancorrado Escher 1. 1. Einführendes Beispiel Die Verkehrsbetriebe einer Stadt unterhalten ein Netz von 5 Linien mit folgendem maximalen Wagenbedarf pro Linie: Linie Fahrzeuge 1 17 2 16 3 21 (1. 1) 4 8 5 12 total 74 Der Wagenpark beträgt 80 Fahrzeuge, es stehen also jeweils minde stens 6 Fahrzeuge ausser Betrieb (Revisionen, Reparaturen, Ein satzmöglichkeit bei Notfällen, etc.). Erhebungen aus dem letzten Betriebsjahr ergaben folgende mittlere Zahlen von beförderten Passagieren (in 1000) pro Tag: Linie Passagiere (in 1000) 1 11 2 14 3 16 (1. 2) 4 8 5 7 total 56 - 2 - Auf sämtlichen Linien verkehrt Rollmaterial desselben Typus, das je doch infolge langjährigen Gebrauchs im Betrieb sehr teuer geworden ist. Es ist ausserdem veraltet und genügt nicht mehr den Anforderungen an Bequemlichkeit, die der Fahrgast erwartet. Die Gesellschaft beschliesst daher, ihren Wagenpark zu erneuern; in einer 1. Etappe steht ihr zu diesem Zwecke ein Kredit zur Verfügung, der es gestattet, höchstens 40 Fahrzeuge durch wirtschaftlichere, modernere und komfortablere zu ersetzen. Der Austausch der Fahrzeuge soll nach folgenden Richtlinien vorgenom men werden: 1) Auf allen Linien bleibt die gleiche Anzahl Fahrzeuge wie bisher im Einsatz. 2) Die Linien mit den höheren Beförderungszahlen sollen als erste be rücksichtigt werden, um möglichst viele Passagiere in den Genuss der grösseren Bequemlichkeit zu bringen. 3) Die Ersetzung soll linienweise erfolgen, d. h., am Schluss soll es keine Linie geben, auf der gleichzeitig neue und alte Wagen verkeh ren. Dies mit Rücksicht auf die Wagenführer, die linienweise ein gesetzt sind und umgeschult werden müssen, falls die Linie auf neues Rollmaterial eingerichtet wird. 4) Es ist damit zu rechnen, dass, bei Bestellungen bis 30 Wagen deren 2, von 31 bis 40 Wagen deren 3 wegen Reparaturen, Revisionen, Einsatz bei Notfällen, etc. ausser Betrieb in Reserve gelassen wer den müssen. Wieviel Fahrzeuge soll die Gesellschaft ersetzen und wie sollen die neuen Wagen auf die Linien verteilt werden, um möglichst vielen Fahr gästen den höheren Komfort zur Verfügung zu stellen? - 3 - Bei diesem recht einfachen Problem dürfte es nicht schwierig sein, die Optimallösung zu "erraten". Man findet sie z. B., indem man, unter möglichster Ausschöpfung des "Plafonds" von 40-3 = 37 Fahrzeugen, diese auf verschiedene Arten auf die Linien verteilt: Linien Total Wagen Total Passagiere (in 1000) 1 2 33 25 1 4 5 37 26 2 3 37 30 (1. 3) 2 4 5 36 29 3 4 29 24 3 5 33 23 Durch Vergleich der beförderten Passagierzahlen erkennt man, dass die dritte Politik - "Ersetzen der Wagen auf Linien 2 und 3" - die opti male ist. Sie schöpft - nebenbei bemerkt - die Maximalzahl Fahrzeuge aus. Nachdem dieser erste, mehr intuitive Lösungsweg gezeigt wurde, soll eine strengere, verallgemeinerungsfähige Methode ausgearbeitet werden. Zu diesem Zwecke führe man folgende Variable ein: x. Anteil neuer Wagen am Bedarf für die Linie 1 (i = 1, ... , 5). Dann kann man das Problem wie folgt schreiben: J Max. (1.4) z = 1 (1. 5) x. = 0 oder 1 (i = 1, ... ,5). (1. 6) 1