basisoplossing

Basisoplossing is in lineaire programmering een haalbare oplossing die voortkomt uit een basis van het constraint-systeem Ax = b onder x ≥ 0. In de standaardvorm van een LP zoekt men een vector x die voldoet aan Ax = b en x ≥ 0, waarbij A een m×n-matrix is. Een basis B bestaat uit m kolommen van A die lineair onafhankelijk zijn. Uit deze basis wordt x_B = A_B^{-1} b berekend en worden de overige variabelen x_N op nul gezet. De resulterende vector x heet een basisoplossing als x_B ≥ 0; is dit ook x ≥ 0, dan is het een feasible basisoplossing, oftewel een BFS (basic feasible solution).

Basisoplossingen vormen de hoekpunten van het feasible-gebied {x ≥ 0, Ax = b}. Degeneratie treedt op wanneer een of meer basisvariabelen nul zijn; daardoor kunnen verschillende bases naar hetzelfde BFS leiden. Een niet-degeneratieve BFS heeft alle basisvariabelen strikt positief. De simplex-methode verplaatst zich langs BFS’en door middel van pivot-operaties, waarbij de basis B verandert naar een andere basis B', en zo het optimum kan worden bereikt (voor maximize of minimize).

Verifieerbaar maken van BFS is essentieel in algoritmen voor LP. Als er geen triviale haalbare oplossing bestaat, kan men via een twee-fasen methode te werk gaan: in fase I worden kunstmatige variabelen toegevoegd en wordt de som ervan geminimaliseerd. Als de minimale som nul is, bestaat er een haalbare oplossing en kan fase II starten om het werkelijke optimum te vinden. Basisoplossingen vormen zo de bouwstenen van de meeste prikpunten en iteratieve oplossingsmethoden in lineaire programmering.