1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Programming Proof

  1. Sep 17, 2009 #1
    1. The problem statement, all variables and given/known data
    A feasible dictionary whose last row reads z = z* + ∑ cjxjdescribes an optimal solution if and only if cj ≤ 0 for all j.
    Prove or disprove.

    2. Relevant equations



    3. The attempt at a solution
    It is clear that if all c's are ≤ 0, then the solution is optimal since increasing any of the variables would either lower or not affect the value of the objective function.
    The opposite direction does not seem like it would be true, but I have no idea how to start proving that.
     
  2. jcsd
  3. Sep 17, 2009 #2

    Mark44

    Staff: Mentor

    What is a "feasible dictionary?" And what is z*?
     
  4. Sep 17, 2009 #3
    A feasible dictionary shows the system of equations in the program with the basic variables on the left hand side and the non-basic variables on the right and it describes a feasible solution to the system.

    z* is the constant from the objective equation when you set the non-basic variables equal to zero.

    These are the terms that Chvatal uses.
     
  5. Sep 17, 2009 #4
    Actually, I found a counterexample so I think I've got it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linear Programming Proof
  1. Linear programming (Replies: 2)

  2. Linear Programming (Replies: 0)

  3. Linear Programming (Replies: 0)

Loading...