Results 1 to 9 of 9

Math Help - Simplex Method Proof

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    Simplex Method Proof

    Show that the variable that becomes nonbasic in one iteration of the simplex
    method cannot become basic in the next iteration.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    What are the selection criteria for the next entering nonbasic variable?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    225
    Hi,

    Since nothing is mentioned, I think the only criteria is that the variable have a negative coefficient in the objective function that we want to maximize.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    And once you have selected the column, you are led to a row, right? What is the value in that row for the column representing the previous non-basic variable?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    225
    I'm not sure what you mean... the value in that row depends on the problem, right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    Let's keep rows and columsn straight. After an iteration, you have just created all zeros, except one, in some column. If you then operate on another row, that row will have zero in that previous column.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2008
    Posts
    225
    I think I'm confused because we have been using dictionary notation, not matrix notation. I understand that the column that corresponded to the variable that just left is now 0 because that variable is now 0. Can we say that the variable will never be basic again because it will have the wrong sign on the coefficient in the objective function after it has exited the basis?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    I see. Time to back up to the geometry. What are the requirements or assumptions for a solution to exist?

    Feasible
    Bounded
    Concave

    Any of these things lead in the right direction?

    In other words, as you just created a nonbasic variable, because it was a maximal constraint, the choice to return it to basic on the next iteration would seem to indicate that we didn't use it all.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    Okay, as I read more and more on the subject, I begin to feel old. Almost all that is interesting was written since I last studied the matter. Perhaps one with more current background will bail me out and tell me what I'm trying to say.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simplex Method
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 24th 2011, 09:47 PM
  2. LPP-Simplex method
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2010, 08:38 AM
  3. the simplex method
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: May 2nd 2010, 07:16 PM
  4. Simplex method help
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 22nd 2010, 03:40 PM
  5. Simplex method
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: November 23rd 2009, 10:03 PM

Search Tags


/mathhelpforum @mathhelpforum