Pivotauswahlverfahren in der Linearen Programmierung

Von den verschiedenen Verfahren zur Losung linearer Optimierungsprobleme gilt das Simplexverfahren bislang als dasjenige, welches das Optimum mit dem geringsten Losungsaufwand ermittelt. Der Losungsaufwand setzt sich dabei im wesentlichen aus zwei Faktoren zusammen: dem Aufwand fur die Durchfuhrung einer Iteration und der Anzahl an Iterationen, die zur Berechnung des Optimums benotigt werden. Beide Faktoren werden durch das Auswahlkriterium zur Bestimmung des Pivotelements beeinflusst. Von den bekanntesten Pivotauswahlkriterien konnen nur zwei als effizient eingestuft werden, namlich das steepest-ascent Kriterium und das Gradientenkriterium. Es wird gezeigt, dass sich die Effizienz des Simplexverfahrens durch Variationen dieser Pivotauswahlkriterien noch verbessern lasst. Anderen Losungsverfahren durfte es damit noch schwerer fallen, das Simplexverfahren als das bevorzugte Verfahren zur Losung linearer Optimierungsprobleme zu verdrangen."