Grundlösning (linjär programmering)

Inom linjär programmering , en disciplin inom tillämpad matematik , är en grundläggande lösning vilken lösning som helst av ett linjärt programmeringsproblem som uppfyller vissa specificerade tekniska villkor.

För en polyeder $P$ och en vektor ${\displaystyle \mathbf {x} ^{*}\in \mathbb {R} ^{n}} ,$ x $\displaystyle \mathbf { x} ^{*}}$ är en grundläggande lösning om:

1. Alla likhetsbegränsningar som definierar $P$ är aktiva vid $\mathbf {x} ^{*}$
2. Av alla restriktioner som är aktiva vid den vektorn måste minst $n$ av dem vara linjärt oberoende . Observera att detta också betyder att minst $n$ -begränsningar måste vara aktiva vid den vektorn.

En begränsning är aktiv för en viss lösning $\mathbf {x}$ om den är uppfylld vid likhet för den lösningen.

En grundläggande lösning som uppfyller alla begränsningar som definierar $P$ (eller, med andra ord, en som ligger inom $P$ ) kallas en grundläggande genomförbar lösning .