Basic Solutions and Basic Feasible Solutions
Suppose we have the linear programming problem: Maximise
\[O=x_1+2x_2+3x_3+4x_4\]
subject to the constraints\[x_1+2x_2+x_3+x_4 \leq 3\]
(1)\[x_1-x_2+2x_3+x_4 \leq 4\]
(2)\[x_1+x_2-x_3-x_4 \leq -1\]
(3)\[x_1, \: x_2, \: x_3, \: x_4 \geq 3\]
(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
\[k\]
constraints in \[n\]
unknowns, we must pick \[k\]
of the n equations, so there are \[{}^n C_k\]
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
\[x_2=0\]
the problem becomes: Maximise \[O=x_1+3x_3+4x_4\]
subject to the constraints\[x_1+x_3+x_4 \leq 3\]
\[x_1+2x_3+x_4 \leq 4\]
\[x_1-x_3-x_4 \leq -1\]
\[x_1, \: x_3, \: x_4 \geq 3\]
A basic feasible solution is
\[x_1=1, \: x_2=0, \: x_3=1, \: x_4=1\]
Then
\[O=1+3 \times 1+ 4 \times 1=8\]
. 
