Basisvariabelen

Basisvariabelen zijn de variabelen die in een lineair systeem of lineaire programmering behoren tot een gekozen basis van de kolomruimte. Ze bepalen samen met de niet-basisvariabelen de oplossing van het systeem en krijgen meestal waarden door de andere variabelen op nul te zetten.

Bij een systeem Ax = b met A een m×n-matrix en rank(A) = m wordt een basis gevormd door een selectie B van m kolommen van A die lineair onafhankelijk zijn. De variabelen die horen bij deze kolommen, x_B, noemen we basisvariabelen. De overige variabelen, x_N, noemen we niet-basisvariabelen. In een basisoplossing worden de niet-basisvariabelen vaak op nul gezet, waarna x_B wordt opgezocht via x_B = A_B^{-1} b, mits A_B inverteerbaar is.

Basisvariabelen geven samen met de niet-basisvariabelen een hoekpunt van het feasible gebied weer; dit punt heet dan een basisfeasible oplossing. Tijdens het simplex-algoritme kan een pivot-operatie een niet-basisvariabele in de basis brengen en een basisvariabele uit de basis verwijderen, waardoor men naar een aangrenzende hoekpunt gaat.

Er zijn vaak meerdere mogelijke bases voor hetzelfde probleem; de keuze van de basis kan gevolgen hebben voor degeneratie, numerieke stabiliteit en het pad dat men volgt naar optimaliteit. Als de geselecteerde kolomverzameling niet inverteerbaar is, kan geen basisoplossing bestaan voor die keuze.

Voorbeeld: A = [[1, 0, 2], [0, 1, 3]], b = [4, 5]. Met basiskolommen {1, 2} is A_B = I, dus x_B = b en x_N = 0 geeft een basisoplossing met x = [4, 5, 0].