Der duale Steepest Edge Simplex Algorithmus

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

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

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 ff]). Bisher wurden zahlreiche Varianten des dualen Simplexalgorithmus vor- gestellt, welche sich durch ihre Pricing-Strategien unterscheiden. Eine dieser Stra- tegien ist das Steepest Edge Pricing. Gegenstand dieser Arbeit ist die Vorstellung und Verdeutlichung dieses Ansatzes und einige seiner Varianten, welche auf unter- schiedlichen 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.

2 Grundlagen

Im Rahmen der Unternehmensforschung (Operations Research) werden Entscheidungen mit Hilfe von Modellen getroffen. Der wichtigste Algorithmus zur Lösung linearer Entscheidungsmodelle ist der Simplexalgorithmus. Seit seiner Einführung 1947 von G. B. Dantzig wurde der Simplexalgorithmus stetig weiterentwickelt, seine Grundprinzipien blieben aber unverändert. Zu den vielfältigen Varianten des Simplexalgorithmus gehört 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ür die Lösung linearer Probleme (vgl.[Maros 2003a][S. 19]).

In dieser Arbeit wird vorausgesetzt, dass der Leser mit der Vorgehensweise der Sim- plexmethode bereits vertraut ist. Eine detaillierte Beschreibung dieser Vorgehens- weise und erläuternde Beispiele finden sich in [Chvátal 1983][S. 13 ff]. Nachfolgend werden die im weiteren Verlauf der Arbeit wichtigsten Begrifflichkeiten kurz ein- geführt.

2.1 Der duale Simplexalgorithmus

Die Dualität ist ein allgemeiner Begriff, der eine große Rolle in der linearen Program- mierung spielt. Ihre einfache Form kann durch folgendes Beispiel gezeigt werden.

Jedes LP der Form

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

Das duale Problem lässt sich durch Multiplikation der Zielfunktion und der Nebenbedingungen mit (−1) in die Form von (P1) bringen

Abbildung in dieser Leseprobe nicht enthalten

(D1*) kann man durch Variablensubstitution folgendermaßen vereinfachen:

Abbildung in dieser Leseprobe nicht enthalten

Hat das primale Problem die Form [Abbildung in dieser Leseprobe nicht enthalten], dann lautet das dazugehörige duale Problem

(D2) [Abbildung in dieser Leseprobe nicht enthalten]

Aus den letzten Umformungen wird die starke Verbindung zwischen einem prima- len und dem zugehörigen dualen LP deutlich. Das primale Problem wird mittels Anwendung des primalen Simplexalgorithmus gelöst, oder auch durch Anwendung des dualen Simplexalgorithmus auf seinem dualen Problem (vgl. [Maros 2003a][S. 38 ff]). Der duale Simplexalgorithmus ist mathematisch gesehen nichts anderes als eine leicht veränderte Anwendung des primalen Simplexalgorithmus auf das duale Problem. Während der primale Simplexalgorithmus ausgehend von einer zulässigen Basislösung eine Verbesserung der Zielfunktion durch Basiswechsel anstrebt, strebt der duale Simplex die primale Zulässigkeit der gewählten Basislösung an. Die erste, durch Anwendung des dualen Simplexalgorithmus erhaltene primal zulässige Lösung des dualen Problems ist zugleich die optimale Lösung des primalen Problems und somit die Abbruchbedingung des dualen Simplexalgorithmus (vgl. [Dantzig 1966][S. 278]).

2.1.1 Ablauf des Algorithmus

Wie bereits erwähnt, sucht der duale Simplexalgorithmus bei seinen Iterationen eine primal zulässige Lösung. Wenn eine solche gefunden ist, terminiert der Algorithmus (vgl. [Chvátal 1983][S. 137 ff]). Daher gehören zu einer Iteration des Algorithmus folgende Schritte:

