# What is the Dual of this particular Linear Program ( I get a weird Dual)

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.

• 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.
– A.Γ.
Aug 8 '15 at 16:30

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 ?

• 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. Aug 8 '15 at 16:59
• Unfortunately it is not correct. All constraints have to be satisfied, i.e. $y\geq 1$. But all the others too. Next try. Aug 8 '15 at 17:04
• Aha, y = 3 satisfies all constraints and gives the optimal value of 60 Aug 8 '15 at 17:13
• That's it. Congrats. Aug 8 '15 at 17:16
• Thanks again for your help! Aug 8 '15 at 17:20