nach oben

2018 | Buch

Lineare Optimierung – eine anwendungsorientierte Einführung in Operations Research

verfasst von: Dr. Andreas Koop, Prof. Dr. Hardy Moock

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Leicht verständlich und praxisorientiert behandelt das vorliegende Buch die wesentlichsten Gebiete der Linearen Optimierung, einem Kernbereich des Operations Research. Es wendet sich an Studierende betriebswirtschaftlicher und technischer Disziplinen. Aber auch der Praktiker aus kleinen und mittelständischen Unternehmen wird in hohem Maße davon profitieren. Da kaum mathematische Kenntnisse vorausgesetzt werden, fällt es gerade ihm leicht, sich selbstständig in die Lineare Programmierung einzuarbeiten, die erhebliche Kostensenkungen und Zeiteinsparungen ermöglicht. Auch Studierende der Mathematik und der Informatik werden durch das Buch angesprochen, da sie sehr schnell einen Überblick über die Lineare Programmierung gewinnen können. Kurz und prägnant, dabei vollständig und mathematisch exakt, werden die Methoden hergeleitet, rezeptartig zusammengefasst, durch zahlreiche Beispiele und Übungsaufgaben ergänzt und mit zwei Fallstudien aus der betriebswirtschaftlichen und technischen Praxis angereichert. Nicht zu vergessen die softwaretechnische Umsetzung der Linearen Programme mittels Excel-Solver bzw. der Programmiersprache C. Dieses Buch ist ein Muss für jeden, der in die Thematik der Linearen Optimierung einsteigen möchte.

Inhaltsverzeichnis

Frontmatter

1. Einführung

Zusammenfassung

In Kapitel 1 wird erklärt wie der Begriff Operations entstanden ist und was man darunter versteht. Anschließend wird die Vorgehensweise im Rahmen eines OR-gestützten Planungsprozesses erläutert. Anhand von einigen speziellen Beispielen wird die für den Einsatz von OR-Methoden wichtige Modellbildung näher beschrieben.

Andreas Koop, Hardy Moock

2. Mathematische Grundlagen

Zusammenfassung

In diesem Kapitel behandeln wir einige wichtige mathematische Grundlagen, insbesondere Algorithmen zur Lösung linearer Gleichungssysteme, auf denen diverse Rechenverfahren des Operations Research basieren.

Andreas Koop, Hardy Moock

3. Lineare Optimierung

Zusammenfassung

Im 3. Kapitel wird das wichtigste Verfahren der Linearen Optimierung, das Simplex- Verfahren, ausführlich behandelt. Nach der Definition des linearen Modells wird zunächst gezeigt, wie sich Probleme mit zwei Variablen graphisch lösen lassen. Anschließend werden die für die weiteren Betrachtungen erforderlichen Begriffe wie Normalform eines Linearen Programms, Basislösung, Konvexkombination usw. eingeführt. Nach diesen Vorbereitungen werden zunächst das Primalsimplex-Verfahren für das spezielle Maximumproblem und danach das Dualsimplex-Verfahren für das spezielle Minimumproblem hergeleitet. Ein größerer Abschnitt ist dem Thema Dualität gewidmet. Hier wird insbesondere auf die ökonomische Interpretation des Zusammenhangs zwischen primalem und dualem Optimierungsproblem eingegangen. Zum Abschuss wird das Zweiphasen-Simplex-Verfahren zum Lösen eines allgemeinen linearen Problems präsentiert. Zahlreiche Beispiele und Übungen zu den vorgestellten Algorithmen runden das Kapitel ab.

Andreas Koop, Hardy Moock

4. Innere-Punkt-Verfahren

Zusammenfassung

Ein Nachteil des Simplex-Verfahrens besteht darin, dass der Aufwand exponentiell mit der Größe des Problems wachsen kann. Auch wenn dieser Nachteil bei den meisten praxisrelevanten Problemen nicht zum Tragen kommt, führte er dazu, dass man nach Alternativen zu diesem Verfahren suchte. Es wurden verschiedene Methoden entwickelt, die man zusammenfassend als Innere-Punkt-Verfahren bezeichnet. Dieses Kapitel beinhaltet eine Einführung in die diesen Verfahren zugrundeliegenden Ideen.

Andreas Koop, Hardy Moock

5. Transportprobleme

Zusammenfassung

In Zeiten zunehmender Globalisierung steht die Wirtschaft tagtäglich vor der Herausforderung, Güter von verschiedenen Versandorten zu mehreren Empfangsorten zu transportieren. Die dabei entstehenden Kosten sind so gering wie möglich zu kalkulieren. Setzt man die Problemstellung in ein mathematisches Modell um, so erhält man ein lineares Optimierungsproblem mit einer speziellen Struktur, das sich in eigens dafür vorgesehenen Transporttableaus sehr kompakt darstellen lässt. In diesem Kapitel werden Verfahren vorgestellt, die die gegebene Struktur dieser Probleme ausnutzen und dadurch effizienter sind als der Simplex-Algorithmus.

Andreas Koop, Hardy Moock

6. Zuordnungsprobleme

Zusammenfassung

Beim Zuordnungsproblem geht es um die paarweise Zuordnung von Elementen aus zwei unterschiedlichen Mengen. Damit handelt es sich um einen Spezialfall des klassischen Transportproblems (vgl. Kap. 5) mit \(m=n\), \(a_{i}=1\) und \(b_{j}=1\). Das hier vorgestellte Verfahren zum Lösen von Zuordnungsproblemen, die Ungarische Methode, geht auf den Mathematiker H. W. Kuhn zurück (vgl. Kuhn 1955).

