Given a linear programming problem, a basic feasible solution to the problem is any set of variables that satisfies the constraints.
Suppose we have the linear programming problem: Maximise  {jatex options:inline}O=x_1+2x_2+3x_3+4x_4{/jatex}  subject to the constraints
{jatex options:inline}x_1+2x_2+x_3+x_4 \leq 3{/jatex}  (1)
{jatex options:inline}x_1-x_2+2x_3+x_4 \leq 4{/jatex}  (2)
{jatex options:inline}x_1+x_2-x_3-x_4 \leq -1{/jatex}  (3)
{jatex options:inline}x_1, \: x_2, \: x_3, \: x_4 \geq 3{/jatex}  (4)
There are three constraints, (1), (2), (3) but four unknowns. We can set any one of the variables equal to zero and write the inequalities as equations, which gives us three equations and three unknowns. We can solve these equations uniquely to gives a 'basic solution'. The basic solution is not feasible if any variable is negative since (4) is not satisfied. A basic feasible solution, when substituted into the objective function, will give a value, not necessarily optimal. In general, given  {jatex options:inline}k{/jatex}  constraints in  {jatex options:inline}n{/jatex}  unknowns, we must pick  {jatex options:inline}k{/jatex}  of the n equations, so there are  {jatex options:inline}{}^n C_k{/jatex}  possible basic solutions. If (4) is
According to the Fundamental Theory of Linear Algebra, if a optimal solution to the original problem exists,exists, then an optimal basic solution exists, so the optimal solution can be found by putting some variables equal to 0 and considering a set of equations with as many unknowns as equations. If we let  {jatex options:inline}x_2=0{/jatex}  the problem becomes: Maximise  {jatex options:inline}O=x_1+3x_3+4x_4{/jatex}  subject to the constraints
{jatex options:inline}x_1+x_3+x_4 \leq 3{/jatex}
{jatex options:inline}x_1+2x_3+x_4 \leq 4{/jatex}
{jatex options:inline}x_1-x_3-x_4 \leq -1{/jatex}
{jatex options:inline}x_1, \: x_3, \: x_4 \geq 3{/jatex}
A basic feasible solution is  {jatex options:inline}x_1=1, \: x_2=0, \: x_3=1, \: x_4=1{/jatex}
Then  {jatex options:inline}O=1+3 \times 1+ 4 \times 1=8{/jatex}.