This is a simple problem, but after spending some hours with linear programs in the primal and its dual form, I still can't do it quite intuitively for LPs which are not in the standard form. I know, I could simply convert it first to the standard, but in this case is required that I do it directly. I also know there's plenty of tables and explanations everywhere, but I would appreciate if someone could help me out with this specific case.

Given the primal problem (P):

$$ Primal =\begin{Bmatrix} max \ \ \ \ 2x_1 - 2x_2 +x_3 + 4x_4 \\ s.t. \ \ \ \ x_1 - x_2 - x_3 \ge 3\\ \ \ \ \ \ \ \ \ -x_1 + x_2 + x_3 \ge -3\\ \ \ \ \ \ \ \ \ \ \ + x_3 + 3x_4 \le 2\\ \ -5x_1 + 5x_2 + 4x_3 + x_4 = 10\\ \ \ \ \ x_1, x_2, x_3 \geq 0\\ \end{Bmatrix} $$

The dual problem (D) to (P) (my solution:

\begin{array}{rlrrrrr} \min & 3y_1 & -3y_2&+2y_3&+10y_4 \\ \mbox{s.t.} & y_1 &-y_2 && -5y_4&\geq& 2\\ &-y_1&+y_2&&+5y_4&\geq& -2\\ &-y_1&+y_2&+y_3&+4y_4&\geq& 3\\ &&&3y_3&+y_4&=& 4\\ &y_1& &&&&free\\ & &y_2,&y_3,& y_4 &\ge& 0 \end{array}

Is this correct? What's the rationale here to say if some $y_i$ is free, $\ge$ or $\le$?

Thank you very much!


You're close. You should have $y_1 \leq 0$, $y_2 \leq 0$, $y_3 \geq 0$, and $y_4$ should be free. Everything else is correct.

One way to view the dual of a primal maximization problem is that it arises from attempting to find a tight upper bound on the optimal value of the primal problem.

Suppose we decide to take a linear combination of the four primal constraints to find an upper bound on the optimal primal value. Then we're looking for multipliers $y_1, y_2, y_3,$ and $y_4$ to force $$\begin{align} 2x_1 - 2x_2 + x_3 + 4x_4 &\leq y_1(x_1 - x_2 - x_3) + y_2(-x_1 + x_2 + x_3) + y_3(x_3 + 3x_4) \\&\:\:\:\:\:\:\:\:\:\:\:+ y_4(-5x_1 + 5x_2 + 4x_3 + x_4) \\&\leq 3y_1 -3y_2 + 2y_3 + 10y_4 .\end{align}$$ Now, we want the upper bound to be as tight as possible, so we want to minimize $3y_1 -3y_2 + 2y_3 + 10y_4$. That's where the dual objective comes from.

In order for the second inequality to hold, we've got to flip the direction of the first inequality constraint in the primal from $\geq$ to $\leq$. In other words, we've got $x_1 - x_2 - x_3 \geq 3$, but we want $y_1(x_1 - x_2 - x_3) \leq 3y_1$. So the multiplier $y_1$ must be negative or zero. The same logic dictates that $y_2$ be negative or zero and that $y_3$ be positive or zero. The fourth primal constraint is an equality, though. Since we don't have to worry about the sign on $y_4$ flipping the inequality in the wrong direction, we don't get any restrictions on $y_4$. Thus $y_4$ is free.

Similar logic yields the form of the constraints in the dual (i.e., $=$, $\leq$, or $\geq$), which you have correct.

For more details, see my answer to "Duality. Is this the correct Dual to this Primal LP?"

  • $\begingroup$ Thank you very much! It helped a lot! $\endgroup$ – Proghero Dec 3 '12 at 8:37

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.