The dual of the primal problem

Question

Consider the primal linear programming problem Maximize z =c(transpose) x Subject to Ax<=b X is unrestricted .Then its dual problem given by Minimize ź=b(transpose) w Subject to A(transpose) w =c W>=0

I can't complete the proof proof: Because of x is unrestricted let x =u-v , u,v>=0 The primal problem will be : Max. Z=c(transpose)(u-v) Subject to A(u-v)<=b u,v>=0

The dual problem: Min. Z=[b(transpose)-b(transpose)] [ u v] Subject to [A(transpose)-A(transpose)] [u v]>=c u,v>=0

How I can continue to get A(transpose)w=c w>=0 Thanks in advance If I suppose that w=u-v that does not mean that w>=0

Marcello Sammarra · Answer 1 · 2016-11-21T05:18:52.627

2

Setting $x=u-v, \ u,v\geq 0$ in the primal you get the symmetric dual \begin{align} \min \ & b^{\top} w\\ & A^{\top} w \geq c\\ & -A^{\top}w \geq -c\\ & w\geq 0 \end{align} that is \begin{align} \min \ & b^{\top} w\\ & A^{\top} w = c\\ & w\geq 0 \end{align}

edited Nov 21 '16 at 05:18

answered Nov 20 '16 at 18:51

Marcello Sammarra

385

You mean -A(transpose)w>=-c. Thanks – Tasneem Nov 20 '16 at 18:59
No, it is $-A^{\top}w \leq -c\ \longrightarrow A^{\top}w \geq c$ – Marcello Sammarra Nov 20 '16 at 20:52
oh yah I understand it's just simple step ....thank you very much – Tasneem Nov 20 '16 at 21:03
you were right. I considered the primal in your question as a minimum problem. I'm sorry about that! – Marcello Sammarra Nov 21 '16 at 05:23

The dual of the primal problem

1 Answers1