Operations Research E-Book

Ulrich Müller-Funk

• Herausgeber: UVK
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Deutsch
• Veröffentlichungsjahr: 2017

Seitenzahl: 237

Beschreibung

Der Band führt Studienanfänger in die Grundlagen des Operations Research ein. Anhand zahlreicher Beispiele vermittelt er verständlich und anwendungsnah kompaktes Prüfungswissen und spricht ausdrücklich auch Nicht-Mathematiker an.Behandelt werden zentrale Fragen und Algorithmen des Operations Research wie diskrete, lineare und ganzzahlige Optimierungsmethoden sowie Entscheidungs- und Spieltheorie. Anwendungen sind beispielsweise Netzplantechnik, Transportprobleme oder Routenplanung. Verweise auf weiterführende Themenbereiche runden die Darstellung ab.

Leseprobe

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.

Inhalt

Vorwort

Einführung

Übersicht

1.1 Fragestellungen des Operations Research

1.1.1 Modellierung

1.1.2 Algorithmen

1.2 Optima

1.2.1 Diskrete Optimierungsprobleme

1.2.2 Lineare Optimierungsprobleme

1.2.3 Ganzzahlige Optimierungsprobleme

1.2.4 Nichtlineare Optimierung

1.2.5 Multikriterielle Optimierung

1.3 Gleichgewichte

1.4 Stochastische Probleme des Operations Research

1.4.1 Risikomodelle

1.4.2 Warteschlangenmodelle

1.4.3 M

ARKOV

-Entscheidungs-Modelle

Zusammenfassung

Kontrollfragen

Literatur

Optimierung in Graphen

Übersicht

2.1 Relationen, Graphen, Bäume

2.1.1 Relationen

2.1.2 Graphen

2.1.3 Digraphen

2.1.4 Netzwerke

2.1.5 Teilbedarfsrechnung – Gozintographen

2.1.6 Bäume

2.2 Kürzeste Wege in Netzwerken

2.2.1 D

IJKSTRA

-Algorithmus für Digraphen

2.2.2 Minimal aufspannende Bäume

2.3 Netzplantechnik

2.3.1 Vorgangsliste

2.3.2 CPM-Netzpläne

2.3.3 CPM-Zeitplanung

2.4 Dynamische Optimierung

2.4.1 Problemstellung

2.4.2 Lösungsansatz

2.4.3 Erweiterungen

Zusammenfassung

Kontrollfragen

Literatur

Lineare Optimierung

Übersicht

3.1 Lineare Optimierungsprobleme

3.1.1 Struktur eines linearen Optimierungsproblems

3.1.2 Zeilenstufenform und Basisformen

3.1.3 Lösbarkeit eines linearen Optimierungsproblems

3.2 Simplex-Algorithmus

3.3 Zweiphasenmethode

3.4 Sensitivität und Dualität

3.4.1 Dualität

3.4.2 Complementary Slackness

3.4.3 Die duale Simplex-Methode

Zusammenfassung

Kontrollfragen

Literatur

Ganzzahlige Optimierungsprobleme

Übersicht

4.1 Lineare Probleme mit Ganzzahligkeitsforderungen

4.2 Transportprobleme

4.2.1 Anfangslösungen

4.2.2 Die Zyklenmethode

4.3 Zuordnungsprobleme

4.4 Lösungsverfahren für ganzzahlige Optimierungsprobleme

4.4.1 Lösung durch Runden

4.4.2 Schnittebenen-Verfahren

4.4.3 Branch-and-Bound-Verfahren

4.4.4 Der D

AKIN

-Algorithmus

Zusammenfassung

Kontrollfragen

Literatur

Nichtlineare Optimierung

Übersicht

5.1 Methoden der Analysis

5.1.1 Optimierungsprobleme ohne Restriktionen

5.1.2 Optimierungsprobleme mit Restriktionen

5.2 Deterministische Suchverfahren

5.2.1 Intervallschachtelung

5.2.2 Intervallhalbierung

5.2.3 N

EWTON

-Verfahren

5.2.4 Gradientenabstiegsverfahren

5.2.5 Verfahren des steilsten Abstiegs

5.2.6 Das N

EWTON

-Verfahren als Abstiegsverfahren

5.3 Simulated Annealing

5.3.1 Lokale Suche

