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!

Printable View

- Feb 5th 2009, 01:39 PMjlt1209basic 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! - Feb 5th 2009, 02:37 PMHallsofIvy
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. - Feb 7th 2009, 12:50 AMgrapplerBasic feasible solutions
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. - Feb 7th 2009, 09:40 AMgrapplerAn additional comment
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.