Andreas Koop, Hardy Moock

7. Parametrische lineare Programmierung

Zusammenfassung

Wir betrachten in diesem Kapitel lineare Programme, bei denen die Koeffizienten der Zielfunktion und der rechten Seite reelle Parameter enthalten. Ziel ist es, die Lösung des LPs in Abhängigkeit von diesen Parametern zu bestimmen. Dabei orientieren wir uns an der Vorgehensweise in Dinkelbach 1969. In diesem Werk wird die parametrische lineare Programmierung ausführlich behandelt. Neben den im Folgenden angegebenen Definitionen findet man dort weitere Erläuterungen zum mathematischen Hintergrund. Insbesondere wird auf charakteristische Eigenschaften der Lösungen von Problemstellungen mit Parametern eingegangen. Darüber hinaus wird der Fall von Parametern in der Koeffizientenmatrix untersucht, den wir hier nicht erörtern werden.

Andreas Koop, Hardy Moock

8. Ganzzahlige Probleme

Zusammenfassung

Probleme mit ganzzahligen Variablen sind weitaus schwieriger zu lösen als Probleme mit reellen Variablen. Bei ganzzahligen Problemen kann mit wachsender Anzahl von Variablen der Lösungsaufwand, d. h. der Speicherplatzbedarf und die Laufzeit, exponentiell ansteigen. Für viele Probleme reicht es aus, wenn man sich auf das Berechnen einer reellen Lösung beschränkt, auch wenn die Variablen streng genommen ganzzahlig sein sollten. Man rundet dann einfach auf die nächste ganze Zahl und erhält so eine zwar nicht exakte, aber dennoch zufriedenstellende Lösung. Für andere Probleme, z. B. das Knapsack-Problem, ist die Bedingung der Ganzzahligkeit unabdingbar. In diesem Abschnitt wollen wir diesen Sachverhalt etwas genauer untersuchen und ein Verfahren zur Lösung ganzzahliger Probleme vorstellen.

Andreas Koop, Hardy Moock

9. Fallstudien aus der Praxis

Zusammenfassung

In den vorangegangenen Kapiteln haben wir aufgezeigt, wie man von einer gegebenen Problemstellung zu einem adäquaten mathematischen Modell gelangt und wie man es mit den vorgestellten Verfahren lösen kann. Zahlreiche Anwendungsbeispiele wurden zur Verdeutlichung und Vertiefung des Stoffes besprochen, sie sollten aber auch darlegen, wo in der Praxis und bei welcher Art von Aufgabenstellung die beschriebenen Methoden zum Tragen kommen. Bei der Auswahl der Beispiele entschieden wir uns bewusst für solche Probleme, die zu kleinen mathematischen Modellen führten und die in der Regel für die Berechnung von Hand geeignet waren. In diesem Kapitel stellen wir jetzt zwei Fallstudien vor, die bezüglich Umfang und Komplexität weit über das bisher Betrachtete hinausgehen, in Kooperation mit industriellen Partnern entwickelt wurden und in der Praxis eingesetzt werden.

Andreas Koop, Hardy Moock

10. Verwendung des Excel-Solvers

Zusammenfassung

In den vorangegangenen Kapiteln haben wir den Umfang der mathematischen Modelle immer so weit eingeschränkt, dass sie noch mit Handrechnung zu lösen waren. Um aber die vorgestellten Algorithmen effizient auf größere Problemstellungen anwenden zu können, ist der Einsatz von Computern unerlässlich. Dass man dabei durchaus auch auf Standardprogramme zurückgreifen kann, zeigt dieses Kapitel.

Ein nützliches Hilfsmittel zur Lösung Linearer Probleme bietet das weitverbreitete Tabellenkalkulationsprogramm Excel der Firma Microsoft (vgl. www.microsoft.de). Der sogenannte Solver, ein Bestandteil des Excel-Programms, enthält alle dazu benötigten Routinen und hat sich als stabil und flexibel erwiesen. Andere Tabellenkalkulationsprogramme mit entsprechenden Optimierungs-Add-Ins funktionieren im Prinzip ähnlich, sind jedoch weniger im Einsatz.

Andreas Koop, Hardy Moock

11. C-Programme

Zusammenfassung

In diesem Kapitel sollen einige der besprochenen Algorithmen als Fragmente von C-Programmen dargestellt werden. Wir haben uns bewusst für eine vereinfachte Form entschieden und uns auf wesentliche Funktionen beschränkt, um die Programme für den Leser leichter verwendbar zu machen. Auf die Optimierung hinsichtlich der Geschwindigkeit, der Effizienz und der numerischen Stabilität wurde zugunsten der Verständlichkeit verzichtet.

Andreas Koop, Hardy Moock

12. Lösungen zu den Übungsaufgaben

Zusammenfassung

Dieses Kapitel beinhaltet die ausführlichen Lösungen zu allen gestellten Übungsaufgaben.

Andreas Koop, Hardy Moock

Backmatter

Titel: Lineare Optimierung – eine anwendungsorientierte Einführung in Operations Research
verfasst von: Dr. Andreas Koop
Prof. Dr. Hardy Moock
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-56141-6
Print ISBN: 978-3-662-56140-9
DOI: https://doi.org/10.1007/978-3-662-56141-6