Duality - linear programming

170 Views Asked by At

I have to find a respective dual programme for the given LP

$$ \max \ 2 x_1 + 2x_2$$

s.t. $ -x_1 - x_2 \ge -5 \\\phantom{-}x_1,\phantom{,,}x_2 \ge 0$

I got this:

$$\min \ 5y_1$$

s.t. $y_1 \ge 2 \\ y_1 \ge 0$

But I'm not convinced with this argument..

1

There are 1 best solutions below

0
On BEST ANSWER

Your dual is correct. What confuses you, is that if you take the dual of the dual you take not the primal (exactly). This confusion should be resolved if you observe that $x_1, x_2$ appear only in the form $x_1+x_2$ in the LP and thus practically constitute one variable (as variable $w$ below).


Indeed, the primal can be equivalently written as $$\max b^T\mathbf x$$ s.t. $A\mathbf x\le c\\x_1,x_2\ge 0$

where $$b^T=(2,2), \qquad A=(1,1) \qquad \text{and}\qquad c=5$$ Obviously the optimal solution is $10$ for any choice of $x_1,x_2$ such that $x_1+x_2=5$. Observe that if we set $$w:=x_1+x_2$$ then the (LP) can be written as $$\max 2w$$ s.t. $w \le 5 \\ w\ge 0$

The dual is given by $$\min c^Ty$$ s.t. $A^Ty\ge b,\\ y\ge0$

which is equivalent to $$\min 5y$$ s.t. $y\ge2\\y\ge 2 \\ y\ge0$

again with obvious solution $y=2$ and value of the objective function equal to $10$ (which was expected due to the strong duality theorem).