Schranken für die durchschnittliche Laufzeit des Simplexverfahrens und von Innere-Punkte-Verfahren

Lineare Optimierungsprobleme spielen in der Praxis eine wichtige Rolle und man ist deshalb an effizienten Lösungsverfahren interessiert. Seit 50 Jahren ist der Simplexalgorithmus das Standardverfahren zur Lösung dieser Probleme und es hat sich in der Praxis sehr gut bewährt. Allerdings können theoretisch extrem schlechte Laufzeiten auftreten. Um diese Diskrepanz zu erklären, untersucht man durchschnittliche Laufzeiten. So zeigte Borgwardt 1981/82, daß eine spezielle Variante des Simplexverfahrens im Mittel eine polynomiale Laufzeit besitzt. In der vorliegenden Arbeit werden beliebige Varianten des Simplexverfahrens untersucht und Unterschranke für deren durchschnittliche Laufzeit angegeben. In den 80er Jahren bekam das Simplexverfahren Konkurrenz durch Innere-Punkte-Verfahren, die sowohl praktisch als auch theoretisch eine gute (polynomiale) Laufzeit aufweisen. Bei diesen Verfahren ist in der Praxis oft ein frühzeitiger Abbruch möglich, so daß auch hier die praktisch auftretende Laufzeit besser ist als die theoretisch nachweisbare. Der zweite Teil dieser Arbeit enthält die probabilistische Analyse eines Abbruchkriteriums, die belegt, daß Innere-Punkte-Verfahren im Mittel eine streng polynomiale Laufzeit besitzen.