1

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.

T. Huynh
  • 111

1 Answers1

2

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

copper.hat
  • 172,524