Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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