Optimality Condition for Linear Programming Solutions

[Kalinka35]

Homework Statement

A feasible dictionary whose last row reads z = z* + ∑ c_jx_jdescribes an optimal solution if and only if c_j ≤ 0 for all j.
Prove or disprove.

Homework Equations

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.

 

[Mark44]

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

 

[Kalinka35]

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.

 

[Kalinka35]

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