# Prove property of dual Linear Programming problem

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})$$

-
What are your thoughts thus far? –  Mike Spivey Oct 27 '10 at 23:20
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. –  GBa Oct 28 '10 at 1:03