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 21 Mar '12, 12:37

secondrate's gravatar image

secondrate
1114
accept rate: 0%

edited 24 Mar '12, 10:20

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

(24 Mar '12, 10:28) Michael Trick ♦♦

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.

  1. 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?
  2. 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.

link

answered 21 Mar '12, 14:26

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

edited 21 Mar '12, 14:28

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.

link

answered 21 Mar '12, 18:54

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×18
×17

Asked: 21 Mar '12, 12:37

Seen: 1,662 times

Last updated: 24 Mar '12, 10:28

OR-Exchange! Your site for questions, answers, and announcements about operations research.