BWL-Crash-Kurs Operations Research

Dr. Ulrich Kathöfer lehrt an der Universität Münster. Prof. Dr. Ulrich Müller-Funk lehrt an der Universität Münster.

Vorwort 9

1 Einführung 11

Übersicht 11

1.1 Fragestellungen des Operations Research 11

1.1.1 Modellierung 12

1.1.2 Algorithmen 14

1.2 Optima 21

1.2.1 Diskrete Optimierungsprobleme 22

1.2.2 Lineare Optimierungsprobleme 24

1.2.3 Ganzzahlige Optimierungsprobleme 26

1.2.4 Nichtlineare Optimierung 27

1.2.5 Multikriterielle Optimierung 28

1.3 Gleichgewichte 29

1.4 Stochastische Probleme des Operations Research 34

1.4.1 Risikomodelle 34

1.4.2 Warteschlangenmodelle 35

1.4.3 Markov-Entscheidungs-Modelle 36

Zusammenfassung 38

Kontrollfragen 38

Literatur 39

2 Optimierung in Graphen 41

Übersicht 41

2.1 Relationen, Graphen, Bäume 41

2.1.1 Relationen 41

2.1.2 Graphen 44

2.1.3 Digraphen 47

2.1.4 Netzwerke 51

2.1.5 Teilbedarfsrechnung – Gozintographen 51

2.1.6 Bäume 54

2.2 Kürzeste Wege in Netzwerken 56

2.2.1 Dijkstra-Algorithmus für Digraphen 57

2.2.2 Minimal aufspannende Bäume 60

2.3 Netzplantechnik 64

2.3.1 Vorgangsliste 64

2.3.2 CPM-Netzpläne 65

2.3.3 CPM-Zeitplanung 70

2.4 Dynamische Optimierung 76

2.4.1 Problemstellung 76

2.4.2 Lösungsansatz 78

2.4.3 Erweiterungen 80

Zusammenfassung 82

Kontrollfragen 82

Literatur 82

3 Lineare Optimierung 83

Übersicht 83

3.1 Lineare Optimierungsprobleme 83

3.1.1 Struktur eines linearen Optimierungsproblems 84

3.1.2 Zeilenstufenform und Basisformen 86

3.1.3 Lösbarkeit eines linearen Optimierungsproblems 89

3.2 Simplex-Algorithmus 91

3.3 Zweiphasenmethode 101

3.4 Sensitivität und Dualität 108

3.4.1 Dualität 110

3.4.2 Complementary Slackness 111

3.4.3 Die duale Simplex-Methode 116

Zusammenfassung 120

Kontrollfragen 120

Literatur 120

4 Ganzzahlige Optimierungsprobleme 121

Übersicht 121

4.1 Lineare Probleme mit Ganzzahligkeitsforderungen 121

4.2 Transportprobleme 124

4.2.1 Anfangslösungen 128

4.2.2 Die Zyklenmethode 130

4.3 Zuordnungsprobleme 141

4.4 Lösungsverfahren für ganzzahlige Optimierungsprobleme 148

4.4.1 Lösung durch Runden 148

4.4.2 Schnittebenen-Verfahren 148

4.4.3 Branch-and-Bound-Verfahren 152

4.4.4 Der Dakin-Algorithmus 154

Zusammenfassung 159

Kontrollfragen 159

Literatur 160

5 Nichtlineare Optimierung 161

Übersicht 161

5.1 Methoden der Analysis 161

5.1.1 Optimierungsprobleme ohne Restriktionen 162

5.1.2 Optimierungsprobleme mit Restriktionen 164

5.2 Deterministische Suchverfahren 170

5.2.1 Intervallschachtelung 170

5.2.2 Intervallhalbierung 171

5.2.3 Newton-Verfahren 172

5.2.4 Gradientenabstiegsverfahren 173

5.2.5 Verfahren des steilsten Abstiegs 174

5.2.6 Das Newton-Verfahren als Abstiegsverfahren 175

5.3 Simulated Annealing 176

5.3.1 Lokale Suche 177

5.3.2 Schritte des Simulated Annealing 179

5.3.3 Konvergenzverhalten 181

Zusammenfassung 183

Kontrollfragen 183

Literatur 183

6 Elemente der Spieltheorie 185

Übersicht 185

6.1 Strategische Spiele 185

6.1.1 Nash-Gleichgewichte 185

6.1.2 Zwei-Personen-Nullsummenspiele 193

6.1.3 Symmetrische binäre Zwei-Personen-Spiele 195

6.2 Kooperative Spiele 200

6.2.1 Fragestellung und Formalisierung 200

6.2.2 Die Nash-Lösung 204

6.2.3 Kritik an der Nash-Lösung 206

6.2.4 Die monotone Verhandlungslösung 207

6.3 Koalitionsspiele 209

Zusammenfassung 214

Kontrollfragen 214

Literatur 214

Klausuren 215

Klausur 1 215

Klausur 2 219

Klausur 3 222

Lösungen 225

Klausur 1 225

Klausur 2 231

Klausur 3 236

Glossar 241

Abbildungen 246

Symbole und Abkürzungen 249

Literatur 251

Index 253