Der durchschnittliche Rechenaufwand des Simplexverfahrens unter einem verallgemeinerten Rotationssymmetriemodell

Das Simplexverfahren, welches erstmals 1947 von George Dantzig vorgestellt wurde, ist die in der Praxis meistgenutzte Methode zum Lösen linearer Optimierungsprobleme. Obwohl das Verfahren im schlimmsten Fall sehr rechenaufwendig werden kann, haben praktische Erfahrungen gezeigt, dass es in den allermeisten Fällen sehr effizient arbeitet. Um diese große Differenz zwischen theoretischem Worst-Case und praktischer Beobachtung mathematisch fundiert erklären zu können, wurden in den vergangenen Jahrzehnten zahlreiche Average-Case-Analysen durchgeführt. Das erste bahnbrechende Ergebnis diesbezüglich gelang Borgwardt 1981/82. Die vorliegende Arbeit verallgemeinert die asymptotische Analyse von Borgwardt in der Weise, dass nun bei der Ermittlung des durchschnittlichen Rechenaufwands zusätzlich auch unzulässige lineare Optimierungsprobleme, bei denen die Unzulässigkeit erst durch Berechnung festgestellt werden muss, berücksichtigt werden. Als zentrales Resultat wird schließlich bewiesen, dass diese Verallgemeinerung im Mittel zu keinem höheren Rechenaufwand führt als der bereits von Borgwardt behandelte Fall.