3
$\begingroup$

If i have a standard LP problem:

$$\min \mathbf{d}^T \mathbf{x}$$

subject to

$$\mathbf{B}\mathbf{x}=\mathbf{f},\qquad \mathbf{x} \geq 0$$

$\mathbf{y}$ is the optimal solution and $\mathbf{z}$ is the optimal solution to the dual problem

Now, for the same cost function $\mathbf{d}$, if $\mathbf{f}$ is replaced by $\mathbf{b}$ then $\mathbf{x}$ becomes the new optimal solution.

How can it be shown:

$$\mathbf{z}^T (\mathbf{b}-\mathbf{f}) \leq \mathbf{d}^T (\mathbf{x}-\mathbf{y})$$

  • 0
    What are your thoughts thus far?2010-10-27
  • 0
    Expanding, and adding the optimal solutions which we know are equivilent according to strong duality, we are left with showing z' b <= d'x. d'x is obviously optimal. If it can be shown somehow that z'b is feasbile for the dual, we can use weak duality to prove our result.2010-10-28

1 Answers 1

2

You are almost there. The feasible region of the dual for the new problem is exactly the same as that of the dual for the original problem. (Write down the two duals to see that.) Since z is feasible for the dual of the original problem, it is also feasible for the dual of the new problem.