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
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 & Themen
Die vorliegende Seminararbeit untersucht die Effizienz verschiedener Pricing-Strategien innerhalb des dualen Simplexalgorithmus, mit einem besonderen Fokus auf den dualen Steepest Edge Simplexalgorithmus. Ziel ist es, die theoretischen Ansätze der steilsten Kante zu verdeutlichen und aufzuzeigen, wie durch effiziente Updateformeln der Rechenaufwand zur Bestimmung dieser Kanten minimiert werden kann, um eine leistungsfähigere Optimierung linearer Probleme zu erreichen.
- Grundlagen des dualen Simplexalgorithmus und der Pricing-Strategien
- Methodik des Steepest Edge Pricings und seine grafische Interpretation
- Herleitung von Updateformeln für verschiedene duale Problemstellungen
- Vergleichende Analyse der Laufzeiten und Iterationszahlen gegenüber anderen Strategien
Auszug aus dem Buch
3.1 Grafische Veranschaulichung
Sei ein LP in der Form von (P2) gegeben. Fur eine primal zulässige Basislösung gilt nach (2.1)
xB = B−1b − B−1ANxN
Fur die Zielfunktion gilt
z = cTBxB + cTNxN Substitution von xB in z ergibt
z = cTB B−1b − cTB B−1ANxN + cTNxN
z = cTB B−1b + (cTN − cTB B−1AN)xN
Die Anderung des Zielfunktionswertes hängt von der neuen Basisvariable ab, also von der Anderung des Terms (cTN − cTB B−1AN)xN . Die reduzierten Kosten einer Nichtbasisvariable xj sind somit:
c¯j = cj − cTB B−1Aj (3.1)
Die Gleichung (3.1) lässt sich (unter der Annahme, dass die ersten m Variablen in der Basis sind) in der Matrixform folgendermaßen schreiben:
c¯j = (cTB, cTN) −B−1AN I e(j−m) (3.2)
Sei ηj = −B−1AN I e(j−m), dann ist (3.2) äquivalent zu ¯cj = cTηj. Die Bestimmung der in die Basis aufzunehmenden Nichtbasisvariable erfolgt mit Hilfe der reduzierten Kosten ¯cj. Bei dem primalen Steepest Edge Pricing wird jene Nichtbasisvariable gewählt, welche negative reduzierte Kosten aufweist und die Bedingung
cTηq / ||ηq|| = min j>m { cTηj / ||ηj|| } (3.3)
erfüllt (vgl. [Forrest und Goldfarb 1992][S. 344]).
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Problematik des Rechenaufwands bei der Wahl des Pivotelements ein und skizziert den Aufbau der Arbeit.
2 Grundlagen: Hier werden die theoretischen Voraussetzungen des dualen Simplexalgorithmus sowie grundlegende Pricing-Strategien wie das Dantzig- und Devex-Pricing erläutert.
3 Der duale Steepest Edge Simplexalgorithmus: In diesem Hauptteil wird das Steepest Edge Pricing detailliert beschrieben, grafisch veranschaulicht und mathematisch auf verschiedene Problemformen wie einfache duale Probleme, Probleme mit Schlupfvariablen und Oberschranken angewendet.
4 Vergleich der Pricing-Strategien: Dieses Kapitel präsentiert eine vergleichende Analyse der Testumgebungen und Ergebnisse, welche die Effizienzvorteile der untersuchten Algorithmen belegen.
5 Zusammenfassung: Die Arbeit schließt mit einer Synthese der Ergebnisse, die bestätigt, dass der Effizienzvorteil des Steepest Edge Pricings durch den Einsatz von Updateformeln in der Praxis realisierbar ist.
Schlüsselwörter
Lineare Optimierung, Simplexalgorithmus, Dualer Simplex, Steepest Edge Pricing, Pricing-Strategie, Pivotregel, Rechenaufwand, Updateformeln, Mathematische Optimierung, Operations Research, Basislösung, Nichtbasisvariablen.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der effizienten Gestaltung des Simplexalgorithmus, speziell mit dem sogenannten Steepest Edge Pricing, um die Anzahl der Iterationen bei der Lösung linearer Optimierungsprobleme zu reduzieren.
Was sind die zentralen Themenfelder der Untersuchung?
Im Mittelpunkt stehen die mathematische Herleitung von Updateformeln für Steepest Edge Gewichte, der duale Simplexalgorithmus in verschiedenen Ausprägungen und der Vergleich der Leistungsfähigkeit unterschiedlicher Pricing-Strategien.
Was ist das primäre Ziel der Arbeit?
Ziel ist es, den Effizienzvorteil des Steepest Edge Ansatzes aufzuzeigen und mathematisch zu begründen, wie man diesen durch eine Reduktion des Rechenaufwands bei der Kantenbestimmung in der Praxis vorteilhaft nutzen kann.
Welche wissenschaftliche Methode wird in dieser Arbeit verwendet?
Es handelt sich um eine theoretische Analyse, die durch eine mathematische Herleitung der Updateformeln und eine deskriptive Auswertung von empirischen Testergebnissen aus der Fachliteratur gestützt wird.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil widmet sich der detaillierten Beschreibung des Steepest Edge Algorithmus, beginnend bei einer grafischen Veranschaulichung bis hin zur spezifischen Behandlung von dualen Problemen mit Schlupfvariablen und Oberschranken.
Welche Schlüsselwörter charakterisieren die Arbeit am besten?
Die wichtigsten Begriffe sind Lineare Optimierung, Simplexalgorithmus, Steepest Edge Pricing, Duales Problem und Updateformeln.
Warum ist die Wahl der Pricing-Strategie so entscheidend?
Die Strategie der Wahl des Pivotelements bestimmt maßgeblich, wie effizient das Optimum angesteuert wird. Während das Dantzig-Pricing zu einer exponentiellen Anzahl an Iterationen führen kann, reduziert das Steepest Edge Pricing die Iterationszahl im Durchschnitt signifikant.
Inwiefern beeinflussen die Updateformeln den Rechenaufwand?
Die Updateformeln erlauben es, neue Steepest Edge Gewichte direkt aus den Werten der vorherigen Iteration zu berechnen, anstatt diese jedes Mal aufwändig neu bestimmen zu müssen, was den Rechenaufwand pro Iteration massiv senkt.
- Quote paper
- Diplom Wirtschaftsinformatiker Youssef El Haoum (Author), 2005, Der duale Steepest Edge Simplex Algorithmus, Munich, GRIN Verlag, https://www.grin.com/document/34431
