Directly from primal to dual when primal not in standard form

Question

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!

Answer 1

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?"