5.3.2 Schritte des Simulated Annealing

5.3.3 Konvergenzverhalten

Zusammenfassung

Kontrollfragen

Literatur

Elemente der Spieltheorie

Übersicht

6.1 Strategische Spiele

6.1.1 N

ASH

-Gleichgewichte

6.1.2 Zwei-Personen-Nullsummenspiele

6.1.3 Symmetrische binäre Zwei-Personen-Spiele

6.2 Kooperative Spiele

6.2.1 Fragestellung und Formalisierung

6.2.2 Die N

ASH

-Lösung

6.2.3 Kritik an der N

ASH

-Lösung

6.2.4 Die monotone Verhandlungslösung

6.3 Koalitionsspiele

Zusammenfassung

Kontrollfragen

Literatur

Klausuren

Klausur 1

Klausur 2

Klausur 3

Lösungen

Klausur 1

Klausur 2

Klausur 3

Glossar

Abbildungen

Symbole und Abkürzungen

Literatur

Index

Vorwort

„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. ([email protected])

Münster, im August 2005Ulrich Kathöfer

Ulrich Müller-Funk

Vorwort zur 2. Auflage

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

1 Einführung

Übersicht

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.

1.1 Fragestellungen des Operations Research

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.

Anwendungsgebiete sind etwa:

Produktionsplanung

Transportprobleme

Flussprobleme

Routenplanung

Verschnittprobleme

Investitionsentscheidungen

Lagerhaltung

Maschinenbelegungsplanung

Warteschlangen

Marktgleichgewichte

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.

1.1.1 Modellierung

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

der Formulierung und Formalisierung des Problems,

der Durchführung des Verfahrens,

der Validierung des Ergebnisses.

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:

Ist dieses Ergebnis tatsächlich eine Antwort auf die gestellte Frage?

Kann die Lösung verwendet werden, z.B. wenn sie negative oder nichtganzzahlige Werte hat?

Würden im Modell nicht berücksichtigte Parameter das Ergebnis maßgeblich beeinflussen?

Wie ändert sich die Lösung, wenn es z.B. kleine Ungenauigkeiten in den Parametern gibt?

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.

1.1.2 Algorithmen

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

effektive Algorithmen, falls sie unter Ausnutzung der jeweiligen mathematischen Struktur nach endlich vielen Schritten zu einem Ergebnis führen. Das Erreichen dieser Lösung ist zwar sicher, es kann aber sein, dass solche Verfahren beliebig ineffizient sind, d.h. nicht in akzeptabler Zeit oder mit vertretbarem Aufwand zum Ergebnis kommen. Algorithmen, die effektiv

und

effizient sind, sind erstrebenswert.

heuristische Algorithmen, die nicht bei einer Charakterisierung von Optima ansetzen, sondern lediglich auf Plausibilitätsüberlegungen für eine Zielwertverbesserung basieren. Sie führen – zumeist in schwach strukturierten Problemen – vergleichsweise schnell zu einer Verbesserung der Anfangslösung, enden aber oft mit einer suboptimalen Lösung. Aus betriebswirtschaftlicher Sicht kann die Einsparung durch den Verzicht auf aufwändige Algorithmen oft den Verlust durch die Suboptimalität aufwiegen.

Simulations-Algorithmen, falls sie den Suchraum mit Methoden erforschen, die Zufallselemente enthalten, z.B. eine reine Zufallssuche. Die Ergebnisse sind in vielen Fällen erstaunlich gut.

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:

Maschinenbelegungsplanung, Produktionsplanung:

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.

Chip-Herstellung:

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:

Komplette Enumeration als effektives Verfahren

Heuristiken zur Anfangslösung und zur lokalen Verbesserung vgl. S. 17

Stochastische Suchverfahren vgl. S. 19

Komplette 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.

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.

Gierige Verfahren

ermitteln eine Lösung, indem sie unmittelbar erkennbare Vorteile ausnutzen. In manchen Fällen, die wir kennen lernen werden, ist damit tatsächlich ein Optimum zu finden. Oft aber resultieren aus den anfänglichen Vorteilen negative Konsequenzen in der End-Gestaltung dieser Lösung. Bei vielen Problemstellungen lässt sich dieser Ansatz verwenden, um eine gültige Anfangslösung zu ermitteln, die dann mit anderen Verfahren weiter optimiert wird.

