Der Simplex Algorithmus ist eine Methode der linearen Optimierung. Er wird zur Portfoliooptimierung, Logistikoptimierung, Verschnittreduktion, Mischoptimierung, Produktionsoptimierung, Personalplanung, in der Spieltheorie und in vielen weiteren Bereichen verwendet.
In diesem Buch wird die Simplex Methode an einfachen, nachvollziehbaren Praxisbeispielen erklärt. Es geht darum, ein anspruchsvolles Thema leicht zugänglich zu machen.
Im ersten Teil wird auf die Vorbereitung zur darauf hin folgenden Aufstellung des Mathematischen Modells eingegangen. Der zweite Teil beschäftigt sich mit dem dualen und primalen Simplex Algorithmus, um dann im nachfolgenden Kapitel auf Probleme einzugehen, die bei der Berechnung auftreten können. Zum Ende hin wird auf die Sensitivitätsanalyse, welche bei der Interpretation der Optimalen Lösungen eine Rolle spielt, eingegangen. Die letzten beiden Abschnitte beschäftigen sich mit der Mehrfachzielsetzung, denn Unternehmen haben für gewöhnlich nicht nur ein Ziel, sowie mit der Praxisrelevanz des Simplex Algorithmus.
Inhaltsverzeichnis
Optimierung allgemein
1. Das allgemeine Vorgehen, bevor der Algorithmus durchlaufen wird
1.1 Die Entscheidungsvariablen
1.2 Die Nebenbedingungen und die Zielfunktion "F"
1.2.1 ≤ Bedingungen
1.2.2 ≥ Bedingungen
1.2.3 Gleichungen als Nebenbedingungen
1.2.4 Besondere Nebenbedingungen
1.2.5 Die Zielfunktion "F"
1.3 Die Normalform
2. Primale und duale Iterationen
2.1 Der primale Simplex Algorithmus
2.2 Der duale Simplex Algorithmus
3. Probleme bei der Lösungsfindung
3.1 Primale Degeneration
3.2 Duale Degeneration
3.3 Unlösbarkeit und unendlich viele Lösungen
4. Neue Nebenbedingungen & Sensitivitätsanalyse
4.1 Einfügen einer neuen Nebenbedingung
4.2 Die Schattenpreise und die reduzierten Kosten
4.3 Wie weit darf sich „bi“ ändern bis sich die Basis ändert?
4.4 Wie weit darf sich „cj“ ändern, bis sich die Basis ändert?
5. Mehrfachzielsetzung
5.1 Lexikographische Zielhierarchie
5.2 Nebenziele als Nebenbedingung
5.3 Die Gewichtung der Ziele
6. Konklusion
6.1 Praxisrelevanz
6.2 Wann werden welche Iterationen benutzt?
Zielsetzung und Themen
Die vorliegende Arbeit hat zum Ziel, den Simplex-Algorithmus als Instrument des Operations Research praxisnah und verständlich zu vermitteln. Im Kern steht die Beantwortung der Frage, wie Unternehmen unter gegebenen linearen Nebenbedingungen und Zielfunktionen eine exakte, optimale Lösung für ihre Problemstellungen finden können.
- Methodische Einführung in den primalen und dualen Simplex-Algorithmus.
- Detaillierte Analyse der Lösungsfindung und deren potenzielle Schwierigkeiten wie Degeneration.
- Durchführung einer Sensitivitätsanalyse zur Bewertung von Kapazitätsänderungen.
- Erweiterung der Optimierungsansätze durch Integration von Mehrfachzielsetzungen.
- Verknüpfung der theoretischen Grundlagen mit der betriebswirtschaftlichen Praxis.
Auszug aus dem Buch
2.1 Der primale Simplex Algorithmus
Folgendes Optimierungsproblem ist gegeben:
Maschinenkapazität : 2x1 + x2 ≤ 150
Budget : x1 + 3x2 ≤ 300
Absatzpotential : x1 ≤ 150
F : 5x1 + 4x2
Das Simplex-Tableau wird nach den Vorgaben von 1. 3 aufgebaut. Hierzu wird eine erweiterte Koeffizientenmatrix aus der Koeffizientenmatrix (A) der Strukturvariablen, einer Einheitsmatrix (I) aus den Schlupfvariablen, sowie einem Vektor (b) aus den Konstanten aufgestellt. Es handelt sich um eine (m *(n + m + 1)) Matrix, wobei m die Anzahl der linearen (unabhängigen) Nebenbedingungen und n die Anzahl der Variablen ist. Plus eins entsteht wegen dem Konstantenvektor b.
Zusammenfassung der Kapitel
Optimierung allgemein: Einführung in die ökonomische Relevanz der linearen Optimierung und Abgrenzung des Simplex-Algorithmus von bloßen Annäherungsmethoden.
1. Das allgemeine Vorgehen, bevor der Algorithmus durchlaufen wird: Erläuterung der Identifikation von Entscheidungsvariablen sowie der korrekten Definition von Nebenbedingungen und Zielfunktionen.
2. Primale und duale Iterationen: Detaillierte Darstellung der Berechnungsschritte des primalen und dualen Simplex-Algorithmus zur Erreichung einer optimalen Basislösung.
3. Probleme bei der Lösungsfindung: Erörterung der Ursachen für Nicht-Optimallösungen wie Degeneration oder Unlösbarkeit in einem System.
4. Neue Nebenbedingungen & Sensitivitätsanalyse: Untersuchung der Auswirkungen von Änderungen der Rahmenbedingungen oder Kapazitäten auf das bestehende Optimum durch Schattenpreise und Opportunitätskosten.
5. Mehrfachzielsetzung: Darstellung verschiedener Strategien wie Zielhierarchien oder Zielgewichtungen, um konkurrierende Unternehmensziele simultan zu optimieren.
6. Konklusion: Abschließende Einordnung der Praxisrelevanz des Algorithmus in der modernen Unternehmensführung und Zusammenfassung der Anwendungslogik.
Schlüsselwörter
Simplex-Algorithmus, Operations Research, Lineare Optimierung, Entscheidungsvariablen, Zielfunktion, Nebenbedingungen, Sensitivitätsanalyse, Basislösung, Schattenpreise, Degeneration, Mehrfachzielsetzung, Kapazitätsbeschränkung, Opportunitätskosten, Schlupfvariable, Normalform.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Anwendung des Simplex-Algorithmus, einem exakten Verfahren zur Lösung linearer Optimierungsprobleme in wirtschaftlichen Kontexten.
Welche zentralen Themenfelder werden abgedeckt?
Die zentralen Themen umfassen die Vorbereitung von Optimierungsproblemen, die rechnerische Durchführung der Simplex-Iterationen, den Umgang mit Degenerationserscheinungen sowie die Sensitivitätsanalyse.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist es, dem Leser ein grundlegendes Verständnis für die Funktionsweise und Interpretation des Simplex-Algorithmus zu vermitteln, um Optimierungsprobleme in der Praxis selbstständig bearbeiten zu können.
Welche wissenschaftliche Methode kommt zum Einsatz?
Es wird das mathematische Verfahren der linearen Optimierung mittels des primalen und dualen Simplex-Algorithmus angewandt, unterstützt durch grafische Darstellungen und tabellarische Berechnungen.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die Aufstellung von Modellen, die Durchführung von Iterationen, die Fehleranalyse bei der Lösungsfindung sowie die Erweiterung auf Mehrfachzielsetzungen und Sensitivitätsbetrachtungen.
Durch welche Schlüsselwörter lässt sich der Inhalt charakterisieren?
Wesentliche Begriffe sind Simplex-Algorithmus, Zielfunktion, Nebenbedingungen, Basislösung, Sensitivitätsanalyse und Schattenpreise.
Wie unterscheidet sich der primale vom dualen Simplex-Algorithmus?
Der primale Algorithmus geht von einer primär zulässigen Lösung aus und verbessert diese iterativ, während der duale Simplex-Algorithmus vorwiegend dann eingesetzt wird, wenn das Starttableau nicht sofort eine zulässige Basislösung bereitstellt.
Wann ist eine Lösung als "degeneriert" zu bezeichnen?
Eine Degeneration liegt vor, wenn im Optimaltableau Basisvariablen den Wert Null annehmen, was darauf hindeutet, dass das Optimum auf mehr als einem Punkt liegen kann, beispielsweise auf einer Linie oder Fläche.
Welchen Zweck erfüllt die Sensitivitätsanalyse?
Sie dient dazu, zu bewerten, wie sich Änderungen bei den Kapazitäten oder den Zielfunktionskoeffizienten auf die bereits gefundene optimale Lösung auswirken, ohne das gesamte Modell von Grund auf neu rechnen zu müssen.
Wie gehen Unternehmen mit konkurrierenden Zielen um?
Unternehmen können dies durch Methoden wie die lexikographische Zielhierarchie, die Definition von Nebenzielen als Restriktionen oder eine Gewichtung der Ziele innerhalb der Zielfunktion lösen.
- Quote paper
- Bachelor of Arts Frank Raulf (Author), 2012, Der Simplex Algorithmus leicht gemacht!, Munich, GRIN Verlag, https://www.grin.com/document/199030
