Zu den Autoren:
Dr. Ulrich Kathöfer ist Akademischer Direktor im Bereich Informationsverarbeitung an der Medizinischen Fakultät der Universität Münster.
Prof. Dr. Ulrich Müller-Funk lehrt Quantitative Methoden an der Universität Münster.
Bibliografische Information der Deutschen Bibliothek
Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über <www.dnb.de> abrufbar.
Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlages unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen.
ISBN 978-3-86764-813-4 (Print)
ISBN 978-3-7398-0342-5 (EPUB)
ISBN 978-3-7398-0343-2 (EPDF)
© UVK Verlagsgesellschaft mbH, Konstanz und München 2017
Einbandgestaltung: Susanne Fuellhaas, Konstanz
UVK Verlagsgesellschaft mbH
Schützenstr. 24 • 78462 Konstanz
Tel. 07531-9053-0 • Fax 07531-9053-98
www.uvk.de
„Die Vorlesung ist gut und interessant – aber das Skript ist schlecht.“ Seit die studentische Veranstaltungskritik ins deutsche Hochschulwesen eingezogen ist, lesen wir diesen Vorwurf immer wieder schwarz auf weiß. Auch der Einwand, das „Skript“ sei ja gar keins, sondern nur die Sammlung der in der Vorlesung verwendeten Folien, die wir aus reiner Freundlichkeit im Internet bereit stellen, nützt da nur wenig. Der Verweis auf gedruckte Literatur ist oft problematisch – zu mathematisch, zu umfangreich oder auch zu oberflächlich stellt sich Manches dar.
So erscheint die Gelegenheit, im Rahmen des BWL-Crash-Kurses von UTB/UVK einmal alles aufzuschreiben, was in einer Vorlesung durch Folien und Vortrag vermittelt wird, sinnvoll zu sein für alle Beteiligten. Für die Studierenden, die nun endlich ihren Wunsch nach einer geschlossenen Darstellung der Themen erfüllt bekommen. Und auch für die Dozenten, die beim Formulieren der Zusammenhänge hinterfragen konnten, warum einige Verfahren des Operations Research in der Vorlesung bisher etwas mühsam rüberkamen; diese Überlegungen kommen sicher nicht nur dem Buch, sondern auch der Vorlesung zugute.
Operations Research ist sicherlich kein unzugängliches Thema im wirtschaftswissenschaftlichen Studium. Trotz der Ablehnung von mathematischen Vorgehensweisen, die manche Studierenden gern mal demonstrativ zur Schau stellen, kann die anwendungsorientierte Ausrichtung des Operations Research bei vielen genügend Interesse wecken, um auch mal etwas Methodisches auf sich zu nehmen. Unser Ansatz ist es, dies dem mehr oder weniger geneigten Leser nicht allzuschwer zu machen. So nutzen wir aus der Mathematik die Methodiken und Schreibweisen, aber nur so weit, wie es unbedingt nötig ist. Dort, wo man Verfahren auch sprachlich beschreiben kann, möchten wir nicht darauf verzichten. Den größten Teil dieses Buches sollte man daher mit durchschnittlichen mathematischen Kenntnissen aus der gymnasialen Oberstufe verstehen können; eine einführende Mathematik-Vorlesung, wie sie in jedem wirtschaftswissenschaftlichen Studium zu Beginn üblich ist, hilft dann beim Rest.
Die zentralen Themen des Operations Research wie Graphen und Optimierungsprobleme deckt das vorliegende Buch natürlich ab. Wenn wir in Randgebieten nicht weiter in die Tiefe gehen, sondern auf weiterführende Literatur verweisen, liegt das in der Natur eines „Crash-Kurses“. Zur Abrundung der Thematik haben wir ein Kapitel über Spieltheorie angefügt. Die Beschäftigung mit diesem Bereich bringt für die betriebliche Entscheidungsfindung, der das Operations Research ja dient, sicher mehr als eine Vielzahl weiterer Optimierungsalgorithmen.
Dank gebührt zunächst einmal den ehemaligen und derzeitigen Studierenden der Wirtschaftsinformatik, die durch konstantes Nach- und Hinterfragen die Dozenten herausgefordert haben, die Themen verständlich und interessant zu vermitteln. Auch beim Aufdecken von Fehlern hat sich die jahrelange Erfahrung mit der Vorlesung gelohnt. Ein besonderer Dank geht an die Mitarbeiterinnen und Mitarbeiter, die in den letzten Jahren die Übungen zur Vorlesung betreut haben. Von jedem steckt irgendwo etwas im jetzt vorliegenden Text oder in den Aufgaben. Hervorheben möchten wir Dr. Ingolf Terveer, der mit vielen Anregungen und Details beigetragen hat.
Wir danken besonders Frau Dipl.-Kffr. Andrea Vogel, die uns als Lektorin gehörig angetrieben hat – ohne sie wäre dieses Buch vermutlich nie oder erst in einigen Jahren fertig geworden.
„Die Vorlesung ist gut und interessant – und mit dem Buch dazu eine runde Sache.“ Das hoffen wir in Zukunft auf den Fragebögen in Münster zu lesen. Und etwas Ähnliches steht vielleicht auch an anderen Hochschulen auf den Bögen; über positive wie konstruktive negative Rückmeldung würden wir uns freuen. (or-buch@kathoefer.de)
Münster, im August 2005Ulrich Kathöfer
Ulrich Müller-Funk
Eine Reihe von Fehlern sind verschwunden – den Findern sei für die Mithilfe ganz herzlich gedankt. Wir haben die Gelegenheit genutzt, ein paar Formulierungen zu verbessern, Ungenauigkeiten auszuschalten, Klarheit einzubringen. Der Versuchung, den Umfang des Buches durch ein paar total wichtige Ergänzungen aufzublähen, konnten wir weitgehend widerstehen – das einführende Kapitel zur Dynamischen Optimierung haben wir uns und den Lesern aber doch geleistet.
Münster, im Januar 2008Ulrich Kathöfer
Ulrich Müller-Funk
Das erste Kapitel soll die Fragestellungen und Ziele des Operations Research in Übersichtsform darstellen. Dazu werden wir schon reichlich Beispiele und erste Lösungsansätze kennen lernen. Im Abschnitt 1.1 wollen wir die zentralen Begriffe „Modell“ und „Algorithmus“ praktisch erläutern. Der Abschnitt 1.2 
vgl. S. 21 stellt die Optimierung als Ziel in das Zentrum der Betrachtung. Verschiedene Modelle, die auch unterschiedliche Optimierungsverfahren erfordern, werden vorgestellt. Die Darstellung von Entscheidungssituationen, die von mehreren Parteien bestimmt werden, führt in Abschnitt 1.3 vgl. S. 29 zum Begriff des Gleichgewichts. Abschnitt 1.4 vgl. S. 34 beschäftigt sich mit stochastischen Modellen, die wir in diesem Buch aber nicht weiter vertiefen werden.
Operations Research (OR) steht als Oberbegriff für eine Reihe von mathematischen Verfahren, die für wirtschaftswissenschaftliche Zwecke eingesetzt werden. Viele dieser Verfahren wurden im zweiten Weltkrieg in den USA und Großbritannien entwickelt – es ging darum, militärische Operationen zu planen und auch zu verbessern. Nach dem Krieg wurde bald klar, dass die entwickelten Algorithmen sich ebenso für viele Fragestellungen in Unternehmen eigneten. Daraus resultiert die im Deutschen verwendete Bezeichnung „Unternehmensforschung“; treffendere Bezeichnungen wie Planungsrechnung haben sich nicht durchsetzen können. Auch Verfahren, die deutlich älter sind und sich z.B. mit Namen wie Cournot oder Leontief verbinden, werden heute zum Operations Research gezählt.
Diese Fragestellungen zeigen einige Gemeinsamkeiten, so etwa die Notwendigkeit, eine optimale Entscheidung zu treffen. Trotz unterschiedlicher betrieblicher Anwendungsgebiete gibt es somit strukturelle Ähnlichkeiten. Das Operations Research stellt universelle Lösungsmöglichkeiten bereit, die erfordern, dass die verschiedenen Fragestellungen in eine standardisierte Form gebracht werden, z.B. die Darstellung in Graphen oder die Formulierung als lineares Optimierungsproblem.
Eine Abgrenzung dessen, was zum Operations Research gehört und was nicht, ist in einem präzisen Sinne kaum möglich. Dies gilt sowohl in inhaltlicher wie in methodischer Hinsicht. So sind die Grenzen zu Teildisziplinen der Betriebswirtschaftslehre wie Produktion und Logistik (oder – zeitgemäßer –dem Operations Management) ebenso fließend wie zu Formalwissenschaften wie der Wahrscheinlichkeitstheorie und Statistik oder der konvexen Analysis.
Die Behandlung mit Verfahren des Operations Research setzt also den Übergang von der realen Welt in ein mathematisches MODELL 
Glossar voraus. Wir können die Modellierung eingebettet sehen in einen Prozess, der besteht aus
Formulierung des Problems
Zunächst wird in der Regel in Worten beschrieben, worin eigentlich das Problem besteht und was als Lösung anzusehen ist. Teilweise werden auch grafische Hilfsmittel zur Beschreibung verwendet. Hier ist zu beachten, dass alle Informationen, die für die Problemlösung erforderlich sind, auch vorliegen. Für die Entscheidung irrelevante Daten sollten nicht aufgenommen werden. Bei der Modellierung entsteht dadurch bewusst ein vergröbertes Abbild der realen Welt.
Es folgt dann die Beschreibung in mathematischer Form durch die Angabe von Mengen, Variablen, Relationen etc., bei der alle Zusammenhänge eindeutig formuliert sind. Die Beschreibung sollte sich auch daran orientieren, welche Lösungsverfahren die Mathematik bzw. das Operations Research bereitstellen können. Dazu kann es eventuell sinnvoll sein, weitere Vereinfachungen vorzunehmen, insbesondere auch um die Komplexität zu reduzieren.
Durchführung des Verfahrens
Die Durchführung des mathematischen Verfahrens stützt sich nur noch auf das mathematische Modell, abstrahiert also praktisch von den realen Gegebenheiten. Es werden nach Möglichkeit bekannte Algorithmen angewandt, um zu einer Lösung in mathematischer Formulierung zu kommen. Das Operations Research stellt für eine große Menge wirtschaftswissenschaftlicher Fragen geeignete Verfahren bereit.
Validierung der Ergebnisse
Schließlich ist die mathematische Lösung eines Problems mit der ursprünglichen Fragestellung zu konfrontieren. Kritische Fragen können etwa sein:
Unbefriedigende Antworten auf solche Fragen können es erfordern, die Modellierung noch einmal Schritt für Schritt in modifizierter Form durchzuführen.
Die Beispiele, die in diesem Buch immer wieder als Illustration auftauchen werden, setzen oft erst mit dem mathematischen Modell ein. Wir werden aber des öfteren auch Anwendungsbeispiele sehen, deren erster Lösungsschritt die Modellierung ist.
Kern des Operations Research sind nun natürlich nicht etwa die standardisierten Fragestellungen, sondern die Lösungsverfahren. Die genaue Beschreibung der Verfahrensweise, Schritt für Schritt, wie in einem Kochrezept, wird als ALGORITHMUS Glossar bezeichnet. Man nennt solche Verfahren
Wir wollen die verschiedenen Arten von Verfahren an einer bekannten Fragestellung erläutern. Die Problemformulierung ist – wie bei vielen Problemen des Operations Research – eine leicht erfassbare, etwas spielerische. Meist lassen sich aber „tatsächliche“ betriebliche Probleme ganz ähnlich lösen.
Das Problem des Handlungsreisenden (TRAVELLING SALESMAN PROBLEM Glossar) ist ein solches klassisches Beispiel. Eine Formulierung kann so aussehen: Ein Geschäftsmann will in zehn Städten Deutschlands Besprechungstermine festlegen und jeweils mit dem Zug anreisen. Anschließend will er zum Ausgangspunkt (Bielefeld) zurückfahren. Alle Städte sind in Abbildung 1.1 eingezeichnet.
Die Reihenfolge der Besprechungstermine soll nun so gewählt werden, dass die Gesamtfahrzeit möglichst gering gehalten wird. Die Fahrzeit zwischen den Orten (in Stunden) ist der folgenden Tabelle zu entnehmen.
Abbildung 1.1: Die 11 Städte des Rundreiseproblems
Das Problem des Handlungsreisenden besitzt eine Reihe von ökonomisch relevanten Anwendungen und Verallgemeinerungen. Beispiele sind:
Auf einer Maschine sollen nacheinander n Aufträge ausgeführt werden; die Umrüstung der Maschine zwischen zwei Auftragsausführungen ist abhängig von der Art der beiden Aufträge. Gesucht ist eine Abarbeitungsreihenfolge, die minimale Gesamt-Umrüstkosten verursacht.
Auf einem Mikro-Chip müssen durch winzige Drähte Kontakte verbunden werden (oft mehrere tausend Stück). Gesucht ist eine – kurzschlussfreie – Routenwahl für die Drähte auf dem Chip, die vorgegebene Streckenführungen berücksichtigt und dabei minimalen Drahtverbrauch (d.h. minimale Wärmeentwicklung) verursacht.
Zur Lösung von Rundreiseproblemen stehen etliche Strategien zur Auswahl, von denen ein paar hier anhand des obigen Beispiels kurz hinsichtlich ihrer Vor- und Nachteile besprochen werden sollen:
vgl. S. 17 vgl. S. 19Komplette Enumeration
Bei der KOMPLETTEN ENUMERATION Glossar wird jede der möglichen Strecken und ihre Dauer bestimmt. Bei diesem Lösungsverfahren ist ein wesentliches Problem die systematische Abarbeitung aller Lösungskandidaten. Sollen beispielsweise nur fünf Städte besucht werden, so ergeben sich die in Abbildung 1.2 dargestellten zwölf wesentlich verschiedenen Routen. Die kürzeste Strecke BI – HH – B – M – BN – BI kann in 21 Stunden bewältigt werden.
Ein Nachteil der kompletten Enumeration ist hier, dass für größere Städtezahlen der Rechenaufwand, selbst bei systematischem Abzählen, schnell in Bereiche steigt, die auch mit Computerunterstützung nicht mehr vertretbar sind.
So gibt es bei festem Startpunkt und n Städten eine überraschend große Anzahl von insgesamt (n−1)·(n−2)·(n−3)·· · ··3·2·1 = (n−1)! verschiedenen Rundreisen. Sind – wie im Beispiel – alle Distanzen unabhängig von der Richtung, so reduziert sich diese Zahl auf „lediglich“ 
Rundreisen.
Im Beispiel mit elf Städten muss also aus 10! = 3.628.800 Rundreisen (bzw. bei symmetrischen Distanzen aus 1.814.400 Rundreisen) die kürzeste gefunden werden. Viele Anwendungen des Rundreiseproblems gehen sogar von erheblich größeren Werten für n aus. Es ist klar, dass komplette Enumeration hier völlig versagt.
Glücklicherweise ist das Travelling Salesman Problem eine nicht sehr typische Aufgabenstellung. Viele andere Fragen lassen sich durch effektive Algorithmen auch durchaus effizient lösen.
Abbildung 1.2: Das Rundreiseproblem mit fünf Städten
Heuristiken
HEURISTIKEN Glossar versuchen, einfachste oberflächliche Strukturen des Problems auszunutzen. Dabei werden oft sogenannte gierige Algorithmen oder Verfahren der lokalen Suche verwendet.
Beispiele für Heuristiken im Rundreiseproblem
Die Rundreise wird mit einer festen Stadt (etwa Bielefeld) begonnen. Die nächste Stadt wird dann festgelegt als diejenige, die von der ersten Stadt die geringste Entfernung hat, die dritte Stadt als diejenige der noch nicht besuchten Städte, die von der zweiten Stadt die geringste Entfernung hat usw. Abbildung 1.3 gibt zwei mögliche Eröffnungslösungen nach dieser Methode an. Der Vorteil liegt in der leichten Handhabbarkeit des Verfahrens. Als nachteilig erweist sich, dass die gierige Strategie bei den letzten zu besuchenden Städten „Lehrgeld“ in Form hoher Distanzen zahlt.
Abbildung 1.3: Eröffnungslösungen nach Methode des besten Nachfolgers
Variante: Eröffnungslösungen nach der Methode der sukzessiven Einbeziehung.
Aus einer „Rundreise“ zwischen zwei Städten (etwa Bielefeld und Hamburg) wird sukzessive durch Hinzufügen von Städten eine Rundreise zwischen 3, 4, 5, . . . Städten. Die jeweils neu hinzuzufügende Stadt bzw. die Stelle der Rundreise, an der die Stadt eingefügt wird, wählt man so, dass die Gesamtlänge der neu entstehenden Rundreise möglichst gering ist. Diese Methode dürfte etwas bessere Ergebnisse erzielen, aber auch sie hat die oben beschriebenen Vor- bzw. Nachteile.
Aus einer Anfangslösung versucht man eine bessere Lösung zu ermitteln, indem man beispielsweise zwei Strecken einer Rundreise so durch zwei neue Strecken ersetzt, dass sich eine möglichst große Verringerung der Gesamtweglänge ergibt. Abbildung 1.4 illustriert dies anhand der Ersetzung der Strecken Bonn – München und Stuttgart – Nürnberg durch die Strecken Bonn – Stuttgart und München – Nürnberg.
Auch dieses Verfahren ist – zumindest auf dem Computer – leicht zu implementieren, besitzt aber den Nachteil, dass man, falls keine bessere Lösung als die aktuelle durch das Austauschverfahren erzielt werden kann, bei einer in der Regel suboptimalen Rundreise „stecken bleibt“. Das Verfahren besitzt diesbezüglich die typischen Nachteile lokaler Suchverfahren.
Abbildung 1.4: Verbesserung der Startlösung durch Änderung zweier Strecken
Stochastische Suchverfahren
Stochastische Suchverfahren sind z.B. Random Search, Genetische Algorithmen oder Simulated Annealing, die die Menge der zu vergleichenden Alternativen geeignet zufällig durchlaufen, ohne eine komplette Enumeration vorzunehmen. „Neue“ Lösungen werden dann z.B. durch geringfügige zufällige Modifikationen oder auch durch die der Evolution nachempfundene Rekombination alter Lösungen (Genetische Algorithmen) gefunden.
Für das Elf-Städte-Rundreiseproblem wurde die in Abbildung 1.5 dargestellte (vermutliche) Optimallösung mittels Simulated Annealing ermittelt.
Abbildung 1.5: Mit Simulated Annealing ermittelte Rundreise der Länge 25
Im Zentrum betriebswirtschaftlicher Fragestellungen steht in der Regel die Suche nach einer optimalen Lösung. Zielwerte sind etwa der maximal erreichbare Gewinn oder minimal realisierbare Kosten. So beschäftigen sich auch die meisten Algorithmen des Operations Research mit dem Ermitteln von optimalen Lösungen.
Ein OPTIMIERUNGSPROBLEM Glossar ist durch die Angabe folgender Bestimmungsstücke mathematisch festgelegt:
Formal zu lösen (bei Formulierung als Minimierungsproblem) ist also
x* ∈ Z heißt optimal, falls c(x*) ≤ c(x) ∀x ∈ Z. Ein Maximierungsproblem wäre entsprechend mit „max“ statt „min“ zu formulieren.
Die meisten Verfahren – und alle in diesem Buch besprochenen – setzen eine reellwertige Zielfunktion voraus. Eine solche Bewertung ist in manchen Fällen weder einfach noch natürlich, nämlich dann, wenn gleichzeitig nach mehreren Kriterien optimiert werden soll. Ein Lösungsansatz dazu wird in Abschnitt 1.2.5 vgl. S. 28 vorgestellt.
Es stellen sich unmittelbar die folgenden Fragen:
aber keine dieser Schranken realisiert werden kann.
Im Falle der Lösbarkeit können dann eine oder mehrere optimale Lösungen vorliegen.
Wie ein solcher Algorithmus aufgebaut ist, hängt maßgeblich von der Art des Suchraumes Z ab. Kriterien sind beispielsweise:
Verschiedene Arten von Optimierungsproblemen sollen auf den nächsten Seiten anhand von Beispielen skizziert werden. Dieser Aufteilung von Problemklassen wird das Buch in den Kapiteln 2 bis 5 folgen.
Wir wollen mit der Eisenbahn von Münster nach Konstanz reisen. Die Fahrt soll nicht allzu teuer und möglichst schnell beendet sein. Gesucht ist also ein optimaler Weg von Münster nach Konstanz. Auf der Streckenkarte der IC-Züge der Deutschen Bahn vgl. Abbildung 1.6 sehen wir viele Verbindungsmöglichkeiten.
Konkrete Fragestellungen könnten sein:
Man erkennt in diesen Fragestellungen verschiedene Zielfunktionen (Streckenlänge, Zeit), aber auch verschiedene zulässige Lösungen (gesamtes Netz, bevorzugte Teilwege, eingeschränktes Netz).
Denkbar sind neben der reinen Routensuche auch ganz andere Fragestellungen:
Abbildung 1.6: IC-Netz der Deutschen Bahn
All dies führt zu Modellen, die sich mit Methoden des Operations Research optimal lösen lassen.
Viele Gegebenheiten der Realität lassen sich wie ein Bahnnetz in grafischer Form darstellen. Wie die Modellierung durchgeführt wird und wie dann Optimierungsprobleme zu lösen sind, wird in Kapitel 2 vgl. S. 41 ausführlich erklärt.
Eine Firma stellt zwei Produkte her, die in drei Stufen in Handarbeit gefertigt werden müssen. In der ersten Stufe werden für das Produkt A zwei, für das Produkt B eine Mann-Stunde benötigt. Der zweite Schritt benötigt ebenfalls zwei Mann-Stunden für das Produkt A, aber sogar drei Mann-Stunden für Produkt B. In der letzten Stufe ist je eine Mann-Stunde für Produkt A und für Produkt B notwendig. Die Kapazität in der ersten Stufe sind 12 Mann-Stunden, in der zweiten 18 und in der dritten 8 Mann-Stunden. Die Firma verdient mit Produkt A 40 € pro Stück, mit Produkt B 30 €.
Wie viel Stück von jedem Produkt sollten hergestellt werden (im Rahmen der Möglichkeiten), um einen möglichst hohen Gewinn zu erzielen?
Bezeichnet man mit xA die Anzahl der hergestellten Stücke von Typ A und mit xB die Anzahl von Typ B, so kann man den Gewinn durch die Formel 40 · xA + 30 · xB berechnen. Dieser Wert soll möglichst groß sein. Die Zuordnung wird als Zielfunktion bezeichnet.
Hier können für xA und xBxA + 1 · xB maximal den Wert 12 ergeben darf, alsoxAxBEine solche Einschränkung bezeichnet man alsNebenbedingungoderRestriktion.