Lokale Suchverfahren

verbessern eine gefundene Anfangslösung nur in manchen Aspekten und wiederholen eine derartige Modifikation an den sukzessive gefundenen Lösungen, bis keine Verbesserung mehr möglich ist. Oftmals sind sie als gierige Verfahren ausgelegt, d.h. es wird die beste unter den Nachbarlösungen ausgewählt. Ein Nachteil ist, dass oft suboptimale Lösungen gefunden werden, die nicht mehr lokal verbessert werden können.

Beispiele für Heuristiken im Rundreiseproblem

Eröffnungslösung nach der Methode des besten Nachfolgers:

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.

Deterministische, lokale Verbesserungsverfahren:

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

1.2 Optima

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:

eine Menge

Z

der zulässigen Lösungen (d.h. Alternativen, mögliche Aktionen, Preisfestlegungen etc.),

eine reellwertige Funktion c(

x

),

x ∈ Z

, welche die „Kosten“ (oder eine andere Zielgröße) angibt.

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:

Ist das Problem überhaupt lösbar? Dies wäre

nicht

der Fall, wenn

Z

eine leere Menge ist,

c(·) über

Z

nicht nach unten beschränkt ist,

c(·) zwar über

Z

nach unten beschränkt ist,

aber keine dieser Schranken realisiert werden kann.

Im Falle der Lösbarkeit können dann eine oder mehrere optimale Lösungen vorliegen.

Wie bestimmt man gegebenenfalls eine optimale Lösung? Hier ist nach einem konkreten, schematisierten Rechenverfahren, also dem Algorithmus gefragt. Dieses sollte sich für praktische Zwecke bequem in ein Computerprogramm überführen lassen.

Wie ein solcher Algorithmus aufgebaut ist, hängt maßgeblich von der Art des Suchraumes Z ab. Kriterien sind beispielsweise:

Z

ist ein Kontinuum. Hier wird man nach Möglichkeit Methoden der Differentialrechnung verwenden.

Z

ist endlich oder abzählbar unendlich. Solche Probleme der diskreten bzw. kombinatorischen Optimierung lassen sich z.B. durch heuristische Suchverfahren lösen.

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.

1.2.1 Diskrete Optimierungsprobleme

Beispiel 1.1:

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.6sehen wir viele Verbindungsmöglichkeiten.

Konkrete Fragestellungen könnten sein:

Wie lang ist der kürzeste Weg von Münster nach Konstanz (in Kilometern)?

Wie lange dauert die kürzeste Fahrt von Münster nach Konstanz (in Stunden)?

Wie lange müssen wir reisen, wenn wir unbedingt am Rhein entlang fahren wollen?

Um welche Zeit verlängert sich die Reise, wenn die Teilstrecke Bonn – Koblenz gesperrt ist?

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:

Weil ich in der Nacht fahre und meinen Schlaf brauche, soll die Fahrt möglichst lange dauern.

Der Bahn-Fan möchte in kurzer Zeit möglichst viele verschiedene Strecken bereisen.

Das Verkehrsministerium interessiert sich für die maximale Kapazität im Netz.

Ein Reisebüro möchte eine Deutschlandrundreise (Berlin, Heidelberg, Hamburg, München, Münster, Dresden) anbieten und interessiert sich für den günstigsten Einkaufspreis.

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.

1.2.2 Lineare Optimierungsprobleme

Beispiel 1.2:

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 alsZielfunktionbezeichnet.

Hier können für xA und xB allerdings nicht beliebig große Werte eingesetzt werden, da die Produktion ja eingeschränkt ist durch die zur Verfügung stehenden Mann-Stunden. So ergibt sich etwa aus der ersten Stufe, dass 2 · xA + 1 · xB maximal den Wert 12 ergeben darf, also 2 · xA + 1 · xB ≤ 12. Eine solche Einschränkung bezeichnet man alsNebenbedingungoderRestriktion.

Die beiden anderen Stufen der Produktion ergeben die Nebenbedingungen 2xA + 3xB ≤ 18 und xA + xB ≤ 8. Eine eigentlich immer vorausgesetzte Nebenbedingung fordert noch, dass keine negativen Mengen zu produzieren sind, also xA ≥ 0 und xB ≥ 0. Diese Forderung nennt manNichtnegativitätsbedingungen.Zusammengefasst lässt sich das Problem darstellen in der Form:

