Ferdinand Geue Eckenabsuchende Verfahren und Entartung

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 Pivotauswahlverfahren bilden. Übergangsknoten-Pivotauswahlregeln pivotisieren in einer Teilmenge der Übergangsknoten eines positiven Entartungsgraphen, so dass eine entartete Ecke von jedem der ausgewählten Knoten durch genau einen Pivotschritt in eine Nachbarecke verlassen werden kann. Modifizierte Versionen des N-Baum-Verfahrens sind ein Bestandteil des algorithmisch orientierten Teils, der mit einer Variante zur Bestimmung aller Ecken eines konvexen Polyeders endet.

Zum Abschluss werden die entwickelten Konzepte in zwei Testreihen auf ihre Praxiseignung überprüft. In der ersten Testreihe wird die Effizienz des N-Baum-Verfahrens in Abhängigkeit von der verwendeten Pivotauswahlregel untersucht. Die zweite Testreihe dient zur Überprüfung der Effizienz von Anticyclingregeln beim Simplexverfahren und gibt einen umfassenden Überblick über die Leistungsfähigkeit bis heute veröffentlichter Strategien.