Results 1 to 2 of 2

Math Help - simplex algorithm:can leaving variable enter the basis again?

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    I am here.
    Posts
    1

    simplex algorithm:can leaving variable enter the basis again?

    hi.
    Is it possible that variable Xi leaves the basis and enter the basis again in the next step? what about other steps (not next to current step)?
    Last edited by ehsazh; August 11th 2012 at 09:20 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    From
    Curitiba - Brazil
    Posts
    10

    Re: simplex algorithm:can leaving variable enter the basis again?

    In each step of simplex algorithm, exactly one variable leaves the basis and exactly another one enter the basis. That said, if the same variable leaves and enter the basis in subsequent steps, then the basis dont change, and the algorithm enters in infinite loop. I dont remember exactly how simplex works, but supposing that simplex is correct, then this case cannot happen. On the other hand, it is completely normal the same variable leave the basis and then, in a future step, enters the basis again. Remember, the simplex is an exponential time algorithm, and its worst running time is determined by the number of different basis it has. Therefore, if a variable leaves the basis and never comes back, then simplex would quickly run out of variables to enter the basis, and then it would be a polinomial time algorithm.

    BUT!! I remember that there was some king of "degenerate cases" that could bring problems to simplex functioning, but right now i dont remeber exactly what are these "degenerate cases".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: August 8th 2011, 10:29 PM
  2. Simplex Algorithm help
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 5th 2010, 06:01 PM
  3. Simplex Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 3rd 2008, 12:40 PM
  4. Simplex Algorithm
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 29th 2008, 10:49 PM
  5. Leaving single variable by itself.
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: September 9th 2005, 11:08 AM

Search Tags


/mathhelpforum @mathhelpforum