1
$\begingroup$

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong.

This is the primal Linear Problem:

$$ \begin{array}{cccc} \mathop{\mathrm{maximize}}& 4y_1 + 3y_2 + 2y_3 + 3y_4+ 2y_5 &+ 3x_1 \\ s.t. & & \\ &y_1 + 2y_2 &+2x_1 &\leq 3 \\ & 2y_1 + y_2 & +x_1 &\leq 3 \\ & -2y_1+ 3y_2 &+x_1 &\leq7 \\ & y_3 &+3x_1 &\leq4 \\ & 2y_3 &-x_1 &\leq3 \\ & y_4 &&\leq1 \\ & 2y_4 +4y_5 &+3x_1 &\leq5 \\ & 3y_4 +y_5 &-x_1 &\leq4 \end{array} $$

So the above problem is the primal. The authors claim that the following problem is the dual. I have found 2 mistakes in the dual. First, the constraints must be of type '>=' rather than '='. Except if in the primal, the variables yi, xi are unconstrained , which is not clearly stated by the authors. The second mistake is that the variables $u_i$ are '<='. This is incomprehensible. Since the primal constraints are '>=', the dual variables $u_i$ should have been '>='. Do you agree?

$$ \begin{array}{ccccc} \mathop{\mathrm{minimize}}& 3u_1 + 3u_2 + 7u_3 + 4u_4 + 3u_5& + u_6 + 5u_7 + 4u_8 && \\ s.t. & & & & \\ & u_1 + 2u_2 - 2u_3 & &=4 \\ & 2u_1 + u_2 + 3u_3& &=3 \\ & u_4& + 2u_5 &=2 \\ & &u_6 + 2u_7 + 3u_8 &=3 \\ & & 4u_7 + u_8 &=2 \\ & 2u_1 + u_2 +u_3 +3u_4 &-u_5 + 3u_7 - u_8 &= 3 \\ &u_1, u_2, u_3 , u_4 , &u_5 , u_6 , u_7 ,u_8 &\leq 0 \end{array} $$

$\endgroup$
1
  • 3
    $\begingroup$ Why not including exact reference instead of the vague description well-respected book? Then other users can check if their copy of the same book contains the same problem. (There might be several editions.) Or somebody might be aware whether errata are published somewhere online. $\endgroup$
    – Martin Sleziak
    Jan 27, 2016 at 14:02

1 Answer 1

Reset to default
2
$\begingroup$

I do not agree. It looks correct to me.

  • First of all, if variables $x$ and $y$ are unconstrained, it is correct to have $=$ type constraints in the dual. Authors are not required to specify that a variable is unconstrained, they only have to specify which ones are not, and how. This makes sense.
  • If your primal is a minimization problem and constraints are of type $\le$, than again it is normal to have dual variables $u\le 0$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .