Thread: basic feasible solutions

Let P = {2x1 + x2 + x3 = 2,
x1 + x2 = 1
x1,x2 >= 0}

List all of the basic feasible solutions. Which of them are degenerate?

Not sure how to go about this ... thanks!

If x1 is any positive number, since x1+ x2= 1, x2= 1- x1. Since x2 must alos be postive, x1 cannot be larger than 1. Then the second equation, 2x1 + x2 + x3 = 2, x3= 2- 2x1- x2= 2- 2x1-(1- x1)= 1- 3x1. Since x3 must be larger than 0, x1 must be less than 1/3.

So the set of all feasible solutions is the set of all triples (x1, 1- x1, 1- 3x1) where x1 is between 0 and 1/3.

This is a problem in linear programming. The basic feasible solutions are the extreme points of the convex set given by the constraints. They are obtained by setting some of the variables equal to zero and solving for the others. In this case one of the variables is set to zero. Each variable has to be tried in turn.

We first set x1=0. Then the equations become x2+x3=2, x2=1. This has solution x1=0, x2=1, x3=1, which has the property that all of the x's are non-negative, so this is a basic feasible solution.

Now set x2=0. The equations are 2x1+x3=2, x1=1. This gives x1=1, x2=0, x3=0. This is also basic feasible, though degenerate since also x3=0.

Finally set x3=0. This gives equations 2x1+x2=2, x1+x2=1. The solution is
x1=1, x2=0. Again this is feasible and also degenerate.

These are the three basic feasible solutions.

One thing I forgot to mention, in fact because of degeneracy, the second
and third basic feasible solutions are the same - x1=1, x2=0, x3=0. So there are only two basic feasible solutions.