Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose x is the solution to a standard linear programming problem ($Ax=b$, $x>=0$) and the set $S$ is every $i$ where $x_{i} = 0$.

How can I show this is optimal only where

minimize $c'f$ subject to $Af=0, f_{i} \ge 0$, $i$ is in $S$

has a cost of zero.

share|cite|improve this question
What is the objective function in the first problem? – Jyotirmoy Bhattacharya Oct 13 '10 at 23:08
objective function is to minimize c'x – GBa Oct 13 '10 at 23:32
up vote 1 down vote accepted

$f=0$, yielding a cost of $0$, is a feasible point for your second problem. So if the optimal cost is non-zero then it must be negative.

But then $y=x+\lambda f$ would be an improvement over $x$ in the original problem for all $\lambda>0$. Because of the nature of constraints in the second problem $y$ satisfies the equality and binding non-negativity constraints in the first problem. We can choose $\lambda$ small enough so that it also satisfies the non-binding non-negativity constraints. But then $y$ would be superior to $x$ in the original problem, proving that the latter was not an optimal point.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.