Pivotverfahren

Pivotverfahren (auch Basisaustauschverfahren) sind Algorithmen der mathematischen Optimierung, insbesondere der linearen Optimierung. Für ein vorgegebenes System linearer Gleichungen in nichtnegativen Variablen (im Wesentlichen dasselbe wie ein System linearer Ungleichungen) wird nach der bestmöglichen von vielen Alternativlösungen (einer sogenannten Optimallösung) gesucht und auf dieser Suche das Gleichungssystem Schritt für Schritt umgewandelt, ohne dabei die Lösungsmenge zu verändern. Wichtige Pivotverfahren sind die Simplex-Verfahren und die Criss-Cross-Verfahren.

Pivotverfahren spielen für die Behandlung von linearen Ungleichungen eine analoge und ähnlich wichtige Rolle wie das gaußsche Eliminationsverfahren für die Lösung linearer Gleichungssysteme in unbeschränkten Variablen. Hauptanwendungsgebiet der Pivotverfahren ist die lineare Optimierung: sie gehören zu den meistverwendeten Lösungsmethoden in der Unternehmensforschung, der Wirtschaftswissenschaft, dem Gütertransport und sie werden auch in vielen anderen Gebieten wie im Ingenieurbau (Strukturoptimierung), in der Statistik (Regressionsanalyse) und in der Spieltheorie zunehmend eingesetzt. Aufgaben mit zehntausenden Variablen und Ungleichungen sind an der Tagesordnung.