Der Rechenaufwand beim Simplexalgorithmus hängt wesentlich von der Strategie der Wahl des Pivotelementes (dem so genannten Pricing) ab (vgl. [Müller-Merbach 1970] [S. 207 ]). Bisher wurden zahlreiche Varianten des dualen Simplexalgorithmus vorgestellt, welche sich durch ihre Pricing-Strategien unterscheiden. Eine dieser Strategien ist das Steepest Edge Pricing. Gegenstand dieser Arbeit ist die Vorstellung und Verdeutlichung dieses Ansatzes und einige seiner Varianten, welche auf unterschiedlichen Darstellungen des zu optimierenden Problems basieren. Die vorliegende Arbeit ist wie folgt aufgebaut: Zunächst werden in Kapitel 2 einige der für diese Arbeit relevanten Grundlagen des Simplexalgorithmus eingeführt. In diesem Zusammenhang erfolgt die Beschreibung der algorithmischen Vorgehensweise des dualen Simplex sowie einiger Pricingstrategien. In Kapitel 3 wird das Steepest Edge Pricing veranschaulicht und drei Varianten des dualen Steepest Edge Simplexalgorithmus vorgestellt. Kapitel 4 enthält die Beschreibung ausgewählter Testergebnisse, welche [Forrest und Goldfarb 1992] beim Vergleich der Laufzeiten verschiedener Simplexvarianten erzielt haben. Anschließend folgt eine Zusammenfassung der wesentlichen Ergebnisse dieser Arbeit.
Inhaltsverzeichnis
- 1 Einleitung
- 2 Grundlagen
- 2.1 Der duale Simplexalgorithmus
- 2.1.1 Ablauf des Algorithmus
- 2.2 Pricing-Strategien.
- 2.1 Der duale Simplexalgorithmus
- 3 Der duale Steepest Edge Simplexalgorithmus
- 3.1 Grafische Veranschaulichung
- 3.2 Duales Problem in einfacher Form.
- 3.3 Duales Problem mit Schlupfvariablen
- 3.4 Duales Problem mit Oberschranken
- 4 Vergleich der Pricing-Strategien
- 4.1 Testumgebung.
- 4.2 Testergebnisse
- 5 Zusammenfassung
Zielsetzung und Themenschwerpunkte
Diese Arbeit befasst sich mit dem dualen Steepest Edge Simplexalgorithmus, einer Variante des Simplexalgorithmus, die sich durch ihre effiziente Pricing-Strategie auszeichnet. Sie analysiert den Algorithmus und stellt verschiedene Ansätze vor, die auf unterschiedlichen Darstellungen des zu optimierenden Problems basieren.
- Der duale Simplexalgorithmus und seine grundlegenden Prinzipien
- Das Steepest Edge Pricing und seine Anwendung im dualen Simplexalgorithmus
- Verschiedene Varianten des dualen Steepest Edge Simplexalgorithmus
- Vergleich der Effizienz verschiedener Pricing-Strategien
- Die praktische Anwendung des dualen Steepest Edge Simplexalgorithmus in der Optimierung
Zusammenfassung der Kapitel
Kapitel 2 stellt die Grundlagen des Simplexalgorithmus vor, einschließlich des dualen Simplexalgorithmus und verschiedener Pricing-Strategien. Kapitel 3 beleuchtet das Steepest Edge Pricing und präsentiert drei Varianten des dualen Steepest Edge Simplexalgorithmus, die auf unterschiedlichen Darstellungen des Problems basieren. Kapitel 4 analysiert Testergebnisse, die beim Vergleich der Laufzeiten verschiedener Simplexvarianten erzielt wurden.
Schlüsselwörter
Dualer Simplexalgorithmus, Steepest Edge Pricing, Pricing-Strategien, Optimierung, Lineare Programmierung, Testumgebung, Testergebnisse.
- Arbeit zitieren
- Diplom Wirtschaftsinformatiker Youssef El Haoum (Autor:in), 2005, Der duale Steepest Edge Simplex Algorithmus, München, GRIN Verlag, https://www.hausarbeiten.de/document/34431
