Basic Solutions and Basic Feasible Solutions

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  
  subject to the constraints
\[x_1+2x_2+x_3+x_4 \leq 3\]
\[x_1-x_2+2x_3+x_4 \leq 4\]
\[x_1+x_2-x_3-x_4 \leq -1\]
\[x_1, \: x_2, \: x_3, \: x_4 \geq 3\]
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  
  constraints in  
  unknowns, we must pick  
  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  
  the problem becomes: Maximise  
  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\]

\[O=1+3 \times 1+ 4 \times 1=8\]

Add comment

Security code