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.

  • $\begingroup$ What is the objective function in the first problem? $\endgroup$ – Jyotirmoy Bhattacharya Oct 13 '10 at 23:08
  • $\begingroup$ objective function is to minimize c'x $\endgroup$ – GBa Oct 13 '10 at 23:32

$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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