1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.