Während die vordergründigen Handwerkszeuge des Informatikers, Software und Hardware, einem kaum greifbaren Wandel unterliegen - was heute gelernt wird, ist morgen schon wieder veraltet - stehen die zugrunde legenden Strukturen als unverrückbare Invarianten fest. Ihr Verständnis stellt somit eine notwendige Bedingung sowohl für tiefer gehende Einsichten, als auch für einen verstandesgemäßen Gebrauch der Anwendungen dar.
In der Informatik sind diese Strukturen insbesondere die Logik und daran anknüpfend der Algorithmus. Beide haben eine mehr als zweitausendjährige Geschichte (vgl. den berühmten Euklid'schen Divisionalalgorithmus!).
Während diese Begriffe allgemein im Rahmen der Theoretischen Informatik abgehandelt werden, sollen hier nun darauf aufbauend, exemplarisch konkrete Algorithmen und insbesondere die fundamentalen Entwurfstechniken dargestellt werden. Diese wurden im Wesentlichen in den sechziger Jahren des vorigen Jahrhunderts entwickelt und gelten bis heute unverändert.
Entsprechend dem Studiengang Wirtschaftsinformatik, für den diese Vorlesung konzipiert ist, werden beispielhaft einige ökonomische Anwendungen aufgezeigt.
Die Monographie stellt die Grundlage einer dreißigstündigen Vorlesung an der Dualen Hochschule Mosbach dar. Sie schließt an die Vorlesung über theoretische Informatik an und setzt Grundlagen in diesem Bereich im Wesentlichen voraus.
Inhaltsverzeichnis
0 Einführung
1 Lineare Optimierung
1.1 Beispiel
1.2 Graphische Lösung
1.3 Der Simplex-Algorithmus
1.4 Das Simplex-Tableau
1.5 Der Allgemeine Simplex-Algorithmus für den Grundtypus
1.6 Beispiel bei mehrstufiger Kuppelproduktion
1.7 Aufgaben
Aufgabe 1
Aufgabe 2
Aufgabe 3
Augabe 4
Aufgabe 5
Lösung Aufgabe 2
Lösung Aufgabe 3
2 Heuristisches Verfahren am Beispiel des Travelling Salesman Problems
2.1 Das Travelling Salesman Problem
2.2 Heuristische Verfahren
2.2.1 Das Verfahren des „besten Nachfolgers“
2.2.2 „Die sukzessive Einbeziehung von Stationen“
3 Dynamische Programmierung am Beispiel des Travelling Salesman Problem
3.1 Erläuterung der Methode am Beispiel
3.2 Der Algorithmus der dynamischen Programmierung für das Travelling Salesman Problem
3.3 Das allgemeine Prinzip der dynamischen Programmierung
3.4 Aufgaben
4 Die Methode „Branch and Bound“ am Beispiel des Travelling Salesman Problems
4.1 Die allgemeine Methode am Beispiel des „0-1 Rucksack Problems“
4.2 Anwendung des Prinzips „Branch and Bound“ auf das Travelling Salesman Problem
4.3 Aufgaben
Aufgabe 1
Aufgabe 2
Aufgabe 3
Aufgabe 4
Zielsetzung & Themen
Das Buch vermittelt eine praxisnahe Einführung in das Operations Research, mit dem primären Ziel, Studierenden die wesentlichen Algorithmen und Entwurfstechniken näherzubringen. Durch konkrete ökonomische Anwendungsbeispiele wird aufgezeigt, wie komplexe Problemstellungen in mathematische Modelle überführt und durch systematische Methoden gelöst werden können.
- Grundlagen der linearen Optimierung und des Simplex-Algorithmus.
- Einsatz heuristischer Verfahren zur Lösung schwieriger Kombinatorikprobleme.
- Anwendung der dynamischen Programmierung bei Optimierungsaufgaben.
- Einführung in die Branch-and-Bound-Methode zur Lösung diskreter Probleme.
Auszug aus dem Buch
1.2 Graphische Lösung:
Wir beziehen uns auf das Beispiel in 1.1.
Umformen der Zielfunktion (Z) in die Hauptform der Geradengleichung:
(Z) <=> x2 = - 4/3 x1 + z / 1,5
Für konkrete Werte von z erhält man dann beispielsweise folgende Geraden, die jeweils denselben Gewinn liefern (Isogewinnlinien):
z1 = 90 ; x2 = - 4/3 x1 + 60 ; z.B. für (30/20)
z2 = 120 ; x2 = - 4/3 x1 + 90 ; z.B. für (30/40)
Allgemein erkennt man, dass der Gewinn so lange gesteigert werden kann, solange die Isogewinnlinie der Zielfunktionsgeraden parallel verschoben werden kann und dabei noch Punkte des Definitionsbereichs erfasst.
Hieraus ergibt sich insbesondere:
„Der Lösungspunkt befindet sich stets in einem Eckpunkt“
Zusammenfassung der Kapitel
0 Einführung: Klärung der Begriffe „Operations“ und „Research“ sowie Zielsetzung der Vorlesung.
1 Lineare Optimierung: Vermittlung von Modellbildung, graphischer Lösung und dem Simplex-Algorithmus anhand von Produktionsplanungsbeispielen.
2 Heuristisches Verfahren am Beispiel des Travelling Salesman Problems: Diskussion von Näherungsverfahren für komplexe Probleme, bei denen exakte Lösungen zu aufwendig sind.
3 Dynamische Programmierung am Beispiel des Travelling Salesman Problem: Erklärung des Optimierungsprinzips zur systematischen Lösung des Problems durch Teilentscheidungen.
4 Die Methode „Branch and Bound“ am Beispiel des Travelling Salesman Problems: Erläuterung des systematisches Aufteilungs- und Schätzverfahrens zur Lösung diskreter Optimierungsprobleme.
Schlüsselwörter
Operations Research, Lineare Optimierung, Simplex-Algorithmus, Travelling Salesman Problem, Dynamische Programmierung, Branch and Bound, Rucksackproblem, Heuristik, Zielfunktion, Nebenbedingungen, Kombinatorik, Optimierung, Algorithmus, Modellbildung, Kuppelproduktion
Häufig gestellte Fragen
Worum geht es in diesem Buch grundsätzlich?
Das Buch dient als Einführung in das Operations Research und behandelt mathematische Methoden zur Lösung betriebswirtschaftlicher Optimierungsprobleme.
Welche zentralen Themenfelder werden abgedeckt?
Die Schwerpunkte liegen auf der linearen Optimierung, der dynamischen Programmierung sowie heuristischen und exakten Verfahren wie Branch and Bound.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist es, den Leser mit klassischen Algorithmen und Entwurfstechniken vertraut zu machen, um ökonomische Fragestellungen methodisch fundiert lösen zu können.
Welche wissenschaftliche Methode wird primär verwendet?
Die Arbeit nutzt mathematische Modellbildung sowie algorithmische Lösungsverfahren aus dem Bereich der mathematischen Optimierung.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die vier großen Kapitel zur linearen Optimierung, heuristischen Verfahren, dynamischen Programmierung und Branch and Bound, jeweils illustriert durch Praxisbeispiele.
Welche Schlüsselwörter charakterisieren das Werk?
Zu den prägenden Begriffen zählen Simplex-Algorithmus, Travelling Salesman Problem, Optimierung und methodische Lösungsansätze für NP-schwere Probleme.
Was ist das Besondere am Travelling Salesman Problem im Kontext dieses Buches?
Es dient als durchgängiges Beispiel, um verschiedene methodische Ansätze wie Heuristiken, dynamische Programmierung und Branch and Bound direkt miteinander vergleichbar zu machen.
Warum wird das Rucksackproblem als Beispiel für Branch and Bound genutzt?
Es eignet sich hervorragend, um die Prinzipien der Zerlegung (Branching) und der Abschätzung (Bounding) zur Reduktion des Suchbaums in einem anschaulichen 0-1-Problem darzustellen.
- Citar trabajo
- Dr. Wolfgang Schlageter (Autor), 2003, Einführung in das Operations Research, Múnich, GRIN Verlag, https://www.grin.com/document/208600
