0

To understand the conversion without standard form I read: Directly from primal to dual when primal not in standard form

The posted LP there is: $$ 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 corrected dual:

\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& &&& \leq & 0 \\ &&y_2&&& \leq& 0 \\ &&&y_3 &&\geq & 0\\ &&&& y_4 && free \end{array}

I also read Duality. Is this the correct Dual to this Primal L.P.?.

With the comment I tried to solve the LP. But I don't understand why the third constraint of the Dual LP is $-y_1+y_2+y_3+4y_4\geq 3$ and not $-y_1+y_2+y_3+4y_4\geq 1$.

Is greater than or equal to 3 really correct, and if so, why?

I've also put this LP into a solver, so it seems like it should be 1 and not 3.

Miss Mae
  • 1,576
Martin Stuwe
  • 55

1 Answers1

2

You are correct in calling out the constraint $-y_1+y_2+y_3+4y_4\geq 1$, as it shouldn't be $-y_1+y_2+y_3+4y_4\geq 3$. Thus, it appears to be a typo on OP's part.

For the future, an easier way to intuitively convert primal-dual problems is via the S.O.B. method. See this as well.

\begin{matrix} &\text{Primal Problem} && \text{Dual Problem}\\ &\text{(or Dual Problem)} && \text{(or Primal Problem)}\\ \\ &\text{Maximization} && \text{Minimization}\\ \text{Sensible} & \le\text{ Constraint} & \text{Paired With} & \text{Non-Negative Variable}\\ \text{Odd} & =\text{ Constraint} & \text{Paired With} & \text{Unconstrained Variable}\\ \text{Bizzare} & \ge\text{ Constraint} & \text{Paired With} & \text{Non-Positive Variable} \\\\ \text{Sensible} &\text{Non-Negative Variable} & \text{Paired With} &\ge\text{ Constraint}\\ \text{Odd} &\text{Unconstrained Variable} & \text{Paired With} &=\text{ Constraint}\\ \text{Bizzare} &\text{Non-Positive Variable} & \text{Paired With} &\le\text{ Constraint}\\ \\ \end{matrix}

Miss Mae
  • 1,576