1
$\begingroup$

maximize $x_1-2x_2+3x_3-4x_4$

s.t.

$x_1+x_2+x_3+x_4 = 20$

$x_1,x_2,x_3,x_4\geq 0$

The Dual can be found by transposing the constraint matrix and interchanging the objective function with 20 in this case but I get something really weird if I do that as can be seen below.

minimize $20y$

s.t.

$y = 1$

$y = -2$

$y = 3$

$y = -4$

$y\geq 0$

I don't know another way of finding the dual, if you know it then please show me the way.

$\endgroup$
1
  • $\begingroup$ All equalities for $y$ should be inequalities $\ge$ and the inequality $y\ge 0$ should not be there at all. The dual solution $y=3$, the primal solution $x_3=20$, other $x_k$ are zeros. $\endgroup$
    – A.Γ.
    Aug 8 '15 at 16:30
1
$\begingroup$

If all the variables of the primal max-problem are $\geq 0$, then the inequality signs of all constraints of the dual min-problems are $\geq$-signs. And if a constraint of a primal max-problem has a equality sign, then the corresponding dual variable can be positive or negative. Therefore the dual problem is

$\texttt{minimize} \ \ 20y$

s.t.

$y \geq 1$

$y \geq -2$

$y \geq 3$

$y \geq -4$

$y \ \texttt{free}$

What is the optimum value of the objective function ?

$\endgroup$
6
  • $\begingroup$ Since we want to minimize the objective function $20y$ the answer should be $-4$ if y is indeed free to be chosen, the optimal value is then $20*-4 = -80$, is this correct? Thanks for answering my question btw. $\endgroup$
    – Egbert
    Aug 8 '15 at 16:59
  • $\begingroup$ Unfortunately it is not correct. All constraints have to be satisfied, i.e. $y\geq 1$. But all the others too. Next try. $\endgroup$ Aug 8 '15 at 17:04
  • $\begingroup$ Aha, y = 3 satisfies all constraints and gives the optimal value of 60 $\endgroup$
    – Egbert
    Aug 8 '15 at 17:13
  • $\begingroup$ That's it. Congrats. $\endgroup$ Aug 8 '15 at 17:16
  • $\begingroup$ Thanks again for your help! $\endgroup$
    – Egbert
    Aug 8 '15 at 17:20

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.