1. Wahl einer Basisvariable xp, welche die Zulässigkeitsbedingung [Abbildung in dieser Leseprobe nicht enthalten] verletzt und deswegen die Basis verlassen muss. Falls kei- ne solche Variable vorhanden ist, terminiert der Algorithmus, da die aktuelle Basislösung optimal ist.
2. Wahl einer Nichtbasisvariable (NBV) mit dem Index [Abbildung in dieser Leseprobe nicht enthalten] welche die duale Zulässigkeit erfüllt und Tausch von x_p und x_q .
3. Aktualisierung der LP-Daten.

Anders als bei der tabellarischen Vorgehensweise des dualen Simplexalgorithmus, bei welcher nach jeder Iteration alle Daten aktualisiert werden, wird in dieser Arbeit der revidierte duale Simplex benutzt. Dieser hat zwei Vorteile gegenüber der tabellarischen Form. Zum einen verursacht er weniger Rechenaufwand und benötigt weniger Speicherkapazität und zum anderen vermeidet er einige numerische Fehler (vgl. [Wunderling 1996][S. 68]).

Wie wird in jeder Iteration die Zulässigkeit der aktuellen Basislösung überprüft und welche Daten werden aktualisiert? Ist [Abbildung in dieser Leseprobe nicht enthalten] dann ist die aktuelle Lösung zulässig. Zur Beantwortung der zweiten Frage sind folgende Vorüberlegungen hilfreich. Das zu optimierende Problem sei in der Standardform gegeben. Die Matrix A ∈ Rm×(m+n) wird in eine Basismatrix[Abbildung in dieser Leseprobe nicht enthalten] und eine Nichtbasismatrix AN [Abbildung in dieser Leseprobe nicht enthalten] geteilt.

Dann gilt

Abbildung in dieser Leseprobe nicht enthalten

Sei x die aktuelle Lösung des LP. Analog zur Matrix A kann auch x in xB und xN unterteilt werden. Dabei gilt [Abbildung in dieser Leseprobe nicht enthalten] wobei [Abbildung in dieser Leseprobe nicht enthalten] der zur Basis B gehörende Vektor und [Abbildung in dieser Leseprobe nicht enthalten] der zu AN gehörende Vektor ist. Da x eine Lösung des LP darstellt, gilt

Abbildung in dieser Leseprobe nicht enthalten

(2.1)

Mit x als Basislösung des LP, gilt xN = 0 und deswegen nach (2.1) [Abbildung in dieser Leseprobe nicht enthalten]. In (2.1) ist desweiteren erkennbar, dass sich die Basislösung bei einem Basiswechsel um [Abbildung in dieser Leseprobe nicht enthalten] ändert. Da aber in einer Iteration nur die Variable xq aus xN in die Basis aufgenommen wird, muss nur eine Komponente des Produktes B−[[1]]AN xN berechnet werden, nämlich [Abbildung in dieser Leseprobe nicht enthalten], wobei aq für die Pivotspalte steht. Für die Wahl der Pivotspalte wird von AN nur die Pivotzeile benötigt, deswegen wird diese erst nach der Bestimmung der Variable xp aktualisiert (vgl. [Chvátal 1983][S. 154 bis 157]). Die Bestimmung der Pivotzeile erfolgt in Schritt2 des nachfolgend beschriebenen Algorithmus. Der Vektor c lässt sich genauso wie x in cB und cN teilen und wird nach jeder Iteration aktualisiert. Für alle ci wird der aktuelle Wert mit ci notiert und als reduzierte Kosten der Variable xi bezeichnet.

Im Folgenden wird ein LP in der Form von (D1) betrachtet und durch Erweiterung um die Bedingungen

Abbildung in dieser Leseprobe nicht enthalten

in die allgemeine Form gebracht. Die algorithmische Arbeitsweise des erweiterten revidierten dualen Simplex entspricht den folgenden Schritten (vgl. [Chvátal 1983][S. 157]):

[...]