Eine Möglichkeit zur Lösung dieses Optimierungsproblems ist es, den zulässigen Bereich grafisch darzustellen und so ein Optimum zu ermitteln. Für diesen Fall sind die Nebenbedingungen in Abbildung 1.7 dargestellt. Die zulässigen Lösungen müssen in dem Bereich gesucht werden, der links von bzw. unterhalb der dünn eingezeichneten Geraden liegt (sowie über der xA - und rechts von der xB - Achse).

Abbildung 1.7:Lineares Optimierungsproblem in grafischer Darstellung

Dieses Vorgehen lässt sich verallgemeinern. Sind in einem Optimierungsproblem sowohl die Zielfunktion als auch die Nebenbedingungen linear, so ist der zulässige Bereich – auch bei mehr als zwei Variablen – der Durchschnitt von Halbebenen und damit konvex. Die Form des zulässigen Bereichs wird als Simplex bezeichnet. Die optimale Lösung liegt immer in einer Ecke.

Wir werden in Kapitel 3 vgl. S. 83 den Simplex-Algorithmus vorstellen als ein Verfahren, das ein Optimum dadurch bestimmt, dass in möglichst effizienter Weise Ecken bestimmt und auf Optimalität überprüft werden.

1.2.3 Ganzzahlige Optimierungsprobleme

Beispiel 1.3:

Ein prominentes Beispiel der ganzzahligen Optimierung ist das sogenannte „Rucksack-Problem“. Die Benennung resultiert daraus, dass man die Problemstellung anhand der folgenden Situation verdeutlichen kann.

Ein Wanderer kann in seinem Rucksack vier Gegenstände mitnehmen, deren Mitnahme für ihn jeweils mit dem Nutzen 3, 4, 2 bzw. 3 verbunden ist und die die Gewichte 3, 2, 4 bzw. 1 besitzen.

Auf welche Weise kann der Wanderer seinen Nutzen maximieren, wenn er höchstens 9 Gewichtseinheiten einpacken darf?

3x1 + 2x2 + 4x3 + x4

und darf 9 nicht überschreiten. Der Gesamtnutzen der mitgenommenen Gegenstände beträgt

3x1 + 4x2 + 2x3 + 3x4

und sollte unter der Gewichtsrestriktion maximiert werden.

Eine echte Anwendung, bei der es sogar mehr als eine Gewichtsrestriktion gibt, lässt sich im Bereich Investitionsprogrammplanung finden.

Beispiel 1.4:

Es muss entschieden werden, welche von n Projekten (Investitionsmöglichkeiten) mit Kapitalwerten c1, . . . , cnin Angriff genommen werden sollen, wenn Projekt j in Periode i Kosten aij verursacht und insgesamt in Periode i ein Budget der Höhe ri für alle Projekte zur Verfügung steht. Planungszeitraum seien die Perioden 1, . . . , m.

Das Rucksack-Problem lautet dann:

Maximierec1x1 + c2x2 + · · · + cnxn

unter den Budget-Perioden-Restriktionen

1. Periode:a11x1 + a12x2 + · · · + a1nxn ≤ r1

2. Periode:a21x1 + a22x2 + · · · + a2nxn ≤ r2

m–te Periode:am1x1 + am2x2 + · · · + amnxn ≤ rm

x1 ∈ {0, 1}, . . . , xn ∈ {0, 1}

Die Form erinnert an die eines linearen Optimierungsproblems, da sowohl Zielfunktion als auch Restriktionen lineare Funktionen bzw. (Un-)Gleichungen sind. Allerdings sind die Entscheidungsvariablen binär, d.h. xi ∈ {0, 1}. Damit wird die Lösung nicht etwa einfacher, wie man vermuten könnte, sondern tatsächlich komplizierter.

Allgemein spricht man von einem Problem der „ganzzahligen linearen Programmierung“, wenn Zielfunktion und Restriktionen linear sind, die Forderung „xi ≥ 0 ∀i“ jedoch zu „xi ∈ 0 ∀i“ verschärft wird. Bei Vernachlässigung der Ganzzahligkeit liegt dann ein gewöhnliches lineares Programm vor, das mit Hilfe des Simplex-Algorithmus gelöst werden könnte.

