Über das Buch

Zum Inhalt

Entartung ist ein Phänomen, das die Effizienz und Konvergenz pivotisierender Verfahren maßgeblich beeinflussen kann. Das bekannteste Beispiel hierfür stellt das Zykeln des Simplexverfahrens dar, zu dessen Verhinderung eine Reihe von Zusatzregeln entwickelt wurden. Störungsregeln bzw. numerisch äquivalente lexikographische Pivotauswahlregeln können dabei als geläufigste prinzipielle Strategien zum Erhalt einer eindeutigen Pivotauswahl betrachtet werden. Sie bilden auch einen Grundbestandteil des N-Baum-Verfahrens, das zur Lösung des sog. Nachbarschaftsproblems, d. h. zur Bestimmung aller Nachbarecken einer entarteten Ecke, entwickelt wurde und als ideales Testproblem zur Überprüfung der Effizienz lexikographischer Pivotauswahlregeln angesehen werden kann. In diesem Einsatzbereich stoßen die klassischen Konzepte lexikographischer Pivotauswahl an die Grenzen ihrer Anwendbarkeit.

Die Arbeit von Ferdinand Geue ist durch diese Effizienzprobleme motiviert. Sie beinhaltet elementare theoretische Eigenschaften lexikographischer Pivotauswahlregeln, stellt spezielle neue Strategien vor und geht in ausführlich beschriebenen Testreihen insbesondere auf die praktische Eignung dieser und konkurrierender Pivotauswahlverfahren zur Lösung von Entartungsproblemen ein.

Die Untersuchung basiert auf dem zunächst vorgestellten Konzept des einer entarteten Ecke zugeordneten sogenannten positiven Entartungsgraphen, der die Pivotschritte repräsentiert, die zwischen den Basen dieser Ecke möglich sind. Lexikographische Pivotauswahlregeln bestimmen durch die Einschränkung des üblichen Zulässigkeitsbegriffs eine Teilmenge dieser Basenmenge. Diese Teilmenge induziert einen Teilgraphen des positiven Entartungsgraphen, dessen wesentliche Eigenschaften im theoretischen Teil vorgestellt werden. Die Ergebnisse können unmittelbar auf die im Anschluss präsentierten Übergangsknoten-Pivotauswahlverfahren übertragen werden, die eine Klasse spezieller lexikographischer…

Schlagworte

Lineare Optimierung, Simplexverfahren, Pivotauswahl, Entartungsgraph, Entartete Ecke, Übergangsknoten, N-Baum, Nachbarschaftsproblem, Informatik