Der duale Steepest Edge Simplex Algorithmus

Front Cover
GRIN Verlag, Feb 3, 2005 - Computers - 24 pages
Studienarbeit aus dem Jahr 2005 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 2,0, Universität Paderborn, 11 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: 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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Einleitung
iii
Grundlagen
1
22 PricingStrategien
4
Der duale Steepest Edge Simplexalgorithmus
6
32 Duales Problem in einfacher Form
8
33 Duales Problem mit Schlupfvariablen
10
34 Duales Problem mit Oberschranken
12
Vergleich der PricingStrategien
15
Zusammenfassung
18

Common terms and phrases

Bibliographic information