In linear programming, Von Neumann define the dual of

$$(I)\, \left\{ \begin{array}{rl} c^Tx &\to \min\\ Ax &\ge b\\ x&\ge 0 \end{array} \right. $$ is the problem $$(II)\, \left\{ \begin{array}{rl} b^Ty &\to \max\\ A^Ty &\le c\\ y&\ge 0 \end{array} \right. $$ The question is: How to show that the dual of a dual is the primal? I know many proof that change ($b^Ty \to \max$) into ($(-b)^Ty \to \min$) and then take the dual. But how can we change like that, because the problem $$(II')\, \left\{ \begin{array}{rl} (-b)^Ty &\to \min\\ A^Ty &\le c\\ y&\ge 0 \end{array} \right. $$ is different from (II). What is the relation of (II) and (II') that we can use to change max to min?

Thanks for helping me.


Think of it formally. The LP is characterised by the triple $(c,A,b)$. The dual can then be characterised by $(-b, -A^T, -c)$ (the negative signs to account for $\max \to \min$, and the reversal of direction in the constraint).

You can see that by applying this rule formally twice, we end up with $(c,A,b)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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