Results 1 to 4 of 4

Math Help - basic feasible solutions

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    33
    Thanks
    1

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,541
    Thanks
    1394
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2009
    Posts
    3

    Basic 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2009
    Posts
    3

    An 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic Solutions and Extreme Points
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: April 13th 2011, 03:39 AM
  2. [SOLVED] Basic solutions at x_{0} = 1
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: February 16th 2011, 01:40 PM
  3. Non-Basic solutions to equations...
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 1st 2010, 08:06 AM
  4. Objective functions, region of feasible solutions
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 22nd 2007, 05:36 PM
  5. feasible solutions
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 6th 2007, 09:29 PM

Search Tags


/mathhelpforum @mathhelpforum