Man beachte jedoch, dass eine (optimale) Ecke dann nicht zulässig für das eigentliche Problem zu sein braucht. Daher führt eine solche Vorgehensweise nur in Zusammenhang mit weiteren Überlegungen zu einem iterativ arbeitenden heuristischen Verfahren (Schnittebenenverfahren, Branch-and-Bound-Techniken). Wir werden mögliche Lösungsverfahren in Kapitel 4 vgl. S. 121 kennen lernen.

1.2.4 Nichtlineare Optimierung

Oft bietet es sich an, im Modell Funktionen so zu vereinfachen, dass lineare Zusammenhänge angegeben werden können. Wenn das für Zielfunktion und Nebenbedingungen vertretbar ist, entstehen leicht lösbare Probleme der linearen Optimierung. Doch in vielen Fällen würde durch die Linearisierung das Problem so verfälscht, dass die vermeintlich optimale Lösung die Konfrontation mit der Realität nicht verträgt.

Beispiel 1.5:

Wenn ein Zusammenhang etwa nur in der Form

dargestellt werden kann, lässt sich schwerlich ein Optimum mit der linearen Optimierung finden.

Angenommen, wir suchen das Minimum dieser Funktion im Bereich von 0 bis 1. „Einfach“, sagt der mathematisch vorgebildete Leser. Man müsste doch nur die Ableitung bilden und gleich 0 setzen, dann wäre zumindest ein Kandidat für die Lösung vorhanden. Und dann wäre noch der Rand, also die Funktionswerte von 0 und 1 zu überprüfen.

Die Ableitung der Funktion lautet

Wer daraus einfach algebraisch die Nullstelle(n) ermittelt, darf sich getrost als genial bezeichnen. Tatsächlich findet man hier eine Nullstelle wohl nur numerisch (der Wert liegt in der Nähe von 0,656).

Welche verschiedenen Vorgehensweisen es für solche Fälle nichtlinearer Optimierung gibt, wird in Kapitel 5 vgl. S. 161 angesprochen.

1.2.5 Multikriterielle Optimierung

Sollen mehrere Kriterien gleichzeitig einen optimalen Wert annehmen, müssen wir etwas anders vorgehen. Bei den bislang diskutierten Optimierungsaufgaben wurde eine reellwertige Funktion als Zielgröße ausgezeichnet. Die weiteren Aspekte konnten dann in Form von Nebenbedingungen berücksichtigt werden.

Eine Variante dieser Vorgehensweise besteht darin, mehrere R-wertige Kriteriumsfunktionen f1(x), . . . , fN(x) gleichzeitig zu betrachten. Zu diesen setzt man „realistische“ Zielvorgaben z1, . . . , zN fest. Die Minimierung der Abweichungen führt dann wieder zu einem gewöhnlichen Optimierungsproblem.

Zur Umsetzung bieten sich Zielfunktionen f(x) der Form

oder

mit Gewichten w1, . . . , wN und einem geeigneten α > 0 an. Diese Methode wird als Goal Programming bezeichnet. Für eine ausführliche Diskussion sei auf WEBER [1993] verwiesen.

1.3 Gleichgewichte

Optimierungsprobleme sind vollständig beschrieben durch die Angabe der zulässigen Lösungen x ∈ Z und der Zielfunktion c(x). Zu bestimmen ist dann nur ihr optimaler Wert. Häufig sind solche Entscheidungen aber unter Risiken zu treffen. Zu unterscheiden ist hierbei zwischen

Umfeldrisiken, d.h. zufallsabhängige Schwankungen im Entscheidungsrahmen wie z.B. Wettereinflüsse oder Zinsschwankungen,

Verhaltensrisiken durch die Aktionen anderer Beteiligter, z.B. Preissenkungen von Konkurrenten, Käuferverhalten oder politische Entscheidungen.

Umfeldrisiken werden zumeist dadurch in das Kalkül mit einbezogen, dass für deren mögliche Zustände s ∈ S Eintretenswahrscheinlichkeiten p(s) spezifiziert werden. Zu bewerten ist in dieser Situation dann das Ergebnis von x und s, etwa durch c(x, s). Nach Bildung des Erwartungswertes

erhält man dann die Zielfunktion des Optimierungsproblems.