Inhaltsverzeichnis

1  Einleitung  1

2  Grundlagen  2

2.1  Der duale Simplexalgorithmus  2

2.1.1  Ablauf des Algorithmus  3

2.2  Pricing-Strategien  5

3  Der duale Steepest Edge Simplexalgorithmus  7

3.1  Grafische Veranschaulichung  7

3.2  Duales Problem in einfacher Form  9

3.3  Duales Problem mit Schlupfvariablen  11

3.4  Duales Problem mit Oberschranken  13

4  Vergleich der Pricing-Strategien  16

4.1  Testumgebung  16

4.2  Testergebnisse  16

5  Zusammenfassung  19

i

Symbolverzeichnis

A Matrix (a ij ), wobei a ij der Multiplikator der Variable x j in der Nebenbedingung i

A B Teilmatrix von A, welche spaltenm¨ aßig die Koeffizienten der Basisvariablen enth¨ alt. In der Literatur wird diese Matrix auch mit B beschrieben.

A N Teilmatrix von A, welche spaltenm¨ aßig die Koeffizienten der Nichtbasisvariablen enth¨ alt. In der Literatur wird diese Matrix auch mit R beschrieben.

a j j-te Spalte der Matrix A

B Indizesmenge der Basisvariablen

b Beschr¨ ankungsvektor der Restriktionen

c Kostenvektor bzw. Gradient der Zielfunktion z

c i i-te Komponente des Kostenvektors c

c B die Koeffizienten der Basisvariablen in der Zielfunktion

c N die Koeffizienten der Nichtbasisvariablen in der Zielfunktion

d i die reduzierten Kosten der Variable x i

(m × m)-Elementarmatrix, die genauen Eigenschaften sind dem Kontext zu E entnehmen.

e p p-te Spalte der Einheitsmatrix I

(m × m)-Einheitsmatrix, wobei die Dimension m dem Kontext zu entnehmen I ist.

l Vektor der Untergrenzen der Optimierungsvariablen

l i Untergrenze der Optimierungsvariable x i

LP ein Problem der linearen Optimierung

N Indizesmenge der Nichtbasisvariablen

u Vektor der Obergrenzen der Optimierungsvariablen

ii

u i Obergrenze der Optimierungsvariable x i

x zu optimierender Mengenvektor des primalen Problems

x ^∗ aktuelle Basisl¨ osung

B

x N Menge der Variablen x j , welche nicht in der Basis sind.

y zu optimierender Mengenvektor des dualen Problems

¨ η j Anderung der Variable x j , welche durch den Basiswechsel im primalen Sim-plexalgorithmus erfolgt (η j = ∆x j ).

ρ ^j Wird in der Literatur meistens als j-te Zeile der Inversen der Basismatrix ρ ^j = j B ⁻¹ . Bei komplexeren Basen ist die Formel dieses Vektors dem Kontext zu e ^T entnehmen.

transponierter Vektor des Vektors ρ ^j (ρ T j = ρ ^j ) ρ j

(c, η j ) Winkel zwischen den Vektoren c und η j

iii

1 Einleitung

Der Rechenaufwand beim Simplexalgorithmus h¨ angt wesentlich von der Strategie der Wahl des Pivotelementes (dem so genannten Pricing) ab (vgl. [M¨ uller-Merbach 1970] [S. 207 ff]). 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¨ achst werden in Kapitel 2 einige der f¨ ur diese Arbeit relevanten Grundlagen des Simplexalgorithmus eingef¨ uhrt. 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¨ alt die Beschreibung ausgew¨ ahlter Testergebnisse, welche [Forrest und Goldfarb 1992] beim Vergleich der Laufzeiten verschiedener Simplexvarianten erzielt haben. Anschließend folgt eine Zusammenfassung der wesentlichen Ergebnisse dieser Arbeit.

1

2 Grundlagen

Im Rahmen der Unternehmensforschung (Operations Research) werden Entscheidungen mit Hilfe von Modellen getroffen. Der wichtigste Algorithmus zur L¨ osung linearer Entscheidungsmodelle ist der Simplexalgorithmus. Seit seiner Einf¨ uhrung 1947 von G. B. Dantzig wurde der Simplexalgorithmus stetig weiterentwickelt, seine Grundprinzipien blieben aber unver¨ andert. Zu den vielf¨ altigen Varianten des Sim-plexalgorithmus geh¨ ort der so genannte duale Simplexalgorithmus.

Theoretisch gesehen ist der Simplexalgorithmus nicht vielversprechend, denn Klee und Minty bewiesen, dass seine Worst-Case-Laufzeit exponentiell ist (vgl. [Klee und Minty 1972]). In der Praxis jedoch ist seine durchschnittliche Laufzeit linear. Deswegen gilt der Simplexalgorithmus als hocheffizient f¨ ur die L¨ osung linearer Probleme (vgl.[Maros 2003a][S. 19]).

In dieser Arbeit wird vorausgesetzt, dass der Leser mit der Vorgehensweise der Simplexmethode bereits vertraut ist. Eine detaillierte Beschreibung dieser Vorgehensweise und erl¨ auternde Beispiele finden sich in [Chv´ atal 1983][S. 13 ff]. Nachfolgend werden die im weiteren Verlauf der Arbeit wichtigsten Begrifflichkeiten kurz eingef¨ uhrt.

2.1 Der duale Simplexalgorithmus

Die Dualit¨ at ist ein allgemeiner Begriff, der eine große Rolle in der linearen Programmierung spielt. Ihre einfache Form kann durch folgendes Beispiel gezeigt werden.

Jedes LP der Form

das primales Problem genannt wird, hat ein dazu geh¨ origes LP (D1), welches als duales Problem von (P1) bezeichnet wird, mit