0
$\begingroup$

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.

  • 0
    What is the objective function in the first problem?2010-10-13
  • 0
    objective function is to minimize c'x2010-10-13

1 Answers 1

1

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