# Linear Programming Proof

1. Sep 17, 2009

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. Sep 17, 2009

### Staff: Mentor

What is a "feasible dictionary?" And what is z*?

3. Sep 17, 2009

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.

4. Sep 17, 2009

Actually, I found a counterexample so I think I've got it.