# Convert linear programming problem

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.

• 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

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