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 Losen linearer Optimierungsprobleme. Obwohl das Verfahren im schlimmsten Fall sehr rechenaufwendig werden kann, haben praktische Erfahrungen gezeigt, dass es in den allermeisten Fallen sehr effizient arbeitet. Um diese grosse Differenz zwischen theoretischem Worst-Case und praktischer Beobachtung mathematisch fundiert erklaren zu konnen, wurden in den vergangenen Jahrzehnten zahlreiche Average-Case-Analysen durchgefuhrt. Das erste bahnbrechende Ergebnis diesbezuglich gelang Borgwardt 1981/82. Die vorliegende Arbeit verallgemeinert die asymptotische Analyse von Borgwardt in der Weise, dass nun bei der Ermittlung des durchschnittlichen Rechenaufwands zusatzlich auch unzulassige lineare Optimierungsprobleme, bei denen die Unzulassigkeit erst durch Berechnung festgestellt werden muss, berucksichtigt werden. Als zentrales Resultat wird schliesslich bewiesen, dass diese Verallgemeinerung im Mittel zu keinem hoheren Rechenaufwand fuhrt als der bereits von Borgwardt behandelte Fall.