1. Limited time only! Sign up for a free 30min personal 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


    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 Threads - Linear Programming Proof Date
Bland rule proof linear programming Mar 7, 2018
Linear Programming Case Study - Case Problem Mar 29, 2016
Equivalent minimum linear program Jul 20, 2014
Linear Programming proof Oct 7, 2013
Linear programming proofs PLEASE HELP! Feb 9, 2012