Hi guys, I'm trying to solve the following problem: [Solved: thanks for all the help!] An LP (maximization) is given with an optimal solution. Let's say there is an additional constraint and that the given optimal solution to the original LP does not satisfy this constraint. We are given that the new LP has a feasible solution. How do we show that there exists an optimal solution for which the slack variable of the additional constraint is 0?
asked
secondrate |

In case this is homework (and because it should be educational anyway) I'm going to try not to give the whole game away right at the start, but you are stuck at exactly the right place to have the key insight. And you can get that insight in one of two ways. **Algorithmic version.**An iterative algorithm comes with an invariant condition. For the primal simplex, that condition is that every solution visited is primal feasible and basic, that is, all basic variables are nonnegative and all nonbasic variables are zero. What's the corresponding condition for the dual simplex method, and what's the implication for the reduced cost on this new slack variable?**Conceptual version.**Suppose that the condition you are stuck on occurred. What would that mean for the optimal solution to the revised problem? In turn, what would that mean for the optimal solution to the original problem?
Hope that helps. BTW, there is one possible outcome that you haven't considered yet.
answered
Matthew Salt... ♦ |

Without giving away any state secrets (as this appears to be a homework problem), let me just say that a "conceptual" proof (relying on convexity and not invoking any algorithms) is two our three lines long with no special cases.
answered
Paul Rubin ♦♦ |

No need to edit the titles to add "Solved". Just "accept" an answer to highlight it and show it answered in the question list.