I have LP of the form min $c^tx$ such that $Ax\leq b$, there is no restricition on $x$.
I need to show the dual of the dual of this LP is the original LP.
To get the dual of my LP, I need to put it first into a maximization problem.
- My LP is equivalent to max $-c^tx$ such that $Ax\leq b$.
- Dualise this to get min $b^ty$ such that $A^ty=-c$ and $y\geq 0$
- Turn this into a maximization problem : max $-b^ty$ such that $A^ty=-c$ and $y\geq 0$.
- Into standard inequational form this is : max $-b^ty$ such that $A^ty\leq -c$.
- Dualise this : min $-c^tw$ such that $(A^t)^tw=-(b^t)^t$ and $w\geq 0$
- That is, min $-c^tw$ such that $Aw=-b$ and $w\geq 0$.
- Or min $-c^tw$ such that $Aw\leq-b$
Which is quite different from the original LP. Where are my mistakes ? I think I am confused when I go from a minimization problem to a minimization problem. In the lecture we have seen we can go from a minimization problem min $c^tx$ to maximization problem by maximizing $-c^tx$. But what happens to the inequality $Ax\leq b$ ?
This question have been asked before but I did not understand the explanation, the technique is different I think. Thanks !