Eckenabsuchende Verfahren unter Entartung

Meer over het boek

Entartung beeinflusst maßgeblich die Effizienz und Konvergenz pivotisierender Verfahren, wie das Zykeln des Simplexverfahrens zeigt. Um dies zu verhindern, wurden verschiedene Zusatzregeln entwickelt, darunter Störungsregeln und lexikographische Pivotauswahlregeln, die als zentrale Strategien zur Sicherstellung einer eindeutigen Pivotauswahl gelten. Diese Regeln sind auch ein Grundbestandteil des N-Baum-Verfahrens, das zur Lösung des Nachbarschaftsproblems dient und als Testproblem zur Effizienzprüfung lexikographischer Pivotauswahlregeln gilt. In diesem Kontext stoßen klassische Konzepte an ihre Grenzen. Ferdinand Geues Arbeit thematisiert diese Effizienzprobleme und untersucht theoretische Eigenschaften lexikographischer Pivotauswahlregeln, stellt neue Strategien vor und testet deren praktische Eignung zur Lösung von Entartungsproblemen. Ein zentrales Konzept ist der positive Entartungsgraph, der die möglichen Pivotschritte zwischen den Basen einer entarteten Ecke darstellt. Lexikographische Pivotauswahlregeln schränken die Basenmenge ein und induzieren einen Teilgraphen, dessen Eigenschaften theoretisch analysiert werden. Die Ergebnisse sind auf Übergangsknoten-Pivotauswahlverfahren übertragbar, die eine entartete Ecke durch einen Pivotschritt in eine Nachbarecke überführen. Modifizierte N-Baum-Verfahren und deren Effizienz werden in zwei Testreihen untersucht, die die Praxiseignung der entwickelten Konzepte evaluieren.