Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

Your Answer


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.