Basislösung

Siehe auch

Simplex-Algorithmus

Gegeben sei ein LP in Normalform und Matrixschreibweise mit

• ist die Koeffizientenmatrix
• ist die Anzahl der Variablen
• ist die Anzahl der Nebenbedingungen

Dann heißt Basislösung (kurz Basis) genau dann, wenn

• Komponenten gleich Null sind und
• die zu den restlichen Variablen (Basisvariablen, BV) gehörenden Spaltenvektoren (Basisvektoren) der Matrix linear unabhängig sind.

Eine zulässige Basislösung ist dann eine Basislösung, die alle Nebenbedingungen erfüllt.

Hauptsatz der linearen Optimierung

Es gibt immer eine Optimallösung, die eine zulässige Basislösung ist.

Im Fall einer unzulässigen Basislösung () wird das duale Problem betrachtet. Die Vorgehensweise dabei ist wie folgt:

• In der Tabelle wird nicht bei der Zielfunktion, sondern in der Basis der kleinste Wert gesucht, dieser bildet zuerst die Pivotzeile
• Anschließend ist die Pivotspalte die mit dem maximalen Quotient aus x und der Zielfunktion